set vs unordered_set in C++: Performance, Custom Comparators and Hashes, and Set Operations

set vs unordered_set

Feature	set	unordered_set
Sorting	O (auto-sorted)	X
Speed	O(log n)	O(1) average, O(n) worst
Duplicates	Not allowed	Not allowed
Traversal	Sorted order	Unspecified (bucket order)
Key requirement	Strict weak ordering (<)	Hash + equality

Both containers answer the same question (“is this value in the collection?”) and reject duplicates, but they are built on different data structures, and nearly every practical difference follows from that. std::set keeps its elements in a balanced binary search tree, so the elements are always ordered and you can ask ordered questions: the smallest element, the first element not less than x, everything between a and b. std::unordered_set puts each element in a bucket chosen by its hash, which makes lookups by exact value fast on average but gives no meaningful order at all; iteration order can even change after more elements are inserted.

set vs unordered_set Performance Comparison

From time complexity (average/amortized) perspective, set is based on balanced binary search tree (typically red-black), so insert/delete/search is O(log n). unordered_set is a hash table, so average O(1), but with many hash collisions can approach worst case O(n).

Practical differences are:

• Small n·order needed: If element count is hundreds~thousands and need sorted traversal or range search like lower_bound, set is simpler.
• Large n·key lookup only: For millions+ where you only need fast “exists/not exists” check and order doesn’t matter, unordered_set is often advantageous.
• Memory: Hash table has additional overhead from buckets/load factor, tree has pointer overhead per node. Varies by n and key size, so measurement is safe.
• Cache locality: Neither uses contiguous memory, both have frequent skip access causing cache misses. Hard to say “unordered is always faster” based on traversal alone.

Selection Summary: If need order/range search use set, if keys are hash-friendly (integers, well-distributed strings) and mostly lookups, consider unordered_set first.

Big-O hides constant factors that matter in practice. A set lookup in a million elements visits about 20 tree nodes, each a separate heap allocation and likely a cache miss. An unordered_set lookup computes a hash, jumps to a bucket, and follows a short chain, usually one or two cache misses. That is why unordered_set typically wins for large lookup-heavy workloads. For long string keys, though, hashing reads the entire string, while a tree comparison can stop at the first differing character, which narrows the gap. For small collections (dozens of elements), a sorted std::vector with std::binary_search, or even a linear scan, often beats both containers, because contiguous memory is so much friendlier to the cache than node-based structures.

The O(n) worst case of unordered_set is not only theoretical. In libstdc++ and libc++, std::hash<int> is the identity function, so keys that are all multiples of the bucket count land in the same bucket. If keys come from untrusted input (request parameters, uploaded data), an attacker who knows this can deliberately produce collisions and make each insertion linear, a hash-flooding attack. set has no such weakness: its O(log n) bound holds for every input.

multiset and unordered_multiset

set / unordered_set store only one of each key. If need same value multiple times, use multiset, unordered_multiset.

Feature	multiset	unordered_multiset
Order	Maintains sort; equal values keep insertion order (C++11 inserts at the end of the equal range)	No order
Lookup	count, equal_range for same key range	count, equal_range
Delete	erase(key) removes all of that key, use iterator to remove one	Same

#include <set>
#include <unordered_set>
#include <iostream>

int main() {
    std::multiset<int> ms{1, 1, 2, 2, 2};
    std::cout << ms.count(2) << '\n';  // 3

    auto [first, last] = ms.equal_range(2);
    for (auto it = first; it != last; ++it) { /* ... */ }

    std::unordered_multiset<std::string> ums;
    ums.insert("a"); ums.insert("a");
    std::cout << ums.count("a") << '\n';  // 2
}

When only top k needed, multiset maintains sorted state making it easy to handle max/min at ends. If only counting frequency and order not needed, unordered_multiset or unordered_map<T, int> is often better.

Custom Comparator and Hash Function

set: Compare and operator<

set sorting criterion must satisfy strict weak ordering. Can use operator< or std::less for custom types.

struct Person {
    std::string name;
    int id;
};

struct ById {
    bool operator()(const Person& a, const Person& b) const {
        return a.id < b.id;
    }
};

std::set<Person, ById> by_id_set;

A consequence that surprises people: set never uses operator==. Two elements are considered the same when neither is less than the other (!comp(a, b) && !comp(b, a)). With ById, two Person objects with the same id but different names are “equal”, so inserting the second one does nothing and insert returns false in its .second. That is exactly what you want for a set keyed by ID, and exactly what causes silent data loss when the comparator compares fewer fields than you intended.

Strict weak ordering means, in practice: comp(a, a) must be false, and the ordering must be consistent (if a < b and b < c, then a < c). Writing <= instead of < breaks the first rule. The results are not a compile error but undefined behavior: duplicates get inserted, find misses elements that are present, and with debug iterators enabled (MSVC debug builds, _GLIBCXX_DEBUG) you may get an assertion like “invalid comparator”. Comparing floating-point fields that can be NaN breaks the ordering the same way.

unordered_set: Hash and KeyEqual

In unordered_set<Key, Hash, KeyEqual>, same key must always produce same hash, and KeyEqual determines actual equality on hash collision. Custom types typically provide both.

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const noexcept {
        // Simple combination example (consider boost::hash_combine for projects)
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    }
};

std::unordered_set<Point, PointHash> pts;

Caution: When putting strings in unordered_set, bad custom hash causes severe performance drop. If key is std::string, typically use default hash.

The x ^ (y << 1) combination above is a common first attempt, and it’s weak. Since std::hash<int> is the identity in the major standard libraries, the result is just x ^ 2y, so many different points share a hash: (0, 1), (2, 0) and (6, 2) all hash to 2. For grid coordinates that is a lot of collisions, and the symptom is an unordered_set that is inexplicably slower than set. A better combiner mixes the bits, for example the boost::hash_combine formula seed ^= h + 0x9e3779b9 + (seed << 6) + (seed >> 2);, or, for two 32-bit ints, packing them into one 64-bit value and hashing that. The hard requirement is consistency with equality: if a == b, then hash(a) == hash(b). Hashing a field that operator== ignores breaks lookups silently.

Practice: Duplicate Removal·Intersection·Union Summary

• Duplicate removal only with original order preservation: Putting in set then moving to vector changes order, and so does sort then unique. To keep the first occurrence of each value in its original position, walk the input once with an unordered_set of values already seen and append a value to the output only when seen.insert(v).second is true. If order doesn’t matter, sort + unique + erase on the vector itself is usually the fastest option since it needs no extra node allocations.
• Intersection·union·difference: Above set_intersection / set_union / set_difference patterns require both ranges sorted. Using set automatically satisfies sorted order via iterators.
• unordered_set operations: If library doesn’t provide one-shot operations, collect one side into vector and sort, or iterate smaller side and check inclusion in other with count/find (choose better algorithm by size).

Iterator Invalidation

set / multiset

• insert / emplace: Existing element iterators and references not invalidated.
• erase(it): Only that iterator invalid. Other iterators maintained.
• erase(key) / clear: Iterators to deleted elements invalid.

unordered_set / unordered_multiset

• Rehash changes bucket structure, all iterators may be invalid. insert exceeding load factor can trigger rehash, so indiscriminate insertion during iteration is dangerous. References and pointers to elements stay valid across a rehash, though, because the nodes themselves don’t move; only their bucket links change.
• reserve(n) (or appropriate bucket count reservation) reduces rehash frequency, making iterator invalidation less frequent. After reserve(n), inserting up to n elements in total is guaranteed not to rehash.
• erase: The standard guarantees that only iterators and references to the erased elements are invalidated; all others remain valid. The erased iterator itself is dead, though, so ++it after erase(it) is undefined behavior; use the iterator that erase returns.

Even when no rehash happens, inserting while iterating an unordered_set has a second problem: the new element may land in a bucket the loop has already passed, or one it hasn’t reached yet, so whether the loop visits it is unpredictable. Collect insertions in a separate container and apply them after the loop.

for (auto it = s.begin(); it != s.end(); ) {
    if (condition) it = s.erase(it);  // erase returns next iterator
    else ++it;
}

set Basic Usage

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> s;
    
    // Insert
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(1);  // Duplicate ignored
    
    // Traverse (auto-sorted: 1, 2, 3)
    for (int x : s) {
        cout << x << " ";
    }
    
    // Search
    if (s.find(2) != s.end()) {
        cout << "\n2 exists" << endl;
    }
    
    // Delete
    s.erase(2);
    
    // Size
    cout << "Size: " << s.size() << endl;
    
    return 0;
}

unordered_set Basic Usage

#include <unordered_set>
#include <iostream>
using namespace std;

int main() {
    unordered_set<string> words;
    
    words.insert("apple");
    words.insert("banana");
    words.insert("apple");  // Duplicate ignored
    
    // Check existence (fast)
    if (words.count("apple") > 0) {
        cout << "apple exists" << endl;
    }
    
    // Traverse (order not guaranteed)
    for (const string& word : words) {
        cout << word << " ";
    }
    
    return 0;
}

Practical Examples

Example 1: Remove Duplicates from Array

#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector<int> removeDuplicates(const vector<int>& arr) {
    set<int> s(arr.begin(), arr.end());
    return vector<int>(s.begin(), s.end());
}

int main() {
    vector<int> arr = {5, 2, 8, 2, 9, 5, 1, 8};
    
    cout << "Original: ";
    for (int x : arr) cout << x << " ";
    
    vector<int> unique = removeDuplicates(arr);
    
    cout << "\nDuplicate removed (sorted): ";
    for (int x : unique) cout << x << " ";
    
    return 0;
}

Explanation: Most basic pattern utilizing set’s auto-sorting and duplicate removal. It is concise but allocates one tree node per unique element. For large vectors, std::sort followed by std::unique and erase produces the same sorted, deduplicated result in place and is typically several times faster, because it works on contiguous memory.

Example 2: Intersection/Union of Two Arrays

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    set<int> a = {1, 2, 3, 4, 5};
    set<int> b = {3, 4, 5, 6, 7};
    
    // Intersection
    set<int> intersection;
    set_intersection(a.begin(), a.end(),
                     b.begin(), b.end(),
                     inserter(intersection, intersection.begin()));
    
    cout << "Intersection: ";
    for (int x : intersection) cout << x << " ";  // 3 4 5
    
    // Union
    set<int> union_set;
    set_union(a.begin(), a.end(),
              b.begin(), b.end(),
              inserter(union_set, union_set.begin()));
    
    cout << "\nUnion: ";
    for (int x : union_set) cout << x << " ";  // 1 2 3 4 5 6 7
    
    // Difference
    set<int> difference;
    set_difference(a.begin(), a.end(),
                   b.begin(), b.end(),
                   inserter(difference, difference.begin()));
    
    cout << "\nDifference (A-B): ";
    for (int x : difference) cout << x << " ";  // 1 2
    
    return 0;
}

Explanation: Can implement mathematical set operations directly. Frequently used in algorithm problems.

The set_* algorithms work on any two sorted ranges in a single linear merge pass, which is why they pair naturally with std::set iterators. The output iterator matters: std::inserter(result, result.begin()) calls insert with a hint for each element, and because the output arrives in sorted order, each hinted insert is amortized constant time. If the output is a vector, use std::back_inserter instead. These algorithms do not work on unordered_set: its iteration order isn’t sorted, and passing unsorted ranges produces wrong results without any error. For two hash sets, iterate the smaller one and find/contains in the larger.

Example 3: Visit Check (Graph Traversal)

#include <iostream>
#include <unordered_set>
#include <queue>
#include <vector>
using namespace std;

void bfs(int start, vector<vector<int>>& graph) {
    unordered_set<int> visited;
    queue<int> q;
    
    q.push(start);
    visited.insert(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        cout << node << " ";
        
        for (int neighbor : graph[node]) {
            if (visited.count(neighbor) == 0) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // Graph: 0-1, 0-2, 1-3, 2-3
    vector<vector<int>> graph = {
        {1, 2},    // Node 0's neighbors
        {0, 3},    // Node 1's neighbors
        {0, 3},    // Node 2's neighbors
        {1, 2}     // Node 3's neighbors
    };
    
    cout << "BFS traversal: ";
    bfs(0, graph);
    
    return 0;
}

Explanation: Use unordered_set to check visited status at O(1) speed. Essential pattern for graph algorithms.

Two refinements are worth knowing. First, visited.insert(neighbor).second tells you whether the value was newly inserted, so the count followed by insert can be one hash lookup instead of two. Second, when nodes are numbered densely from 0 to n−1, as here, a std::vector<bool> or std::vector<char> of size n is a better “visited” set than any hash set: it is a direct index with no hashing and no allocation per element. The hash set earns its place when node IDs are sparse or not integers, such as coordinates or strings.

Common Problems

Problem 1: Cannot Modify set Elements

Symptom: Compile error when trying to modify set element directly

Cause: set elements are const to maintain sorting. The tree’s position of each element depends on its value; if you could change the value in place, the element would sit in the wrong spot and every later search would be wrong. So set::iterator behaves like a const iterator, and modification means remove-then-insert (or extract, shown later, which avoids the reallocation).

Solution:

// ❌ Wrong code
set<int> s = {1, 2, 3};
auto it = s.find(2);
*it = 5;  // Compile error! const int&

// ✅ Correct code (delete then reinsert)
set<int> s = {1, 2, 3};
auto it = s.find(2);
if (it != s.end()) {
    s.erase(it);
    s.insert(5);
}

// ✅ For structs (use mutable)
struct Item {
    int id;
    mutable int count;  // mutable can be modified
    
    bool operator<(const Item& other) const {
        return id < other.id;
    }
};

set<Item> items;
auto it = items.find(Item{1, 0});
if (it != items.end()) {
    it->count++;  // OK (mutable)
}

The mutable trick is safe only because count does not participate in operator<. If someone later adds count to the comparison, the code still compiles, and the set is silently corrupted the first time count changes. When a struct mixes key fields and payload, std::map<Key, Payload> usually expresses the intent more clearly than a set with mutable members.

Problem 2: Custom Comparison Function

Symptom: Compile error when inserting custom type into set

Cause: Needs operator< or comparison function

Solution:

// ❌ Compile error
struct Point {
    int x, y;
};

set<Point> points;  // Error! No operator<

// ✅ Method 1: Define operator<
struct Point {
    int x, y;
    
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

set<Point> points;  // OK

// ✅ Method 2: Comparison function object
struct PointCompare {
    bool operator()(const Point& a, const Point& b) const {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    }
};

set<Point, PointCompare> points;  // OK

// ✅ Method 3: Lambda (C++11)
auto cmp = [](const Point& a, const Point& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
};

set<Point, decltype(cmp)> points(cmp);  // OK

The typical compiler error for the first case is long, but it includes a line like no match for 'operator<' (operand types are 'const Point' and 'const Point'), reported from inside std::less. The three methods differ in where the ordering lives: operator< makes it the ordering of Point everywhere, while a comparator type lets you have several orderings for different containers. The lambda form needs the lambda object passed to the constructor before C++20; since C++20, captureless lambdas are default-constructible, so set<Point, decltype(cmp)> points; also works. In C++20 you can also write auto operator<=>(const Point&) const = default; to get lexicographic comparison of all members.

Problem 3: Confusion with multiset

Symptom: Want to allow duplicates but set doesn’t

Cause: set doesn’t allow duplicates, multiset does

Solution:

// ❌ set doesn't allow duplicates
set<int> s;
s.insert(1);
s.insert(1);
s.insert(1);
cout << s.size();  // 1 (duplicates ignored)

// ✅ Use multiset
#include <set>
multiset<int> ms;
ms.insert(1);
ms.insert(1);
ms.insert(1);
cout << ms.size();  // 3 (duplicates allowed)

// Count specific value
cout << ms.count(1);  // 3

// Delete all of specific value
ms.erase(1);  // All 1s deleted

// Delete only one
auto it = ms.find(1);
if (it != ms.end()) {
    ms.erase(it);  // Delete only one
}

ms.erase(1) removing every 1 is the multiset bug I’ve seen most often: code that means “remove one occurrence” (for example, removing one price from a multiset of open orders) passes the value instead of an iterator and wipes out all matching entries. Using find and erasing the iterator is the fix, as shown.

---

Advanced: reserve·rehash·Load Distribution

unordered_set triggers rehash when exceeding load factor, at which point all iterators may be invalid. If approximate element count known before insertion:

std::unordered_set<int> s;
s.reserve(1'000'000); // Reduce rehash frequency, stabilize benchmark

set doesn’t have reserve, but reducing unnecessary copies/temporary objects helps perceived performance.

The default maximum load factor is 1.0, meaning the table grows once there are more elements than buckets. Each rehash allocates a new bucket array and relinks every node, so building a large set by repeated insert without reserve performs a series of increasingly expensive rehashes. Lowering max_load_factor shortens chains (faster lookups) at the cost of more memory; raising it does the opposite.

---

Advanced: Heterogeneous Lookup

When the key is std::string, find("literal") or find(some_string_view) normally constructs a temporary std::string first, which can allocate. Heterogeneous lookup avoids that. For std::set it has been available since C++14: declare the set with a transparent comparator, std::set<std::string, std::less<>>, and find accepts anything comparable with std::string. For unordered containers it arrived in C++20 and needs both a transparent hash and a transparent equality:

struct StringHash {
    using is_transparent = void;  // opts in to heterogeneous lookup
    std::size_t operator()(std::string_view sv) const noexcept {
        return std::hash<std::string_view>{}(sv);
    }
};

std::unordered_set<std::string, StringHash, std::equal_to<>> names;
names.insert("alice");
bool found = names.contains(std::string_view{"alice"});  // no temporary std::string

This works because the standard requires std::hash<std::string> and std::hash<std::string_view> to produce the same value for the same characters. Library support came later than the language standard (GCC 11 and recent Clang/libc++ and MSVC have it). If find with a string_view fails to compile, check that both is_transparent markers are present; with only one, the non-template overload is chosen and the conversion fails.

---

Advanced: node_type / extract (C++17)

set/unordered_set can extract nodes and move to other containers, used for patterns that update keys without reallocation.

std::set<int> a{1, 2, 3};
auto nh = a.extract(2);
if (!nh.empty()) {
    nh.value() = 5;
    a.insert(std::move(nh));
}

extract unlinks the node from the tree without freeing it and hands it to you as a node handle, the only way to get non-const access to a set element’s value. After changing it, insert(std::move(nh)) links the same node back at its new position, with no allocation or copy of the value. The same mechanism moves elements between two sets of the same type, and merge (also C++17) moves all non-duplicate nodes from one set into another. unordered_set supports the same API; reinserting may trigger a rehash like any insert.

---

Advanced: Benchmark Method (Practically)

1. Fix: Compiler optimization (-O2/-O3), CPU fixed frequency (if possible), same seed.
2. Warmup: Start timer after cache/hash table warmup.
3. Metrics: Not just average but p95/p99, especially for unordered_* include worst-case hash input as separate case.

#include <chrono>

template<typename F>
auto bench(F&& f, int reps) {
    using clock = std::chrono::steady_clock;
    auto t0 = clock::now();
    for (int i = 0; i < reps; ++i) f();
    return clock::now() - t0;
}

---

Advanced: Debugging Guide

Symptom	Check
Slow in unordered_set	Hash quality, key collision, load factor, wrong operator==
Abnormal behavior during iteration	Rehash invalidates iterators — use reserve or copy-then-iterate
set sorting is strange	Check if comparison operation satisfies strict weak ordering

---

Advanced: Common Mistake Patterns (Additional)

• Using vector as key in unordered_set with only default hash → Hash inefficient or definition missing. Use immutable key as identifier or define custom hash.
• Wrong iterator increment during erase while iterating → Use it = container.erase(it) pattern.
• Mixing readers and a writer across threads → Concurrent calls to const member functions (find, count, iteration) from many threads are safe as long as no thread modifies the container. As soon as one thread inserts or erases, every access needs synchronization, for example a std::shared_mutex with shared locks for readers, or publishing immutable snapshots. An occasional insert from a “read mostly” code path is the usual way this rule gets broken.

---

Related Posts

Posts connected to this topic.

• std::string Pitfalls
• std::set_union, set_intersection and set_difference on Sorted Ranges: Duplicates, Comparators and Silent Wrong Output
• std::vector in Practice

---

Related Articles

• std::string Pitfalls
• C++ if and switch Pitfalls
• C++ Functions

---