Constructing Generic Algorithms: Principles and Practice
summary
Starts from a raw recursive divide‑and‑conquer: pick mid, partition in place around the expected value, recurse on the half with the gap, and show the cost sums to linear time (≈2n). Tail recursion becomes a loop; pointer arithmetic is replaced by std::distance and std::next so the algorithm accepts a forward iterator and preserves random‑access speed. Type requirements surface: values vs difference types (durations work; time_point needs a fine‑space diff), tests for empty/even/odd, and a return choice named min_absent. Ranges add composable views but not new fundamentals.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 0:56Algorithm importance
- 2:34Case study problem
- 4:46Initial approaches
- 8:04Divide and conquer
- 11:24Iterative algorithm
- 14:14Testing and refactoring
- 19:20Generic design principles
- 23:47Refining for iterators
- 27:20Standard library limitations
- 30:43Strength reduction
- 33:33Const-correctness
- 37:25Naming and documentation
- 39:03Type requirements
- 41:51Affinitive space types
- 44:32Ranges and composition
- 46:20Alternative formulations
- 48:20Epilogue
related talks
51mAlgorithms Demystified
57mFun with Algorithms
01h 00mSTL Algorithms - why you should use them, and how to write your own
59mThe Most Average Function There Is
01h 09mThere's Treasure Everywhere
01h 00mBuilding and Extending the Iterator Hierarchy in a Modern, Multicore World
09mAn Algorithm Generator for Fixed-point Oriented Programming (Lightning Talk)
50mReusable C++ Code, Reusable C++ Data Structures