Search⌘ K
Home
Courses
Competitive Programming in C++: The Keys to Success

STL

Explore the use of balanced binary search trees in the C++ Standard Template Library. Understand Set, Multiset, and Map containers, their operations, and how to iterate through them efficiently. Learn time complexities and practical usage to improve your competitive programming solutions.

We'll cover the following...

Library

As briefly mentioned before, there are 3 variants of Balanced BST in STL that we are particularly interested in:

  1. Set

  2. MultiSet

  3. Map

Include statement:

#include <set>

#include <multiset>

#include <map>

Set

The Set is a container that stores unique elements following a specific order.

Below are the operations we’ll be using frequently. For complete documentation check here.

set<int> S; // empty set
bool x = S.empty(); // to check if set is empty
int sz = S.size(); // get size of set
S.insert(x); // Insert integer x into the set
S.erase(x); // Remove integer x from the set
S.erase(it); // Iterator version of erase
set<int>::iterator it = S.find(x); // Returns iterator to element with passed value if exists else return iterator to S.end()

Since a set only has unique elements, adding duplicate elements doesn’t have any effect.

Multiset

Multiset elevates the limitation with Set, we can have duplicate elements in a multiset.

Below are the operations we’ll be using frequently. For complete documentation check here.

multiset<int> S; // empty multiset
bool x = S.empty(); // to check if multiset is empty
int sz = S.size(); // get size of multiset
S.insert(x); // Insert integer x into the multiset
S.erase(x); // Remove integer x from the multiset
S.erase(it); // Iterator version of erase
multiset<int>::iterator it = S.find(x); // Returns iterator to element with passed value if exists else return iterator to S.end()

The Iterator version of erase() should be used when dealing with multiset. The non-iterator version ...