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

[Jonathan Wakely]

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.