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.
