Back to Basics: Classic STL
summary
Overview explains the original STL design, claims containers+iterators+algorithms as the core and shows how iterators are the real glue. Demonstrations include sentinel-node and contiguous implementations, iterator categories (input/forward/bidirectional/random) and half-open ranges. Concrete guarantees include big-O for sort (worst-case n log n) and the caveat that lower_bound does log comparisons but may perform linear iterator increments on non-random-access iterators. Examples emphasize what operations are constant, logarithmic, or linear.
AI-written summary · about
chapters (22)
- 0:00Introduction
- 0:53Overview
- 4:18Motivation
- 7:05History
- 10:19Design Principles
- 12:15Big O Notation
- 13:32Containers and Algorithms
- 15:11Iterators
- 16:52Containers
- 17:50Containers Overview
- 20:29Hierarchy of Requirements
- 21:24Algorithm Categories
- 22:47Iterator Categories
- 26:00Multipass iteration
- 27:20Reading from a file
- 31:08Sequences
- 36:15Iterator Interfaces
- 40:55Iterator adapters
- 43:56Nested type aliases
- 46:55Vector
- 52:42Template
- 56:07Algorithms
related talks
01h 00mBack to Basics: (Range) Algorithms in C++
01h 23mC++ Iteration Revisited 2024
05mChoosing an Abstraction
01h 05mThe Imperatives Must Go!
01h 04mEffective Ranges: A Tutorial for Using C++2x Ranges
01h 00mMissing (and future?) C++ range concepts
01h 03mBreaking Dependencies: The SOLID Principles
01h 05mBetter C++ ranges