C++ unordered_set

What is unordered_set?

std::unordered_set stores unique elements with no guaranteed order, using a hash table internally. It offers average O(1) insertion, deletion, and lookup, faster than set when sorted order is not needed.

Example: What is unordered_set?

#include <iostream>
#include <unordered_set>

int main() {
	std::unordered_set<int> s = {3, 1, 2}; // hash table, no guaranteed order
	std::cout << s.size() << std::endl;
	return 0;
}

Inserting and Erasing

insert() and erase() behave like std::set but operate on hash buckets instead of a tree, so there is no relationship between insertion order and iteration order.

This trade-off gives up ordering guarantees in exchange for average constant-time insertion and lookup.

Example: Inserting and Erasing

#include <iostream>
#include <unordered_set>

int main() {
	std::unordered_set<int> s;
	s.insert(5);
	s.erase(5); // operates on hash buckets, not a tree
	std::cout << s.size() << std::endl;
	return 0;
}

Hashing & Performance

Like unordered_map, unordered_set hashes elements into buckets. Average-case operations are O(1), but a poor hash or many collisions can degrade to O(n) worst case.

Choosing or customizing a good hash function for your key type is essential to actually achieving that average O(1) performance.

Example: Hashing & Performance

#include <iostream>
#include <unordered_set>

int main() {
	std::unordered_set<int> s;
	s.insert(42); // hashed into a bucket -- average O(1)
	std::cout << (s.count(42) > 0) << std::endl;
	return 0;
}

Iterating (Unordered)

Iterating an unordered_set visits elements in an unspecified order determined by the hash table layout. Do not rely on it matching insertion order.

If you need elements in a predictable order, std::set (or manually sorting a copy) is the better choice instead.

Example: Iterating (Unordered)

#include <iostream>
#include <unordered_set>

int main() {
	std::unordered_set<int> s = {3, 1, 2};
	for (int n : s) { // order determined by hash layout, not insertion or value
		std::cout << n << " ";
	}
	std::cout << std::endl;
	return 0;
}

Searching an unordered_set

find() and count() locate elements in average O(1) time via hashing, which is why unordered_set is a common choice for fast membership tests on large datasets.

This makes unordered_set the natural choice whenever the goal is simply 'does this value exist here', without caring about order.

Example: Searching an unordered_set

#include <iostream>
#include <unordered_set>

int main() {
	std::unordered_set<int> s = {1, 2, 3};
	if (s.find(2) != s.end()) { // average O(1) via hashing
		std::cout << "Found" << std::endl;
	}
	return 0;
}