• i. Containers, Hashing and Choosing a Structure: What the standard containers really cost, how to hash safely and fast, and a decision map to pick the right structure for a query pattern.
• ii. Ordered Set and PBDS: std::set can’t answer “$k$-th smallest” or “how many are less than $x$”.
• iii. Heaps: The binary heap is the default priority queue.
• iv. Disjoint Set Union: Union-find maintains a partition under “merge two sets” and “which set is $x$ in”.
• v. Treaps and Balanced BSTs: A treap is a BST on keys and a heap on random priorities, so it has expected depth $O(\log n)$ with no balancing code.
• vi. Chtholly Tree (Interval Map): Store the array as maximal runs of equal values in an ordered map.
• vii. Binary Trie: A trie over the bits of integers, most significant bit first.
• viii. Fast Set and Integer Structures: When keys are integers in $[0,n)$, word-level tricks beat comparison-based trees.
• ix. KD-Tree and Spatial Structures: A KD-tree splits points by the median along alternating axes.
• x. Persistent Data Structures: A persistent structure keeps every version.
• xi. Data Structure Catalog: every structure in one place: operation costs, measured memory per element, iterator stability and when to use it.