Chapter 09 of 30
Sets, Maps & Multi-Containers
Master ordered and unordered containers, stack, queue, deque, and priority queue for competitive programming.
std::set — Ordered Unique Elementsstd::multiset — Ordered Elements with Duplicatesstd::map — Key-Value Associationsstd::unordered_map & std::unordered_set — Hash-Based Containersstd::stack — LIFO Container Adapterstd::queue — FIFO Container Adapterstd::deque — Double-Ended Queuestd::priority_queue — Heap-Based Container
Share:
Sets, Maps & Multi-Containers
STL containers solve specific problems efficiently. Knowing which container to reach for — and understanding its time complexity — is what separates a 1200-rated coder from a 1800-rated one.
std::set — Ordered Unique Elements
A set stores unique elements in sorted order. Internally, it's a red-black tree.
hljs cpp
set<int> s;
s.insert(3); // O(log n)
s.insert(1); // O(log n)
s.insert(3); // duplicate — ignored
s.erase(1); // O(log n)
s.count(3); // 1 if present, 0 if not — O(log n)
s.find(3); // iterator to element, or s.end() — O(log n)
s.size(); // number of elements — O(1)
Iterating (Always Sorted)
hljs cpp
for (int x : s) {
cout << x << " "; // 3
}
Lower/Upper Bound
hljs cpp
set<int> s = {1, 3, 5, 7, 9};
auto it = s.lower_bound(4); // iterator to 5 (first >= 4)
auto it = s.upper_bound(5); // iterator to 7 (first > 5)
// Erase a range
s.erase(s.lower_bound(3), s.upper_bound(7)); // removes 3, 5, 7
std::multiset — Ordered Elements with Duplicates
Like set, but allows duplicates:
hljs cpp
multiset<int> ms;
ms.insert(3);
ms.insert(3);
ms.insert(3);
ms.count(3); // 3
ms.size(); // 3
// Erase ALL occurrences of 3
ms.erase(3);
// Erase ONE occurrence
auto it = ms.find(3);
if (it != ms.end()) ms.erase(it);
Finding k-th Largest
hljs cpp
multiset<int> ms = {1, 3, 5, 7, 9};
auto it = ms.end();
advance(it, -3); // 3rd largest: 5
std::map — Key-Value Associations
A sorted associative array (red-black tree):
hljs cpp
map<string, int> mp;
mp["alice"] = 25; // O(log n)
mp["bob"] = 30; // O(log n)
mp.count("alice"); // 1 — O(log n)
mp.find("alice"); // iterator — O(log n)
mp.erase("alice"); // O(log n)
Iterating (Sorted by Key)
hljs cpp
for (const auto &[key, value] : mp) {
cout << key << ": " << value << "\n";
}
Map as Frequency Counter
hljs cpp
map<char, int> freq;
for (char c : s) {
freq[c]++;
}
Default Values
hljs cpp
// Accessing a non-existent key creates it with default value (0 for int)
mp["unknown"]; // creates entry with value 0
std::unordered_map & std::unordered_set — Hash-Based Containers
O(1) average-case operations vs O(log n) for ordered containers:
hljs cpp
unordered_map<int, int> ump;
unordered_set<int> us;
ump[42] = 1; // O(1) average
us.insert(42); // O(1) average
us.count(42); // O(1) average
When to Use Unordered
- Faster average case (O(1) vs O(log n))
- No ordering — iteration order is undefined
- Worst case O(n) if many hash collisions
- Use
unordered_mapby default; switch tomapif you need ordering or if the hash is adversarial
std::stack — LIFO Container Adapter
Last-In-First-Out:
hljs cpp
stack<int> st;
st.push(1); // O(1)
st.push(2); // O(1)
st.top(); // 2 — O(1)
st.pop(); // removes 2 — O(1)
st.empty(); // false — O(1)
st.size(); // 1 — O(1)
Classic Stack Problem: Valid Parentheses
hljs cpp
bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else {
if (st.empty()) return false;
char t = st.top(); st.pop();
if (c == ')' && t != '(') return false;
if (c == ']' && t != '[') return false;
if (c == '}' && t != '{') return false;
}
}
return st.empty();
}
std::queue — FIFO Container Adapter
First-In-First-Out:
hljs cpp
queue<int> q;
q.push(1); // O(1)
q.push(2); // O(1)
q.front(); // 1 — O(1)
q.pop(); // removes 1 — O(1)
q.back(); // 2 — O(1)
q.empty(); // O(1)
BFS uses queues; DFS uses stacks.
std::deque — Double-Ended Queue
O(1) push/pop at both ends, O(1) indexed access:
hljs cpp
deque<int> dq;
dq.push_back(1); // O(1)
dq.push_front(0); // O(1)
dq.pop_back(); // O(1)
dq.pop_front(); // O(1)
dq[0]; // O(1)
std::priority_queue — Heap-Based Container
O(log n) push, O(log n) pop, O(1) top:
hljs cpp
// Max-heap (default)
priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(5);
pq.top(); // 5
pq.pop(); // removes 5
// Min-heap
priority_queue<int, vector<int>, greater<int>> minPq;
// Custom comparator
auto cmp = [](int a, int b) { return a > b; };
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
Dijkstra's Uses a Min-Heap
hljs cpp
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, source}); // {distance, node}
Summary
| Container | Ordered | Duplicates | Access | Insert | Delete |
|---|---|---|---|---|---|
set | Yes | No | O(log n) | O(log n) | O(log n) |
multiset | Yes | Yes | O(log n) | O(log n) | O(log n) |
map | Yes | N/A | O(log n) | O(log n) | O(log n) |
unordered_map | No | N/A | O(1) avg | O(1) avg | O(1) avg |
stack | — | — | O(1) top | O(1) | O(1) |
queue | — | — | O(1) front | O(1) | O(1) |
priority_queue | — | — | O(1) top | O(log n) | O(log n) |
Use set/map when you need ordering. Use unordered_map when you only need fast lookup. Use priority_queue for "always get the max/min" problems.
Prefer reading offline? Download the full book as a PDF.
Download Free Book