Evolution of a Median Algorithm in C++
Talkat CppCon 2023 · on Thursday, 2023-10-05· at 15:50· Adams, 6700 North Gaylord Rockies Boulevard·
summary
Starts from the simple sort-and-index approach and evolves into a templated, ranges-aware median() that uses nth_element and max_element and handles overflow with midpoint. An experiment on 10 million integers shows runtime drop from about 972 ms to 89 ms. The API moves from returning values to returning iterator pairs, then to a tidy median result class that hides details; it runs in average linear time but crucially permutes the container and considers execution policies and concepts.
AI-written summary · about
chapters (22)
- 0:00Median algorithm challenge
- 1:48Standard library lacks median
- 3:55Standardize generic median
- 5:23Empty containers and edge cases
- 6:49Even-sized range median
- 8:15Avoiding integer overflow
- 9:18Performance bottleneck sort
- 10:23Linear-time median nth_element
- 11:46Fixing nth_element usage
- 12:50Second middle element
- 13:34Benchmarking improvements
- 14:37Generic for any container
- 15:44Returning iterators
- 17:53Range-based generic algorithm
- 18:59Execution policies C++20
- 20:24Constraints with Concepts
- 21:28Median result class
- 23:36Key takeaways generic median
- 24:37Performance trade-offs
- 25:39Standardization next steps
- 27:05Community call to action
- 28:28Closing remarks Q&A
related talks
09mAlgorithms and Iterators for Multidimensional Arrays
45mBeyond Lists: High Performance Data Structures
13mInterpolation Search Can Be Fast, in Some Situations, Sometimes, If You Try!
33mFair intersection of seekable iterators
42mMergeable Summaries and the Data Sketches Library
01h 04mBack to Basics: Standard Library Containers in Cpp
32mKnow your data the stats behind the Alters
06mAmortized O(1) Complexity in C++