Libstdc++: Optimize ranges::distance for segmented iterators.
ranges::distance is optimized for segmented iterators by summing distances of individual segments.
The ranges::distance function in libstdc++ now includes an optimization for segmented iterators. For iterators that span multiple contiguous segments (like those used in std::deque or certain ranges views), ranges::distance is now calculated by summing the distances of each individual segment. This improves performance for operations involving such iterators.
In Details
The non-sized-sentinel overload of std::ranges::distance in include/bits/ranges_base.h has been augmented to recursively handle segmented iterators. It uses the newly introduced __for_each_segment utility to iterate over the segments of a segmented iterator and sums the results of ranges::distance calls on each segment. This directly addresses PR libstdc++/123211 by providing an efficient distance calculation for composed ranges.
- 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::distance
- A C++ function, part of the Ranges library, that calculates the number of elements between two iterators.
- iterator
- An object that enables traversal over elements in a container or data structure.
- 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.