C++ Reference ยท Containers
C++ std::unordered_set class
Reference for std::unordered_set: average O(1) membership tests, unique elements, custom hash and equality, buckets, reserve and iterator invalidation.
std::unordered_set<T> is a hash table of unique elements. Insertion, membership tests and removal take O(1) on average. There is no ordering, so iteration visits the elements in an unspecified sequence. It is the container to reach for when all you need to know is "have I seen this value before?".
It shares its design and tuning interface with std::unordered_map: reserve, rehash, bucket_count, load_factor, custom Hash and KeyEqual. The difference is that elements are the keys themselves and are const.
#include <unordered_set> std::unordered_set<int> seen; bool isNew = seen.insert(42).second; // true the first time
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<Key>> class unordered_set; std::pair<iterator, bool> insert(const Key& k); size_type erase(const Key& k); iterator find(const Key& k); bool contains(const Key& k) const; // contains: C++20 void reserve(size_type n); void rehash(size_type buckets);
| Name | Description |
|---|---|
Hash |
Maps an element to a std::size_t. Equal elements must hash equally. |
KeyEqual |
Decides if two elements are the same. |
k |
The element to insert, find or erase. |
n |
How many elements to make room for. |
Returns: insert returns an iterator and a bool (true if the element was new); erase(key) returns the number of removed elements (0 or 1); find returns end() if absent.
Errors / undefined behavior: dereferencing end() is undefined. Inconsistent hash/equality functions give undefined behavior.
Usage notes
- Never depend on iteration order. It is unspecified and changes with growth. Sort a copy if you must print.
- Complexity: average O(1), worst case O(n). A bad hash (for example, always returning the same value) turns it into a linked list.
- Rehash invalidates iterators (not references or pointers).
reserve(n)before bulk inserts keeps the table from rehashing repeatedly. - Custom types need
operator==(or aKeyEqual) and aHash; see theunordered_mapexample. - No
lower_bound, no ordered traversal, and no set algorithms (std::set_unionneeds sorted ranges). Usestd::setfor those. - Memory: one node per element plus buckets, so it is heavier than a sorted vector. For small sets (a handful of values), a plain
std::vectorwith a linear scan is often faster. - Duplicates?
std::unordered_multisetkeeps equal elements. - Elements are const. To change one, erase it and insert the new value, or use
extract(node handles).