Library

since C++98

Basic

std::multimap and std::multiset

Ordered associative containers allowing duplicate keys — equal_range, node handles, erase semantics, and flat variants.

std::multimap / std::multisetsince C++98

Ordered associative containers backed by a red-black tree that permit multiple elements with equivalent keys, providing O(log n) insertion, removal, and single-key lookup.

Overview

std::multiset and std::multimap are the duplicate-key variants of std::set and std::map. Both maintain sorted order (ascending by default via std::less<Key>) and share the same iterator invalidation guarantees: only the erased element's iterator is invalidated; all others remain valid across insertions and erasures.

The critical semantic differences from their unique-key counterparts:

multiset retains all inserted values, including equal ones, in sorted order.
multimap retains all key–value pairs sharing a key; duplicate-key entries appear in insertion order relative to each other.
Neither container supports operator[] or try_emplace — those operations require key uniqueness.
insert() on a multimap always succeeds; there is no rejection on duplicate keys.

Syntax

cpp

#include <set>
template<class Key,
         class Compare   = std::less<Key>,
         class Allocator = std::allocator<Key>>
class multiset;

#include <map>
template<class Key,
         class T,
         class Compare   = std::less<Key>,
         class Allocator = std::allocator<std::pair<const Key, T>>>
class multimap;

A custom Compare must establish a strict weak ordering. Passing std::greater<Key> reverses iteration direction; passing a lambda requires it as a constructor argument (not just a template argument).

Examples

Fundamental operations

cpp

#include <set>
#include <iostream>

std::multiset<int> ms{3, 1, 4, 1, 5, 9, 2, 6, 5};
// Stored in sorted order with duplicates: {1, 1, 2, 3, 4, 5, 5, 6, 9}

ms.count(1);   // 2 — O(log n + k)
ms.count(7);   // 0

// C++20: contains() short-circuits after finding one match; prefer over count() > 0
if (ms.contains(5)) { /* ... */ }             // C++20

// equal_range — O(log n) to locate bounds, O(k) to iterate
auto [lo, hi] = ms.equal_range(5);            // C++17 structured bindings
for (auto it = lo; it != hi; ++it)
    std::cout << *it << ' ';                  // 5 5

// Erase ONE occurrence: pass an iterator
auto it = ms.find(1);
if (it != ms.end()) ms.erase(it);             // removes exactly one element

// Erase ALL occurrences of a value: pass the value
ms.erase(5);                                  // removes both 5s

cpp

#include <map>
#include <string>

std::multimap<std::string, int> scores;
scores.insert({"Alice", 95});
scores.insert({"Alice", 88});   // duplicate key — both stored
scores.insert({"Alice", 91});
scores.insert({"Bob",   82});

scores.count("Alice");   // 3

// operator[] does NOT exist on multimap
// scores["Alice"] would not compile

// Iterate all values for a key
auto [lo, hi] = scores.equal_range("Alice");  // C++17
for (auto it = lo; it != hi; ++it)
    std::cout << it->second << '\n';           // 95, 88, 91 (insertion order)

// find() returns an unspecified element when duplicates exist
auto it = scores.find("Alice");               // could point to any of the three

// Remove one specific entry
for (auto it = scores.lower_bound("Alice"); it != scores.upper_bound("Alice"); ) {
    if (it->second == 88) it = scores.erase(it);
    else ++it;
}

C++17: node handles — extract and merge

C++17 added extract() and merge(), enabling zero-copy element transfer between compatible containers.

cpp

#include <map>
#include <set>

std::multiset<int> a{1, 2, 3, 3};
std::multiset<int> b{4, 5, 3};

// merge() moves ALL elements of b into a (duplicates are permitted)
a.merge(b);     // a == {1, 2, 3, 3, 3, 4, 5}, b is now empty  // C++17

// extract() removes one element and returns a node handle
std::multiset<int> src{10, 20, 20, 30};
auto node = src.extract(src.find(20));        // removes one 20  // C++17
// src == {10, 20, 30}; node.value() == 20

std::multiset<int> dst;
dst.insert(std::move(node));                  // zero-copy transfer into dst

// Cross-container transfer: map node → multimap (same Key/T required)
std::map<std::string, int>      unique_tbl{{"alpha", 1}};
std::multimap<std::string, int> multi_tbl;

auto nh = unique_tbl.extract("alpha");        // C++17
multi_tbl.insert(std::move(nh));              // no copy of key or value

Inverted index

cpp

#include <map>
#include <string>
#include <iostream>

std::multimap<std::string, int> index;
index.emplace("c++",       1);
index.emplace("templates", 2);
index.emplace("c++",       5);
index.emplace("templates", 5);
index.emplace("concepts",  5);

auto lookup = [&](const std::string& term) -> std::vector<int> {
    std::vector<int> docs;
    auto [lo, hi] = index.equal_range(term);  // C++17
    for (auto it = lo; it != hi; ++it)
        docs.push_back(it->second);
    return docs;
};
// lookup("c++") → {1, 5}

Event scheduler with equal timestamps

cpp

#include <map>
#include <cstdint>
#include <functional>

struct Event { std::string name; std::function<void()> fn; };
std::multimap<int64_t, Event> schedule;

schedule.emplace(1000, Event{"tick",   []{ /* physics  */ }});
schedule.emplace(1000, Event{"render", []{ /* graphics */ }});  // same time
schedule.emplace(2000, Event{"save",   []{ /* persist  */ }});

auto dispatch = [&](int64_t now) {
    auto end = schedule.upper_bound(now);
    for (auto it = schedule.begin(); it != end; ++it)
        it->second.fn();
    schedule.erase(schedule.begin(), end);
};

C++23: flat_multimap and flat_multiset

C++23 introduces contiguous-storage variants with the same interface but radically better cache behavior.

cpp

#include <flat_map>    // C++23
#include <flat_set>    // C++23

std::flat_multiset<int> fms{3, 1, 4, 1, 5, 9};
// Elements stored in a sorted vector — iteration is cache-hot

std::flat_multimap<std::string, int> fmm;
fmm.emplace("key", 1);
fmm.emplace("key", 2);

auto [lo, hi] = fmm.equal_range("key");   // same API, better cache locality

flat_multimap/flat_multiset pay O(n) on each insertion (vector shift), so they are ideal for build-once, query-many workloads. For containers that mutate frequently, the tree-based forms remain superior.

Choosing the Right Container

Container	Duplicate keys	Order	Lookup	Insert/erase	Cache
`multimap` / `multiset`	yes	sorted	O(log n)	O(log n)	poor (nodes)
`unordered_multimap` / `unordered_multiset`	yes	none	O(1) avg	O(1) avg	poor (buckets)
`flat_multimap` / `flat_multiset` (C++23)	yes	sorted	O(log n)	O(n)	excellent
`map<K, vector<V>>`	via vector	sorted	O(log n)	O(log n)	good for V

Prefer map<K, vector<V>> when you predominantly access all values for a key at once — grouped storage eliminates repeated tree traversals. Use multimap when elements arrive and depart individually and sorted key order is required.

Best Practices

Prefer equal_range over repeated find. Both locate the range in O(log n), but equal_range returns both bounds in a single lookup; walking from find's result requires a second O(log n) call to upper_bound if you need the end.
Use contains() (C++20) instead of count() > 0 when only existence matters — it stops at the first match.
Use emplace over insert with temporary pairs. emplace constructs in-place, avoiding the extra construction that insert({k, v}) incurs.
Use merge() (C++17) to absorb entire containers. It transfers node handles without allocation, far faster than a loop of insert.
Reserve flat_multimap/flat_multiset (C++23) for read-dominated cases. Populate once, then benefit from contiguous iteration.

Common Pitfalls

operator[] does not exist on multimap. It would be ambiguous — which value should it return when three entries share a key? Reach for find() or equal_range().

find() picks an unspecified element among duplicates. The standard only guarantees an iterator to some matching element, not the first inserted. If order matters, iterate the full equal_range.

erase(key) removes every matching element. Passing a value instead of an iterator to erase eliminates all entries with that key in one call. For surgical removal, extract an iterator via find() or walk equal_range and call erase(iterator).

std::distance(lo, hi) is O(k), not O(1). Iterators are bidirectional, not random-access. To count matches, use count(key) which is O(log n + k) and avoids constructing an iterator pair.

merge() (C++17) empties the source for multi-containers. Because multimap/multiset accept all duplicates, every element from the source transfers unconditionally — the source is left empty. This differs from map::merge(), where elements with already-present keys stay in the source.

Prefix Lookup with `lower_bound` / `upper_bound`

A multimap<string, V> can serve as a trie-like prefix index when keys are sorted strings. Because the red-black tree maintains lexicographic order, all keys sharing a given prefix are contiguous in the sorted sequence, making range-based prefix queries efficient.

The canonical pattern uses two bound calls: lower_bound("prefix") finds the first key that is not less than the prefix, and lower_bound("prefix" + '\xff') finds the first key beyond any valid extension of the prefix (since '\xff' sorts after all printable ASCII and most UTF-8 continuation bytes).

cpp

// C++20
#include <map>
#include <string>
#include <vector>

std::multimap<std::string, int> word_index;
word_index.emplace("apple",   1);
word_index.emplace("applet",  2);
word_index.emplace("application", 3);
word_index.emplace("banana",  4);
word_index.emplace("apply",   1);

// Autocomplete: find all entries whose key starts with "app"
auto prefix_search = [&](const std::string& prefix)
    -> std::vector<std::pair<std::string, int>>
{
    std::vector<std::pair<std::string, int>> results;
    auto lo = word_index.lower_bound(prefix);
    auto hi = word_index.lower_bound(prefix + '\xff');
    for (auto it = lo; it != hi; ++it)
        results.emplace_back(it->first, it->second);
    return results;
};
// prefix_search("app") → {{"apple",1},{"applet",2},{"application",3},{"apply",1}}

With C++20 you can also walk forward from lower_bound("prefix") while key.starts_with("prefix") holds, which avoids constructing the sentinel string and handles arbitrary Unicode gracefully.

cpp

// C++20
auto lo = word_index.lower_bound("app");
for (auto it = lo; it != word_index.end() && it->first.starts_with("app"); ++it)
    // process it->first, it->second
    ;

This works because sorted order makes prefixes contiguous. The strategy fails for unordered containers; it is unique to sorted associative containers like multimap, map, and their flat_ siblings.

Custom Comparator with C++20 `std::compare_three_way`

Before C++20, writing a custom comparator required careful implementation of strict weak ordering — irreflexivity, asymmetry, and transitivity — which was easy to get subtly wrong, particularly for multi-field keys or locale-aware string comparison.

C++20's operator<=> and std::compare_three_way make it straightforward to derive a correct comparator from a spaceship expression. For case-insensitive string keys, use std::ranges::lexicographic_compare with a tolower projection, or fold the key to lowercase before insertion.

cpp

// C++20
#include <map>
#include <string>
#include <cctype>
#include <algorithm>

// Case-insensitive comparator with transparent lookup
struct CILess {
    using is_transparent = void;  // enables heterogeneous lookup

    bool operator()(std::string_view a, std::string_view b) const {
        return std::ranges::lexicographical_compare(
            a, b,
            [](unsigned char x, unsigned char y) {
                return std::tolower(x) < std::tolower(y);
            });
    }
};

std::multimap<std::string, int, CILess> ci_map;
ci_map.emplace("Alice", 1);
ci_map.emplace("alice", 2);  // treated as same key by comparator
ci_map.emplace("ALICE", 3);

// Heterogeneous lookup: pass std::string_view without constructing std::string
auto [lo, hi] = ci_map.equal_range(std::string_view{"alice"});
// lo..hi covers all three entries

Lambda comparators require passing the lambda instance to the container constructor, not just as a type argument. The type of a lambda has no default constructor before C++20, so the container cannot default-construct the comparator internally.

cpp

// C++20
auto cmp = [](const std::string& a, const std::string& b) {
    return a.size() < b.size();  // sort by length
};
std::multimap<std::string, int, decltype(cmp)> m(cmp);
// Without passing `cmp` to the constructor this would fail to compile pre-C++20

The is_transparent marker enables heterogeneous lookup. Without it, every call to find, count, equal_range, or contains constructs a temporary Key object from the argument — adding unnecessary allocation when the argument is a string_view or string literal.

C++20 Ranges Integration

equal_range returns a std::pair of iterators. Wrapping it in std::ranges::subrange converts the pair into a proper range that participates in the ranges pipeline, unlocking std::views::transform, std::views::values, and algorithm compositions.

cpp

// C++20
#include <map>
#include <ranges>
#include <string>
#include <vector>
#include <algorithm>

std::multimap<std::string, int> scores;
scores.insert({"Alice", 95});
scores.insert({"Alice", 88});
scores.insert({"Alice", 91});
scores.insert({"Bob",   82});
scores.insert({"Bob",   77});

// Wrap equal_range result in a subrange for ranges compatibility
auto [lo, hi] = scores.equal_range("Alice");
auto alice_range = std::ranges::subrange(lo, hi);

// Project to values only via std::views::values
for (int v : alice_range | std::views::values)
    // v = 95, 88, 91
    ;

// Full pipeline: collect Alice's scores into a sorted vector
auto alice_scores =
    alice_range
    | std::views::values
    | std::ranges::to<std::vector>();          // C++23 for std::ranges::to
std::ranges::sort(alice_scores);
// alice_scores = {88, 91, 95}

std::views::transform lets you project any field or computed value from each mapped entry, while std::views::filter narrows the range without materialising intermediate collections.

cpp

// C++20
// Get only Alice's scores above 90
auto high_scores =
    std::ranges::subrange(scores.equal_range("Alice").first,
                          scores.equal_range("Alice").second)
    | std::views::values
    | std::views::filter([](int v) { return v > 90; });

for (int v : high_scores) { /* 95, 91 */ }

Prefer std::ranges::subrange over manual iterator loops when composing pipelines. It integrates cleanly with views and avoids repeating the range bounds throughout a processing chain.

`multiset` as Sliding Window / Running Statistics

multiset is uniquely suited for sliding window statistics because it maintains sorted order automatically on every insert and erase, giving O(log n) access to the current minimum, maximum, and arbitrary percentiles — without resorting the window after each change.

For a sliding window median, maintain two multiset instances — one for the lower half and one for the upper half — and rebalance them after each insert or eviction so that their sizes differ by at most one.

cpp

// C++11
#include <set>
#include <vector>
#include <stdexcept>

class SlidingMedian {
    std::multiset<int> low;   // max-half: largest value at *low.rbegin()
    std::multiset<int> high;  // min-half: smallest value at *high.begin()

    void rebalance() {
        // Ensure |low| - |high| <= 1 and max(low) <= min(high)
        while (low.size() > high.size() + 1) {
            high.insert(*low.rbegin());
            low.erase(std::prev(low.end()));
        }
        while (high.size() > low.size()) {
            low.insert(*high.begin());
            high.erase(high.begin());
        }
        if (!low.empty() && !high.empty() && *low.rbegin() > *high.begin()) {
            int lo_max = *low.rbegin(), hi_min = *high.begin();
            low.erase(std::prev(low.end())); high.erase(high.begin());
            low.insert(hi_min); high.insert(lo_max);
        }
    }

public:
    void insert(int x) {
        if (low.empty() || x <= *low.rbegin()) low.insert(x);
        else high.insert(x);
        rebalance();
    }
    void erase(int x) {
        if (low.count(x)) low.erase(low.find(x));
        else high.erase(high.find(x));
        rebalance();
    }
    double median() const {
        if (low.empty()) throw std::runtime_error("empty");
        if (low.size() == high.size())
            return (*low.rbegin() + *high.begin()) / 2.0;
        return *low.rbegin();
    }
};

// Sliding window median of last K values
std::vector<double> sliding_window_median(
    const std::vector<int>& nums, int k)
{
    SlidingMedian sm;
    std::vector<double> result;
    for (int i = 0; i < (int)nums.size(); ++i) {
        sm.insert(nums[i]);
        if (i >= k) sm.erase(nums[i - k]);
        if (i >= k - 1) result.push_back(sm.median());
    }
    return result;
}

Running min/max are O(log n) per operation. After each insert or erase, *ms.begin() and *ms.rbegin() give the current extremes in O(1) — the O(log n) cost lies entirely in the structural update.

Sliding window element frequency — how many times a value appears in the current window — is O(log n + k) via count(), versus an O(n) scan of a raw array. For windows of tens of thousands of elements this difference is significant.

Performance: Tree vs Hash vs Flat Multimap

Container choice has measurable impact at scale. The table and estimates below assume a 100 K-element store with uniformly distributed integer keys on a modern x86-64 with a warm L3 cache.

Operation	`multimap`	`unordered_multimap`	`flat_multimap` (C++23)
Insert	O(log n) ~200 ns	O(1) avg ~50 ns	O(n) ~10 µs (vector shift)
Lookup	O(log n) ~150 ns	O(1) avg ~30 ns	O(log n) ~20 ns (binary search)
Iteration	poor — pointer chase	poor — bucket hop	excellent — contiguous
Memory overhead	~3× `sizeof(value)` per node	~2–4× + load-factor slack	~0 overhead (packed arrays)

Use multimap when elements arrive and depart individually and sorted order is required. Its O(log n) insert/erase make it the only choice among the three when the container mutates continuously.

Prefer unordered_multimap when lookup dominates and order is irrelevant. Hash collisions can degrade worst-case performance; use a high-quality hash or reserve() to keep the load factor below 0.7.

flat_multimap (C++23) is the fastest for read-heavy, build-once workloads. Load all data once, then benefit from cache-line–friendly binary search and sequential iteration that approaches std::vector throughput.

cpp

// C++23
#include <flat_map>
#include <vector>

// Build once from sorted data — O(n log n) total
std::flat_multimap<int, std::string> fmm(
    std::sorted_equivalent,   // hint: input already sorted, O(n) build
    sorted_pairs.begin(), sorted_pairs.end());

// Iteration is contiguous — nearly as fast as iterating a plain vector
for (auto& [k, v] : fmm) { /* cache-hot */ }

Memory overhead matters at large scale: 100 K multimap nodes each carrying left/right/parent pointers and an allocator block can occupy 3–5× more memory than an equivalent flat_multimap with two packed vectors.

`map<K, vector<V>>` vs `multimap<K, V>` Trade-offs

Both map<K, vector<V>> and multimap<K, V> model a one-to-many relationship, but they have complementary strengths that make one clearly preferable depending on the access pattern.

multimap stores each key–value pair as an individual tree node; every insertion and erasure touches the tree structure. map<K, vector<V>> groups all values for a key into a contiguous block, which is ideal when you typically want all values for a key at once.

Operation	`multimap<K, V>`	`map<K, vector<V>>`
Insert one value	O(log n)	O(log n) + amortised O(1) `push_back`
Lookup all values for key	O(log n) + O(k) iterate `equal_range`	O(log n) → direct `vector` access
Erase one specific value	O(1) via iterator	O(k) erase from inner vector
Erase all values for key	O(log n + k)	O(log n) erase map entry
Bulk algorithms on values	awkward — range of pairs	trivial — `std::sort(v.begin(), v.end())`
JSON / serialisation	requires grouping step	natural — key maps to array

cpp

// C++11 — multimap: natural streaming inserts, awkward bulk access
std::multimap<std::string, int> mm;
mm.emplace("Alice", 95);
mm.emplace("Alice", 88);

// Collect all Alice scores into a vector for sorting — extra allocation needed
auto [lo, hi] = mm.equal_range("Alice");
std::vector<int> tmp(lo, hi);          // copies values into a temp vector
// (lo..hi are pairs, not ints, so a transform is needed in practice)

cpp

// C++11 — map<K,vector<V>>: grouped access, vector algorithms directly available
std::map<std::string, std::vector<int>> mv;
mv["Alice"].push_back(95);
mv["Alice"].push_back(88);

auto& alice = mv["Alice"];            // O(log n), then direct reference
std::sort(alice.begin(), alice.end()); // no extra allocation

Use multimap for streaming individual events with random insertion and erasure. Each node is independent; erasing one entry is O(1) via its iterator and does not shift any other data.

Use map<K, vector<V>> for batch queries, vector algorithms on grouped values, or when you need to serialise to JSON. The inner vector gives you full random access, sorting, and range algorithms without materialising a temporary container.

See Also

std::map / std::set — unique-key ordered associative containers
std::unordered_multimap — hash-based duplicate-key map, O(1) average lookup
std::flat_multimap — C++23 sorted-vector variant with cache-friendly layout