C++ Reference ยท Containers
C++ std::multimap and std::multiset
Reference for std::multimap and std::multiset: ordered containers that allow equal keys, equal_range, count, erase by key versus by iterator, and insertion order.
std::multimap<Key, T> and std::multiset<Key> are the versions of std::map and std::set that allow several elements with equivalent keys. They stay sorted by key, with O(log n) insertion, lookup and erasure, and they are found in the same headers (<map> and <set>). The unordered counterparts, std::unordered_multimap and std::unordered_multiset, live in the unordered headers.
Because a key can occur more than once, some operations change meaning. A multimap has no operator[] and no at(): which of several values would it return? Instead you ask for the whole group of matching elements with equal_range. insert always succeeds and returns just an iterator.
#include <map> std::multimap<std::string, int> m; m.insert({"a", 1}); m.insert({"a", 2}); // both kept
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
template <class Key, class T, class Compare = std::less<Key>, class Allocator = ...> class multimap; template <class Key, class Compare = std::less<Key>, class Allocator = ...> class multiset; iterator insert(const value_type& v); // always inserts std::pair<iterator, iterator> equal_range(const Key& k); size_type count(const Key& k) const; size_type erase(const Key& k); iterator erase(const_iterator pos);
| Name | Description |
|---|---|
k |
The key to search for. |
v |
For a multimap, a std::pair<const Key, T>; for a multiset, the key itself. |
pos |
An iterator to one specific element. |
Returns: insert returns an iterator to the new element. equal_range returns the half-open range [first, last) of all elements with that key (empty if none). count returns the number of matches; erase(key) returns how many were removed.
Errors / undefined behavior: erasing with an end() iterator, or using an iterator after erasing its element, is undefined. The comparator must be a strict weak ordering.
Usage notes
- No
operator[]orat()on a multimap. Usefind(any one match, not necessarily the first),lower_bound, orequal_range. erase(key)removes all matches;erase(iterator)removes exactly one. To delete one element, find it first (erase(ms.find(x))).- Order of equal keys: elements with equivalent keys are kept in the order in which they were inserted.
countis not O(1): it is O(log n + k) for k matches. When you also need the elements, useequal_rangeonce.contains(C++20) works and is a cheap membership test.- Alternative design:
std::map<Key, std::vector<T>>groups the values per key and gives indexable access, at the cost of manual insertion code. - Unordered versions (
std::unordered_multimap,std::unordered_multiset) offer average O(1) operations but no order, and equal keys are adjacent in iteration but in no particular order. - Complexity and iterators follow
std::map: inserts never invalidate iterators.
Related
- std::map, std::set, std::unordered_map
- Lessons: std::map, std::set