[PATCH 1/2] libstdc++: Introduce notion of segmented iterators
Patrick Palka
ppalka@redhat.com
Tue Jul 14 04:29:47 GMT 2026
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 | 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
More information about the Libstdc++
mailing list