On Tue, Jul 14, 2026 at 2:00 PM Patrick Palka <[email protected]> wrote:
> On Tue, 14 Jul 2026, Tomasz Kaminski wrote: > > > > > > > On Tue, Jul 14, 2026 at 6:32 AM Patrick Palka <[email protected]> wrote: > > This patch defines a new utility function std::__for_each_segment > for > > iterating over "segmented" iterators, i.e. iterators for ranges > composed > > of sub-ranges. Such iterators must provide a static member > function > > _S_for_each_segment implementing traversal over their segments via > a > > callback function. This patch implements such traversal for > iterators > > of std::deque, ranges::join_view and ranges::concat_view. > > > > Could you explain what problems you see with this approach? > > I'm biased because that would be the interface I would use for segmented > > iterators, and the I like how it end up being used in distance. > > In short I would be happy to merge this as the starting point. > > My main reservation with this approach is code duplication. > If we want a __for_each_segment_backward that traverses the segments in > reverse then I think we'll need to implement it from scratch for each > segmented iterator type. Indeed, but I couldn't think of standard algorithm that would need backward iteration. > Same if we want a version of > __for_each_segment whose callback returns void and never short circuits. > That indeed is the case even with distance, but I assumed that the benefit would not be worth the extra complexity. > Same if we want a __for_each_segment whose __last is an arbitrary > sentinel instead of another iterator, I think? > I think segmented iteration is only possible if the sentinel is `end()` from the range. Otherwise, I think we need to reconstruct the combined iterator after each element to compare it against the sentinel. Do you have specific case in mind? But when trying a different approach -- having an API in terms of more > fundamental primitives: > There is interesting talk, about for_each being better primitive operation (easier to compile, more optimal) for ranges when implementing a lot of algorithms. > > template<typename _Iter> > struct __segmented_iterator_traits; > /* > { > using __outer_iter_it = ...; > - The iterator type of the outer range. > > using __inner_iter_t = ...; > - The iterator type of the inner range. > > static __outer_iter_t __outer_iter(_Iter __it); > - Return the outer iterator corresponding to __it. > »·······If the underlying range is not empty then the returned outer > iterator > »·······is always dereferenceable even if __it is the past-the-end > iterator. > > static __inner_iter_t __inner_iter(_Iter __it); > - Return the iterator into *__outer_it(__it) corresponding to __it. > > static __inner_iter_t __begin(__outer_iter_t __it); > - Return the inner iterator corresponding to the beginning of *__it. > > static __inner_iter_t __end(__outer_iter_t __it); > - Return the inner iterator corresponding to the end of *__it. > } > */ > > with which we could in turn generically define __for_each_segment and > __for_each_segment_backward functions, I ran into complications > with the fact that the join_view::end iterator's outer range is > not dereferencable (unlike deque::end). This needed > to be worked around by either adding a bool __is_end_iter(_Iter) > predicate to the API or by transparently transforming the > join_view::end() iterator from > {_M_outer=end(_M_base), _M_inner={}} > to > {_M_outer=prev(end(_M_base)), _M_inner=end(_M_outer)} > within the __segmented_iterator API for join_view so that > we could assume it's always derereferenceable. Both workarounds > seemed undesirable to me (the first complicates the API, the second > imposes an additional bidirectional constraint to join_view's > outer range). > And of course this more fundamental API would rule out iterators with > heteregeneous segments such as concat_view since it doesn't have a fixed > inner iterator type. > Indeed, when thinking about the design space, I gravitated toward `memcpy`. Concatenating vectors is something desirable. > > So I think I prefer the current approach too, and live with the code > duplication when the time comes that we want additional versions of > __for_each_segment. > > > > > This patch defines > > > > PR libstdc++/123211 > > > > libstdc++-v3/ChangeLog: > > > > * include/bits/stl_deque.h > (_Deque_iterator::_S_for_each_segment): > > Define. > > (_Deque_iterator::_S_enable_for_each_segment): Define. > > * include/bits/stl_iterator_base_funcs.h: Include > <bits/move.h>. > > (__for_each_segment): Define. > > * include/bits/stl_iterator_base_types.h: Include > > <ext/type_traits.h> in C++98 mode. > > (__enable_for_each_segment): Define. > > (__segmented_iterator): Define in C++20. > > * include/std/ranges (join_view::_Iterator::_Iterator): New > > constructor taking both an inner and outer iterator. > > (join_view::_Iterator::_S_for_each_segment): Define. > > (join_view::_Iterator::_S_enable_for_each_segment): Define. > > (concat_view::_Iterator::_S_for_each_segment): Define. > > (concat_view::_Iterator::_S_enable_for_each_segment): > Define. > > * testsuite/23_containers/deque/for_each_segment.cc: New > test. > > * testsuite/std/ranges/adaptors/join/for_each_segment.cc: > New test. > > * testsuite/std/ranges/concat/for_each_segment.cc: New > test. > > --- > > libstdc++-v3/include/bits/stl_deque.h | 37 +++++++ > > .../include/bits/stl_iterator_base_funcs.h | 20 ++++ > > .../include/bits/stl_iterator_base_types.h | 22 ++++- > > libstdc++-v3/include/std/ranges | 99 > +++++++++++++++++++ > > .../23_containers/deque/for_each_segment.cc | 74 ++++++++++++++ > > .../ranges/adaptors/join/for_each_segment.cc | 80 +++++++++++++++ > > .../std/ranges/concat/for_each_segment.cc | 67 +++++++++++++ > > 7 files changed, 398 insertions(+), 1 deletion(-) > > create mode 100644 > libstdc++-v3/testsuite/23_containers/deque/for_each_segment.cc > > create mode 100644 > libstdc++-v3/testsuite/std/ranges/adaptors/join/for_each_segment.cc > > create mode 100644 > libstdc++-v3/testsuite/std/ranges/concat/for_each_segment.cc > > > > diff --git a/libstdc++-v3/include/bits/stl_deque.h > b/libstdc++-v3/include/bits/stl_deque.h > > index 29a3f1b62896..b51342e1751d 100644 > > --- a/libstdc++-v3/include/bits/stl_deque.h > > +++ b/libstdc++-v3/include/bits/stl_deque.h > > @@ -417,6 +417,43 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > > friend _Self > > operator+(difference_type __n, const _Self& __x) > _GLIBCXX_NOEXCEPT > > { return __x + __n; } > > + > > + template<typename _Fn> > > + static _Self > > + _S_for_each_segment(_Self __first, _Self __last, _Fn > __func) > > + { > > + if (__first._M_node == __last._M_node) > > + { > > + _Elt_pointer __ret = __func(__first._M_cur, > __last._M_cur); > > + if (__ret != __last._M_cur) > > + return _Self(__ret, __first._M_node); > > + return __last; > > + } > > + else > > + { > > + _Elt_pointer __ret = __func(__first._M_cur, > __first._M_last); > > + if (__ret != __first._M_last) > > + return _Self(__ret, __first._M_node); > > + > > + for (_Map_pointer __node = __first._M_node + 1; > > + __node < __last._M_node; > > + ++__node) > > + { > > + _Elt_pointer __end = *__node + _S_buffer_size(); > > + __ret = __func(*__node, __end); > > + if (__ret != __end) > > + return _Self(__ret, __node); > > + } > > + > > + __ret = __func(__last._M_first, __last._M_cur); > > + if (__ret != __last._M_cur) > > + return _Self(__ret, __last._M_node); > > + > > + return __last; > > + } > > + } > > + > > + static const bool _S_enable_for_each_segment = true; > > }; > > > > /** > > diff --git a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h > b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h > > index 2762090c6e48..0e992adfb005 100644 > > --- a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h > > +++ b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h > > @@ -66,6 +66,7 @@ > > #include <bits/concept_check.h> > > #include <debug/assertions.h> > > #include <bits/stl_iterator_base_types.h> > > +#include <bits/move.h> // For _GLIBCXX_MOVE > > > > namespace std _GLIBCXX_VISIBILITY(default) > > { > > @@ -383,6 +384,25 @@ namespace __detail > > #define _GLIBCXX_ITER_MOVE(__it) _GLIBCXX_MOVE(*__it) > > #endif > > > > + /* Mechanism for traversing ranges that are composed of > "segments" of other > > + ranges, such as std::deque and ranges::join_view. The > callback __func > > + is sequentially called on each constituent segment as a pair > of inner > > + iterators. If the callback returns something other than the > past-the-end > > + inner iterator, then the rest of the traversal gets > short-circuited and > > + returns the iterator at which we stopped. */ > > + template<typename _Iter, typename _Fn> > > +#if __cplusplus >= 201103L > > + __enable_if_t<__enable_for_each_segment<_Iter>::__value, > _Iter> > > +#else > > + _Iter > > +#endif > > + __for_each_segment(_Iter __first, _Iter __last, _Fn __func) > > + { > > + return _Iter::_S_for_each_segment(_GLIBCXX_MOVE(__first), > > + _GLIBCXX_MOVE(__last), > > + _GLIBCXX_MOVE(__func)); > > + } > > + > > /// @endcond > > > > _GLIBCXX_END_NAMESPACE_VERSION > > diff --git a/libstdc++-v3/include/bits/stl_iterator_base_types.h > b/libstdc++-v3/include/bits/stl_iterator_base_types.h > > index 2366b5b5ce3e..21a482444383 100644 > > --- a/libstdc++-v3/include/bits/stl_iterator_base_types.h > > +++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h > > @@ -66,7 +66,9 @@ > > #include <bits/c++config.h> > > > > #if __cplusplus >= 201103L > > -# include <type_traits> // For __void_t, is_convertible > > +# include <type_traits> // For __void_t, is_convertible, > __enable_if_t > > +#else > > +# include <ext/type_traits.h> // For __gnu_cxx::__enable_if > > #endif > > > > #if __cplusplus > 201703L && __cpp_concepts >= 201907L > > @@ -283,6 +285,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > { enum { __value = __is_base_of(random_access_iterator_tag, > _Cat) }; }; > > #endif > > > > + template<typename _Iter, typename = void> > > + struct __enable_for_each_segment > > + { static const bool __value = false; }; > > + > > + template<typename _Iter> > > + struct __enable_for_each_segment<_Iter, > > +#if __cplusplus >= 201103L > > + __enable_if_t<_Iter::_S_enable_for_each_segment>> > > +#else > > + typename > __gnu_cxx::__enable_if<_Iter::_S_enable_for_each_segment, void>::__type> > > +#endif > > + { static const bool __value = true; }; > > + > > +#if __cpp_lib_concepts > > + template<typename _Iter> > > + concept __segmented_iterator = > __enable_for_each_segment<_Iter>::__value; > > +#endif > > + > > /// @endcond > > /// @} > > > > diff --git a/libstdc++-v3/include/std/ranges > b/libstdc++-v3/include/std/ranges > > index f89907d3e10e..a25a07f5d3dd 100644 > > --- a/libstdc++-v3/include/std/ranges > > +++ b/libstdc++-v3/include/std/ranges > > @@ -3149,6 +3149,12 @@ namespace views::__adaptor > > : _M_outer(std::move(__outer)), _M_parent(__parent) > > { _M_satisfy(); } > > > > + constexpr > > + _Iterator(_Parent* __parent, _Outer_iter __outer, > _Inner_iter __inner) > > + requires forward_range<_Base> > > + : _M_outer(std::move(__outer)), > _M_inner(std::move(__inner)), _M_parent(__parent) > > + { } > > + > > constexpr explicit > > _Iterator(_Parent* __parent) requires > (!forward_range<_Base>) > > : _M_parent(__parent) > > @@ -3272,6 +3278,50 @@ namespace views::__adaptor > > > > friend _Iterator<!_Const>; > > template<bool> friend struct _Sentinel; > > + > > + template<typename _Fn> > > + static constexpr _Iterator > > + _S_for_each_segment(_Iterator __first, _Iterator > __last, _Fn __func) > > + { > > + _Inner_iter __first_inner = __first._M_get_inner(); > > + _Outer_iter __first_outer = __first._M_get_outer(); > > + _Inner_iter __last_inner = __last._M_get_inner(); > > + _Outer_iter __last_outer = __last._M_get_outer(); > > + > > + if (__first_outer == __last_outer) > > + { > > + auto __ret = __func(__first_inner, __last_inner); > > + return _Iterator(__first._M_parent, > __first_outer, __ret); > > + } > > + else > > + { > > + auto __end = ranges::end(*__first_outer); > > + auto __ret = __func(__first_inner, __end); > > + if (__ret != __end) > > + return _Iterator(__first._M_parent, > __first_outer, __ret); > > + > > + while (++__first_outer != __last_outer) > > + { > > + __end = ranges::end(*__first_outer); > > + __ret = > __func(ranges::begin(*__first_outer), __end); > > + if (__ret != __end) > > + return _Iterator(__first._M_parent, > __first_outer, __ret); > > + } > > + > > + if (__last != __last._M_parent->end()) > > + { > > + __end = __last_inner; > > + __ret = __func(ranges::begin(*__last_outer), > __end); > > + if (__ret != __end) > > + return _Iterator(__first._M_parent, > __first_outer, __ret); > > + } > > + > > + return __last; > > + } > > + } > > + > > + static constexpr bool _S_enable_for_each_segment > > + = forward_iterator<_Iterator>; > > }; > > > > template<bool _Const> > > @@ -10345,6 +10395,55 @@ namespace ranges > > ranges::swap(*__it1, *__it2); > > }, __x._M_it, __y._M_it); > > } > > + > > + template<typename _Fn> > > + static constexpr _Iterator > > + _S_for_each_segment(_Iterator __first, _Iterator __last, > _Fn __func) > > + { > > + return _S_invoke_with_runtime_index([&]<size_t _Ix>() -> > _Iterator { > > + return _S_invoke_with_runtime_index([&]<size_t _Iy>() -> > _Iterator { > > + if constexpr (_Ix == _Iy) > > + { > > + auto __ret = __func(std::get<_Ix>(__first._M_it), > std::get<_Iy>(__last._M_it)); > > + return _Iterator(__first._M_parent, > std::in_place_index<_Ix>, __ret); > > + } > > + else if constexpr (_Ix < _Iy) > > + { > > + auto __first_range = > std::get<_Ix>(__first._M_parent->_M_views); > > + auto __ret = __func(std::get<_Ix>(__first._M_it), > > + ranges::end(__first_range)); > > + if (__ret != ranges::end(__first_range)) > > + return _Iterator(__first._M_parent, > std::in_place_index<_Ix>, __ret); > > + > > + return [&]<size_t _Idx = _Ix + 1>(this auto&& > __self) { > > + if constexpr (_Idx < _Iy) > > + { > > + auto __mid_range = > std::get<_Idx>(__first._M_parent->_M_views); > > + auto __mid_ret = > __func(ranges::begin(__mid_range), > > + > ranges::end(__mid_range)); > > + if (__mid_ret != ranges::end(__mid_range)) > > + return _Iterator(__first._M_parent, > std::in_place_index<_Idx>, __mid_ret); > > + return __self.template operator()<_Idx + > 1>(); > > + } > > + else > > + { > > + auto __last_range = > std::get<_Iy>(__last._M_parent->_M_views); > > + auto __last_ret = > __func(ranges::begin(__last_range), > > + > std::get<_Iy>(__last._M_it)); > > + return _Iterator(__first._M_parent, > std::in_place_index<_Iy>, __last_ret); > > + } > > + }(); > > + } > > + else > > + { > > + __builtin_unreachable(); > > + __glibcxx_assert(false); > > + } > > + }, __last._M_it.index()); > > + }, __first._M_it.index()); > > + } > > + > > + static constexpr bool _S_enable_for_each_segment = true; > > }; > > > > namespace views > > diff --git > a/libstdc++-v3/testsuite/23_containers/deque/for_each_segment.cc > b/libstdc++-v3/testsuite/23_containers/deque/for_each_segment.cc > > new file mode 100644 > > index 000000000000..d6127b0f0e2c > > --- /dev/null > > +++ > b/libstdc++-v3/testsuite/23_containers/deque/for_each_segment.cc > > @@ -0,0 +1,74 @@ > > +// { dg-do run } > > + > > +#include <deque> > > +#include <algorithm> > > +#include <testsuite_hooks.h> > > + > > +struct Finder > > +{ > > + static int call_count; > > + > > + int target; > > + > > + explicit Finder(int t) : target(t) { } > > + > > + int* > > + operator()(int* first, int* last) const > > + { > > + ++call_count; > > + return std::find(first, last, target); > > + } > > +}; > > + > > +int Finder::call_count = 0; > > + > > +void > > +test01() > > +{ > > + // A deque of 500 ints spans ~4 internal nodes (128 elements > per node) > > + // Node 0: elements 0 - 127 > > + // Node 1: elements 128 - 255 > > + // Node 2: elements 256 - 383 > > + // Node 3: elements 384 - 499 > > + std::deque<int> d; > > + for (int i = 0; i < 500; ++i) > > + d.push_back(i); > > + > > + std::deque<int>::iterator it; > > + > > + Finder::call_count = 0; > > + it = std::__for_each_segment(d.begin(), d.begin() + 100, > Finder(50)); > > + VERIFY( it == d.begin() + 50 ); > > + VERIFY( Finder::call_count == 1 ); > > + > > + Finder::call_count = 0; > > + it = std::__for_each_segment(d.begin(), d.begin() + 100, > Finder(999)); > > + VERIFY( it == d.begin() + 100 ); > > + VERIFY( Finder::call_count == 1 ); > > + > > + Finder::call_count = 0; > > + it = std::__for_each_segment(d.begin(), d.end(), Finder(100)); > > + VERIFY( it == d.begin() + 100 ); > > + VERIFY( Finder::call_count == 1 ); > > + > > + Finder::call_count = 0; > > + it = std::__for_each_segment(d.begin(), d.end(), Finder(200)); > > + VERIFY( it == d.begin() + 200 ); > > + VERIFY( Finder::call_count == 2 ); > > + > > + Finder::call_count = 0; > > + it = std::__for_each_segment(d.begin(), d.end(), Finder(450)); > > + VERIFY( it == d.begin() + 450 ); > > + VERIFY( Finder::call_count == 4 ); > > + > > + Finder::call_count = 0; > > + it = std::__for_each_segment(d.begin(), d.end(), Finder(999)); > > + VERIFY( it == d.end() ); > > + VERIFY( Finder::call_count == 4 ); > > +} > > + > > +int > > +main() > > +{ > > + test01(); > > +} > > diff --git > a/libstdc++-v3/testsuite/std/ranges/adaptors/join/for_each_segment.cc > b/libstdc++-v3/testsuite/std/ranges/adaptors/join/for_each_segment.cc > > new file mode 100644 > > index 000000000000..aad00606c97f > > --- /dev/null > > +++ > b/libstdc++-v3/testsuite/std/ranges/adaptors/join/for_each_segment.cc > > @@ -0,0 +1,80 @@ > > +// { dg-do run { target c++20 } } > > + > > +#include <ranges> > > +#include <vector> > > +#include <algorithm> > > +#include <testsuite_hooks.h> > > + > > +namespace ranges = std::ranges; > > + > > +void > > +test01() > > +{ > > + // 4 discrete vectors serving as segments > > + std::vector<std::vector<int>> vec > > + = { {0, 1, 2}, // Segment 0 > > + {3, 4, 5}, // Segment 1 > > + {6, 7, 8}, // Segment 2 > > + {9, 10, 11} // Segment 3 > > + }; > > + > > + auto jv = vec | std::views::join; > > + std::__segmented_iterator auto begin = jv.begin(); > > + std::__segmented_iterator auto end = jv.end(); > > + > > + static int call_count = 0; > > + auto make_finder = [](int target) { > > + return [target](auto first, auto last) { > > + if (first != last) > > + ++call_count; > > + return std::find(first, last, target); > > + }; > > + }; > > + > > + call_count = 0; > > + auto it = std::__for_each_segment(ranges::next(begin, 3), > ranges::next(begin, 6), > > + make_finder(4)); > > + VERIFY( it == ranges::next(begin, 4) ); > > + VERIFY( call_count == 1 ); > > + > > + call_count = 0; > > + it = std::__for_each_segment(ranges::next(begin, 3), > ranges::next(begin, 6), > > + make_finder(99)); > > + VERIFY( it == ranges::next(begin, 6) ); > > + VERIFY( call_count == 1 ); > > + > > + call_count = 0; > > + it = std::__for_each_segment(ranges::next(begin, 1), > ranges::next(begin, 11), > > + make_finder(2)); > > + VERIFY( it == ranges::next(begin, 2) ); > > + VERIFY( call_count == 1 ); > > + > > + call_count = 0; > > + it = std::__for_each_segment(ranges::next(begin, 1), > ranges::next(begin, 11), > > + make_finder(7)); > > + VERIFY( it == ranges::next(begin, 7) ); > > + VERIFY( call_count == 3 ); > > + > > + call_count = 0; > > + it = std::__for_each_segment(ranges::next(begin, 1), > ranges::next(begin, 11), > > + make_finder(9)); > > + VERIFY( it == ranges::next(begin, 9) ); > > + VERIFY( call_count == 4 ); > > + > > + call_count = 0; > > + it = std::__for_each_segment(ranges::next(begin, 1), > ranges::next(begin, 11), > > + make_finder(99)); > > + VERIFY( it == ranges::next(begin, 11) ); > > + VERIFY( call_count == 4 ); > > + > > + call_count = 0; > > + it = std::__for_each_segment(ranges::next(begin, 1), end, > make_finder(99)); > > + VERIFY( it == end ); > > + VERIFY( call_count == 4 ); > > +} > > + > > +int > > +main() > > +{ > > + test01(); > > +} > > diff --git > a/libstdc++-v3/testsuite/std/ranges/concat/for_each_segment.cc > b/libstdc++-v3/testsuite/std/ranges/concat/for_each_segment.cc > > new file mode 100644 > > index 000000000000..a74372b50456 > > --- /dev/null > > +++ b/libstdc++-v3/testsuite/std/ranges/concat/for_each_segment.cc > > @@ -0,0 +1,67 @@ > > +// { dg-do run { target c++26 } } > > + > > +#include <ranges> > > +#include <vector> > > +#include <algorithm> > > +#include <testsuite_hooks.h> > > + > > +namespace ranges = std::ranges; > > + > > +void > > +test01() > > +{ > > + // 4 discrete vectors serving as segments > > + std::vector<int> v0 = {0, 1, 2}; // Segment 0 > > + std::vector<int> v1 = {3, 4, 5}; // Segment 1 > > + std::vector<int> v2 = {6, 7, 8}; // Segment 2 > > + std::vector<int> v3 = {9, 10, 11}; // Segment 3 > > + > > + auto cv = std::views::concat(v0, v1, v2, v3); > > + std::__segmented_iterator auto begin = cv.begin(); > > + std::__segmented_iterator auto end = cv.end(); > > + > > + static int call_count = 0; > > + auto make_finder = [](int target) { > > + return [target](auto first, auto last) { > > + if (first != last) > > + ++call_count; > > + return std::find(first, last, target); > > + }; > > + }; > > + > > + call_count = 0; > > + auto it = std::__for_each_segment(begin + 3, begin + 6, > make_finder(4)); > > + VERIFY( it == begin + 4 ); > > + VERIFY( call_count == 1 ); > > + > > + call_count = 0; > > + it = std::__for_each_segment(begin + 3, begin + 6, > make_finder(99)); > > + VERIFY( it == begin + 6 ); > > + VERIFY( call_count == 1 ); > > + > > + call_count = 0; > > + it = std::__for_each_segment(begin + 1, begin + 11, > make_finder(2)); > > + VERIFY( it == begin + 2 ); > > + VERIFY( call_count == 1 ); > > + > > + call_count = 0; > > + it = std::__for_each_segment(begin + 1, begin + 11, > make_finder(7)); > > + VERIFY( it == begin + 7 ); > > + VERIFY( call_count == 3 ); > > + > > + call_count = 0; > > + it = std::__for_each_segment(begin + 1, begin + 11, > make_finder(9)); > > + VERIFY( it == begin + 9 ); > > + VERIFY( call_count == 4 ); > > + > > + call_count = 0; > > + it = std::__for_each_segment(begin + 1, end, make_finder(99)); > > + VERIFY( it == end ); > > + VERIFY( call_count == 4 ); > > +} > > + > > +int > > +main() > > +{ > > + test01(); > > +} > > -- > > 2.55.0.141.g55526a1826 > > > > > > >
