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 ↗

(On Diff #193039)

This needs to be constexpr (same with right_shift)

5736 ↗

(On Diff #193039)

Negative ranges are supported too.

[zoecarver]

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

include/algorithm

5736 ↗

(On Diff #193039)

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

[zoecarver]

Make shift functions constexpr.

[EricWF]

include/algorithm

5806 ↗

(On Diff #193920)

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

[zoecarver]

include/algorithm

5806 ↗

(On Diff #193920)

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

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

5693

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

5724

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

5734

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

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

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 :-)

libcxx/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>());
 }
 
+#if _LIBCPP_VERSION > 17
+
+template<class _It>
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _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 || __n >= __size) return __first;
+
+    _It __first1 = __first;
+    _It __first2 = __first;
+    for(__first2++; __first2 != __last; ++__first1, (void)++__first2) {
+        std::iter_swap(__first1, __first2);
+    }
+
+    return shift_left(__first, __last, __n - 1);
+}
+
+template<class _Ep, class _It>
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _It
+shift_left(_Ep&&, _It __first, _It __last, typename iterator_traits<_It>::difference_type __n)
+{ return shift_left(__first, __last, __n); }
+
+template<class _It>
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _It
+__get_rbegin(_It __first, _It __last)
+{
+    _It __first1 = __first;
+    for (__first1++; __first1 != __last; ++__first, (void)++__first1) {}
+    return __first;
+}
+
+template<class _It, class _St = typename iterator_traits<_It>::difference_type>
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _It
+__n_before_end(_It __first, _It __last, _St __n)
+{
+    _It __first1 = __first;
+    for (_St __i = 0; __i < __n; ++__i, (void)++__first1) {}
+    for (; __first1 != __last; ++__first, (void)++__first1) {}
+    return __first;
+}
+
+template<class _It>
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _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 || __n >= __size) return __first;
+    if (__n > __size / 2) return shift_left(__first, __last, __size - __n);
+
+    _It __current = __first;
+    _It __before = __n_before_end(__first, __last, __n);
+    _It __rbegin = __get_rbegin(__first, __last);
+
+    while(__current != __rbegin) {
+        _It __before1 = __before;
+        do {
+            std::iter_swap(__current++, __before1++);
+        } while (__before1 != __last && __current != __rbegin);
+    }
+
+    return __first;
+}
+
+template<class _Ep, class _It>
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _It
+shift_right(_Ep&&, _It __first, _It __last, typename iterator_traits<_It>::difference_type __n)
+{ return shift_right(__first, __last, __n); }
+
+#endif // _LIBCPP_VERSION > 17
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif  // _LIBCPP_ALGORITHM

libcxx/test/std/algorithms/alg.shift/shift_left.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+
+// <algorithm>
+
+// template<class ForwardIterator>
+//     constexpr ForwardIterator
+//     shift_left(ForwardIterator first, ForwardIterator last,
+//                typename iterator_traits<ForwardIterator>::difference_type n); // C++20
+//
+// Effects: If n <= 0 or n >= last - first, does nothing.
+//          Otherwise, moves the element from position first + n + i into position
+//          first + i for each non-negative integer i < (last - first) - n.
+//          Does so in order starting from i = 0 and proceeding to i = (last - first) - n - 1.
+//
+// Returns: first + (last - first - n) if n is positive and n < last - first,
+//         otherwise first if n is positive, otherwise last.
+
+
+#include <algorithm>
+#include <cassert>
+#include <iterator>
+#include <numeric>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+constexpr bool test_constexpr() {
+    int ia[] = {0, 1, 1, 3, 4};
+    const int expected[] = {1, 1, 3, 4, 0};
+    const size_t shift = 1;
+
+    std::shift_left(std::begin(ia), std::end(ia), shift);
+    return std::equal(std::begin(expected), std::end(expected), std::begin(ia));
+}
+
+struct MInt
+{
+    MInt (int v) : v_{v} {}
+    MInt (     ) : v_{0} {}
+
+    MInt (const MInt  &rhs) : v_{rhs.v_} {}
+    MInt (      MInt &&rhs) : v_{rhs.v_} { rhs.v_ = -1;}
+
+    MInt& operator=(const MInt  &rhs) { v_ = rhs.v_;              return *this; }
+    MInt& operator=(      MInt &&rhs) { v_ = rhs.v_; rhs.v_ = -1; return *this; }
+
+    int v_;
+};
+
+template <typename T>
+bool hasBeenMoved(const T&) { return true; }
+
+template <>
+bool hasBeenMoved(const MInt& t) { return t.v_ == -1; }
+
+bool operator==(const MInt &rhs, const MInt &lhs)
+{ return lhs.v_ == rhs.v_ && lhs.v_ != -1; } // we shouldn't be comparing moved-from objects
+
+template <class Iter>
+void test()
+{
+    using T = typename std::iterator_traits<Iter>::value_type;
+
+    // n < 0
+    {
+        T input[]          = {0, 1, 2};
+        const T expected[] = {0, 1, 2};
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_left(b, e, -1);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+
+    // n == 0
+    {
+        T input[]          = {0, 1, 2};
+        const T expected[] = {0, 1, 2};
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_left(b, e, 0);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+
+    // n > 0 && n < len
+    {
+        T input[]          = {0, 1, 2};
+        const T expected[] = {1, 2, 0};
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_left(b, e, 1);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+    {
+        T input[]          = { 1, 2, 3, 4, 5, 6, 7, 8 };
+        const T expected[] = { 3, 4, 5, 6, 7, 8, 1, 2 };
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_left(b, e, 2);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+    {
+        T input[]          = { 1, 2, 3, 4, 5, 6, 7, 8 };
+        const T expected[] = { 7, 8, 1, 2, 3, 4, 5, 6 };
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_left(b, e, 6);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+
+    // n == len
+    {
+        T input[]          = {0, 1, 2};
+        const T expected[] = {0, 1, 2};
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_left(b, e, std::size(input));
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+
+    // n > len
+    {
+        T input[]          = {0, 1, 2};
+        const T expected[] = {0, 1, 2};
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_left(b, e, std::size(input) + 1);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+}
+
+int main(int, char**)
+{
+    static_assert(test_constexpr());
+
+    test<forward_iterator<int*>>();
+    test<bidirectional_iterator<int*>>();
+    test<random_access_iterator<int*>>();
+    test<int*>();
+
+    test<forward_iterator<MInt*>>();
+    test<bidirectional_iterator<MInt*>>();
+    test<random_access_iterator<MInt*>>();
+    test<MInt*>();
+
+    return 0;
+}

libcxx/test/std/algorithms/alg.shift/shift_right.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+
+// <algorithm>
+
+// template<class ForwardIterator>
+//     constexpr ForwardIterator
+//     shift_right(ForwardIterator first, ForwardIterator last,
+//                typename iterator_traits<ForwardIterator>::difference_type n); // C++20
+//
+// Effects: If n <= 0 or n >= last - first, does nothing.
+//          Otherwise, moves the element from position first + i into position
+//          first + n + i for each non-negative integer i < (last - first) - n.
+//          If ForwardIterator satisfies the Cpp17BidirectionalIterator requirements,
+//          does so in order starting from i = (last - first) - n - 1 and proceeding to i = 0.
+//
+// Returns: first + n if n is positive and n < last - first,
+//          otherwise last if n is positive, otherwise first.
+
+#include <algorithm>
+#include <cassert>
+#include <iterator>
+#include <numeric>
+#include <iostream>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+constexpr bool test_constexpr() {
+    int ia[] = {0, 1, 1, 3, 4};
+    const int expected[] = {4, 0, 1, 1, 3};
+    const size_t shift = 1;
+
+    std::shift_right(std::begin(ia), std::end(ia), shift);
+    return std::equal(std::begin(expected), std::end(expected), std::begin(ia));
+}
+
+struct MInt
+{
+    MInt (int v) : v_{v} {}
+    MInt (     ) : v_{0} {}
+
+    MInt (const MInt  &rhs) : v_{rhs.v_} {}
+    MInt (      MInt &&rhs) : v_{rhs.v_} { rhs.v_ = -1;}
+
+    MInt& operator=(const MInt  &rhs) { v_ = rhs.v_;              return *this; }
+    MInt& operator=(      MInt &&rhs) { v_ = rhs.v_; rhs.v_ = -1; return *this; }
+
+    int v_;
+};
+
+template <typename T>
+bool hasBeenMoved(const T&) { return true; }
+
+template <>
+bool hasBeenMoved(const MInt& t) {
+    std::cout << t.v_ << std::endl;
+    return t.v_ == -1;
+}
+
+bool operator==(const MInt &rhs, const MInt &lhs)
+{ return lhs.v_ == rhs.v_ && lhs.v_ != -1; } // we shouldn't be comparing moved-from objects
+
+template <class Iter>
+void test()
+{
+    using T = typename std::iterator_traits<Iter>::value_type;
+
+    // n < 0
+    {
+        T input[]          = {0, 1, 2};
+        const T expected[] = {0, 1, 2};
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_right(b, e, -1);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+
+    // n == 0
+    {
+        T input[]          = {0, 1, 2};
+        const T expected[] = {0, 1, 2};
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_right(b, e, 0);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+
+    // n > 0 && n < len
+    {
+        T input[]          = {0, 1, 2};
+        const T expected[] = {2, 0, 1};
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_right(b, e, 1);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+    {
+        T input[]          = { 1, 2, 3, 4, 5, 6, 7, 8 };
+        const T expected[] = { 7, 8, 1, 2, 3, 4, 5, 6 };
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_right(b, e, 2);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+    {
+        T input[]          = { 1, 2, 3, 4, 5, 6, 7, 8 };
+        const T expected[] = { 3, 4, 5, 6, 7, 8, 1, 2 };
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_right(b, e, 6);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+
+    // n == len
+    {
+        T input[]          = {0, 1, 2};
+        const T expected[] = {0, 1, 2};
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_right(b, e, std::size(input));
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+
+    // n > len
+    {
+        T input[]          = {0, 1, 2};
+        const T expected[] = {0, 1, 2};
+        Iter b = Iter(std::begin(input));
+        Iter e = Iter(std::end(input));
+        Iter it = std::shift_right(b, e, std::size(input) + 1);
+        assert(std::equal(std::begin(expected), std::end(expected), b));
+        assert(it == b);
+    }
+}
+
+int main(int, char**)
+{
+    static_assert(test_constexpr());
+
+    test<forward_iterator<int*>>();
+    test<bidirectional_iterator<int*>>();
+    test<random_access_iterator<int*>>();
+    test<int*>();
+
+    test<forward_iterator<MInt*>>();
+    test<bidirectional_iterator<MInt*>>();
+    test<random_access_iterator<MInt*>>();
+    test<MInt*>();
+
+    return 0;
+}