OLD VERSION: The Fine Details Behind C++ Containers And Algorithms
summary
Covers concrete C++ library rules and measured outcomes: shows vector push_back is amortized O(1), demonstrates a missing noexcept on move makes reallocations much slower (benchmarked big penalty), explains memcpy for trivially copyable types, compares sorting list vs copying list→vector then sort (vector wins due to cache locality), gives a node_handle extract/insert example that avoids reallocation, shows a push_front-by-reverse trick and an erase-by-indices optimization (≈10% faster in tests), and stresses iterator invalidation, thread-safety guarantees and when to benchmark parallel/range algorithms.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:35Vector resizing
- 6:43Container specifications
- 9:35Sorting algorithms
- 14:36Front insertion tactics
- 16:53Erase-remove idiom
- 19:30Efficient index erasure
- 24:07Unordered map mechanics
- 30:31C++17 map improvements
- 35:50Node handles and hints
- 40:15Views and data locality
- 43:08Algorithm optimizations
- 45:50Parallelism and safety
- 48:48Iterator implementation
- 52:19Final summary and Q&A
related talks
01h 31mNew (& Old) C++ Standard Library Containers - How to Choose the Right Container in C++26 and Beyond
58mRefresher on Containers, Algorithms and Performance
01h 00mMoving Faster: Everyday efficiency in modern C++
01h 23mAlex Stepanov, Generic Programming in Cpp, and the STL
57mSome Things C++ Does Right
01h 01mRecipes for Reducing Allocations by C++ Containers
40mImmutable Data Structures in C++
01h 25mComparing 'Classic C++' and 'Modern C++' Ways to Solve Programming Tasks