Neoclassical C++: segmented iterators revisited (1)
Hi,
I've written a blog post revisiting Matt Austern's great Segmented Iterators and Hierarchical Algorithms paper (2000) and benchmarking an experimental implementation I've been playing with in Boost.Container.
Quick idea: std::deque and friends are internally segmented (blocks of contiguous memory), but STL-like iterators hide that, so every ++it has to check for a block boundary. Austern's proposal splits the iterator into a segment_iterator (walks blocks) + local_iterator (inside one block), so algorithms can run a tight loop per block and only do bookkeeping at the boundaries.
I benchmarked several "simple" STL algorithms on a Boost deque, and the speedup is way bigger than Austern's original estimation when modern auto-vectorizers enter the game.
Article link: https://boostedcpp.net/2026/05/18/neoclassical-c-segmented-iterators-revisited-1/
Happy to receive feedback!