Neoclassical C++: segmented iterators revisited (1) – template

" Feed" href="https://boostedcpp.net/feed/" /><br>" Comments Feed" href="https://boostedcpp.net/comments/feed/" /><br>" Neoclassical C++: segmented iterators revisited (1) Comments Feed" href="https://boostedcpp.net/2026/05/18/neoclassical-c-segmented-iterators-revisited-1/feed/" />

" />

Neoclassical C++: segmented iterators revisited (1)

Introduction to segmented iterators

The legendary STL library has been an inspiration in the development of the C++ language and libraries. The understanding of the concepts and code developed by Stepanov, Lee, Musser, Austern, etc. is a treasure trove for any C++ programmer.

Stepanov’s core claim was that abstraction should have near-zero overhead. He argued that generic programming, done correctly, should not impose a noticeable runtime cost (abstraction penalty) compared to hand-written specialized code. This was not just a hope but a design principle of the STL.

Following this philosophy, in 2000 Matt Austern published the paper Segmented Iterators and Hierarchical Algorithms. The paper’s core argument was that many data structures are naturally segmented (e.g. deque), and generic algorithms that ignore that feature — treating every data structure as a uniform range of elements — are unnecessarily inefficient. A new kind of iterator abstraction, in which segmentation is explicit, could make possible to write hierarchical algorithms that exploit segmentation and reduce the abstraction penalty associated with standard iterators.

The classic motivating example is std::deque, which is internally a sequence of fixed-size arrays. Every ++it on a deque iterator may cross a block boundary, so inplicitly std::find or std::fill has to evaluate, on every step, whether the current pointer has reached the end of the current block, an indirection that makes deque iteration measurably slower and also defeats most compilers’ auto-vectorisers.

A segmented iterator could be a two-level structure, allowing an algorithm to operate on each contiguous segment efficiently (for instance, calling memset or a tight inner loop on each chunk) and only handle the segment-to-segment transitions at the outer level.

This paper remained influential but its ideas were never adopted into the C++ standard. On the other hand, some libraries have internally developed those core ideas. Some examples::

Around 2023, libc++‘s std::for_each was optimized for segmented iterators, which lead to high performance improvements and there is an ongoing effort to add more algorithms.)

Some Boost libraries, like Boost.PolyCollection, have internal algorithm implementations specially tuned for their internal segmented nature.

Austern’s paper explained

A traditional iterator presents a flat view: increment, decrement, dereference. A segmented iterator additionally admits being decomposed into two coordinates:

a segment iterator that walks the outer sequence of segments (the blocks of a deque, the chunks of a chunk-list, the buckets of a chained hash table, etc.). This iterator is not dereferenceable.

a local iterator that walks the inner range inside one segment. This iterator is dereferenceable.

A hierarchical algorithm is then a generic algorithm that, when given a segmented iterator, dispatches to a two-level loop: an outer loop over the segments and, inside each segment, a simplified algorithm over a higher performance, less segmented, local_iterator that could be further segmented into new, lower-level, segment iterator /local iterator pairs. Ultimately, this recursive segmentation reaches to a non-segmentable, probably highly efficient, local_iterator.

For a deque the picture is the canonical one-level segmentation case: a segment_iterator is essentially walking the block index, and the corresponding local_iterator is walking inside one block.

For a deeper container such as vector>> the same decomposition recurses: the local_iterator produced at the outer level can be itself decomposed in a new segment_iterator (its segments are the middle vectors) and local_iterator, and the local_iterator of the innermost vector is truly flat.

For transformations between iterators, local_iterators, and segment_iterators Austern proposes a segmented_iterator_traits class template that defines the primitives for segmentation-aware algorithms. Its synopsis, transcribed from the paper, is:

//General definition containing a flag identifying the iterator as non-segmented<br>template class Iterator><br>struct segmented_iterator_traits {<br>typedef /* Type::value == false */ is_segmented_iterator;<br>};

//The traits class is specialized for every segmented iterator type<br>template class Iterator><br>struct segmented_iterator_traits {<br>// is_segmented_iterator::value == true if Iterator is segmented<br>typedef /* unspecified */ is_segmented_iterator;

// A non-dereferenceable iterator that traverses the sequence of segments<br>typedef /* unspecified */ segment_iterator;

// An...