Introduction to C++ Containers - Know Your Data Structures
summary
Overview of the Standard Library containers with concrete examples and costs: sequence, associative, unordered, and adapters are shown with C++ code, documented time complexities, and common implementations (vectors as contiguous arrays with capacity doubling, lists as doubly linked lists, hash tables for unordered_map). Demonstrations include iterator invalidation cases, use of reserve()/shrink_to_fit to avoid reallocations, and notes on thread-safety tradeoffs. New in C++23 is flat_map with contiguous storage for better locality. Code samples and slides are available from the uploader.
AI-written summary · about
chapters (11)
- 0:00Welcome
- 2:06Data and data structures
- 3:52Arrays and linked structures
- 10:15Standard Template Library and containers introduction
- 16:12Sequence containers
- 21:08Vector performance
- 29:55Deque and linked lists
- 35:55Container pitfalls
- 39:27Container adapters
- 45:04Associative containers
- 54:20Summary
related talks
01h 04mBack to Basics: Standard Library Containers in Cpp
48mC++ Data Structures That Make Video Games Go Round
06mUsing STL containers efficiently
24mDesigning Fast and Efficient List-like Data Structures
06mAmortized O(1) Complexity in C++
01h 02m“Lightweight Object Persistence With Relocatable Heaps in Modern C++"
01h 03m#Hashing (Hashing Values)
48mA Helicopter Tour of Purely Functional Data Structures