Libstdc++: Introduce segmented iterator concept and traversal.
Defines a 'segmented iterator' concept and traversal mechanism for composed ranges in libstdc++.
Libstdc++ now introduces the concept of ‘segmented iterators’ and a utility function std::__for_each_segment for traversing them. These iterators represent ranges composed of sub-ranges, and they must provide a special member function for segment traversal. This change implements this traversal mechanism for std::deque, ranges::join_view, and ranges::concat_view, laying the groundwork for optimizations like efficient distance calculations.
In Details
This patch introduces the __segmented_iterator concept and the __for_each_segment utility in libstdc++-v3/include/bits/stl_iterator_base_funcs.h. Segmented iterators are defined as those that model a _S_for_each_segment static member function, which takes a callback to traverse their constituent sub-ranges. Implementations are provided for std::deque, ranges::join_view, and ranges::concat_view iterators, addressing PR libstdc++/123211 and enabling further range-based optimizations.
- libstdc++
- The C++ standard library implementation used by GCC.
- segmented iterator
- An iterator that represents a range composed of multiple contiguous sub-ranges. For example, iterators for
std::dequeorranges::join_viewcan be segmented. - ranges::join_view
- A C++ ranges adaptor that concatenates the elements of a range of ranges into a single range.
- ranges::concat_view
- A C++ ranges adaptor that concatenates two or more ranges into a single range.
- iterator
- An object that enables traversal over elements in a container or data structure.
- C++20
- The 2020 edition of the C++ programming language standard, which introduced significant new features, including the Ranges library.