C++ STL Series · Part 2 of 5

Maps & Sets — Ordered vs Unordered

March 2026 · 14 min read

The Four Associative Containers

The STL provides two families of key-value stores:

Ordered — std::map, std::set (backed by red-black trees)
Unordered — std::unordered_map, std::unordered_set (backed by hash tables)

Ordered: std::map & std::set

These store keys in sorted order using a balanced BST (red-black tree). Every lookup, insert, and erase is O(log n).

#include <map>
#include <iostream>

int main() {
    std::map<std::string, int> freq;
    freq["apple"] = 5;
    freq["banana"] = 3;
    freq["cherry"] = 7;

    // Iterates in sorted key order
    for (auto& [key, val] : freq)
        std::cout << key << ": " << val << "\n";
}

When to Choose Ordered

You need elements in sorted order.
You need range queries: lower_bound(), upper_bound().
Key type only supports operator<, not a hash function.

Unordered: std::unordered_map & std::unordered_set

These use hash tables for O(1) average operations. Worst case is O(n) when hash collisions degrade to a linked list.

▶ Hash Table Lookup Animation

See how a key is hashed to a bucket for O(1) lookup.

#include <unordered_map>

std::unordered_map<std::string, int> cache;
cache["key1"] = 42;

if (cache.count("key1"))
    std::cout << cache["key1"];  // O(1) average

Load Factor & Rehashing

The container rehashes when size / bucket_count exceeds max_load_factor() (default 1.0). Rehashing is O(n) and invalidates all iterators.

cache.reserve(10000);  // pre-allocate buckets, similar to vector::reserve

Performance tip: Use reserve() when the number of expected keys is known. This avoids expensive rehashes during bulk insertions.

Writing a Custom Hash

For user-defined types, provide a hash functor:

struct PairHash {
    size_t operator()(const std::pair<int,int>& p) const {
        auto h1 = std::hash<int>{}(p.first);
        auto h2 = std::hash<int>{}(p.second);
        return h1 ^ (h2 << 32);
    }
};

std::unordered_set<std::pair<int,int>, PairHash> seen;

Multimaps and Multisets

std::multimap and std::multiset allow duplicate keys. Use equal_range() to iterate over all values for a key:

std::multimap<std::string, int> mm;
mm.insert({"a", 1});
mm.insert({"a", 2});

auto [lo, hi] = mm.equal_range("a");
for (auto it = lo; it != hi; ++it)
    std::cout << it->second << " ";  // 1 2

Quick Comparison

Feature	map / set	unordered_map / set
Backing structure	Red-black tree	Hash table
Lookup	O(log n)	O(1) avg
Ordered iteration	Yes	No
Range queries	Yes	No
Requirements on key	operator<	hash + operator==

Common Pitfalls

operator[] Inserts on Miss

map[key] inserts a default-constructed value if the key doesn't exist. Use find() or count() for read-only lookups.

Iterator Stability

Ordered containers: iterators remain valid after insert/erase (except for the erased element). Unordered containers: iterators are invalidated on rehash.

Summary

Default to std::unordered_map for speed when order doesn't matter.
Use std::map when you need sorted access or range queries.
Always reserve() unordered containers when bulk-loading.
Watch out for accidental insertion via operator[].