Add shift functions (P0769)

[zoecarver]

Summary

Adds shift_right and shift_left functions to algorythems as specified in P0769R2.

In this implementation, I use std::advance to shift the iterators instead of the proposed sample algorithm. This seems to work fine and be much faster, but there may be some reason not to do this which I am unaware of.

The document suggests that _only_ shift_left is a constexpr while all other functions/overloads are not. I think this is a typo, but I can update if needed (edit: emailed to inquire about this).

[mclow.lists]

I don't think that this is right. All advance does is update an iterator. No data is being moved here.

[zoecarver]

Update:
I have re-implemented the shift algorithm. Now it uses a much more similar method to the example given in the paper.

Just so we are all on the same page, here is an example of what this patch does:

T arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto b = std::begin(arr);
auto e = std::end(arr);

auto left = shift_left(b, e, 5); // left = 5,6,7,8,9
auto right = shift_right(b, e, 5); // right = 0,1,2,3,4
auto empty = shift_right(left, left + 10, 5); // empty = <empty>

Thank you @mclow.lists for the tests and help implementing.

[zoecarver]

Fix whitespace.

[zoecarver]

include/algorithm

5733

This needs to be constexpr (same with right_shift)

5736

Negative ranges are supported too.

[zoecarver]

Thoughts on manually (using for loops) decrementing / incrementing iterators vs std::next/std::advance?

include/algorithm

5736

Nevermind, that was an earlier revision. Negative values are UB.

[zoecarver]

Make shift functions constexpr.

[EricWF]

include/algorithm

5739

Can you write explicit braces to make it clear it's an empty loop?

[zoecarver]

include/algorithm

5739

For sure. A lot of the empty loops are formatted like this:

for (...)
    ;

Is that or braces preferred?

[zoecarver]

Fix empty for loop braces

[zoecarver]

Friendly ping. Anything else need to be done on this?

[zoecarver]

Fix spacing / formatting.

[zoecarver]

• valid constexpr
• much simpler implementation
• correct implementation (one that actually works)
• one implementation for all iterators (including forward iterators)
• tests that are more clear (correct on inspection)

[zoecarver]

Fix the complexity of shift_right. The only case where this function is more complex than the standard (assuming shift_left is also updated) is when n is greater than std::distance(first, last) - n.

[ldionne]

libcxx/include/algorithm

644 ↗

(On Diff #212724)

You shouldn't implement the parallel version here, that should be in PSTL.

5693 ↗

(On Diff #212724)

This should just be _LIBCPP_CONSTEXPR since it's a C++20 algorithm anyway.

5724 ↗

(On Diff #212724)

Is this equivalent to std::advance(__first, std::distance(__first, __last) - __n)? If so, why not use that?

5734 ↗

(On Diff #212724)

We're making multiple passes over the whole range to get things like __rbegin. I can't imagine that's the only way of implementing this algorithm, and if so, that was certainly not the intent of the paper.

Did you look at https://github.com/danra/shift_proposal/blob/master/shift_proposal.h?

[zoecarver]

libcxx/include/algorithm

5734 ↗

(On Diff #212724)

I try not to look at the sample implementations, it's more fun that way :) In this case, the implementation is much more performant, so I will implement it (or something close).

[ldionne]

libcxx/include/algorithm

5734 ↗

(On Diff #212724)

I understand, however this is a standard library. Even though it can be fun to implement stuff in the standard library, the primary goal of this software is not to be "fun to implement". Correctness and efficiency should be the primary motivations here -- let's keep that in mind.

I sound boring, I know :-)

include/algorithm

 template <class BidirectionalIterator>
     bool
     prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
 
 template <class BidirectionalIterator, class Compare>
     bool
     prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
 
+template<class ForwardIterator>
+    ForwardIterator shift_left(ForwardIterator first, ForwardIterator last,
+                                         typename iterator_traits<ForwardIterator>::difference_type n);
+template<class ExecutionPolicy, class ForwardIterator>
+    ForwardIterator shift_left(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
+                               typename iterator_traits<ForwardIterator>::difference_type n);
+template<class ForwardIterator>
+    ForwardIterator shift_right(ForwardIterator first, ForwardIterator last,
+                                typename iterator_traits<ForwardIterator>::difference_type n);
+template<class ExecutionPolicy, class ForwardIterator>
+    ForwardIterator shift_right(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
+                                typename iterator_traits<ForwardIterator>::difference_type n);
+
 }  // std
 
 */
 
 #include <__config>
 #include <initializer_list>
 #include <type_traits>
 #include <cstring>

 inline _LIBCPP_INLINE_VISIBILITY
 bool
 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
     return _VSTD::prev_permutation(__first, __last,
                                   __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
 }
 
+template<class _It>
+_It shift_left(_It __first, _It __last, typename iterator_traits<_It>::difference_type __n)
+{
+    auto __size = _VSTD::distance(__first, __last);
+
+    if (__n <= 0 || __size <= 0) return __first;
+
+    auto shift = __n % __size;
+    if (shift < 0) shift += __n;
+
+    _VSTD::advance(__first, shift);
+    _VSTD::advance(__last, shift);
+
+    return __first;
+}
+
+template<class _Ep, class _It>
+_It shift_left(_Ep&&, _It __first, _It __last, typename iterator_traits<_It>::difference_type __n)
+{ return shift_left(__first, __last, __n); }
+
+template<class _It>
+_It shift_right(_It __first, _It __last, typename iterator_traits<_It>::difference_type __n)
+{
+    auto __size = _VSTD::distance(__first, __last);
+
+    if (__n <= 0 || __size <= 0) return __first;
+
+    auto shift = __n % __size;
+    if (shift < 0) shift += __n;
+
+    _VSTD::advance(__first, -shift);
+    _VSTD::advance(__last, -shift);
+
+    return __first;
+}
+
+template<class _Ep, class _It>
+_It shift_right(_Ep&&, _It __first, _It __last, typename iterator_traits<_It>::difference_type __n)
+{ return shift_right(__first, __last, __n); }
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif  // _LIBCPP_ALGORITHM

test/std/algorithms/algorithms.general/shift.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+//    template<class ForwardIterator>
+//    ForwardIterator shift_left(ForwardIterator first, ForwardIterator last,
+//                               typename iterator_traits<ForwardIterator>::difference_type n);
+//    template<class ExecutionPolicy, class ForwardIterator>
+//    ForwardIterator shift_left(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
+//                               typename iterator_traits<ForwardIterator>::difference_type n);
+//    template<class ForwardIterator>
+//    ForwardIterator shift_right(ForwardIterator first, ForwardIterator last,
+//                                typename iterator_traits<ForwardIterator>::difference_type n);
+//    template<class ExecutionPolicy, class ForwardIterator>
+//    ForwardIterator shift_right(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
+//                                typename iterator_traits<ForwardIterator>::difference_type n);
+
+#include <algorithm>
+#include <vector>
+#include <numeric>
+
+template<class T, class It>
+void test(T container, It begin, It end)
+{
+    auto left_check = container[20];
+    auto right_check = container[5];
+
+    auto shifted_container = shift_left(begin, end, 20);
+    assert(left_check == shifted_container[0]);
+    shifted_container = shift_right(shifted_container, shifted_container + 100, 15);
+    assert(right_check == shifted_container[0]);
+}
+
+struct E
+{
+    unsigned x;
+    bool operator==(E rhs) { return x == rhs.x; }
+};
+
+int main(int, char**)
+{
+    std::vector<int> vec(100);
+    std::iota(vec.begin(), vec.end(), 0);
+
+    std::vector<E> evec;
+    for (unsigned i = 0; i < 100; ++i) evec.push_back(E { i });
+
+    int arr[100];
+    for (unsigned i = 0; i < 100; ++i) arr[i] = i;
+
+    test(vec, vec.begin(), vec.end());
+    test(evec, evec.begin(), evec.end());
+    test(arr, arr, arr + 3);
+
+    // Execution policy overloads:
+    // The execution policies have no effect on the shift function.
+    shift_left(/*std::execution::sequenced_policy*/ 0, vec.begin(), vec.end(), 0);
+    shift_right(/*std::execution::parallel_policy*/ 1, vec.begin(), vec.end(), 0);
+
+    return 0;
+}
 No newline at end of file