Sign in to watch this lesson
Algorithms - Foundations · 4:20
The STL Tour
What each standard container really costs once the hardware gets a say: the shapes behind vector, deque, list, set/map and unordered_map, a million ints summed in a vector versus a list on a Mac (with the list's nodes shuffled, over a thousand times slower), and why std::lower_bound on a set walks two hundred thousand steps while s.lower_bound makes seventeen comparisons. It ends with three traps that cost contestants every week: accumulate's init type, map[] inserting on read, and multiset::erase(value).
You will learn
- Describe the memory layout and per-operation cost of vector, deque, list, set/map and unordered_map
- Explain with cache lines why traversing a vector beats traversing a list by orders of magnitude
- Use the member lower_bound on ordered containers and explain why std::lower_bound on set iterators is linear
- Avoid the accumulate init-type, map[] and multiset::erase(value) traps