After hash maps, ordered trees and flat maps, make one more independent choice: should equivalent keys be unique, counted or associated with several values? A deadline scheduler can legitimately contain three jobs at the same time.
Three representations, two multiplicity policies
A comparator defines ordered-key equivalence as neither key being less than the other; it need not be operator==. Unordered containers require compatible hash and equality functions: equivalent keys must hash equally. A multiset contains values with counts, not key/value pairs. A multimap stores a value for every key occurrence. Those distinctions matter for equality, cancellation and ranges.
Remove one occurrence or the whole group deliberately
multiset.erase(key) removes all equivalent keys and returns their count.
erase(iterator) removes only that occurrence. A "cancel one" API must first
find an iterator. multimap has no operator[]: there may be several mapped
values and no single default answer for that expression.
#include <set>
#include <cstdio>
int main() {
std::multiset<int> jobs{4,4,4,8};
jobs.erase(jobs.find(4));
std::printf("remaining fours %zu\n",jobs.count(4));
std::printf("erase whole group %zu\n",jobs.erase(4));
}For an ordered inclusive interval [a,b], traverse from lower_bound(a) to
upper_bound(b). The latter is the first key strictly greater than b, including
all b duplicates. Reject reversed bounds before creating a range whose iterator
order would be invalid. Lookup costs logarithmic time; walking k selected
results adds O(k).
equal_range(key) names the equivalent-key group. For unordered_multimap, use
that group but do not expose the overall container's unspecified iteration order
as your API's output order. Sort the returned values if the caller needs a
reproducible result. Rehashing preserves references to live elements and
invalidates iterators; reacquire the range after a rehash.
Flat variants are real standard containers
The flat family arrived in C++23. flat_set stores sorted unique keys in one
adapted sequence. flat_multiset retains duplicate keys; flat_multimap retains
all key/value pairs. Like flat_map, flat_multimap uses parallel key/value
containers by default. Its iterator dereference is pair-like and may contain
references/proxies rather than a stored pair<const K,V> node.
Bulk constructors accept unsorted input and establish the invariant. When a
public API promises the original relative order of equal-key pairs, make that
promise explicit: stable-sort the pairs by key first, then use the sorted tag.
The tags
std::sorted_unique and std::sorted_equivalent instead assert that the caller
already established the appropriate invariant. They do not sort or validate
an arbitrary range. Distinguish unique from merely sorted equivalent keys.
#include <flat_map>
#include <flat_set>
#include <cstdio>
#include <string>
int main() {
std::flat_multimap<int,std::string> events(std::sorted_equivalent,{{1,"x"},{2,"first"},{2,"second"}});
auto [first,last]=events.equal_range(2);
for(;first!=last;++first)std::printf("%s ",first->second.c_str());
std::puts("");
std::flat_multiset<int> deadlines{2,1,2,3};
std::printf("count twos %td\n",deadlines.upper_bound(2)-deadlines.lower_bound(2));
}Random-access flat iterators make bound subtraction constant time after the search. Node multiset iterators are bidirectional, so std::distance over a group still walks that group. Flat insert/erase can shift elements and invalidate handles; choose node containers when caller-held references must survive.
The build uses each representation directly: one-occurrence cancellation, inclusive multimap queries, deterministic unordered groups, bag equality, flat_set deduplication, flat_multimap bulk construction and flat_multiset range counting. Tests include duplicate ties, negative and reversed bounds, rehashing and unsorted inputs. Each failed case should point to a violated contract, not to a guessed tree shape or bucket order.