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

5800

This needs to be constexpr (same with right_shift)

5803

Negative ranges are supported too.

[zoecarver]

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

include/algorithm

5803

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

[zoecarver]

Make shift functions constexpr.

[EricWF]

include/algorithm

5806

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

[zoecarver]

include/algorithm

5806

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>());
 }
 
+#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;
+
+    for (unsigned __i = 0; __i < __n; ++__i, ++__first) {};
+
+    return __first;
+}
+
+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, class _Ft>
+_LIBCPP_CONSTEXPR_AFTER_CXX14 typename enable_if<
+    !is_same<forward_iterator_tag, _Ft>::value,
+    _It
+>::type
+__shift_right_impl(_It __first, _It __last, typename iterator_traits<_It>::difference_type __n, _Ft)
+{
+    auto __size = _VSTD::distance(__first, __last);
+    if (__n <= 0 || __size <= 0 || __n >= __size) return __first;
+
+    auto __mid = __last;
+    for (unsigned __i = 0; __i < __n; ++__i, --__mid) {};
+
+    return move_backward(__first, __mid, __last);
+}
+
+template<class _It, class _Ft>
+_LIBCPP_CONSTEXPR_AFTER_CXX14 typename enable_if<
+    is_same<forward_iterator_tag, _Ft>::value,
+    _It
+>::type
+__shift_right_impl(_It __first, _It __last, typename iterator_traits<_It>::difference_type __n, _Ft)
+{
+    auto __size = _VSTD::distance(__first, __last);
+    if (__n <= 0 || __size <= 0 || __n >= __size) return __first;
+
+    auto __mid = __first;
+    for (unsigned __i = 0; __i < (__size - __n); ++__i, ++__mid) {};
+    __rotate_forward(__first, __mid, __last);
+
+    for (unsigned __i = 0; __i < __n; ++__i, ++__first) {};
+    return __first;
+}
+
+template<class _It>
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _It
+shift_right(_It __first, _It __last, typename iterator_traits<_It>::difference_type __n)
+{ return __shift_right_impl(__first, __last, __n,
+                            typename std::iterator_traits<_It>::iterator_category()); }
+
+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

test/std/algorithms/alg.shift/shift_exec_policy.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[0];
+
+  auto shifted_container = shift_left(begin, end, 20);
+  assert(left_check == shifted_container[0]);
+  shifted_container = shift_right(begin, end, 20);
+  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 + 100);
+
+  // 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;
+}

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 <array>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+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_;
+};
+
+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
+  for (size_t n = 1; n < 10; ++n)
+  {
+    T input[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+    
+    std::array<T, 10> expected;
+    std::iota(expected.begin(), expected.end(), n);
+
+    Iter b = Iter(std::begin(input));
+    Iter e = Iter(std::end(input));
+    Iter it = std::shift_left(b, e, n);
+
+    for (unsigned x = 0; x < 10 - n; ++x)
+      assert(*it++ == expected[x]);
+
+  //  The complication here (the "min") is because things are different when the
+  //  shift count is more than half the size of the sequence.
+  //  I don't think this is necessary?
+  // assert(std::all_of(std::next(b, std::size(input) - std::min(n, std::size(input) - n)), e, hasBeenMoved<T>));
+  }
+
+  // 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**)
+{
+  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;
+}

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 <array>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+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_;
+};
+
+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
+  for (size_t n = 1; n < 10; ++n)
+  {
+    T input[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+    
+    std::array<T, 10> expected;
+    std::iota(expected.begin(), expected.end(), 0);
+
+    Iter b = Iter(std::begin(input));
+    Iter e = Iter(std::end(input));
+    Iter it = std::shift_right(b, e, n);
+
+    for (unsigned i = 0; i < 10 - n; ++i)
+      assert(*it++ == expected[i]);
+
+  //  The complication here (the "min") is because things are different when the
+  //  shift count is more than half the size of the sequence.
+  //  I don't think this is necessary?
+  // assert(std::all_of(std::next(b, std::size(input) - std::min(n, std::size(input) - n)), e, hasBeenMoved<T>));
+  }
+
+  // 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**)
+{
+  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;
+}