Tested on x86_64-pc-linux-gnu, does this look OK for trunk?

Btw, any thoughts on PR105611 which reports std::shift_left/right's use
of the three-parameter version of ranges::next (on legacy iterators) is
sketchy?  Should we define a three-parameter std::__next analog for
legacy iterators and use that instead?

-- >8 --

The implementation is essentially a copy of std::shift_left/right
(defined directly above) with the following changes:

 - check bidirectional_iterator instead of iterator_category
 - for shift_left, return {__first, X} instead of X
 - for shift_right, return {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, makes the code less readable, and introduces
   subtle use-after-move bugs in some code paths

In passing guard the std::shift_left/right implementations with
__glibcxx_shift as well.

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.
        * 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.
---
 libstdc++-v3/include/bits/ranges_algo.h       | 121 ++++++++++++++++++
 libstdc++-v3/include/bits/version.def         |   4 +
 libstdc++-v3/include/bits/version.h           |   7 +-
 .../25_algorithms/shift_left/constrained.cc   | 105 +++++++++++++++
 .../25_algorithms/shift_right/constrained.cc  | 104 +++++++++++++++
 5 files changed, 340 insertions(+), 1 deletion(-)
 create mode 100644 
libstdc++-v3/testsuite/25_algorithms/shift_left/constrained.cc
 create mode 100644 
libstdc++-v3/testsuite/25_algorithms/shift_right/constrained.cc

diff --git a/libstdc++-v3/include/bits/ranges_algo.h 
b/libstdc++-v3/include/bits/ranges_algo.h
index 5aca6e8d864d..9bb84332d8e1 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -4261,6 +4261,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,
@@ -4351,6 +4352,126 @@ 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
+      {
+       _Iter __lasti = ranges::next(__first, __last);
+       return {_S_impl(__first, __lasti, __n), __lasti};
+      }
+
+    template<typename _Iter>
+      static constexpr _Iter
+      _S_impl(_Iter __first, _Iter __last, iter_difference_t<_Iter> __n)
+      {
+       __glibcxx_assert(__n >= 0);
+       if (__n == 0)
+         return __first;
+
+       if constexpr (bidirectional_iterator<_Iter>)
+         {
+           auto __mid = ranges::next(__last, -__n, __first);
+           if (__mid == __first)
+             return __last;
+
+           return ranges::move_backward(__first, __mid, __last).out;
+         }
+       else
+         {
+           auto __result = ranges::next(__first, __n, __last);
+           if (__result == __last)
+             return __last;
+
+           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.
+                   ranges::move(__first, __dest_head, __result);
+                   return __result;
+                 }
+               ++__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;
+                       ranges::move(__first, __cursor, __dest_head);
+                       return __result;
+                     }
+                   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 880586e91260..917806e9a9a8 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 4300adb22762..ca3b062dfc61 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/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>();
+}
-- 
2.50.0.131.gcf6f63ea6b

Reply via email to