Index: include/algorithm =================================================================== --- include/algorithm +++ include/algorithm @@ -631,6 +631,19 @@ bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); +template + ForwardIterator shift_left(ForwardIterator first, ForwardIterator last, + typename iterator_traits::difference_type n); +template + ForwardIterator shift_left(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, + typename iterator_traits::difference_type n); +template + ForwardIterator shift_right(ForwardIterator first, ForwardIterator last, + typename iterator_traits::difference_type n); +template + ForwardIterator shift_right(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, + typename iterator_traits::difference_type n); + } // std */ @@ -5714,6 +5727,46 @@ __less::value_type>()); } +template +_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 +_It shift_left(_Ep&&, _It __first, _It __last, typename iterator_traits<_It>::difference_type __n) +{ return shift_left(__first, __last, __n); } + +template +_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 +_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 Index: test/std/algorithms/algorithms.general/shift.pass.cpp =================================================================== --- /dev/null +++ test/std/algorithms/algorithms.general/shift.pass.cpp @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// template +// ForwardIterator shift_left(ForwardIterator first, ForwardIterator last, +// typename iterator_traits::difference_type n); +// template +// ForwardIterator shift_left(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, +// typename iterator_traits::difference_type n); +// template +// ForwardIterator shift_right(ForwardIterator first, ForwardIterator last, +// typename iterator_traits::difference_type n); +// template +// ForwardIterator shift_right(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, +// typename iterator_traits::difference_type n); + +#include +#include +#include + +template +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 vec(100); + std::iota(vec.begin(), vec.end(), 0); + + std::vector 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