Skip to content
Tutorials Center
My learning

Topics

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.

C++
#include <unordered_set>
std::unordered_set<int> seen;
bool isNew = seen.insert(42).second;   // true the first time

Try it

C++ Membership and duplicate detection

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.

C++ Strings and the two-sum trick

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

C++
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 a KeyEqual) and a Hash; see the unordered_map example.
  • No lower_bound, no ordered traversal, and no set algorithms (std::set_union needs sorted ranges). Use std::set for 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::vector with a linear scan is often faster.
  • Duplicates? std::unordered_multiset keeps equal elements.
  • Elements are const. To change one, erase it and insert the new value, or use extract (node handles).