[PATCH] libstdc++: P0769R2 Add shift to <algorithm>

[Patrick Palka]

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.