Associative Containers

set

set is an associative container containing a sorted set of objects of key-value type. Searching, erasing, and inserting have logarithmic complexity. set is usually implemented internally using a red-black tree. The properties of a balanced binary tree make set well suited to situations that require lookup, insertion, and deletion to be considered simultaneously.

Similar to a mathematical set, set cannot contain elements with equal values. If a set containing equal elements is needed, use multiset. multiset is used in essentially the same way as set.

Insertion and Erasure Operations

• insert(x) inserts element x into set when the container has no equivalent element.
• erase(x) erases all elements whose value is x and returns the number of erased elements.
• erase(pos) erases the element at iterator pos; the iterator must be valid.
• erase(first,last) erases all elements whose iterators are in the range $[first,last)$.
• clear() clears set.

Return value of the insert function

The return type of the insert function is pair<iterator, bool>. Here, iterator is an iterator pointing to the inserted element (or to an element that was already in the container and is equal to the inserted value), while bool indicates whether the element was inserted successfully. Since elements in set are unique, insertion fails and returns false if an element with an equal value already exists in set; otherwise, insertion succeeds and returns true. insert in map behaves the same way.

Iterators

set provides the following iterators:

1. begin()/cbegin()
   Returns an iterator pointing to the first element, where *begin = front.
2. end()/cend()
   Returns an iterator pointing to the placeholder at the end of the array; note that it does not denote an element.
3. rbegin()/crbegin()
   Returns a reverse iterator pointing to the first element of the reversed array, which can be understood as the last element of the forward container.
4. rend()/crend()
   Returns an iterator pointing to the position after the last element of the reversed array, corresponding to the position before the beginning of the container; it denotes no element.

Among the iterators listed above, those containing the character c are read-only iterators. You cannot modify the values of elements in set through a read-only iterator. If set itself is read-only, its ordinary and read-only iterators are completely equivalent. Read-only iterators have been supported since C++11.

Lookup Operations

• count(x) returns the number of elements in set whose key is x.
• find(x) returns an iterator to the element whose key is x if such an element exists in set; otherwise, it returns end().
• lower_bound(x) returns an iterator pointing to the first element not less than the given key. If no such element exists, it returns end().
• upper_bound(x) returns an iterator pointing to the first element greater than the given key. If no such element exists, it returns end().
• empty() returns whether the container is empty.
• size() returns the number of elements in the container.

Time complexity of lower_bound and upper_bound

The time complexity of the lower_bound and upper_bound provided by set is $O(\log n)$.

However, querying elements in set with the lower_bound and upper_bound functions in the algorithm library has time complexity $O(n)$.

Time complexity of nth_element

set does not provide a built-in nth_element. Using nth_element from the algorithm library to find the $k$-th largest element has time complexity $O(n)$.

If you need the $O(\log n)$ operation for finding the $k$-th largest element provided by a balanced binary tree, you need to implement a balanced binary tree or a segment tree over values yourself, or choose the balanced binary tree in the pb_ds library.

Example

Using set in Greedy Algorithms

Greedy algorithms often need to perform an operation similar to finding and erasing the smallest element greater than or equal to a given value. This operation can be completed easily with set.

// Available elements
set<int> available;
// its value that must be greater than or equal to
int x;

// Find the smallest element greater than or equal to x
set<int>::iterator it = available.lower_bound(x);
if (it == available.end()) {
  // No such element exists; perform the corresponding operation……
} else {
  // Such an element was found; remove it from the available elements
  available.erase(it);
  // Perform the corresponding operation……
}

map

map is an ordered key-value-pair container whose element keys are unique. Search, erase, and insertion operations have logarithmic complexity. map is usually implemented as a red-black tree.

Consider the following scenario: some key-value pairs need to be stored, such as the scores corresponding to student names: Tom 0, Bob 100, Alan 100. However, because array subscripts can only be nonnegative integers, names cannot be used as subscripts for storage. In this case, the simplest approach is to use the STL map.

map overloads operator[], so any type that defines operator < can be used as a subscript (called a key, or index, in map):

map<Key, T> yourMap;

Here, Key is the key type and T is its value type. The following is an example of using map:

map<string, int> mp;

map cannot contain elements with identical keys, while multimap allows multiple elements to have the same key. multimap is used in essentially the same way as map.

Warning

Precisely because multimap allows multiple elements to have the same key, multimap does not provide a way to access the corresponding value by a key.

Insertion and Erasure Operations

• Elements can be queried or inserted directly through subscript access. For example, mp["Alan"]=100.
• An element can be inserted by inserting a value of type pair<Key, T> into map, for example, mp.insert(pair<string,int>("Alan",100));.
• The erase(key) function erases all elements whose key is key. Its return value is the number of erased elements.
• erase(pos) erases the element at iterator pos; the iterator must be valid.
• erase(first,last) erases all elements whose iterators are in the range $[first,last)$.
• The clear() function clears the entire container.

Notes on subscript access

When accessing an element in map using a subscript, if map does not contain an element with the corresponding key, a new element is automatically inserted into map and its value is set to the default value (for integers, its value is zero; for types with a default constructor, the default constructor is called for initialization).

When subscript access is used too frequently, many meaningless elements may appear in the container and affect the efficiency of map. Therefore, in general, it is recommended to use the find() function to look for an element with a specific key.

Query Operations

• count(x): returns the number of elements in the container whose key is x. Its complexity is $O(\log(size)+ans)$ (logarithmic in the container size, plus the number of matches).
• find(x): if an element whose key is x exists in the container, returns its iterator; otherwise, returns end().
• lower_bound(x): returns an iterator pointing to the first element not less than the given key.
• upper_bound(x): returns an iterator pointing to the first element greater than the given key. If all elements in the container are less than or equal to the given key, it returns end().
• empty(): returns whether the container is empty.
• size(): returns the number of elements in the container.

Example

Using map to Store Complex States

In search, we sometimes need to store relatively complex states (such as coordinates, values that cannot be discretized, or strings) and related answers (such as the minimum number of steps to reach the state). map can be used for this purpose. The key is the state, and its value is the answer related to it. The following example shows how to use map to store states represented by string.

// Store states and their corresponding answers
map<string, int> record;

// A newly searched state and its corresponding answer
string status;
int ans;
// Check whether the corresponding state has appeared
map<string, int>::iterator it = record.find(status);
if (it == record.end()) {
  // This state has not been searched; add it to the state record
  record[status] = ans;
  // Perform the corresponding operation……
} else {
  // This state has already been searched; perform the corresponding operation……
}

Traversing Containers

Iterators can be used to traverse all elements of an associative container.

set<int> s;
using si = set<int>::iterator;
for (si it = s.begin(); it != s.end(); it++) cout << *it << endl;

Note that dereferencing an iterator of map gives a key-value pair of type pair<Key, T>.

In C++11, using a range-based for loop makes the code much simpler:

set<int> s;
for (auto x : s) cout << x << endl;

For any associative container, traversing the container with iterators has time complexity $O(n)$.

Custom Comparison

By default, set uses < as its comparison function (for non-built-in types, overload the < operator). However, in some special situations, we may want to customize the comparison method inside set.

This can be solved by passing in a custom comparator.

Specifically, we need to define a class and overload the () operator in that class.

For example, to maintain a set that stores integers with larger values first, it can be implemented as follows:

struct cmp {
  bool operator()(int a, int b) const { return a > b; }
};

set<int, cmp> s;

Custom comparison can be implemented similarly for other associative containers; the details are omitted here.