| Message ID | 20200221192922.2412286-1-ppalka@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | libstdc++: P0769R2 Add shift to <algorithm> | expand |
On Fri, 21 Feb 2020, Patrick Palka wrote: > This patch adds std::shift_left and std::shift_right. Alhough these are > STL-style algos, they are nonetheless placed in <bits/ranges_algo.h> because > they make use of some functions in the ranges namespace that are more easily > reachable from <bits/ranges_algo.h> than from <bits/stl_algo.h>, namely > ranges::next and ranges::swap_ranges. > > This implementation of std::shift_right for non-bidirectional iterators deviates > from the reference implementation a bit. The main difference is that this > implementation is significantly simpler, and yet saves around n/2 additional > iterator increments and n/2 iter_moves at the cost of around n/2 additional > iter_swaps (where n is the shift amount). On second thought, this simplification of shift_right is a not a good idea because the objects that were shifted and that are no longer a part of the new range do not end up in a moved-from state at the end of the algorithm. Here is a version of the patch that instead adds something akin to the reference implementation and improves the tests to verify this moved-from property of both algorithms. -- >8 -- Subject: [PATCH] libstdc++: P0769R2 Add shift to <algorithm> This patch adds std::shift_left and std::shift_right as per P0769R2. Alhough these are STL-style algos, this patch places them in <bits/ranges_algo.h> because they make use of some functions in the ranges namespace that are more easily reachable from <bits/ranges_algo.h> than from <bits/stl_algo.h>, namely ranges::next. In order to place these algos in <bits/stl_algo.h>, we would need to include <bits/range_access.h> from <bits/stl_algo.h> which would undesirably increase the size of <bits/stl_algo.h>. libstdc++-v3/ChangeLog: P0769R2 Add shift to <algorithm> * include/bits/ranges_algo.h (shift_left, shift_right): New. * testsuite/25_algorithms/shift_left/1.cc: New test. * testsuite/25_algorithms/shift_right/1.cc: New test. --- libstdc++-v3/include/bits/ranges_algo.h | 92 ++++++++++++++++ .../testsuite/25_algorithms/shift_left/1.cc | 104 ++++++++++++++++++ .../testsuite/25_algorithms/shift_right/1.cc | 103 +++++++++++++++++ 3 files changed, 299 insertions(+) create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 7de1072abf0..7d7dbf04103 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3683,6 +3683,98 @@ namespace ranges inline constexpr __prev_permutation_fn prev_permutation{}; } // namespace ranges + + template<class ForwardIterator> + constexpr ForwardIterator + shift_left(ForwardIterator __first, ForwardIterator __last, + typename iterator_traits<ForwardIterator>::difference_type __n) + { + __glibcxx_assert(__n >= 0); + if (__n == 0) + return __last; + + auto __mid = ranges::next(__first, __n, __last); + if (__mid == __last) + return __first; + return std::move(std::move(__mid), std::move(__last), std::move(__first)); + } + + template<class ForwardIterator> + constexpr ForwardIterator + shift_right(ForwardIterator __first, ForwardIterator __last, + typename iterator_traits<ForwardIterator>::difference_type __n) + { + __glibcxx_assert(__n >= 0); + if (__n == 0) + return __first; + + using _Cat = iterator_traits<ForwardIterator>::iterator_category; + if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) + { + auto __mid = ranges::next(__last, -__n, __first); + if (__mid == __first) + return __last; + + return std::move_backward(std::move(__first), std::move(__mid), + std::move(__last)); + } + 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. + std::move(std::move(__first), std::move(__dest_head), + std::move(__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 = std::move(__cursor, __result, + std::move(__dest_head)); + std::move(std::move(__first), std::move(__cursor), + std::move(__dest_head)); + return __result; + } + std::iter_swap(__cursor, __dest_head); + ++__dest_head; + ++__dest_tail; + ++__cursor; + } + } + } + } + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // concepts diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc b/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc new file mode 100644 index 00000000000..f7a716e0563 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc @@ -0,0 +1,104 @@ +// Copyright (C) 2020 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-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_container; +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_container<X, Wrapper> cx(x); + auto out = std::shift_left(cx.begin(), cx.end(), n); + 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/1.cc b/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc new file mode 100644 index 00000000000..cf736ea91b1 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc @@ -0,0 +1,103 @@ +// Copyright (C) 2020 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-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_container; +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_container<X, Wrapper> cx(x); + auto out = std::shift_right(cx.begin(), cx.end(), n); + 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>(); +}
On 21/02/20 16:12 -0500, Patrick Palka wrote: >On Fri, 21 Feb 2020, Patrick Palka wrote: > >> This patch adds std::shift_left and std::shift_right. Alhough these are >> STL-style algos, they are nonetheless placed in <bits/ranges_algo.h> because >> they make use of some functions in the ranges namespace that are more easily >> reachable from <bits/ranges_algo.h> than from <bits/stl_algo.h>, namely >> ranges::next and ranges::swap_ranges. >> >> This implementation of std::shift_right for non-bidirectional iterators deviates >> from the reference implementation a bit. The main difference is that this >> implementation is significantly simpler, and yet saves around n/2 additional >> iterator increments and n/2 iter_moves at the cost of around n/2 additional >> iter_swaps (where n is the shift amount). > >On second thought, this simplification of shift_right is a not a good >idea because the objects that were shifted and that are no longer a part >of the new range do not end up in a moved-from state at the end of the >algorithm. Here is a version of the patch that instead adds something >akin to the reference implementation and improves the tests to verify >this moved-from property of both algorithms. > >-- >8 -- > >Subject: [PATCH] libstdc++: P0769R2 Add shift to <algorithm> > >This patch adds std::shift_left and std::shift_right as per P0769R2. Alhough >these are STL-style algos, this patch places them in <bits/ranges_algo.h> >because they make use of some functions in the ranges namespace that are more >easily reachable from <bits/ranges_algo.h> than from <bits/stl_algo.h>, namely >ranges::next. In order to place these algos in <bits/stl_algo.h>, we would need >to include <bits/range_access.h> from <bits/stl_algo.h> which would undesirably >increase the size of <bits/stl_algo.h>. > >libstdc++-v3/ChangeLog: > > P0769R2 Add shift to <algorithm> > * include/bits/ranges_algo.h (shift_left, shift_right): New. > * testsuite/25_algorithms/shift_left/1.cc: New test. > * testsuite/25_algorithms/shift_right/1.cc: New test. >--- > libstdc++-v3/include/bits/ranges_algo.h | 92 ++++++++++++++++ > .../testsuite/25_algorithms/shift_left/1.cc | 104 ++++++++++++++++++ > .../testsuite/25_algorithms/shift_right/1.cc | 103 +++++++++++++++++ > 3 files changed, 299 insertions(+) > create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc > create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc > >diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h >index 7de1072abf0..7d7dbf04103 100644 >--- a/libstdc++-v3/include/bits/ranges_algo.h >+++ b/libstdc++-v3/include/bits/ranges_algo.h These new algos should go in <bits/stl_algo.h> because they're not in namespace ranges. >@@ -3683,6 +3683,98 @@ namespace ranges > inline constexpr __prev_permutation_fn prev_permutation{}; > > } // namespace ranges >+ >+ template<class ForwardIterator> >+ constexpr ForwardIterator >+ shift_left(ForwardIterator __first, ForwardIterator __last, >+ typename iterator_traits<ForwardIterator>::difference_type __n) >+ { >+ __glibcxx_assert(__n >= 0); If I'm reading the current draft correctly, n < 0 is allowed (and does nothing) so we shouldn't assert here. >+ if (__n == 0) >+ return __last; >+ >+ auto __mid = ranges::next(__first, __n, __last); >+ if (__mid == __last) >+ return __first; >+ return std::move(std::move(__mid), std::move(__last), std::move(__first)); >+ } >+ >+ template<class ForwardIterator> >+ constexpr ForwardIterator >+ shift_right(ForwardIterator __first, ForwardIterator __last, >+ typename iterator_traits<ForwardIterator>::difference_type __n) >+ { >+ __glibcxx_assert(__n >= 0); Same here.
On Mon, 24 Feb 2020, Jonathan Wakely wrote: > On 21/02/20 16:12 -0500, Patrick Palka wrote: > > On Fri, 21 Feb 2020, Patrick Palka wrote: > > > > > This patch adds std::shift_left and std::shift_right. Alhough these are > > > STL-style algos, they are nonetheless placed in <bits/ranges_algo.h> > > > because > > > they make use of some functions in the ranges namespace that are more > > > easily > > > reachable from <bits/ranges_algo.h> than from <bits/stl_algo.h>, namely > > > ranges::next and ranges::swap_ranges. > > > > > > This implementation of std::shift_right for non-bidirectional iterators > > > deviates > > > from the reference implementation a bit. The main difference is that this > > > implementation is significantly simpler, and yet saves around n/2 > > > additional > > > iterator increments and n/2 iter_moves at the cost of around n/2 > > > additional > > > iter_swaps (where n is the shift amount). > > > > On second thought, this simplification of shift_right is a not a good > > idea because the objects that were shifted and that are no longer a part > > of the new range do not end up in a moved-from state at the end of the > > algorithm. Here is a version of the patch that instead adds something > > akin to the reference implementation and improves the tests to verify > > this moved-from property of both algorithms. > > > > -- >8 -- > > > > Subject: [PATCH] libstdc++: P0769R2 Add shift to <algorithm> > > > > This patch adds std::shift_left and std::shift_right as per P0769R2. > > Alhough > > these are STL-style algos, this patch places them in <bits/ranges_algo.h> > > because they make use of some functions in the ranges namespace that are > > more > > easily reachable from <bits/ranges_algo.h> than from <bits/stl_algo.h>, > > namely > > ranges::next. In order to place these algos in <bits/stl_algo.h>, we would > > need > > to include <bits/range_access.h> from <bits/stl_algo.h> which would > > undesirably > > increase the size of <bits/stl_algo.h>. > > > > libstdc++-v3/ChangeLog: > > > > P0769R2 Add shift to <algorithm> > > * include/bits/ranges_algo.h (shift_left, shift_right): New. > > * testsuite/25_algorithms/shift_left/1.cc: New test. > > * testsuite/25_algorithms/shift_right/1.cc: New test. > > --- > > libstdc++-v3/include/bits/ranges_algo.h | 92 ++++++++++++++++ > > .../testsuite/25_algorithms/shift_left/1.cc | 104 ++++++++++++++++++ > > .../testsuite/25_algorithms/shift_right/1.cc | 103 +++++++++++++++++ > > 3 files changed, 299 insertions(+) > > create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc > > create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc > > > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h > > b/libstdc++-v3/include/bits/ranges_algo.h > > index 7de1072abf0..7d7dbf04103 100644 > > --- a/libstdc++-v3/include/bits/ranges_algo.h > > +++ b/libstdc++-v3/include/bits/ranges_algo.h > > These new algos should go in <bits/stl_algo.h> because they're not in > namespace ranges. Since their implementation uses ranges::next(__it, __n, __last), putting them in <bits/stl_algo.h> means we would need to include <bits/range_access.h> from <bits/stl_algo.h>, or reimplement the ranges::next() routine in <bits/stl_algo.h> (and its random access iterator optimization) it seems. > > > @@ -3683,6 +3683,98 @@ namespace ranges > > inline constexpr __prev_permutation_fn prev_permutation{}; > > > > } // namespace ranges > > + > > + template<class ForwardIterator> > > + constexpr ForwardIterator > > + shift_left(ForwardIterator __first, ForwardIterator __last, > > + typename iterator_traits<ForwardIterator>::difference_type __n) > > + { > > + __glibcxx_assert(__n >= 0); > > If I'm reading the current draft correctly, n < 0 is allowed (and does > nothing) so we shouldn't assert here. From what I can tell, this is changed by P1243R4 (Rangify new algorithms) which adds the precondition n >= 0 to these routines. > > > > + if (__n == 0) > > + return __last; > > + > > + auto __mid = ranges::next(__first, __n, __last); > > + if (__mid == __last) > > + return __first; > > + return std::move(std::move(__mid), std::move(__last), > > std::move(__first)); > > + } > > + > > + template<class ForwardIterator> > > + constexpr ForwardIterator > > + shift_right(ForwardIterator __first, ForwardIterator __last, > > + typename iterator_traits<ForwardIterator>::difference_type > > __n) > > + { > > + __glibcxx_assert(__n >= 0); > > Same here.
Am Mo., 24. Feb. 2020 um 15:12 Uhr schrieb Patrick Palka <ppalka@redhat.com>: > > On Mon, 24 Feb 2020, Jonathan Wakely wrote: > [...] > > > @@ -3683,6 +3683,98 @@ namespace ranges > > > inline constexpr __prev_permutation_fn prev_permutation{}; > > > > > > } // namespace ranges > > > + > > > + template<class ForwardIterator> > > > + constexpr ForwardIterator > > > + shift_left(ForwardIterator __first, ForwardIterator __last, > > > + typename iterator_traits<ForwardIterator>::difference_type __n) > > > + { > > > + __glibcxx_assert(__n >= 0); > > > > If I'm reading the current draft correctly, n < 0 is allowed (and does > > nothing) so we shouldn't assert here. > > From what I can tell, this is changed by P1243R4 (Rangify new > algorithms) which adds the precondition n >= 0 to these routines. Yes, that's correct. This part of the wording applied the accepted changes of p1233r1. - Daniel
On 24/02/20 09:12 -0500, Patrick Palka wrote: >On Mon, 24 Feb 2020, Jonathan Wakely wrote: > >> On 21/02/20 16:12 -0500, Patrick Palka wrote: >> > On Fri, 21 Feb 2020, Patrick Palka wrote: >> > >> > > This patch adds std::shift_left and std::shift_right. Alhough these are >> > > STL-style algos, they are nonetheless placed in <bits/ranges_algo.h> >> > > because >> > > they make use of some functions in the ranges namespace that are more >> > > easily >> > > reachable from <bits/ranges_algo.h> than from <bits/stl_algo.h>, namely >> > > ranges::next and ranges::swap_ranges. >> > > >> > > This implementation of std::shift_right for non-bidirectional iterators >> > > deviates >> > > from the reference implementation a bit. The main difference is that this >> > > implementation is significantly simpler, and yet saves around n/2 >> > > additional >> > > iterator increments and n/2 iter_moves at the cost of around n/2 >> > > additional >> > > iter_swaps (where n is the shift amount). >> > >> > On second thought, this simplification of shift_right is a not a good >> > idea because the objects that were shifted and that are no longer a part >> > of the new range do not end up in a moved-from state at the end of the >> > algorithm. Here is a version of the patch that instead adds something >> > akin to the reference implementation and improves the tests to verify >> > this moved-from property of both algorithms. >> > >> > -- >8 -- >> > >> > Subject: [PATCH] libstdc++: P0769R2 Add shift to <algorithm> >> > >> > This patch adds std::shift_left and std::shift_right as per P0769R2. >> > Alhough >> > these are STL-style algos, this patch places them in <bits/ranges_algo.h> >> > because they make use of some functions in the ranges namespace that are >> > more >> > easily reachable from <bits/ranges_algo.h> than from <bits/stl_algo.h>, >> > namely >> > ranges::next. In order to place these algos in <bits/stl_algo.h>, we would >> > need >> > to include <bits/range_access.h> from <bits/stl_algo.h> which would >> > undesirably >> > increase the size of <bits/stl_algo.h>. >> > >> > libstdc++-v3/ChangeLog: >> > >> > P0769R2 Add shift to <algorithm> >> > * include/bits/ranges_algo.h (shift_left, shift_right): New. >> > * testsuite/25_algorithms/shift_left/1.cc: New test. >> > * testsuite/25_algorithms/shift_right/1.cc: New test. >> > --- >> > libstdc++-v3/include/bits/ranges_algo.h | 92 ++++++++++++++++ >> > .../testsuite/25_algorithms/shift_left/1.cc | 104 ++++++++++++++++++ >> > .../testsuite/25_algorithms/shift_right/1.cc | 103 +++++++++++++++++ >> > 3 files changed, 299 insertions(+) >> > create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc >> > create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc >> > >> > diff --git a/libstdc++-v3/include/bits/ranges_algo.h >> > b/libstdc++-v3/include/bits/ranges_algo.h >> > index 7de1072abf0..7d7dbf04103 100644 >> > --- a/libstdc++-v3/include/bits/ranges_algo.h >> > +++ b/libstdc++-v3/include/bits/ranges_algo.h >> >> These new algos should go in <bits/stl_algo.h> because they're not in >> namespace ranges. > >Since their implementation uses ranges::next(__it, __n, __last), putting >them in <bits/stl_algo.h> means we would need to include ><bits/range_access.h> from <bits/stl_algo.h>, or reimplement the >ranges::next() routine in <bits/stl_algo.h> (and its random access >iterator optimization) it seems. Ah right. >> > @@ -3683,6 +3683,98 @@ namespace ranges >> > inline constexpr __prev_permutation_fn prev_permutation{}; >> > >> > } // namespace ranges >> > + >> > + template<class ForwardIterator> >> > + constexpr ForwardIterator >> > + shift_left(ForwardIterator __first, ForwardIterator __last, >> > + typename iterator_traits<ForwardIterator>::difference_type __n) >> > + { >> > + __glibcxx_assert(__n >= 0); >> >> If I'm reading the current draft correctly, n < 0 is allowed (and does >> nothing) so we shouldn't assert here. > >From what I can tell, this is changed by P1243R4 (Rangify new >algorithms) which adds the precondition n >= 0 to these routines. Thanks, I forgot that paper still changed shuft_left and shift_right even thogh it didn't add ranges::shift_left and ranges::shift_right. OK for master then, thanks.
On 21/02/2020 20:29, Patrick Palka wrote: > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > index 7de1072abf0..c36afc6e19b 100644 > --- a/libstdc++-v3/include/bits/ranges_algo.h > +++ b/libstdc++-v3/include/bits/ranges_algo.h > @@ -3683,6 +3683,54 @@ namespace ranges > inline constexpr __prev_permutation_fn prev_permutation{}; > > } // namespace ranges > + > + template<class ForwardIterator> > + constexpr ForwardIterator > + shift_left(ForwardIterator __first, ForwardIterator __last, > + typename iterator_traits<ForwardIterator>::difference_type __n) > + { > + __glibcxx_assert(__n >= 0); > + if (__n == 0) > + return __last; > + > + auto __mid = ranges::next(__first, __n, __last); > + if (__mid == __last) > + return __first; > + return std::move(std::move(__mid), std::move(__last), std::move(__first)); > + } > + > + template<class ForwardIterator> > + constexpr ForwardIterator > + shift_right(ForwardIterator __first, ForwardIterator __last, > + typename iterator_traits<ForwardIterator>::difference_type __n) > + { > + __glibcxx_assert(__n >= 0); > + if (__n == 0) > + return __first; > + > + using _Cat = iterator_traits<ForwardIterator>::iterator_category; ^ FYI, the above line causes recent Clang 10 trunk with -std=c++20 to fail due to a "missing" typedef > + if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) > + { > + auto __mid = ranges::next(__last, -__n, __first); > + if (__mid == __first) > + return __last; > + return std::move_backward(std::move(__first), std::move(__mid), > + std::move(__last)); > + } > + else > + { > + auto __result = ranges::next(__first, __n, __last); > + if (__result == __last) > + return __last; > + auto __dest = __result; > + do > + __dest = ranges::swap_ranges(__first, __result, > + std::move(__dest), __last).in2; > + while (__dest != __last); > + return __result; > + } > + } > + > _GLIBCXX_END_NAMESPACE_VERSION > } // namespace std > #endif // concepts
On 02/03/20 10:03 +0100, Stephan Bergmann wrote: >On 21/02/2020 20:29, Patrick Palka wrote: >>diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h >>index 7de1072abf0..c36afc6e19b 100644 >>--- a/libstdc++-v3/include/bits/ranges_algo.h >>+++ b/libstdc++-v3/include/bits/ranges_algo.h >>@@ -3683,6 +3683,54 @@ namespace ranges >> inline constexpr __prev_permutation_fn prev_permutation{}; >> } // namespace ranges >>+ >>+ template<class ForwardIterator> >>+ constexpr ForwardIterator >>+ shift_left(ForwardIterator __first, ForwardIterator __last, >>+ typename iterator_traits<ForwardIterator>::difference_type __n) >>+ { >>+ __glibcxx_assert(__n >= 0); >>+ if (__n == 0) >>+ return __last; >>+ >>+ auto __mid = ranges::next(__first, __n, __last); >>+ if (__mid == __last) >>+ return __first; >>+ return std::move(std::move(__mid), std::move(__last), std::move(__first)); >>+ } >>+ >>+ template<class ForwardIterator> >>+ constexpr ForwardIterator >>+ shift_right(ForwardIterator __first, ForwardIterator __last, >>+ typename iterator_traits<ForwardIterator>::difference_type __n) >>+ { >>+ __glibcxx_assert(__n >= 0); >>+ if (__n == 0) >>+ return __first; >>+ >>+ using _Cat = iterator_traits<ForwardIterator>::iterator_category; > >^ FYI, the above line causes recent Clang 10 trunk with -std=c++20 to >fail due to a "missing" typedef Thanks, fixed by this patch, committed to master now.
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 7de1072abf0..c36afc6e19b 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3683,6 +3683,54 @@ namespace ranges inline constexpr __prev_permutation_fn prev_permutation{}; } // namespace ranges + + template<class ForwardIterator> + constexpr ForwardIterator + shift_left(ForwardIterator __first, ForwardIterator __last, + typename iterator_traits<ForwardIterator>::difference_type __n) + { + __glibcxx_assert(__n >= 0); + if (__n == 0) + return __last; + + auto __mid = ranges::next(__first, __n, __last); + if (__mid == __last) + return __first; + return std::move(std::move(__mid), std::move(__last), std::move(__first)); + } + + template<class ForwardIterator> + constexpr ForwardIterator + shift_right(ForwardIterator __first, ForwardIterator __last, + typename iterator_traits<ForwardIterator>::difference_type __n) + { + __glibcxx_assert(__n >= 0); + if (__n == 0) + return __first; + + using _Cat = iterator_traits<ForwardIterator>::iterator_category; + if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) + { + auto __mid = ranges::next(__last, -__n, __first); + if (__mid == __first) + return __last; + return std::move_backward(std::move(__first), std::move(__mid), + std::move(__last)); + } + else + { + auto __result = ranges::next(__first, __n, __last); + if (__result == __last) + return __last; + auto __dest = __result; + do + __dest = ranges::swap_ranges(__first, __result, + std::move(__dest), __last).in2; + while (__dest != __last); + return __result; + } + } + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // concepts diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc b/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc new file mode 100644 index 00000000000..9bdb843adbc --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc @@ -0,0 +1,67 @@ +// Copyright (C) 2020 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-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_container; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; + +template<int K, template<typename> typename Wrapper> +void +test01() +{ + static_assert(K == 10 || K == 11); + for (int i = 0; i < 15; i++) + { + int x[K]; + for (int t = 0; t < K; t++) + x[t] = t; + test_container<int, Wrapper> cx(x); + auto out = std::shift_left(cx.begin(), cx.end(), i); + if (i < K) + { + VERIFY( out.ptr == x+(K-i) ); + for (int j = i; j < K-i; j++) + VERIFY( x[j] == i+j ); + } + else + { + VERIFY( out.ptr == x ); + for (int j = 0; j < K; j++) + VERIFY( x[j] == j ); + } + } +} + +int +main() +{ + test01<10, forward_iterator_wrapper>(); + test01<10, bidirectional_iterator_wrapper>(); + test01<10, random_access_iterator_wrapper>(); + + test01<11, forward_iterator_wrapper>(); + test01<11, bidirectional_iterator_wrapper>(); + test01<11, random_access_iterator_wrapper>(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc b/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc new file mode 100644 index 00000000000..3ce05ed287b --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc @@ -0,0 +1,67 @@ +// Copyright (C) 2020 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-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_container; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; + +template<int K, template<typename> typename Wrapper> +void +test01() +{ + static_assert(K == 10 || K == 11); + for (int i = 0; i < 15; i++) + { + int x[K]; + for (int t = 0; t < K; t++) + x[t] = t; + test_container<int, Wrapper> cx(x); + auto out = std::shift_right(cx.begin(), cx.end(), i); + if (i < K) + { + VERIFY( out.ptr == x+i ); + for (int j = i; j < K; j++) + VERIFY( x[j] == j-i ); + } + else + { + VERIFY( out.ptr == x+K ); + for (int j = 0; j < K; j++) + VERIFY( x[j] == j ); + } + } +} + +int +main() +{ + test01<10, forward_iterator_wrapper>(); + test01<10, bidirectional_iterator_wrapper>(); + test01<10, random_access_iterator_wrapper>(); + + test01<11, forward_iterator_wrapper>(); + test01<11, bidirectional_iterator_wrapper>(); + test01<11, random_access_iterator_wrapper>(); +}