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.
