C++
Library
since C++98
Basic

std::map / std::unordered_map

std::map (sorted red-black tree, O(log n)) and std::unordered_map (hash table, O(1) avg): when to pick each, how to tune performance, and C++17/20/23 additions.

C++98C++11C++14C++17C++20C++23
std::map / std::unordered_mapsince C++98 / C++11

std::map<K,V> is an ordered associative container backed by a red-black tree that maps unique keys to values with O(log n) operations and guaranteed sorted traversal; std::unordered_map<K,V> (C++11) provides the same key-value mapping via a hash table with O(1) average access at the cost of key ordering.

Overview

Three containers cover the key-value use case in modern C++:

ContainerBacking structureLookupIterationHeader
std::mapRed-black treeO(log n)Sorted ascending<map>
std::unordered_map (C++11)Hash table + chainingO(1) avg, O(n) worstUnordered<unordered_map>
std::flat_map (C++23)Two sorted vectorsO(log n)Sorted, cache-friendly<flat_map>

Choose std::map when sorted iteration, range queries, or stable iterators across insertions matter. Every insertion leaves existing iterators and references valid — a guarantee std::unordered_map cannot make across a rehash.

Choose std::unordered_map when lookup throughput dominates and key order is irrelevant. On large maps, expect 3–5× faster average lookup than std::map, but account for rehashing overhead and cache-hostile bucket traversal under high collision rates.

Choose std::flat_map (C++23) for read-heavy workloads built once and queried many times. Keys and values sit in contiguous vectors, eliminating per-node heap allocations and yielding substantially better cache performance than either node-based container. Insert and erase are O(n), so it is not appropriate for dynamic workloads.

Both std::map and std::unordered_map enforce unique keys. Use std::multimap / std::unordered_multimap for duplicate keys.

Syntax

cpp
// std::map — Key must satisfy LessThanComparable (operator< or custom Compare)
template<
    class Key,
    class T,
    class Compare   = std::less<Key>,                              // C++98
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;

// std::unordered_map — Key must satisfy Hash and EqualityComparable
template<
    class Key,
    class T,
    class Hash      = std::hash<Key>,                             // C++11
    class KeyEqual  = std::equal_to<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class unordered_map;

value_type for both is std::pair<const Key, T>. The const on Key is load-bearing: it prevents in-place key mutation, which would silently corrupt the container's invariant. Use extract() (C++17) when you need to modify a key.

Examples

Lookup patterns

cpp
std::map<std::string, int> scores{{"Alice", 95}, {"Bob", 87}};

// find() — C++98; returns end() on miss; O(log n) for map
if (auto it = scores.find("Alice"); it != scores.end()) {  // C++17 init-if
    std::cout << it->second << '\n';
}

// contains() — C++20; preferred existence check; no accidental insertion
if (scores.contains("Bob")) { ... }

// operator[] — INSERTS a default-constructed value if key is absent!
int x = scores["Charlie"];   // scores now contains {"Charlie", 0}
// Use only when default-insertion is intentional (e.g., frequency counts)

Heterogeneous lookup

Passing std::string_view to a std::map<std::string, V> normally allocates a temporary std::string. Transparent comparators eliminate that cost:

cpp
// C++14: std::less<> (void specialisation) enables heterogeneous lookup in map
std::map<std::string, int, std::less<>> m{{"hello", 1}};
std::string_view sv = "world";
m.find(sv);      // no std::string constructed — C++14
m.contains(sv);  // C++20 + C++14 transparent comparator

// C++20: heterogeneous lookup in unordered_map requires custom hash and equal
// with using is_transparent = void as an opt-in marker in each
struct SvHash {
    using is_transparent = void;
    size_t operator()(std::string_view sv) const { return std::hash<std::string_view>{}(sv); }
    size_t operator()(const std::string& s)  const { return std::hash<std::string>{}(s); }
};
struct SvEqual {
    using is_transparent = void;
    bool operator()(std::string_view a, std::string_view b) const { return a == b; }
};
std::unordered_map<std::string, int, SvHash, SvEqual> um;
um.find(sv);   // zero allocation — C++20

Insertion

cpp
std::map<std::string, std::vector<int>> m;

// insert() — inserts only if key absent; returns {iterator, bool}; C++98
auto [it, ok] = m.insert({"key", {1, 2}});  // structured bindings: C++17

// emplace() — constructs value in-place; avoids extra copies; C++11
m.emplace("key", std::vector<int>{1, 2});

// try_emplace() — C++17: does NOT move-from arguments if key already exists
// The right default for conditional insertion with expensive or move-only values.
m.try_emplace("key", std::initializer_list<int>{1, 2});

// insert_or_assign() — C++17: always assigns the value; returns {iterator, bool}
m.insert_or_assign("key", std::vector<int>{3, 4});

try_emplace is strictly better than emplace or operator[] for conditional insertion: if the key exists, value arguments are left untouched — no spurious move or copy occurs.

Range queries (std::map only)

cpp
std::map<int, std::string> log{{1,"a"},{3,"c"},{5,"e"},{7,"g"},{10,"j"}};

// lower_bound: first key >= query; upper_bound: first key > query
auto lo = log.lower_bound(3);   // → {3,"c"}
auto hi = log.upper_bound(7);   // → {10,"j"}

// Iterate the half-open interval [3, 8):
for (auto it = log.lower_bound(3); it != log.upper_bound(7); ++it) {
    std::cout << it->first << ':' << it->second << ' ';
}
// Output: 3:c 5:e 7:g

// equal_range() returns both bounds as a pair — useful for multimap
auto [beg, end] = log.equal_range(5);  // C++17 structured bindings

Node handles and key modification (C++17)

cpp
std::map<int, std::string> src{{1,"one"},{2,"two"},{3,"three"}};
std::map<int, std::string> dst;

auto node = src.extract(2);    // removes node from src — no allocation, no copy
node.key() = 42;               // mutate the key — impossible via iterator
dst.insert(std::move(node));   // splice into dst — no allocation, no copy

// merge() transfers all non-conflicting nodes from one map to another — C++17
std::map<int,std::string> a{{1,"a"},{2,"b"}}, b{{2,"X"},{3,"c"}};
a.merge(b);   // b's {3,"c"} moved to a; {2,"X"} stays in b (conflict)

std::unordered_map performance tuning

cpp
std::unordered_map<std::string, int> freq;
freq.reserve(50'000);         // pre-size; prevents rehashing during bulk insert
freq.max_load_factor(0.5f);   // rehash threshold (default 1.0); lower → fewer collisions, more memory

// Custom hash for a user-defined key — use hash-combine, not XOR (XOR is symmetric)
struct Point { int x, y; };
struct PointHash {
    size_t operator()(const Point& p) const noexcept {
        size_t h = std::hash<int>{}(p.x);
        h ^= std::hash<int>{}(p.y) + 0x9e3779b9 + (h << 6) + (h >> 2);
        return h;
    }
};
std::unordered_map<Point, double, PointHash> dist;

Best Practices

  • Use try_emplace over operator[] for any value type that is expensive to construct, move, or should not be default-initialized. operator[] always default-constructs the value on a miss.
  • Call reserve(n) before bulk insertion into unordered_map. A default-constructed map rehashes roughly every time the element count crosses a power-of-two threshold — inserting 100k elements without reserving causes ~17 rehashes.
  • Enable heterogeneous lookup (std::less<> for map, is_transparent hash/equal for unordered_map) whenever the key type is heavier than the lookup key (e.g., std::string keyed map queried with std::string_view).
  • Prefer contains() over count() in C++20 and later. count() returns 0 or 1 for unique-key maps and exists mainly for multimap compatibility; contains() expresses intent clearly.
  • After find(), act on the iterator rather than calling operator[] again. A find-then-index pattern does two lookups for one key.

Common Pitfalls

operator[] is always an insertion

cpp
std::map<std::string, int> m;
if (m["missing"]) { ... }    // "missing" → 0 is now in the map — silent mutation
// Fix: m.contains("missing") in C++20, or m.find("missing") != m.end()

This is particularly dangerous in const member functions — operator[] is non-const and will not compile there, but find() and contains() are both const-qualified.

Hash flooding degrades unordered_map to O(n)

If many keys collide into the same bucket — through a poor hash function or adversarial input — lookup degrades from O(1) to O(n). For code that processes externally-supplied keys, use a randomised seed (e.g., FNV-1a with a per-process secret) or fall back to std::map.

Iterator invalidation rules differ

std::map: insertions never invalidate any iterator or reference. Only the erased element's iterator is invalidated on erase.

std::unordered_map: any insertion that triggers a rehash invalidates all iterators. After a rehash, only the erased element's iterator is invalidated on erase.

cpp
// Safe erase-during-iteration for both containers:
for (auto it = m.begin(); it != m.end(); ) {
    it = shouldErase(it->second) ? m.erase(it) : std::next(it);
}

Structured bindings and const correctness

cpp
for (auto& [k, v] : m)       { v = 0; }   // modifies values in-place — correct
for (auto  [k, v] : m)       { v = 0; }   // modifies a copy — silent no-op
for (const auto& [k, v] : m) { ... }      // read-only — preferred

Always use const auto& when iterating for read-only access; auto& when mutating values.

See Also

  • std::set / std::unordered_set — same containers without a mapped value
  • std::multimap / std::unordered_multimap — allow duplicate keys
  • std::flat_map (C++23) — cache-efficient sorted map over contiguous storage
  • Which container should I use?
  • Structured bindings — unpacking pair<const K,V> in range-for