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