https://gcc.gnu.org/g:2a56f3c539b782b15ee76d5752921800ccc53eef
commit r16-2042-g2a56f3c539b782b15ee76d5752921800ccc53eef
Author: Patrick Palka <ppa...@redhat.com>
Date: Sun Jul 6 14:49:34 2025 -0400
libstdc++: Implement ranges::shift_left/right from P2440R1
The implementation is just a copy of std::shift_left/right with the
following changes:
- check bidirectional_iterator instead of iterator_category
- cope with __last being a distinct sentinel type
- for shift_left, return the subrange {__first, X} instead of X
- for shift_right, return the subrange {X, ranges::next(__first, __last)}
instead of X
- use the ranges:: versions of move_backward, move and iter_swap
- don't bother std::move'ing any iterators, it's unnecessary since all
iterators are forward, it's visually noisy, and in earlier versions
of this patch it introduced subtle use-after-move bugs
In passing also use the __glibcxx_shift macro to guard the
std::shift_left/right implementations.
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (shift_left, shift_right): Guard
with __glibcxx_shift >= 201806L.
(ranges::__shift_left_fn, ranges::shift_left): Define for C++23.
(ranges::__shift_right_fn, ranges::shift_right): Likewise.
* include/bits/version.def (shift): Update for C++23.
* include/bits/version.h: Regenerate.
* src/c++23/std.cc.in: Add ranges::shift_left/right.
* testsuite/25_algorithms/shift_left/constrained.cc: New test,
based off of 1.cc.
* testsuite/25_algorithms/shift_right/constrained.cc: New test,
based off of 1.cc.
Reviewed-by: Jonathan Wakely <jwak...@redhat.com>
Diff:
---
libstdc++-v3/include/bits/ranges_algo.h | 115 +++++++++++++++++++++
libstdc++-v3/include/bits/version.def | 4 +
libstdc++-v3/include/bits/version.h | 7 +-
libstdc++-v3/src/c++23/std.cc.in | 8 +-
.../25_algorithms/shift_left/constrained.cc | 105 +++++++++++++++++++
.../25_algorithms/shift_right/constrained.cc | 104 +++++++++++++++++++
6 files changed, 340 insertions(+), 3 deletions(-)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h
b/libstdc++-v3/include/bits/ranges_algo.h
index cf369c5d4dde..9f8945a7133a 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -5218,6 +5218,7 @@ namespace ranges
#endif // __glibcxx_ranges_fold
} // namespace ranges
+#if __glibcxx_shift >= 201806L // C++ >= 20
template<typename _ForwardIterator>
constexpr _ForwardIterator
shift_left(_ForwardIterator __first, _ForwardIterator __last,
@@ -5308,6 +5309,120 @@ namespace ranges
}
}
}
+#endif
+
+namespace ranges
+{
+#if __glibcxx_shift >= 202202L // C++ >= 23
+ struct __shift_left_fn
+ {
+ template<permutable _Iter, sentinel_for<_Iter> _Sent>
+ constexpr subrange<_Iter>
+ operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __n)
const
+ {
+ __glibcxx_assert(__n >= 0);
+ if (__n == 0)
+ return {__first, ranges::next(__first, __last)};
+
+ auto __mid = ranges::next(__first, __n, __last);
+ if (__mid == __last)
+ return {__first, __first};
+ return {__first, ranges::move(__mid, __last, __first).out};
+ }
+
+ template<forward_range _Range>
+ requires permutable<iterator_t<_Range>>
+ constexpr borrowed_subrange_t<_Range>
+ operator()(_Range&& __r, range_difference_t<_Range> __n) const
+ { return (*this)(ranges::begin(__r), ranges::end(__r), __n); }
+ };
+
+ inline constexpr __shift_left_fn shift_left{};
+
+ struct __shift_right_fn
+ {
+ template<permutable _Iter, sentinel_for<_Iter> _Sent>
+ constexpr subrange<_Iter>
+ operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __n)
const
+ {
+ __glibcxx_assert(__n >= 0);
+ if (__n == 0)
+ return {__first, ranges::next(__first, __last)};
+
+ if constexpr (bidirectional_iterator<_Iter> && same_as<_Iter, _Sent>)
+ {
+ auto __mid = ranges::next(__last, -__n, __first);
+ if (__mid == __first)
+ return {__last, __last};
+
+ return {ranges::move_backward(__first, __mid, __last).out, __last};
+ }
+ else
+ {
+ auto __result = ranges::next(__first, __n, __last);
+ if (__result == __last)
+ return {__result, __result};
+
+ auto __dest_head = __first, __dest_tail = __result;
+ while (__dest_head != __result)
+ {
+ if (__dest_tail == __last)
+ {
+ // If we get here, then we must have
+ // 2*n >= distance(__first, __last)
+ // i.e. we are shifting out at least half of the range. In
+ // this case we can safely perform the shift with a single
+ // move.
+ auto __lasti = ranges::move(__first, __dest_head,
__result).out;
+ // __glibcxx_assert(__lasti == __last);
+ return {__result, __lasti};
+ }
+ ++__dest_head;
+ ++__dest_tail;
+ }
+
+ for (;;)
+ {
+ // At the start of each iteration of this outer loop, the range
+ // [__first, __result) contains those elements that after
shifting
+ // the whole range right by __n, should end up in
+ // [__dest_head, __dest_tail) in order.
+
+ // The below inner loop swaps the elements of [__first,
__result)
+ // and [__dest_head, __dest_tail), while simultaneously shifting
+ // the latter range by __n.
+ auto __cursor = __first;
+ while (__cursor != __result)
+ {
+ if (__dest_tail == __last)
+ {
+ // At this point the ranges [__first, result) and
+ // [__dest_head, dest_tail) are disjoint, so we can
safely
+ // move the remaining elements.
+ __dest_head = ranges::move(__cursor, __result,
__dest_head).out;
+ auto __lasti = ranges::move(__first, __cursor,
__dest_head).out;
+ // __glibcxx_assert(__lasti == __last);
+ return {__result, __lasti};
+ }
+ ranges::iter_swap(__cursor, __dest_head);
+ ++__dest_head;
+ ++__dest_tail;
+ ++__cursor;
+ }
+ }
+ }
+ }
+
+ template<forward_range _Range>
+ requires permutable<iterator_t<_Range>>
+ constexpr borrowed_subrange_t<_Range>
+ operator()(_Range&& __r, range_difference_t<_Range> __n) const
+ { return (*this)(ranges::begin(__r), ranges::end(__r), __n); }
+ };
+
+ inline constexpr __shift_right_fn shift_right{};
+#endif // C++23
+} // namespace ranges
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/include/bits/version.def
b/libstdc++-v3/include/bits/version.def
index 5d5758bf2033..64f8190d240b 100644
--- a/libstdc++-v3/include/bits/version.def
+++ b/libstdc++-v3/include/bits/version.def
@@ -1091,6 +1091,10 @@ ftms = {
ftms = {
name = shift;
+ values = {
+ v = 202202;
+ cxxmin = 23;
+ };
values = {
v = 201806;
cxxmin = 20;
diff --git a/libstdc++-v3/include/bits/version.h
b/libstdc++-v3/include/bits/version.h
index 2b00e8419b3a..744246a9938a 100644
--- a/libstdc++-v3/include/bits/version.h
+++ b/libstdc++-v3/include/bits/version.h
@@ -1224,7 +1224,12 @@
#undef __glibcxx_want_constexpr_utility
#if !defined(__cpp_lib_shift)
-# if (__cplusplus >= 202002L)
+# if (__cplusplus >= 202100L)
+# define __glibcxx_shift 202202L
+# if defined(__glibcxx_want_all) || defined(__glibcxx_want_shift)
+# define __cpp_lib_shift 202202L
+# endif
+# elif (__cplusplus >= 202002L)
# define __glibcxx_shift 201806L
# if defined(__glibcxx_want_all) || defined(__glibcxx_want_shift)
# define __cpp_lib_shift 201806L
diff --git a/libstdc++-v3/src/c++23/std.cc.in b/libstdc++-v3/src/c++23/std.cc.in
index 483b6c62443c..86e6d88904b3 100644
--- a/libstdc++-v3/src/c++23/std.cc.in
+++ b/libstdc++-v3/src/c++23/std.cc.in
@@ -278,10 +278,14 @@ export namespace std
}
using std::shift_left;
namespace ranges
- {}
+ {
+ using std::ranges::shift_left;
+ }
using std::shift_right;
namespace ranges
- {}
+ {
+ using std::ranges::shift_right;
+ }
using std::sort;
namespace ranges
{
diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_left/constrained.cc
b/libstdc++-v3/testsuite/25_algorithms/shift_left/constrained.cc
new file mode 100644
index 000000000000..73d061439885
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/shift_left/constrained.cc
@@ -0,0 +1,105 @@
+// Copyright (C) 2020-2025 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++23 } }
+// This test is based on shift_left/1.cc.
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_range;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+struct X
+{
+ int a = -1;
+ bool moved_from = false;
+
+ X() = default;
+
+ X(int a)
+ : a(a)
+ { }
+
+ X(const X&) = delete;
+ X& operator=(const X&) = delete;
+
+ X(X&& other)
+ {
+ if (this != &other)
+ *this = std::move(other);
+ }
+
+ X&
+ operator=(X&& other)
+ {
+ a = other.a;
+ other.moved_from = true;
+ moved_from = false;
+ return *this;
+ }
+};
+
+template<int N, template<typename> typename Wrapper>
+void
+test01()
+{
+ for (int n = 0; n < N+5; n++)
+ {
+ X x[N];
+ for (int i = 0; i < N; i++)
+ x[i] = X{i};
+ test_range<X, Wrapper> rx(x);
+ auto [first,out] = std::ranges::shift_left(rx.begin(), rx.end(), n);
+ VERIFY( first == rx.begin() );
+ if (n < N)
+ {
+ VERIFY( out.ptr == x+(N-n) );
+ for (int i = 0; i < N-n; i++)
+ {
+ VERIFY( x[i].a == n+i );
+ VERIFY( !x[i].moved_from );
+ }
+ for (int i = std::max(n, N-n); i < N; i++)
+ VERIFY( x[i].moved_from );
+ }
+ else
+ {
+ VERIFY( out.ptr == x );
+ for (int i = 0; i < N; i++)
+ {
+ VERIFY( x[i].a == i );
+ VERIFY( !x[i].moved_from );
+ }
+ }
+ }
+}
+
+int
+main()
+{
+ test01<23, forward_iterator_wrapper>();
+ test01<23, bidirectional_iterator_wrapper>();
+ test01<23, random_access_iterator_wrapper>();
+
+ test01<24, forward_iterator_wrapper>();
+ test01<24, bidirectional_iterator_wrapper>();
+ test01<24, random_access_iterator_wrapper>();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_right/constrained.cc
b/libstdc++-v3/testsuite/25_algorithms/shift_right/constrained.cc
new file mode 100644
index 000000000000..0d53707237e4
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/shift_right/constrained.cc
@@ -0,0 +1,104 @@
+// Copyright (C) 2020-2025 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++23 } }
+// This test is based on shift_right/1.cc.
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_range;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+struct X
+{
+ int a = -1;
+ bool moved_from = false;
+
+ X() = default;
+
+ X(int a)
+ : a(a)
+ { }
+
+ X(const X&) = delete;
+ X& operator=(const X&) = delete;
+
+ X(X&& other)
+ {
+ if (this != &other)
+ *this = std::move(other);
+ }
+
+ X&
+ operator=(X&& other)
+ {
+ a = other.a;
+ other.moved_from = true;
+ moved_from = false;
+ return *this;
+ }
+};
+
+template<int N, template<typename> typename Wrapper>
+void
+test01()
+{
+ for (int n = 0; n < N+5; n++)
+ {
+ X x[N];
+ for (int i = 0; i < N; i++)
+ x[i] = X(i);
+ test_range<X, Wrapper> rx(x);
+ auto [out,last] = std::ranges::shift_right(rx.begin(), rx.end(), n);
+ VERIFY( last == rx.end() );
+ if (n < N)
+ {
+ VERIFY( out.ptr == x+n );
+ for (int i = n; i < N; i++)
+ VERIFY( x[i].a == i-n );
+ for (int i = 0; i < std::min(n, N-n); i++)
+ VERIFY( x[i].moved_from );
+ for (int i = std::min(n, N-n); i < std::max(n, N-n); i++)
+ VERIFY( !x[i].moved_from );
+ }
+ else
+ {
+ VERIFY( out.ptr == x+N );
+ for (int i = 0; i < N; i++)
+ {
+ VERIFY( x[i].a == i );
+ VERIFY( !x[i].moved_from );
+ }
+ }
+ }
+}
+
+int
+main()
+{
+ test01<23, forward_iterator_wrapper>();
+ test01<23, bidirectional_iterator_wrapper>();
+ test01<23, random_access_iterator_wrapper>();
+
+ test01<24, forward_iterator_wrapper>();
+ test01<24, bidirectional_iterator_wrapper>();
+ test01<24, random_access_iterator_wrapper>();
+}
