std::set/std::unordered_set
Explanation
Like map/unordered_map but stores only keys.
See std::set and std::unordered_set.
Time complexity:
| Operation | std::set | std::unordered_set |
|---|---|---|
find(), count(), contains() | O(log n) | O(1) avg, O(n) worst |
insert()/emplace() | O(log n) | O(1) avg, O(n) worst |
erase() | O(log n) | O(1) avg, O(n) worst |
Use case
- Deduplication.
Code
#include <print>
#include <set>
#include <unordered_set>
int main() {
std::set<uint64_t> visitedAddrs;
visitedAddrs.insert(0x1000);
visitedAddrs.insert(0x1100);
visitedAddrs.insert(0x1000);
std::println("Visited {} unique addresses.", visitedAddrs.size());
return 0;
}
Output
$ ./src/data-structures/build/std-set-std-unordered_set
Visited 2 unique addresses.