std::unordered_set<T> is a hash-table-backed associative container that stores unique elements with no defined order, added in C++11. It trades the sorted-order guarantee of std::set for average constant-time insert, find, and erase. std::unordered_multiset is its sibling that allows duplicates. This chapter covers the bucket-based internals, the API, custom hashing and equality, the rehash mechanism, and when to pick unordered_set over the tree-based set.

The tree-based std::set from the previous lesson keeps elements sorted, which is useful for ordered traversal, finding the smallest, or range queries. But sorting isn't free. Every insert and lookup costs O(log n) because the tree has to walk down log n levels of nodes.

For membership-only queries ("is this product code already in the wishlist?") where the order doesn't matter, paying for sortedness is wasted work. A hash table reduces that to average O(1) by computing an index from the element itself and jumping straight to where it would live.

std::unordered_set<T> is the standard library's hash-set implementation. Same role as std::set (a collection of unique elements), different machinery.

The container rejects the duplicate insert, just like set. The lookup is O(1) on average instead of O(log n). The print order isn't guaranteed; the standard says nothing about it, and it can change between insertions or after a rehash.

Average O(1) for insert, find, erase, and count. Worst case is O(n) when every element hashes to the same bucket, caused by a bad hash function or an adversarial input pattern.

A hash table is an array of slots, called buckets. To find where an element belongs, the container runs the element through a hash function that produces a size_t, then takes that modulo the bucket count to pick a bucket index.

Two elements with the same hash, or with different hashes that map to the same bucket after the modulo, are said to collide. std::unordered_set resolves collisions with separate chaining: each bucket holds a singly-linked list (or similar structure) of all elements that landed there. Both libstdc++ (GCC) and libc++ (Clang) use this approach.

A diagram of the layout.

Bucket 2 has two elements in a chain because their hashes collided. Lookups for Mouse Pad and HDMI Adapter both land in bucket 2 and then walk the chain comparing each entry with operator== until they find a match (or the end of the chain).

That's the entire idea. Compute hash, jump to bucket, walk a short chain. With short chains, every operation is essentially constant time.

Every everyday operation mirrors std::set. The headline difference is the complexity column.

A tour of the everyday ones. The example uses an order-tracking set that holds the IDs of orders already shipped.

The iteration order isn't sorted and isn't insertion order. Treat it as undefined.

insert returns a std::pair<iterator, bool>. The bool indicates whether the insert actually happened (true) or the element was already there (false). That second return value allows checking for duplicates without an extra find call.

Since C++20, contains(x) is a cleaner spelling of "is this key present?".

Before C++20, the idioms were categories.count("books") > 0 or categories.find("books") != categories.end(). contains reads better; use it when the compiler supports it.

emplace constructs the element in place from the arguments passed, skipping a temporary. For strings and other small types this rarely matters, but for objects with expensive constructors it can save a copy.

For built-in types and the standard string types, std::hash<T> is already defined. Dropping them into an unordered_set works directly. For user-defined types, the container has no idea how to hash the object, so the hash has to be provided.

There are two ways. The first is to specialise std::hash<T> in the std namespace. This is the right move when the type is local and every unordered_set<T> and unordered_map<T, ...> in the program should use the same hash automatically.

Three rules are non-negotiable for a hash function:

The combine step h1 ^ (h2 << 1) mixes both fields into the final hash. It's a common pattern, though for serious code, prefer something like boost::hash_combine or a dedicated mixing function. Both code and region contribute to the hash, so two coupons with the same code but different region produce different hashes (probably) and land in different buckets.

The second way to provide a hash is to pass a functor as a template argument, without touching the std namespace. This is useful when the type isn't local, or when a hash specific to one container instance is needed.

Pick whichever style fits the codebase. The std::hash specialisation is the more common choice in modern code because it works with every unordered_* container automatically.

A bad hash function (for example, one that always returns 0) makes every element land in the same bucket. Every operation degrades from O(1) to O(n). This is the most common reason an unordered container performs worse than expected.

The container needs two pieces of information about the key type: how to hash it, and how to compare two values for equality. Equality is the third template parameter, KeyEqual, defaulting to std::equal_to<T>, which calls operator==.

For a type with a sensible operator==, KeyEqual doesn't need attention. Supplying a custom one is only needed for non-default notions of equality (case-insensitive strings, comparison ignoring some fields).

Hash and equality must agree. If two strings compare equal under CaseInsensitiveEq, they must produce the same hash under CaseInsensitiveHash. That's why CaseInsensitiveHash lowercases each character before mixing it in.

The performance of a hash table depends on keeping the chains short. The load factor is the ratio of elements to buckets:

A load factor of 1.0 means, on average, every bucket holds one element. A load factor of 5.0 means, on average, every bucket holds five elements, so lookups walk longer chains. To keep operations fast, the container grows the bucket array when the load factor exceeds a threshold.

That threshold is the max load factor, accessible via max_load_factor(). The default is 1.0. When an insert would push the load factor above this value, the container rehashes: it allocates a larger bucket array (typically doubling, then rounding up to a prime) and reinserts every element using the new bucket count.

These values are accessible directly.

The bucket count starts at an implementation-defined minimum and grew several times as elements were inserted. Each growth is a rehash. Across many inserts, the cost of rehashing amortises to O(1) per insert: each element is moved a logarithmic number of times overall, but spread across n inserts that's a constant on average.

The single insert that triggers the rehash, though, is O(n) for that one call. When the approximate element count is known, telling the container upfront avoids that hiccup.

reserve(n) sets the bucket count so the load factor stays under max_load_factor after inserting n elements, with no rehashes during the inserts.

rehash(n) is a lower-level cousin: it sets the bucket count to at least n, computing a value that keeps the load factor under the maximum. reserve is almost always the right choice.

A rehash walks every element in the container and reinserts it into the new bucket array. For n elements, that's O(n) work. Use reserve upfront when the expected size is known to avoid these spikes.

unordered_set exposes the bucket structure through a small set of methods. These are rarely needed in application code, but they're useful for diagnostics, benchmarking, and the occasional interview question.

The exact output depends on the standard library implementation. A representative run with libstdc++:

The bucket walk is mostly useful for spotting a bad hash: when one bucket holds an outsized share of elements, the hash isn't distributing them well.

Three insert patterns interact poorly with rehashing without planning.

Inserting in tight loops without reserving. Every time the load factor crosses the threshold, a rehash happens. For 1 million inserts, 20+ rehashes can occur, each doing a linear sweep over what's already there. The total work is still amortised O(n), but the variance per insert is high. reserve flattens that out.

Holding iterators across an insert. Any insert can trigger a rehash, and a rehash invalidates every iterator into the container. Walking the set while inserting can leave the iterator dangling between operations.

Misjudging the max load factor. Setting max_load_factor(0.5) doubles the bucket array size at the same number of elements, which keeps chains shorter (faster lookups) but uses more memory. Setting it to 2.0 does the opposite. The default of 1.0 is a reasonable balance to keep unless measurements say otherwise.

Roughly double the buckets for the same data, and the average chain length is roughly half what it would have been with the default.

std::unordered_multiset<T> is the duplicates-allowed sibling. Everything about buckets, hashing, equality, and rehashing carries over. The only behavioural differences are:

A unordered_multiset is the right pick for fast "how many times did this happen?" lookups when insertion order and sortedness don't matter.

The same job can be done with std::unordered_map<std::string, int> storing counts. The map version uses less memory when most keys have many duplicates, the multiset uses less when most keys have one or two. Either works; pick by what reads more naturally for the problem.

The two containers solve overlapping but different problems. Pick by the ordering requirement.

Choose unordered_set when:

Choose set when:

For most fast-lookup cases, unordered_set is the default. For ordered traversal or range queries, use set.

The sorted output is part of set's contract. The other one is whatever the hash function and bucket layout produce.