Topic 7 of 27 · Intermediate
STL Containers
vector, map, unordered_map, set, deque, stack, queue, priority_queue.
Concept
The STL provides tested containers. vector is the default choice: contiguous, cache-friendly, amortised O(1) push_back.
map/set are red-black trees (sorted, O(log n)); unordered_map/unordered_set are hash tables (average O(1)).
Adapters: stack, queue and priority_queue (max-heap by default; use greater<> for min-heap).
Cheat sheet
| Container | Lookup | Ordered? |
|---|---|---|
| vector | O(1) index | Insertion order |
| map / set | O(log n) | Sorted |
| unordered_map | O(1) avg | No |
| deque | O(1) both ends | Insertion order |
| priority_queue | O(1) top, O(log n) push | Heap |
Code (C++20)
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v{5, 3, 8};
v.push_back(1);
unordered_map<string, int> freq;
for (string w : {"a", "b", "a"}) freq[w]++;
map<int, string> ranks{{2, "Ravi"}, {1, "Asha"}}; // sorted by key
set<int> uniq(v.begin(), v.end());
priority_queue<int, vector<int>, greater<int>> minHeap(v.begin(), v.end());
cout << minHeap.top() << ' ' << freq["a"] << ' ' << ranks.begin()->second << '\n';
}Remember
- vector by default.
- operator[] on map inserts missing keys — use find/contains to check.
- reserve() avoids repeated reallocations.
Interview questions
map vs unordered_map?
map is a sorted red-black tree with O(log n) operations; unordered_map is a hash table with average O(1) but no order and worst case O(n).
How does vector grow?
When full it allocates a bigger block (usually 1.5–2×), moves elements over and frees the old block, giving amortised O(1) push_back.
Lesson test
Take an 8-question test on “STL Containers” — concepts, output prediction, bug spotting and interview questions.