wiki

Segmented Iterator Traits

2 min read

Segmented Iterator Traits

Context

BoostedCpp2026 - Neoclassical C++ Segmented Iterators Revisited revisits Austern’s traits-based interface for expressing that an iterator range is segmented. The purpose is to let generic algorithms switch from one flat loop to a hierarchy of local loops over simpler segment-local iterators.

Formal Statement

A segmented iterator type supplies a traits interface with at least these operations:

segment_iterator segment(Iterator it);
local_iterator local(Iterator it);
Iterator compose(segment_iterator s, local_iterator l);
local_iterator begin(segment_iterator s);
local_iterator end(segment_iterator s);

The central invariant is that compose(segment(it), local(it)) recovers the original logical iterator position, while begin(s) and end(s) delimit the local range for one segment.

Derivation / Construction

For a segmented range [first,last), a single-range hierarchical algorithm usually handles three cases:

  • If first and last are in the same segment, run the ordinary algorithm on [local(first), local(last)).
  • Otherwise, run the ordinary algorithm on the tail of the first segment, then each complete middle segment, then the head of the last segment.
  • If a local_iterator is itself segmented, recurse until the local iterator is flat.

For a deque<T> with fixed-size blocks, this means replacing repeated flat-iterator block-boundary checks with an outer loop over blocks and inner loops over contiguous T* ranges.

Implications

Segmented traits make data-layout locality visible without requiring every algorithm call site to know a container’s internals. The gain is most direct for simple single-pass algorithms where each local range can become a tight, vectorizable loop. The same pattern is harder for multi-input, output-producing, or bidirectional algorithms because segment boundaries may not align across all iterators.

Graph View

Backlinks