Re: [PATCH v2 1/2] libstdc++: Introduce segmented iterator concept and traversal

On Tue, 21 Jul 2026 at 04:35, Patrick Palka <[email protected]> wrote:
>
> Changes in v2:
>   - Declare __for_each_segment constexpr in C++ >= 14
>   - Change __enable_for_each_segment SFINAE helper to be a variable
>     template
>   - Debug iterator support: a _Safe_iterator of a segmented iterator
>     is segmented

OK for trunk, thanks!

>
> -- >8 --
>
> 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.
>
> 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    |  21 ++++
>  .../include/bits/stl_iterator_base_types.h    |  24 ++++-
>  libstdc++-v3/include/debug/safe_iterator.h    |  13 +++
>  libstdc++-v3/include/std/ranges               | 100 ++++++++++++++++++
>  .../23_containers/deque/for_each_segment.cc   |  74 +++++++++++++
>  .../ranges/adaptors/join/for_each_segment.cc  |  80 ++++++++++++++
>  .../std/ranges/concat/for_each_segment.cc     |  67 ++++++++++++
>  8 files changed, 415 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..e6c10601432b 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,26 @@ 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
> +    constexpr
> +    __enable_if_t<__enable_for_each_segment<_Iter>, _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..f2abd28e2417 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,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      { enum { __value = __is_base_of(random_access_iterator_tag, _Cat) }; };
>  #endif
>
> +#pragma GCC diagnostic push
> +#pragma GCC diagnostic ignored "-Wc++14-extensions" // variable templates
> +  template<typename _Iter, typename = void>
> +    const bool __enable_for_each_segment = false;
> +
> +  template<typename _Iter>
> +    const bool __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
> +      > = true;
> +#pragma GCC diagnostic pop
> +
> +#if __cpp_lib_concepts
> +  template<typename _Iter>
> +    concept __segmented_iterator = __enable_for_each_segment<_Iter>;
> +#endif
> +
>    /// @endcond
>    /// @}
>
> diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
> index ceda5575a523..8c049961cca1 100644
> --- a/libstdc++-v3/include/debug/safe_iterator.h
> +++ b/libstdc++-v3/include/debug/safe_iterator.h
> @@ -582,6 +582,19 @@ namespace __gnu_debug
>           return __lhs.base() != __rhs.base();
>         }
>  #endif // three-way comparison
> +
> +      template<typename _Fn>
> +       static _GLIBCXX14_CONSTEXPR _Self
> +       _S_for_each_segment(_Self __first, _Self __last, _Fn __func)
> +       {
> +         __glibcxx_check_valid_range(__first, __last);
> +         _Iterator __ret
> +           = _Iterator::_S_for_each_segment(__first.base(), __last.base(), __func);
> +         return _Self(__ret, __first._M_sequence);
> +       }
> +
> +      static const bool _S_enable_for_each_segment
> +       = std::__enable_for_each_segment<_Iterator>;
>      };
>
>    template<typename _Iterator, typename _Sequence>
> diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
> index f89907d3e10e..95319a295ac4 100644
> --- a/libstdc++-v3/include/std/ranges
> +++ b/libstdc++-v3/include/std/ranges
> @@ -3149,6 +3149,13 @@ 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 +3279,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 +10396,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) -> _Iterator {
> +                 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.329.g48bbf81c29
>