diff options
author | Patrick Palka <ppalka@redhat.com> | 2020-02-21 13:55:01 -0500 |
---|---|---|
committer | Patrick Palka <ppalka@redhat.com> | 2020-02-24 10:08:57 -0500 |
commit | c5eab4ed45e9762dfb8a58d2b5672d358467ad89 (patch) | |
tree | ed6aeb75a5597310ddc61c3da5fd070698b5ab8f /libstdc++-v3/include | |
parent | 027a3f1c38727a1ea0969088b0680b2f6bb1e977 (diff) | |
download | gcc-c5eab4ed45e9762dfb8a58d2b5672d358467ad89.zip gcc-c5eab4ed45e9762dfb8a58d2b5672d358467ad89.tar.gz gcc-c5eab4ed45e9762dfb8a58d2b5672d358467ad89.tar.bz2 |
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.
Diffstat (limited to 'libstdc++-v3/include')
-rw-r--r-- | libstdc++-v3/include/bits/ranges_algo.h | 92 |
1 files changed, 92 insertions, 0 deletions
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 7de1072..7d7dbf0 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -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 (__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); + if (__n == 0) + return __first; + + using _Cat = iterator_traits<ForwardIterator>::iterator_category; + if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) + { + auto __mid = ranges::next(__last, -__n, __first); + if (__mid == __first) + return __last; + + return std::move_backward(std::move(__first), std::move(__mid), + std::move(__last)); + } + else + { + auto __result = ranges::next(__first, __n, __last); + if (__result == __last) + return __last; + + auto __dest_head = __first, __dest_tail = __result; + while (__dest_head != __result) + { + if (__dest_tail == __last) + { + // If we get here, then we must have + // 2*n >= distance(__first, __last) + // i.e. we are shifting out at least half of the range. In + // this case we can safely perform the shift with a single + // move. + std::move(std::move(__first), std::move(__dest_head), + std::move(__result)); + return __result; + } + ++__dest_head; + ++__dest_tail; + } + + for (;;) + { + // At the start of each iteration of this outer loop, the range + // [__first, __result) contains those elements that after shifting + // the whole range right by __n, should end up in + // [__dest_head, __dest_tail) in order. + + // The below inner loop swaps the elements of [__first, __result) + // and [__dest_head, __dest_tail), while simultaneously shifting + // the latter range by __n. + auto __cursor = __first; + while (__cursor != __result) + { + if (__dest_tail == __last) + { + // At this point the ranges [__first, result) and + // [__dest_head, dest_tail) are disjoint, so we can safely + // move the remaining elements. + __dest_head = std::move(__cursor, __result, + std::move(__dest_head)); + std::move(std::move(__first), std::move(__cursor), + std::move(__dest_head)); + return __result; + } + std::iter_swap(__cursor, __dest_head); + ++__dest_head; + ++__dest_tail; + ++__cursor; + } + } + } + } + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // concepts |