Skip to content
Tutorials Center
My learning

Topics

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.

C++
#include <map>
std::multimap<std::string, int> m;
m.insert({"a", 1});
m.insert({"a", 2});     // both kept

Try it

C++ Several values per key

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.

C++ multiset: counting duplicates and erasing one

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

C++
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[] or at() on a multimap. Use find (any one match, not necessarily the first), lower_bound, or equal_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.
  • count is not O(1): it is O(log n + k) for k matches. When you also need the elements, use equal_range once.
  • 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.