std::set and std::unordered_set
Ordered unique-element container backed by a red-black tree (set) and hash-table unique-element container (unordered_set) in C++.
std::setsince C++98An ordered associative container that stores unique elements sorted by key using a red-black tree, providing O(log n) lookup, insert, and erase with stable iterators; std::unordered_set (C++11) is the hash-table counterpart with O(1) average operations but no ordering.
Overview
std::set<T> and std::unordered_set<T> both enforce element uniqueness, but differ in every other operational dimension. The red-black tree backing std::set guarantees sorted order, stable iterators (only the erased element's iterator is invalidated), and O(log n) worst-case for all key operations. The hash table backing std::unordered_set (C++11) gives O(1) average but O(n) worst case, and a rehash — triggered when load factor exceeds max_load_factor() — invalidates all iterators and references.
Both containers model the same conceptual interface: insert, erase, find, and contains. The divergence is in complexity class, ordering guarantees, and the query operations that only make sense on sorted data (lower_bound, upper_bound, range iteration).
Full template signatures:
#include <set> // std::set, std::multiset
#include <unordered_set> // std::unordered_set, std::unordered_multiset (C++11)
template<
class Key,
class Compare = std::less<Key>, // requires strict weak ordering
class Allocator = std::allocator<Key>
> class set;
template<
class Key,
class Hash = std::hash<Key>, // C++11
class KeyEqual = std::equal_to<Key>, // C++11
class Allocator = std::allocator<Key> // C++11
> class unordered_set;Examples
Construction
// std::set — always sorted, always unique
std::set<int> s1; // empty
std::set<int> s2{5, 1, 3, 2, 4}; // {1, 2, 3, 4, 5}
std::set<int, std::greater<int>> desc{5, 1, 3}; // {5, 3, 1}
// From a range — deduplication happens automatically
std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};
std::set<int> deduped(v.begin(), v.end()); // {1, 2, 3, 4, 5, 6, 9}
// std::unordered_set — C++11
std::unordered_set<std::string> us{"apple", "banana", "apple"}; // size 2
us.reserve(256); // pre-allocate bucket array before bulk insert
us.max_load_factor(0.5f); // rehash sooner; fewer collisions, more memoryInsert, emplace, and erase
std::set<int> s{1, 2, 3};
auto [it, inserted] = s.insert(2); // inserted == false; already present
s.emplace(4); // construct in-place; same O(log n)
s.insert(s.end(), 5); // hint insertion — O(1) amortized if hint correct
s.erase(3); // by value — O(log n)
s.erase(s.begin()); // by iterator — O(1) amortized
s.erase(s.lower_bound(2), s.end()); // erase a range
// C++20: free function, works on both set and unordered_set
std::erase_if(s, [](int n){ return n % 2 == 0; });Lookup and ordered queries
std::set<int> s{1, 2, 3, 4, 5};
s.contains(3); // true — C++20; prefer over count() for clarity
s.count(3); // 0 or 1; use contains() instead when you don't need the count
s.find(3); // iterator, or s.end() if absent
// These only exist on std::set (and std::map), not unordered variants:
auto lb = s.lower_bound(3); // iterator to first element >= 3
auto ub = s.upper_bound(3); // iterator to first element > 3
auto [lo, hi] = s.equal_range(3); // {lower_bound, upper_bound}
// Range extraction — O(log n + k), not O(n)
for (auto it = s.lower_bound(2); it != s.upper_bound(4); ++it)
std::print("{} ", *it); // 2 3 4 — std::print is C++23Heterogeneous lookup — avoid temporaries (C++14)
When keys are expensive to construct (e.g., std::string searched with std::string_view), a transparent comparator eliminates the temporary:
// std::less<> — no template argument — is transparent (C++14)
std::set<std::string, std::less<>> words{"alpha", "beta", "gamma"};
// find with string_view: no std::string constructed
auto it = words.find(std::string_view{"beta"}); // C++14 heterogeneous lookup
words.contains("gamma"); // also uses heterogeneous lookup — C++20
// For unordered_set, you need both a transparent hash and transparent equality:
struct StringHash {
using is_transparent = void; // opt-in marker
std::size_t operator()(std::string_view sv) const noexcept {
return std::hash<std::string_view>{}(sv);
}
std::size_t operator()(const std::string& s) const noexcept {
return std::hash<std::string>{}(s);
}
};
struct StringEq {
using is_transparent = void;
bool operator()(std::string_view a, std::string_view b) const noexcept {
return a == b;
}
};
std::unordered_set<std::string, StringHash, StringEq> fast_words{"alpha", "beta"};
fast_words.contains(std::string_view{"alpha"}); // no allocation — C++20Node handles and merge (C++17)
C++17 introduced node handles — a way to transfer tree nodes between containers without heap allocation or copying elements:
std::set<int> src{1, 2, 3};
std::set<int> dst{3, 5, 6};
// Move all nodes from src into dst; duplicates remain in src
dst.merge(src); // dst = {1, 2, 3, 5, 6}; src = {3} (3 was duplicate)
// Extract to modify a key — the only correct way to change a set element
auto node = dst.extract(1); // O(log n); removes node, no deallocation
if (!node.empty()) {
node.value() = 10;
auto [position, inserted, returned_node] = dst.insert(std::move(node));
}
// dst = {2, 3, 5, 6, 10}Custom hash for unordered_set (C++11)
struct Point { int x, y; };
struct PointHash {
std::size_t operator()(const Point& p) const noexcept {
std::size_t h1 = std::hash<int>{}(p.x);
std::size_t h2 = std::hash<int>{}(p.y);
// Shift-xor mixing avoids the symmetry collapse of plain XOR
return h1 ^ (h2 * 2654435761u + (h1 << 6) + (h1 >> 2));
}
};
std::unordered_set<Point, PointHash, [](const Point& a, const Point& b){
return a.x == b.x && a.y == b.y;
}> visited; // lambda as KeyEqual is valid — C++11multiset — ordered duplicates
#include <set>
std::multiset<int> ms{1, 2, 2, 3, 3, 3};
ms.count(3); // 3
// erase(value) removes ALL copies — a frequent source of bugs
ms.erase(2); // removes both 2s
// Remove exactly one copy:
if (auto it = ms.find(2); it != ms.end()) ms.erase(it); // C++17 if-initBest Practices
Choose unordered_set for pure membership testing when ordering is irrelevant and the key type has a quality hash. The O(1) vs O(log n) gap compounds significantly at high cardinality.
Choose set for ordered traversal or range queries. Any algorithm that needs elements in sorted order, or needs lower_bound/upper_bound, belongs with std::set.
Call reserve(n) before bulk-inserting into unordered_set. Each rehash is O(n) and invalidates all iterators. A single upfront reservation eliminates all rehashes for a known dataset size.
Use transparent comparators (std::less<>) for string-keyed sets. Searching a set<string> with a string_view using the default std::less<string> comparator allocates a temporary std::string. The C++14 heterogeneous lookup path is zero-cost.
Never use set<T*> without a custom comparator. Pointer comparison by address produces unspecified order; store unique_ptr<T> with a comparator that dereferences, or redesign to store values.
Common Pitfalls
Set iterators are always const
Modifying an element in-place would silently corrupt sorted order, so all set iterators are const. The correct pattern is extract-modify-reinsert (C++17):
std::set<std::string> s{"hello"};
// *s.begin() = "world"; // compile error
auto node = s.extract(s.begin());
node.value() = "world";
s.insert(std::move(node));multiset::erase(value) removes all copies
std::multiset<int> ms{2, 2, 2};
ms.erase(2); // removes all three — almost certainly wrong
ms.erase(ms.find(2)); // removes exactly oneunordered_set iterators are invalidated by rehash
Unlike std::set, any insert that triggers a rehash invalidates every iterator, pointer, and reference into the container. Call reserve up front, or avoid holding iterators across inserts:
std::unordered_set<int> us;
us.reserve(4);
auto it = us.insert(1).first;
us.insert({2, 3, 4, 5}); // may rehash — 'it' is potentially dangling nowXOR hash combining produces symmetric collisions
hash(x) ^ hash(y) maps {1, 2} and {2, 1} to the same bucket. For composite keys, use a non-commutative combiner (multiplicative mixing as shown above, or the boost::hash_combine pattern).
contains and heterogeneous lookup require C++20 / C++14 respectively
contains() is C++20 — count() != 0 is the portable pre-C++20 form. Heterogeneous lookup via find(string_view) on a set<string> requires both C++14 and a transparent comparator (std::less<>). Without the transparent comparator, even C++14 compilers will silently construct a temporary.
std::flat_set (C++23)
std::flat_set<K, Compare, Container> (C++23, <flat_set>) stores elements in sorted contiguous storage — a std::vector by default — and uses O(log n) binary search for lookup. The key design tradeoff: inserts are O(n) due to shifting, but finds benefit from cache-friendly sequential access.
#include <flat_set> // C++23
// Construction from a range — sorts and deduplicates on construction
std::vector<int> v{5, 3, 1, 4, 1, 2, 3};
std::flat_set<int> fs(v.begin(), v.end()); // {1, 2, 3, 4, 5} — C++23
// O(n) construction when input is already sorted — skip the sort step
std::vector<int> sorted_v{1, 2, 3, 4, 5};
std::flat_set<int> fs2(std::sorted_unique, sorted_v.begin(), sorted_v.end()); // C++23
// Same interface as std::set: insert, find, contains, lower_bound ...
fs.insert(6); // O(n) — shifts elements
fs.contains(3); // O(log n) — binary search on contiguous arrayflat_set is 3–5× faster than std::set on find-dominated workloads because binary search on a contiguous array avoids the 5–7 pointer indirections of a red-black tree traversal. The tradeoff is O(n) insert: flat_set shines in build-once, query-many scenarios.
Iterator invalidation is total on modification. Unlike std::set, where only the erased element's iterator is invalidated, any insert or erase into flat_set invalidates all iterators and references — it must shift underlying vector storage.
// Descending flat_set; custom comparator works identically to std::set
std::flat_set<int, std::greater<int>> desc_fs{5, 1, 3, 2, 4}; // {5, 4, 3, 2, 1} — C++23
// flat_set over custom container (e.g., small_vector for stack-friendly storage)
// std::flat_set<int, std::less<int>, boost::container::small_vector<int, 16>> small_fs;Set Operations with <algorithm> (Set-Theoretic)
The <algorithm> header provides four set-theoretic operations that work on any sorted ranges — not just std::set. They all require sorted inputs and produce sorted output via an output iterator.
#include <algorithm>
#include <vector>
#include <iterator>
std::vector<int> a{1, 2, 3, 4, 5};
std::vector<int> b{3, 4, 5, 6, 7};
std::vector<int> result;
// Intersection — elements in both A and B
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result)); // {3, 4, 5}
result.clear();
// Union — elements in A or B (merged, deduplicated)
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result)); // {1, 2, 3, 4, 5, 6, 7}
result.clear();
// Difference — elements in A but not B
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result)); // {1, 2}
result.clear();
// Symmetric difference — elements in exactly one of A or B
std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result)); // {1, 2, 6, 7}These algorithms operate on sorted ranges, not just std::set. A sorted std::vector is often the most efficient input — it avoids the overhead of std::set altogether for use cases where the data is built once and then queried with set operations.
// Practical example: intersection of two sorted keyword lists
std::vector<std::string> keywords_a{"algorithm", "cache", "hash", "tree"};
std::vector<std::string> keywords_b{"cache", "graph", "hash", "sort"};
std::vector<std::string> common_keywords;
// Both vectors are already sorted; std::set_intersection runs in O(n + m)
std::set_intersection(keywords_a.begin(), keywords_a.end(),
keywords_b.begin(), keywords_b.end(),
std::back_inserter(common_keywords));
// common_keywords == {"cache", "hash"}std::set with Move-Only Types
std::set can hold move-only types such as std::unique_ptr<T>, but doing so requires a custom comparator that dereferences pointers rather than comparing addresses.
#include <set>
#include <memory>
struct DerefLess {
// Transparent: also handles mixed comparisons (raw ptr vs unique_ptr)
using is_transparent = void;
template<class A, class B>
bool operator()(const A& a, const B& b) const { return *a < *b; }
};
// C++11 — set of unique_ptrs, ordered by dereferenced value
std::set<std::unique_ptr<int>, DerefLess> s;
s.emplace(std::make_unique<int>(42)); // constructs in-place, no copy needed
s.emplace(std::make_unique<int>(17));
s.emplace(std::make_unique<int>(99));
// Iteration order: 17, 42, 99 (by value, not by pointer address)Set elements are logically const T, so iterating over a set<unique_ptr<int>> yields const unique_ptr<int>& — you can read *it but cannot move the pointer out through the iterator. To move a unique_ptr out of the set, use extract:
// Extract a node to retrieve (move) the unique_ptr safely — C++17
auto it = s.find(std::make_unique<int>(42)); // heterogeneous find via DerefLess
if (it != s.end()) {
auto node = s.extract(it); // removes node, no deallocation
std::unique_ptr<int> ptr = std::move(node.value()); // move unique_ptr out safely
// Use ptr here; node is now empty, element is gone from the set
}Lambda Comparators in std::set
Every lambda expression has a unique, unnamed type, so lambdas cannot serve as default template arguments. The pattern is to capture the lambda and pass its type via decltype.
struct Foo { int id; std::string name; };
// C++11: pass lambda instance to constructor
auto cmp = [](const Foo& a, const Foo& b) { return a.id < b.id; };
std::set<Foo, decltype(cmp)> s(cmp); // C++11 — lambda instance required at construction
s.insert({1, "alpha"});
s.insert({2, "beta"});C++20 stateless (non-capturing) lambdas are default-constructible, so the set can be default-constructed without an explicit lambda instance:
// C++20: no need to pass the lambda to the constructor
std::set<Foo, decltype([](const Foo& a, const Foo& b){ return a.id < b.id; })> s; // C++20
s.insert({3, "gamma"});Multi-key ordering keeps elements stable across a secondary attribute when the primary key ties:
// Sort by last name, then first name on tie
struct Person { std::string first, last; };
auto person_cmp = [](const Person& a, const Person& b) {
return a.last != b.last ? a.last < b.last : a.first < b.first;
};
std::set<Person, decltype(person_cmp)> people(person_cmp); // C++11A capturing lambda's set needs the lambda instance at construction; the type alone is not enough. If the lambda captures state (e.g., a locale or a threshold value), you must store the lambda and pass it to the set constructor — default construction of such a set is ill-formed.
Concurrent Access Patterns
std::set and std::unordered_set are not thread-safe for concurrent reads mixed with any write. Multiple concurrent readers are safe only if no writer is active simultaneously.
Pattern 1 — std::shared_mutex (C++17): multiple readers, exclusive writer.
#include <shared_mutex>
#include <set>
std::set<int> data;
std::shared_mutex mtx;
// Any number of threads may read concurrently
void reader(int key) {
std::shared_lock lock(mtx); // C++17 — shared (read) lock
bool found = data.contains(key);
}
// Only one thread may write at a time; blocks all readers during write
void writer(int key) {
std::unique_lock lock(mtx); // exclusive (write) lock
data.insert(key);
}Pattern 2 — sharded (striped) locking for unordered_set. Divide the key space into N buckets, each with its own mutex. Contention is reduced by a factor of N:
// C++17 — sharded concurrent set (N=16 shards)
struct ShardedSet {
static constexpr size_t N = 16;
std::array<std::unordered_set<int>, N> shards;
std::array<std::mutex, N> locks;
size_t shard(int key) const { return std::hash<int>{}(key) % N; }
void insert(int key) {
auto idx = shard(key);
std::lock_guard lock(locks[idx]); // C++17 CTAD
shards[idx].insert(key);
}
bool contains(int key) {
auto idx = shard(key);
std::lock_guard lock(locks[idx]);
return shards[idx].contains(key);
}
};Pattern 3 — lock-free / library concurrent sets. For high-throughput scenarios, consider tbb::concurrent_unordered_set (Intel TBB) which allows concurrent inserts and lookups without user-visible locking, or absl::flat_hash_set with an external absl::Mutex for lower overhead than std::mutex.
contains()/find() may run concurrently with other reads, but NOT with insert()/erase(). Even an insert that does not trigger a rehash modifies internal structure (e.g., linked list pointers in unordered_set bucket chains) and constitutes a data race if unsynchronized.
Benchmarking std::set vs Alternatives
Concrete lookup estimates for 100K int elements, random access pattern, warm L3 cache (order-of-magnitude figures; actual numbers are platform-dependent):
| Container | Lookup cost | Notes |
|---|---|---|
std::set | ~200 ns | Red-black tree; 5–7 pointer indirections, poor locality |
std::unordered_set | ~40 ns | Hash table; 1–2 memory accesses per hit |
std::flat_set (C++23) | ~25 ns | Binary search on contiguous array; cache-friendly |
Sorted std::vector + lower_bound | ~20 ns | Same algorithm as flat_set, no deduplication overhead |
absl::flat_hash_set | ~15 ns | Open addressing, inline storage, excellent branch prediction |
The 10× gap between std::set and std::unordered_set rarely matters for small sets. Below roughly 100 elements, the entire tree fits in a few cache lines and the pointer-chasing cost is negligible. For non-hot paths or allocation-dominated workloads, pick whichever container is clearest to read.
The gap matters decisively on lookup-dominated hot paths. If your profiler shows a std::set lookup in a hot loop over millions of integers, migrating to std::unordered_set, std::flat_set, or a sorted std::vector can yield a 5–10× speedup with no algorithmic change.
// Build-once, query-many: sorted vector is the fastest read-only set
std::vector<int> lookup_table{/* ... millions of ints ... */};
std::sort(lookup_table.begin(), lookup_table.end());
lookup_table.erase(std::unique(lookup_table.begin(), lookup_table.end()),
lookup_table.end()); // deduplicate in-place
// O(log n) lookup — same complexity as std::set, far better cache behavior
bool found = std::binary_search(lookup_table.begin(), lookup_table.end(), key);
// Or use lower_bound for the position:
auto it = std::lower_bound(lookup_table.begin(), lookup_table.end(), key);See Also
std::map/std::unordered_map— same tree/hash backing, stores key-value pairsstd::multiset/std::unordered_multiset— permit duplicate keysstd::flat_set— sortedvector-backed set with O(log n) lookup and superior cache locality (C++23)std::ranges::contains— linear O(n) membership test for unsorted ranges (C++23)