STL
EasyC++ containers and algorithms
Problem
C++'s Standard Template Library gives ready-made containers and algorithms: vector, pair, string, queue, stack, map/unordered_map, set/unordered_set, plus sort, max, min. Knowing them saves you from reimplementing basics.
Ready-made toolboxes so you don't rebuild lists, maps, and sorting yourself.
The idea
The Standard Template Library gives you the data structures interviews assume you know: vector for dynamic arrays, map and unordered_map for keyed lookup, set for sorted unique values, stack, queue and priority_queue for the classic orderings. Knowing which container has which complexity is most of the battle.
The trick
- `unordered_map` is O(1) average, `map` is O(log n) but keeps keys sorted.
- `sort(v.begin(), v.end())` is O(n log n); pass a comparator for custom orders.
- `priority_queue` is a max-heap by default; use `greater<>` for a min-heap.
Step 1 of 4. A list keeps what you put in it, in the order you put it in. Values: 3, 1, 2, 1. size 4.
1vector<int> v = {3,1,2}; sort(v.begin(), v.end());2map<string,int> freq; freq["a"]++;3set<int> seen; seen.insert(5);Input
- array
- [3, 1, 2, 1]
Memory
- size
- 4
- keys
- —
- put in
- —
- kept
- —
Check yourself
1 quick question about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- v = {3, 1, 2}; sort(v.begin(), v.end())
- Output:
- {1, 2, 3}
- Explanation:
- You never write a sort in a contest. vector, map, set and sort are already there and already correct.
Example 2
- Input:
- m["a"]++ on an empty map<string,int>
- Output:
- m["a"] == 1
- Explanation:
- A missing key is default-constructed to 0 first, which is why counting with a map needs no 'if it exists' check.
Finished the walkthrough? Add it to your streak.