The Fine Details Behind C++ Containers And Algorithms
summary
The C++ library requires vector::push_back to be amortized O(1) and benchmarks show forgetting noexcept on move constructors causes large slowdowns due to copy instead of move. Sorting a list is faster if copied to a vector first because cache locality wins; tests include full copy+sort+copy measured. Erasing many indexed elements is faster by moving blocks then one shrink rather than repeated erase. unordered_map find can be worst‑case O(n) (hash collisions/attacks). C++17 features like try_emplace/insert_or_assign and node_handle extract/insert measurably reduce allocations; ranges and parallel algorithms help sometimes but always benchmark.
AI-written summary · about
chapters (30)
- 0:00Introduction and speaker intro
- 1:10Talk overview and topics
- 1:51Vector push_back complexity explained
- 5:28Vector resizing and noexcept move constructors
- 6:51std::copy and memory handling
- 8:14Container complexity in C++ spec
- 9:39Sorting vector vs list performance
- 14:38Inserting elements at front of vector
- 16:25std::move vs std::move in algorithms
- 17:07Erase-remove idiom explained
- 19:15C++20 erase function for containers
- 19:36Erasing elements by index from containers
- 24:17Complexity of unordered_map insert
- 27:51Hash function performance and attacks
- 28:16Dangling references and temporary objects
- 30:07C++17 insert_or_assign vs insert
- 33:03C++17 in_place and try_emplace for maps
- 36:15C++17 node_handle for map nodes
- 38:43C++17 try_emplace with hint
- 40:07C++17 string_view and ranges introduction
- 41:56C++23 flat_map and data locality
- 43:20Loop efficiency and cache locality
- 45:08C++20 ranges and lazy evaluation
- 46:13C++17 parallel algorithms overview
- 47:17Thread safety in C++ containers
- 48:41Iterator invalidation rules
- 49:45std::iterator deprecation
- 50:48Reverse iterator implementation details
- 52:17Summary and best practices
- 57:16Q&A on container runtime changes
related talks
01h 19mThis is C++: Uncompromised Performance, Undefined Behavior, & Move Semantics
58mRefresher on Containers, Algorithms and Performance
01h 00mMoving Faster: Everyday efficiency in modern C++
40mImmutable Data Structures in C++
01h 31mNew (& Old) C++ Standard Library Containers - How to Choose the Right Container in C++26 and Beyond
44mC++ Performance and Optimisation
01h 01mRecipes for Reducing Allocations by C++ Containers
13mMissing Optimizations on Node-based Containers