std::unordered_set
A hash-based dynamic container that stores unique elements and allows for fast average-time look-up, addition, and deletion operations. Unlike std::set, it does not sort the elements and generally has higher memory overhead.
Characteristics
- Hash-Based: Utilizes a hash table for its underlying implementation.
- Unique Elements: Only unique elements are stored, similar to
std::set. - Dynamic Size: The container can grow or shrink as needed.
- Average Constant-Time Operations: Average time complexity for insertions, deletions, and lookups is
O(1). - Higher Memory Overhead: Generally requires more memory than tree-based containers like
std::set. - Unsorted: The elements in an
std::unordered_setare not sorted. - Custom Hash Function: Allows specifying custom hash functions for complex data types.
Basic usage
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> numbers;
// Insert elements
numbers.insert(5);
numbers.insert(3);
numbers.insert(8);
// Print elements (order not guaranteed)
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
// Output: 5 3 8
}
When to Use
- When you require fast average-time complexity for insertions, deletions, and lookups.
- When the ordering of elements is not important.
Limitations
- No sorted order of elements.
- Higher memory overhead than
std::set. - All elements must be hashable or you must provide a custom hash function.
Common Functions
Element Management
insert(value): Inserts a unique value.emplace(args): Constructs and inserts a unique value in-place.erase(value): Removes a specific value.clear(): Clears all elements.
Element Lookup
find(value): Returns an iterator to the found element, orend()if not found.count(value): Returns 1 if the element exists, otherwise 0 (since duplicates aren't allowed).
Set Properties
size(): Returns the number of elements in the set.empty(): Checks if the set is empty.max_size(): Returns the maximum number of elements the set can hold.
Iteration
begin(),end(): Provide iterators to traverse the set.