Skip to content

Associative Containers

set

set is an associative container that stores a sorted set of objects of key-value type, with logarithmic complexity for search, removal, and insertion. Internally, set is typically implemented using a Red-Black Tree. The properties of a Balanced Binary Search Tree make set particularly suitable for scenarios requiring simultaneous lookup, insertion, and deletion.

Similar to mathematical sets, duplicate elements cannot appear in a set. If a collection with duplicate elements is needed, multiset should be used. The usage of multiset is essentially the same as that of set.

Insertion and Deletion Operations

  • insert(x) inserts element x into the set when there is no equivalent element in the container.
  • erase(x) deletes all elements with value x and returns the number of deleted elements.
  • erase(pos) deletes the element at iterator pos, requiring the iterator to be valid.
  • erase(first,last) deletes all elements whose iterators are in the range \([first,last)\).
  • clear() empties the set.
Return Value of the insert Function

The return type of the insert function is pair<iterator, bool>, where iterator points to the inserted element (or to an element already in the container that is equal to the inserted value), and bool indicates whether the insertion was successful. Due to the uniqueness property of elements in set, if an equivalent element already exists in the set, the insertion fails and returns false; otherwise, it succeeds and returns true. The same applies to insert in map.

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 after the last element; note that there is no element at this position.
  3. rbegin()/crbegin()
    Returns a reverse iterator pointing to the first element of the reversed container, which can be thought of as the last element of the forward container.
  4. rend()/crend()
    Returns a reverse iterator pointing to the position after the last element of the reversed container, corresponding to the position before the first element of the forward container, with no element present.

Among the iterators listed above, those containing the character c are read-only iterators. You cannot modify the values of elements in set through read-only iterators. If a set itself is read-only, its general iterators 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 with key x.
  • find(x) returns an iterator to the element with key x if it exists in set; otherwise, returns end().
  • lower_bound(x) returns an iterator pointing to the first element not less than the given key. If no such element exists, returns end().
  • upper_bound(x) returns an iterator pointing to the first element greater than the given key. If no such element exists, 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 built-in lower_bound and upper_bound of set have a time complexity of \(O(\log n)\).

However, using the lower_bound and upper_bound functions from the algorithm library to query elements in a set has a time complexity of \(O(n)\).

Time Complexity of nth_element

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

If you need the functionality of a balanced binary search tree to find the \(k\)-th largest element in \(O(\log n)\) time, you must implement your own balanced binary tree or weighted segment tree, or use the balanced binary tree from the pb_ds library.

Usage Example

Using set in Greedy Algorithms

Greedy algorithms often require operations like find and delete the smallest element greater than or equal to a certain value. Such operations can be easily accomplished using set.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// Currently available elements
set<int> available;
// The value to 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 corresponding operations...
} else {
  // Found such an element, remove it from the available elements
  available.erase(it);
  // Perform corresponding operations...
}

map

map is an ordered key-value pair container where the keys of its elements are unique. Search, removal, and insertion operations have logarithmic complexity. map is typically implemented as a Red-Black Tree.

Consider the following scenario: you need to store some key-value pairs, such as student names corresponding to scores: Tom 0, Bob 100, Alan 100. However, since array indices can only be non-negative integers, you cannot use names as indices for storage. The simplest solution in this case is to use map from the STL.

map overloads operator[], allowing any type that defines operator < to be used as an index (called key in map):

1
map<Key, T> yourMap;

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

1
map<string, int> mp;

map cannot contain elements with duplicate keys. multimap allows multiple elements to share the same key. The usage of multimap is essentially the same as that of map.

Warning

Due to the characteristic of multimap allowing multiple elements with the same key, multimap does not provide a method to access the corresponding value by key.

Insertion and Deletion Operations

  • You can directly perform queries or insertions via subscript access. For example, mp["Alan"]=100.
  • Inserting an element can be achieved by inserting a value of type pair<Key, T> into map, e.g., mp.insert(pair<string,int>("Alan",100));;
  • The erase(key) function deletes all elements with key key. The return value is the number of deleted elements.
  • erase(pos): Deletes the element at iterator pos, requiring the iterator to be valid.
  • erase(first,last): Deletes all elements whose iterators are in the range \([first,last)\).
  • clear() empties the entire container.
Notes on Subscript Access

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

When subscript access operations are too frequent, a large number of meaningless elements may appear in the container, affecting the efficiency of map. Therefore, it is generally recommended to use the find() function to search for elements with specific keys.

Lookup Operations

  • count(x): Returns the number of elements in the container with key x. Complexity is \(O(\log(size)+ans)\) (logarithmic in container size plus the number of matches).
  • find(x): If an element with key x exists in the container, returns an iterator to that element; 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, returns end().
  • empty(): Returns whether the container is empty.
  • size(): Returns the number of elements in the container.

Usage Example

Using map to Store Complex States

In search algorithms, we sometimes need to store some relatively complex states (such as coordinates, non-discretizable values, strings, etc.) and their associated answers (e.g., the minimum steps to reach that state). map can be used to implement this functionality, where the key is the state and the value is the associated answer. The following example shows how to use map to store states represented as string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// Store states and corresponding answers
map<string, int> record;

// Newly searched state and corresponding answer
string status;
int ans;
// Check if the corresponding state has appeared before
map<string, int>::iterator it = record.find(status);
if (it == record.end()) {
  // The state has not been searched before; add it to the state record
  record[status] = ans;
  // Perform corresponding operations...
} else {
  // The state has been searched before; perform corresponding operations...
}

Traversing Containers

Iterators can be used to traverse all elements of associative containers.

1
2
3
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 yields a key-value pair of type pair<Key, T>.

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

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

For any associative container, the time complexity of traversing the container using an iterator is \(O(n)\).

Custom Comparison Methods

By default, the comparison function for set is < (for non-built-in types, you need to overload the < operator). However, in some special cases, we may want to customize the comparison method inside set.

This can be solved by passing a custom comparator.

Specifically, we need to define a class and overload the () operator within this class.

For example, if we want to maintain a set that stores integers with larger values appearing first, we can implement it as follows:

1
2
3
4
5
struct cmp {
  bool operator()(int a, int b) const { return a > b; }
};

set<int, cmp> s;

For other associative containers, custom comparisons can be implemented in a similar manner, which will not be elaborated here.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用