std::multiset<T> is a sorted associative container that stores keys in order and allows the same key to appear more than once. It uses the same balanced binary search tree as std::set (red-black in every mainstream implementation), so every key-touching operation is O(log n), and iteration walks the keys in sorted order. The defining property is the dropped uniqueness rule: insert 5 three times and the container stores it three times. This chapter covers what changes once duplicates are allowed, the API differences from std::set, the role of equal_range and count, and the workloads where multiset fits well.

A std::multiset is the same data structure as a std::set. The internal node layout (key, three pointers, color bit), the height bound, and the balancing rules are all identical. The one change is the rule the insert path applies when it finds a node with the same key: set::insert rejects the duplicate and returns false, while multiset::insert adds a new node next to the existing one.

Output:

Six inserts, six elements. Iteration walks them in non-decreasing order: every 3 first, then every 4, then every 5. Equal keys stay grouped together because the tree's in-order traversal sorts by key, and the tie-breaking among equal keys leaves them adjacent.

The diagram below sketches the tree after the six inserts. Equal keys can sit anywhere the balancing rules allow, but they always end up next to each other in the in-order walk.

The exact shape depends on the implementation and the insertion order, but the in-order traversal is fixed: 3 4 4 5 5 5. The cyan nodes are the first occurrences of each key; the orange nodes are the duplicates. They're all real, distinct nodes that take separate space and have separate iterators.

Every key-touching operation is still O(log n) on a multiset. The tree's height stays at log n no matter how many duplicates the container holds, because the balancing rules ignore key equality and only care about ordering. A multiset of 10,000 elements that all share one key is still a balanced tree of depth ~14, not a linked list.

std::set::insert returns std::pair<iterator, bool> because the insert can succeed or fail (key already present). On a multiset, the insert always succeeds, so there's no bool to report.

Output:

Both it1 and it3 are valid iterators pointing at distinct nodes, even though the dereferenced strings compare equal. Modifying through one (which the language forbids anyway, since multiset iterators yield const T&) wouldn't affect the other.

emplace works the same way: it returns an iterator, not a pair. Bulk inserts with an initializer list or a range still compile, and they place every element regardless of duplicates.

Output:

Every value lands in the container, including the ones already present. The 8 elements from stars plus the 3 from the initializer list add up to 11.

The insertion cost is the same O(log n) as std::set: find the right spot, allocate a node, splice it in, rebalance one or two ancestors. There's no equality check to short-circuit the work, so a multiset insert is sometimes marginally faster than the set equivalent on duplicate-heavy data, but the difference is rarely measurable.

On a std::set, count(key) returns 0 or 1, which makes it a roundabout way to spell contains. On a std::multiset, count(key) returns the actual number of occurrences.

Output:

count(key) is O(log n + k), where k is the number of matches. The container walks to one end of the equal range, then iterates through every duplicate to the other end. For a key with thousands of duplicates that walk is the dominant cost.

equal_range(key) returns a std::pair<iterator, iterator> of (lower_bound, upper_bound): the first iterator points at the first occurrence, the second iterator points one past the last occurrence. The pair brackets the run of duplicates as a standard half-open range, ready to iterate.

Output:

When the key isn't present, first == last and the loop body never runs. That's the cheapest way to check "any matches?": compare the two iterators rather than calling count, which walks the whole range.

equal_range(key) is O(log n). It does two binary-search descents (one for lower_bound, one for upper_bound), not a full walk of the matches. Iterating the returned range is then O(k), but the iteration is under the caller's control and can stop early.

lower_bound and upper_bound exist on multiset and behave the same way they do on set: lower_bound(key) returns an iterator to the first element not less than key, upper_bound(key) returns an iterator to the first element strictly greater. On a multiset, they slice a range of duplicate runs by neighbor relationships.

Output:

The duplicates of 89 and 142 both show up because every actual element in the range is visited, not every distinct key.

erase(key) is where the multiset's behavior diverges most visibly from set. On a set, erase(key) removes the single matching element (if any) and returns 0 or 1. On a multiset, it removes every element equal to the key and returns the count of removals.

Output:

All four 5s are gone in one call. The cost is O(log n + k) where k is the number of removed elements, because the container has to locate the equal range and then unlink each node from the tree.

To remove a single occurrence, find an iterator to the specific element and erase by iterator. erase(it) removes exactly the node the iterator points at and leaves the other duplicates alone.

Output:

find(key) on a multiset returns an iterator to some matching element, with the standard not specifying which one. In practice, libstdc++ and libc++ both return the first match in iteration order, but code that depends on that specifically should use lower_bound(key) instead, which always returns the first match. The cost of erase(it) is amortized O(1) once the iterator is known.

To remove every duplicate of a key in a single batch using a range erase:

Output:

erase(first, last) removes every element in the half-open range, leaving the rest of the container intact. Iterators outside the erased range stay valid. As with std::set, an erase never invalidates iterators to other elements; only the iterators to the removed elements become invalid.

Iteration on a std::multiset walks the elements in non-decreasing order, with duplicates appearing consecutively. The order of duplicates within a single key is insertion order, a guarantee that C++11 added and that all current implementations honor.

Output:

The two 1s and the three 2s come out in the same order they were inserted, with the 1s before the 2s. That stability matters when the elements carry payload beyond the sort key (here, the label).

Just as with set, iterators into a multiset dereference to a const T&. The sort key can't be modified through an iterator because that would break the tree invariant. To "change" an element, erase the old one and insert the new value.

Inserts and erases never invalidate iterators to other elements. Long-lived iterators are safe across unrelated mutations:

Output:

it30 survives every mutation. Inserting another 30 does not move or invalidate the existing one; it just adds a second node with the same key.

The comparator works exactly like it does on std::set. The default is std::less<T>, which uses operator< on the element type. To order elements differently, supply a struct with operator() (or a lambda, with the usual decltype dance) as the second template parameter.

The same "strict weak ordering" rule applies: the comparator must use a strict <, never <=, and equality is defined implicitly by !comp(a, b) && !comp(b, a). Two elements that compare equal under the comparator are considered duplicates by the multiset, even if they differ in unrelated fields.

Output:

The orders come out by priority, with the higher priority first. Ties on priority keep insertion order, which is what most schedulers want. Note that ORD-1002 and ORD-1005 are not duplicates as far as the multiset's equality is concerned, even though they share a priority: the comparator returns false for both comp(a, b) and comp(b, a), so they're equal as keys and end up grouped, but they're stored as separate nodes because every insert is accepted.

This is the standard way to use a multiset as an ordered queue: the sort key encodes priority, and the rest of the struct carries payload. Calls like equal_range(key) are then a natural way to iterate over every element with a given priority level.

A multiset fits when three things all hold: keys can repeat, sorted iteration matters, and the count of duplicates per key carries meaning. A few workloads:

For a pure membership check with no duplicates, use std::set (or std::unordered_set, if no order is needed). For frequency counting with no ordering, std::unordered_map<Key, int> is faster. For "the highest-priority element only," a std::priority_queue is lighter. Use std::multiset when both ordering and duplicate counts matter together.

The complexity comparison against alternative containers:

std::unordered_multiset wins on per-operation cost when the data fits its model, but it loses every ordered query. The sorted vector wins on cache behavior and constant factors for read-heavy workloads where inserts are rare or batched.

A small running example: a product-review log where each review is a star rating between 1 and 5. The store wants the median rating, the count of each star value, and the list of "negative" reviews (one or two stars) for follow-up. A multiset answers all three queries.

Output:

count(star) gives every histogram bin in O(log n + k). lower_bound/upper_bound carve out the negative-review range in O(log n). The median walk is the only O(n)-ish step, because std::advance on a tree iterator is linear in the distance, not constant. For a window-of-medians problem where the data updates incrementally, two multisets (one for the lower half, one for the upper half) turn the median into an O(log n) operation per update.

Compile with g++ -std=c++17 file.cpp. Every API used here works back to C++17 (structured bindings are the only modern feature; C++11 if you write auto p = reviews.equal_range(...) explicitly).