这篇文章整理了std::set.
Internal Implementation
| Container | Underlying Structure | Ordering |
|---|---|---|
std::set |
Balanced binary search tree (usually Red-Black Tree) | Elements are sorted by key (ascending by default, or custom comparator) |
std::unordered_set |
Hash table | Elements are unordered (bucketed by hash value) |
Performance Comparison
| Operation | std::set |
std::unordered_set |
|---|---|---|
| Insert / Erase / Find | O(log n) | Average: O(1), Worst case: O(n) |
| Traversal | Sorted order | Arbitrary order |
| Memory overhead | Lower (tree nodes only) | Higher (hash buckets + nodes) |
When to Use Which
| Use Case | Recommended Container |
|---|---|
| You need sorted traversal | std::set |
| You need fast lookup/insertion, and ordering doesn’t matter | std::unordered_set |
| You need custom ordering rule | std::set with custom comparator |
| You have very large datasets and performance is key | std::unordered_set (but tune load_factor() and reserve()) |
summary
| Aspect | std::set |
std::unordered_set |
|---|---|---|
| Order | Sorted | Unordered |
| Underlying structure | Red-Black Tree | Hash Table |
| Average lookup time | O(log n) | O(1) |
| Iterator validity | Stable except erased element | Stable except rehash |
| Custom comparator | Yes | Via hash + equality |
| Allows duplicates | No (std::multiset does) |
No (std::unordered_multiset does) |