map & set — red-black tree, O(log n) ops
Scenario
You need to keep track of a live leaderboard and constantly query the current lowest score while new players are simultaneously joining. If you use a vector, you have to re-sort it (O(N log N)) on every single insert, which completely kills your performance.
Is there a container that keeps everything sorted for you automatically?
Mental model
`std::map` is a self-organizing filing cabinet. Every time you insert a folder, it automatically places it exactly where it belongs alphabetically. It takes a little longer to file something (O(log N)), but it's always perfectly sorted.
Unlike Java or Python where the default map/dictionary is a Hash Table, C++'s `std::map` and `std::set` are implemented as Self-Balancing Binary Search Trees (specifically, Red-Black Trees). They do not use hashing. They guarantee that elements are always sorted by key, making insertions, deletions, and lookups O(log N).
Explanation
**The internal structure:**
When you insert into a `std::set` (just keys) or `std::map` (key-value pairs), the container navigates down a binary search tree, comparing the new key to existing nodes using `operator<`. Once it finds the correct spot, it inserts the node and automatically rebalances the tree to ensure the maximum depth is logarithmic.
**When to use them:**
Because Hash Tables (`unordered_map`) are O(1), you should almost always prefer them for simple lookups. However, `std::map` and `std::set` shine when:
1. **You need ordered data:** If you need to print elements alphabetically or numerically, iterating a `std::map` guarantees an ascending ordered traversal. Additionally, because the tree is always sorted, finding the absolute minimum or maximum element is an O(1) operation simply by checking `*begin()` or `*rbegin()`.
2. **You need range queries:** Finding the "closest number greater than X" is impossible in O(log N) with a hash table, but trivial in a `set` using `set.lower_bound(X)`.
3. **You lack a hash function:** If your key is a complex custom struct (like `std::pair`), `unordered_map` requires you to write a custom, complex hash function. `std::map` only requires a simple `operator<` to establish order.
**Real-world Engineering:** O(log N) ordered operations are mandatory for maintaining a live leaderboard, implementing a sweep-line algorithm in computational geometry, or building a financial trading order book where you must instantly match the highest bid with the lowest ask.
Code examples
Ordered traversal and Range queries
#include <iostream>
#include <set>
int main() {
// Elements are automatically sorted as they are inserted
std::set<int> mySet = {50, 10, 30, 20, 40};
// This will print: 10 20 30 40 50
for (int x : mySet) {
std::cout << x << " ";
}
std::cout << '\n';
// Range Query: Find the first element >= 25
// Because it's a BST, lower_bound runs in O(log N).
auto it = mySet.lower_bound(25);
if (it != mySet.end()) {
std::cout << "First element >= 25 is: " << *it << '\n'; // Prints 30
}
return 0;
}The self-balancing tree inherently maintains order. Methods like `lower_bound` leverage the tree structure to perform binary searches natively.
Key points
- map = BST: `std::map` and `set` are Binary Search Trees. They are O(log N), not O(1).
- Automatic sorting: Use them when you need to iterate data in a guaranteed sorted order, or need to perform fast range/proximity queries.
Common mistakes
- Using map for pure lookup performance: Beginners often use `std::map` for frequency counting in LeetCode problems, not realizing it incurs an O(log N) overhead per insertion. This turns an O(N) algorithm into O(N log N). Always default to `std::unordered_map`.
Recall questions
- What is the underlying data structure of `std::map` and `std::set`?
- What is the time complexity for insertions and lookups in a `std::map`?
- What does the `lower_bound(key)` function do in a `std::set`?
Questions & answers
A candidate is asked to design a system that continuously receives timestamps and must frequently query the smallest timestamp received so far. They use a `std::unordered_set`. What is the flaw?
An `unordered_set` (hash table) scrambles data, meaning finding the minimum timestamp requires an O(N) linear scan. They should use a `std::set` (BST), which keeps elements ordered, allowing them to retrieve the smallest element in O(1) by simply checking `*set.begin()`.
Approach: Identify when maintaining strict order is necessary for algorithmic efficiency.
Why might a `std::map` be preferred over `std::unordered_map` when using a custom struct as a key?
`unordered_map` requires defining a custom hashing struct (like `std::hash`), which is often complex and error-prone. `std::map` only requires defining an `operator<` (less than) for the struct to allow the binary tree to sort it.
Approach: Understand the interface requirements (Hashing vs Comparison) of associative containers.