Segmented Iterators
Definition
Segmented iterators expose that a logical range is physically or structurally divided into segments. Instead of treating iteration as one flat sequence, a segmented iterator can be decomposed into an outer segment_iterator and an inner local_iterator.
Why It Matters
Many containers are not one contiguous array, but their pieces often are contiguous or otherwise simpler than the whole. Exposing that structure lets generic algorithms run optimized inner loops over local segments while preserving a high-level range interface. This can reduce abstraction overhead, branch checks, and missed vectorization opportunities.
Formalism / Key Objects
segment_iterator: traverses the outer sequence of segments and is usually not directly dereferenceable as an element iterator.local_iterator: traverses elements inside one segment and may be a raw pointer or other efficient flat iterator.compose(segment, local): reconstructs the logical iterator position from the two-level coordinates.- Hierarchical algorithm: an algorithm that recursively dispatches over whole segments, then applies a simpler algorithm to each local range.
- For
deque<T>, a typical model is an outer block index and innerT*range for each fixed-size block. - Segmented Iterator Traits records the reusable traits interface and hierarchical
fillschema.
Connections
- Lives under Algorithms and Data Structures because it is both a data-layout abstraction and an algorithm-dispatch technique.
- Complements Quadtrees as another example of exploiting structure hidden beneath a uniform interface.
- Related to cache locality, vectorization, iterator categories, generic programming, and container-specific algorithm customization.
Common Confusions
- A segmented iterator is not simply a random-access iterator with a slower increment; the point is to expose two-level structure to algorithms.
- Segmentation does not guarantee speedups for every algorithm. Multi-range, bidirectional, or irregular algorithms can require more complex handling.
- A compiler cannot always infer segment-local contiguity from a flat iterator abstraction.