unorderedset

Unordered_set is a container in the C++ standard library that stores unique elements using a hash table. It provides average constant-time complexity for insert, find, and erase operations, assuming good hash distribution. Unlike a sorted container, such as std::set, unordered_set does not maintain elements in any particular order; iteration order is unspecified and can vary between implementations and runs.

Elements stored in an unordered_set must be hashable and comparable for equality. By default, the standard library supplies a hash function std::hash for many built-in types, and a default equality predicate std::equal_to. The container stores only keys without any mapped value. Users can supply a custom hasher and a custom key equality predicate at construction to tailor behavior for nonstandard types.

Common operations include insert, emplace, erase, find, and count. Insertion adds a new element if it is not already present and returns a pair consisting of an iterator to the element and a boolean indicating whether the insertion took place. Erase removes elements by key or by iterator. Find returns an iterator to the element or end(). Count returns 0 or 1, indicating membership. Additional member functions expose the internal structure, such as bucket_count, load_factor, max_load_factor, rehash, and reserve, which helps control performance characteristics.

Performance and memory considerations: average-case time for insert, find, and erase is O(1). Worst-case time can degrade to O(n) in the presence of many hash collisions. The container uses buckets and node storage, so memory usage includes space for the bucket array and the elements. Iterators to elements are valid unless the element they refer to is erased or the container rehashes; rehashing generally invalidates all iterators and references.