Better Code: Data Structures
summary
Goal is no incidental data structures: prefer std containers and composite types over ad hoc, self-referential graphs. Demonstrates concrete tools: using stable_partition + rotate to implement a single-pass stable partition and a projection-based gather on parallel arrays, then combining nth_element with partial_sort to sort a subrange. Shows memory costs (L1 vs main memory ~200×) and a physical shoelace-and-beads model that guarantees only hierarchies; points to an ASL forest implementation on GitHub. The techniques work and give big locality and correctness wins.
AI-written summary · about
chapters (25)
- 0:00Introduction
- 2:22Goal
- 3:15What is a data structure
- 4:03What is a structure
- 5:08Dimensionless space
- 5:36Four bits
- 6:56Validity
- 10:56Value Relationships
- 11:26Representation Relationships
- 12:10Physical Relationships
- 15:29Functional Relationships
- 16:30Whole Part Relationships
- 18:37Data Structures
- 19:46Memory
- 22:30Stable Partition
- 25:36Inductive Basis
- 28:33Parallel Structure
- 31:36Partial Sort
- 35:54Sort Subrange
- 36:52incidental data structures
- 37:19structural ambiguities
- 37:42selfreferential interfaces
- 41:09forests and hierarchies
- 44:26shoelaces
- 49:53force data structure
related talks
01h 01mAlgorithm Intuition (part 2 of 2)
01h 23mAlex Stepanov, Generic Programming in Cpp, and the STL
30m“Esoteric Data Structures and Where to Find Them”
46mC++ Fundamentals - Algorithms
01h 30mSorting Algorithms: Speed Is Found In The Minds of People
40mImmutable Data Structures in C++
01h 00mOLD VERSION: The Fine Details Behind C++ Containers And Algorithms
01h 00mMoving Faster: Everyday efficiency in modern C++