C++
Library
since C++11
Intermediate

unordered_set and unordered_multiset

Hash-based sets with O(1) average lookup—custom hashing, rehashing, iterator invalidation, C++17/20 additions, and performance traps.

std::unordered_set / std::unordered_multisetsince C++11

Hash-table–based set containers that provide O(1) average-case insert, erase, and lookup, at the cost of no ordering guarantee and O(n) worst-case performance when hash collisions are pathological.

Overview

Both containers live in <unordered_set> and use separate chaining: each bucket holds a singly-linked list of elements whose hashes map to that bucket. Elements are never physically moved when a bucket grows—only during a rehash, which invalidates all iterators, pointers, and references.

unordered_set enforces uniqueness. unordered_multiset allows duplicate keys and keeps equal elements adjacent within their bucket, making equal_range efficient.

Prefer unordered_set over set when:

  • Membership tests dominate and sorted order is irrelevant.
  • The key type has a cheap, well-distributed hash.
  • The dataset is large enough that O(log n) comparisons matter (empirically ~10k+ elements).

Stay with set when:

  • You need ordered iteration, lower_bound, or range queries.
  • Worst-case guarantees matter—adversarial inputs that degenerate a hash table are real.
  • The key type lacks a natural hash but has a cheap less-than comparison.

Syntax

cpp
template<
    class Key,
    class Hash     = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Alloc    = std::allocator<Key>
>
class unordered_set;   // C++11

The Hash callable must satisfy: equal keys produce equal hashes. It need not be injective. KeyEqual must be consistent with Hash—if a == b then hash(a) == hash(b). Violating this silently corrupts lookup.

Examples

Basic Operations

cpp
#include <unordered_set>
#include <print>   // C++23

std::unordered_set<std::string> words{"apple", "banana", "cherry"};

words.insert("date");
words.emplace("elderberry");          // in-place construction, C++11

// Lookup
bool has = words.contains("apple");   // C++20; use count() != 0 before C++20
auto it  = words.find("banana");      // O(1) avg; returns end() if absent

// insert returns pair<iterator, bool>
auto [pos, inserted] = words.insert("apple");   // C++17 structured bindings
if (!inserted) { /* already present */ }

// Erase by value (O(1) avg) or by iterator (O(1))
words.erase("cherry");
if (it != words.end()) words.erase(it);

// Range insert
std::vector<std::string> extras{"fig", "grape"};
words.insert(extras.begin(), extras.end());

Custom Hash — Proper hash_combine

XOR-only combination (h1 ^ h2) is a common mistake: it is symmetric, so {1, 2} and {2, 1} hash identically, and it zero-cancels equal fields. Use a mixing function instead:

cpp
template<typename T>
void hash_combine(std::size_t& seed, const T& v) noexcept {
    // Boost-style avalanche mixing; the magic constant is 2^32 / phi
    seed ^= std::hash<T>{}(v) + 0x9e3779b9u + (seed << 6) + (seed >> 2);
}

struct Point { int x, y; };

bool operator==(const Point& a, const Point& b) noexcept {
    return a.x == b.x && a.y == b.y;
}

template<>
struct std::hash<Point> {
    std::size_t operator()(const Point& p) const noexcept {
        std::size_t seed = 0;
        hash_combine(seed, p.x);
        hash_combine(seed, p.y);
        return seed;
    }
};

std::unordered_set<Point> grid;
grid.insert({0, 0});
grid.emplace(3, 4);
std::println("{}", grid.contains({3, 4}));   // true; C++20 + C++23

Bucket API and Rehashing

cpp
std::unordered_set<int> s;

// Reserve before bulk insertion — avoids mid-insertion rehashes
s.reserve(10'000);            // equivalent to rehash(ceil(10000 / max_load_factor()))

// Tune load factor before filling; default is 1.0
s.max_load_factor(0.75f);     // rehash when 75% full; lower = fewer collisions, more memory

for (int i = 0; i < 10'000; ++i) s.insert(i);

std::println("buckets: {}",        s.bucket_count());
std::println("load: {:.3f}",       s.load_factor());

// Inspect a specific bucket
std::size_t b = s.bucket(42);
std::println("bucket {} size: {}", b, s.bucket_size(b));

// Force a rehash — ALL iterators, pointers, and references are invalidated
s.rehash(20'000);    // request at least 20 000 buckets

reserve(n) is the idiomatic way to pre-size. rehash(n) directly sets the bucket count; use it when you want explicit control over memory layout after deletions shrink the set.

C++17: Node Extraction and Merge

cpp
std::unordered_set<std::string> src{"foo", "bar", "baz"};
std::unordered_set<std::string> dst{"qux"};

// Extract a node without allocation or copy — O(1)              // C++17
auto node = src.extract("bar");
if (!node.empty()) {
    node.value() += "_v2";      // mutate before reinserting
    dst.insert(std::move(node));
}

// Splice all non-duplicate elements from src into dst            // C++17
dst.merge(src);
// Elements moved to dst are removed from src.
// Duplicates stay in src (no allocation; just not transferred).

extract is the correct way to rename or mutate a set element—the only alternative is erase-then-reinsert, which allocates.

C++20: Heterogeneous Lookup

Without a transparent hash, find("literal") constructs a temporary std::string. Opt into heterogeneous lookup to eliminate that allocation:

cpp
struct StringHash {
    using is_transparent = void;    // required marker; activates heterogeneous overloads

    std::size_t operator()(std::string_view sv) const noexcept {
        return std::hash<std::string_view>{}(sv);
    }
    // string_view is implicitly constructible from string, so one overload suffices
};

// Both Hash and KeyEqual must be transparent for heterogeneous lookup to activate  // C++20
std::unordered_set<std::string, StringHash, std::equal_to<>> words{"alpha", "beta"};

words.contains(std::string_view{"alpha"});   // no string construction, C++20
words.find("beta");                          // const char* — still no allocation

std::equal_to<> (C++14, no template argument) is the transparent equality comparator. The compiler requires both Hash::is_transparent and KeyEqual::is_transparent to exist before enabling the heterogeneous overloads.

unordered_multiset

cpp
std::unordered_multiset<int> bag{1, 2, 2, 3, 3, 3};

bag.insert(2);
std::println("count(2): {}", bag.count(2));   // 3

// equal_range: all copies of a key in O(1) avg
auto [lo, hi] = bag.equal_range(3);           // C++17 structured bindings
std::println("copies of 3: {}", std::distance(lo, hi));  // 3

// Erase exactly one occurrence
auto it = bag.find(2);
if (it != bag.end()) bag.erase(it);           // removes one '2'

// Erase ALL occurrences
bag.erase(3);    // removes all three copies

count() on unordered_multiset is O(k) where k is the number of matches, not O(1)—budget for that in hot paths.

Best Practices

Pre-size with reserve: call reserve(expected_count) before bulk insertion. A single rehash on a 1M-element set recomputes every bucket index and relinks every node.

Write a distributing hash: verify distribution by inspecting max_bucket_size() after loading data. A hash that maps many keys to one bucket silently degrades all operations to O(n). If you control neither the key type nor its hash, wrap it.

Use heterogeneous lookup for string-keyed sets (C++20): every find("literal") on a plain unordered_set<string> allocates. In a search-heavy hot path this dominates.

Prefer emplace over insert for non-trivial types: emplace constructs the element directly inside the allocated node, avoiding a temporary.

Prefer contains over count() != 0 (C++20): more expressive, and for unordered_set equally fast; for unordered_multiset it short-circuits on the first match.

Common Pitfalls

Iterator invalidation on rehash: any insert that pushes the load factor past max_load_factor() triggers a rehash and invalidates all outstanding iterators.

cpp
auto it = s.find(key);
s.insert(other_key);    // may rehash — 'it' is now dangling
*it;                    // undefined behaviour

Capture values, not iterators, across insertions—or reserve enough capacity upfront.

Mutating an element through its iterator is undefined behaviour: elements are stored as const Key in a set. Casting away const and modifying the element corrupts the bucket structure without any diagnostic. Use extract (C++17) to remove, modify, and reinsert safely.

XOR-only hash for compound keys: h1 ^ h2 is commutative—hash({a,b}) == hash({b,a})—and zero-cancels when a == b. Always use hash_combine.

Worst-case O(n) is not theoretical: a carefully chosen or user-supplied key set can deliberately pack all elements into one bucket. For containers keyed on untrusted input, use a randomised seed or a hash-hardened third-party implementation (e.g., absl::flat_hash_set, which applies per-process randomisation by default).

unordered_multiset::erase(key) removes all copies: to drop a single occurrence, pass an iterator from find(), not the key value.

Hash Quality: Testing and Inspecting Distribution

After loading data, the bucket API lets you audit how well your hash spreads elements. A good hash at a load factor of 1.0 produces max bucket size ≤ 3–4; anything higher signals a collision problem that silently degrades every operation.

cpp
#include <unordered_set>
#include <algorithm>
#include <print>   // C++23

template<typename S>
void print_bucket_stats(const S& s) {
    std::size_t max_sz = 0;
    double mean = 0.0;
    std::size_t histogram[16] = {};   // slots 0..14, 15 = "≥15"

    for (std::size_t b = 0; b < s.bucket_count(); ++b) {
        std::size_t sz = s.bucket_size(b);
        max_sz = std::max(max_sz, sz);
        mean  += static_cast<double>(sz);
        histogram[std::min(sz, std::size_t{15})]++;
    }
    mean /= static_cast<double>(s.bucket_count());

    std::println("elements={} buckets={} load={:.3f} mean={:.2f} max={}",
                 s.size(), s.bucket_count(), s.load_factor(), mean, max_sz);
    for (std::size_t i = 0; i <= 6; ++i)
        std::println("  bucket_size={}: {} buckets", i, histogram[i]);
}

A pathological hash exposes the worst case immediately. The identity hash hash(x) = 1 forces every element into a single bucket regardless of key, turning lookup into a linear scan.

cpp
// Demonstrating a broken hash — never use in production           // C++11
struct BadHash {
    std::size_t operator()(int) const noexcept { return 1; }
};

std::unordered_set<int, BadHash> broken;
for (int i = 0; i < 1'000; ++i) broken.insert(i);

// bucket_count() may be 1 or a small prime; max_bucket_size == 1000
// Every find(), insert(), and erase() is O(n) — 1000 comparisons

Red flag: max_bucket_size exceeds 10 at any reasonable load. For string keys, DDoS-style hash-flooding attacks deliberately craft payloads that all collide in a single bucket, reducing a web server's request handling to O(n²) work.

Security Hardening: Randomized Hash for String Keys

The 2012 hash-flooding vulnerabilities in Perl, PHP, Python, Ruby, and Java demonstrated that an adversary who knows your hash function can construct inputs that all map to the same bucket, degrading O(1) lookup to O(n) per operation. Web servers that fed user-supplied form field names or JSON keys directly into an unordered_map were the primary targets. The fix is a per-process random seed mixed into every hash computation.

cpp
#include <string_view>
#include <random>
#include <cstdint>

// SipHash-inspired seeded string hash — seed once per process     // C++11
struct SipHash {
    uint64_t seed_;

    // Initialize seed from a cryptographically seeded source
    SipHash() : seed_([]() -> uint64_t {
        std::random_device rd;
        return (static_cast<uint64_t>(rd()) << 32) | rd();
    }()) {}

    std::size_t operator()(std::string_view s) const noexcept {
        // FNV-1a body mixed with the random seed (production code should
        // use a real SipHash-1-3 or SipHash-2-4 implementation)
        std::size_t h = seed_ ^ 0xcbf29ce484222325ULL;
        for (unsigned char c : s) {
            h ^= c;
            h *= 0x100000001b3ULL;
        }
        return h ^ (h >> 33);
    }
};

using is_transparent = void;   // enable heterogeneous lookup

std::unordered_set<std::string, SipHash, std::equal_to<>> safe_set;

For production web services handling untrusted keys, always use a seeded hash. absl::flat_hash_set (Abseil) and folly::F14FastSet apply per-process randomization by default and are drop-in alternatives that also deliver significantly better cache performance. For trusted inputs — compile-time-constant keys, purely internal data structures, or performance-critical inner loops with known benign datasets — std::hash is fine.

absl::flat_hash_set and Open-Addressing Alternatives

std::unordered_set uses separate chaining: each bucket holds a pointer to a linked list node allocated on the heap. A cache miss is required to follow the pointer, and a second miss may be needed to compare the stored element. For 1M-element sets this pointer chasing is measurable.

Open-addressing tables store all elements inline in a contiguous array and probe neighbouring slots on collision. This means a single cache line often contains both the metadata byte (for fast SIMD comparison) and the value itself.

ImplementationLookup (1M strings)MemoryChaining model
std::unordered_set~100–150 ns~56 bytes/elemseparate chaining
absl::flat_hash_set~30–50 ns~20 bytes/elemopen addressing + SSE2
ankerl::unordered_dense~25–45 ns~16 bytes/elemRobin Hood probing
boost::unordered_flat_set~30–50 ns~18 bytes/elemopen addressing (C++26 preview)
cmake
# CMake integration for Abseil                                      # CMake 3.14+
find_package(absl REQUIRED)
target_link_libraries(my_target PRIVATE absl::flat_hash_set)
cpp
#include "absl/container/flat_hash_set.h"

absl::flat_hash_set<std::string> fast_words;
fast_words.reserve(1'000'000);
fast_words.insert("hello");
bool found = fast_words.contains("hello");   // same API as std::unordered_set

Switching from std::unordered_set to absl::flat_hash_set is usually a one-line type change. The API surface is nearly identical. Invalidation rules differ slightly: any mutation that triggers a rehash invalidates all iterators and pointers, same as the standard, but absl also provides a reserve()-before-insert guarantee of no rehash.

Enum Key Hashing: Perfect Hash Specialization

std::hash works for scoped enum types because the standard provides a specialization for all integral types, and enums are implicitly convertible. However, writing an explicit specialization makes the intent clear and lets you verify the mapping.

cpp
enum class Color { Red, Green, Blue };    // C++11

template<>
struct std::hash<Color> {
    std::size_t operator()(Color c) const noexcept {
        return static_cast<std::size_t>(c);   // identity hash; valid for small enums
    }
};

std::unordered_set<Color> palette;
palette.insert(Color::Red);
palette.insert(Color::Blue);
bool has_green = palette.contains(Color::Green);   // C++20

If the enum values are dense and bounded (0..N-1), a std::array<bool, N> is strictly faster than any hash set — O(1) with zero hashing overhead and a single cache line for small N.

cpp
// For dense enum ranges, prefer a bitset or array                  // C++11
constexpr std::size_t N = 3;
std::array<bool, N> in_set{};
in_set[static_cast<std::size_t>(Color::Red)]  = true;
in_set[static_cast<std::size_t>(Color::Blue)] = true;
// Lookup: in_set[static_cast<std::size_t>(c)] — no hash, no allocation

C++26 static reflection will allow compile-time enum introspection, enabling auto-generated optimal hashes and exhaustiveness checks without manual specialization. Until then, the explicit std::hash<MyEnum> template specialization is the portable approach.

C++23 Batch Operations: insert_range and ranges::to

C++23 adds range-aware mutating operations to all unordered containers. insert_range accepts any std::ranges::input_range and replaces the insert(begin, end) two-iterator idiom, enabling direct piping from view adapters.

cpp
#include <unordered_set>
#include <ranges>
#include <string>

std::unordered_set<std::string> words;
std::string text = "the quick brown fox jumps over the lazy dog";

// insert_range + views pipeline — no manual loop                   // C++23
words.insert_range(
    std::views::split(text, ' ')
    | std::views::transform([](auto rng) {
          return std::string(rng.begin(), rng.end());
      })
);

std::ranges::to constructs a container directly from a range pipeline, giving a concise deduplicate-then-collect idiom:

cpp
#include <vector>

std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

// Deduplicate: vector → unordered_set → vector                    // C++23
auto unique_v =
    v
    | std::ranges::to<std::unordered_set<int>>()
    | std::ranges::to<std::vector<int>>();
// unique_v contains {1,2,3,4,5,6,9} in unspecified order

std::erase_if (C++20) removes all elements matching a predicate in a single pass and returns the count of elements erased — cleaner than a raw erase-loop and avoids iterator invalidation bugs:

cpp
std::unordered_set<int> nums{1, 2, 3, 4, 5, 6, 7, 8};

// Remove all even numbers in one call                              // C++20
std::size_t removed = std::erase_if(nums, [](int x) { return x % 2 == 0; });
std::println("erased {} elements", removed);   // 4

Rehash After Bulk Deletion

After erasing a large fraction of a set, the load factor drops but the bucket array retains its pre-deletion size. The memory is still allocated. s.rehash(0) is not guaranteed to shrink the table — the standard only requires that after rehash(n) the bucket count is at least n; passing 0 may be a no-op on many implementations.

cpp
std::unordered_set<int> s;
s.reserve(1'000'000);
for (int i = 0; i < 1'000'000; ++i) s.insert(i);

// Erase 90% of elements
std::erase_if(s, [](int x) { return x % 10 != 0; });   // C++20

std::println("size={} buckets={}", s.size(), s.bucket_count());
// size=100'000 but bucket_count may still be ~1'000'000 — wasted memory

The portable shrink pattern computes the minimum bucket count required to satisfy max_load_factor at the current size:

cpp
// Portable shrink-to-fit for unordered_set                        // C++11
s.rehash(static_cast<std::size_t>(
    static_cast<double>(s.size()) / s.max_load_factor()
) + 1);

If the reconstruction cost is acceptable, copying the set also compacts it:

cpp
// Reconstruct from current elements — copies but eliminates excess buckets
s = std::unordered_set<int>(s.begin(), s.end());   // C++11

Rule of thumb: trigger a shrink rehash when size() < bucket_count() / 4. At that point the table is at 25% of its allocated capacity and roughly 75% of bucket slots are empty, which wastes memory without improving performance.

See Also

  • std::set — ordered alternative; O(log n), supports range queries, no hash required
  • std::unordered_map — key→value variant of unordered_set
  • std::flat_set — C++23 sorted flat array; cache-friendly for read-heavy workloads, no hash
  • Custom Hash Functions — hash_combine, randomised hashing, writing quality hash functions