Refresher on Containers, Algorithms and Performance in C++
summary
Standard containers behave very differently in real workloads: continuous storage gives cache-friendly random access while node-based containers pay allocation and pointer-chasing costs; worst-case vector insert front is O(n^2) but reserve + push_back + reverse collapses that into linear work; parallel execution policy can slow things down once orchestration and memory bottlenecks kick in; measurements use GCC 10.3 and the Google Benchmark Library with cache emulation from The Foundry, and boost flat containers and hash-based alternatives often win in practice.
AI-written summary · about
chapters (14)
- 0:00Introduction to performance
- 1:05Data structures and complexity
- 6:29Vector vs list benchmarking
- 10:07Memory access and cache usage
- 13:26Insertion performance analysis
- 18:14Optimizing vector usage
- 23:31Sorted container strategies
- 26:36Set insertion benchmarks
- 33:26Flat set alternatives
- 37:36Efficient deletion strategies
- 41:17Unordered container analysis
- 45:53Case study: optimization
- 51:45Flattening and mapping
- 59:17Final summary and tips
