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.
