[libc++][ranges] implement ranges::shift_left
#83231
Open
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
Thank you for submitting a Pull Request (PR) to the LLVM Project! This PR will be automatically labeled and the relevant teams will be If you wish to, you can add reviewers by using the "Reviewers" section on this page. If this is not working for you, it is probably because you do not have write If you have received no comments on your PR for a week, you can request a review If you have further questions, they may be answered by the LLVM GitHub User Guide. You can also ask questions in a comment on this PR, on the LLVM Discord or on the forums. |
xiaoyang-sde
changed the title
ranges::shift_left
|
✅ With the latest revision this PR passed the C/C++ code formatter. |
added 9 commits
February 28, 2024 00:30
…es::shift_left.h'
xiaoyang-sde
commented
Feb 29, 2024
libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/ranges.shift_left.pass.cpp
Outdated
Show resolved
Hide resolved
added 2 commits
February 28, 2024 19:37
… evaluation in 'ranges.shift_left.pass.cpp'
philnik777
requested changes
Feb 29, 2024
| typename iterator_traits<_ForwardIterator>::difference_type __n) { | ||
| template <class _AlgPolicy, class _Iter, class _Sent> | ||
| inline _LIBCPP_HIDE_FROM_ABI constexpr pair<_Iter, _Iter> | ||
| __shift_left(_Iter __first, _Sent __last, typename iterator_traits<_Iter>::difference_type __n) { |
There was a problem hiding this comment.
Suggested change
| __shift_left(_Iter __first, _Sent __last, typename iterator_traits<_Iter>::difference_type __n) { | |
| __shift_left(_Iter __first, _Sent __last, _IterOps<_AlgPolicy>::template __difference_type<_Iter> __n) { |
Please add a test!
There was a problem hiding this comment.
Thanks! Could you please provide more details about the tests I should consider adding?
| if (__n >= __last - __first) { | ||
| return __first; | ||
| _Iter __m = __first; | ||
| if constexpr (__has_random_access_iterator_category<_Iter>::value) { |
There was a problem hiding this comment.
We should check _IterOps<_AlgPolicy>::template __iterator_category. We should also make sure [__first, __last) is a sized range to avoid having to iterate linearly through the range twice. Could you add a benchmark for these cases too?
There was a problem hiding this comment.
Great! I refactored this function.
libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/ranges.shift_left.pass.cpp
Outdated
Show resolved
Hide resolved
libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/ranges.shift_left.pass.cpp
Outdated
Show resolved
Hide resolved
libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/ranges.shift_left.pass.cpp
Outdated
Show resolved
Hide resolved
|
I attempt to explain how the There are three cases:
I wrote a benchmark to cover these cases, following the structure of benchmarks/algorithms/ranges_ends_with.bench.cpp. |
xiaoyang-sde
added
the
libc++
|
@llvm/pr-subscribers-libcxx Author: Xiaoyang Liu (xiaoyang-sde) ChangesAbstractThis pull request implements the template<permutable I, sentinel_for<I> S>
constexpr subrange<I> ranges::shift_left(I first, S last, iter_difference_t<I> n);
template<forward_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> ranges::shift_left(R&& r, range_difference_t<R> n);Implementation
Testing
BenchmarkingThe performance characteristics of this algorithm depends on whether the iterator-sentinel pair
The benchmark covers these scenarios. The result is obtained from Arch Linux running on WSL 2, with an i5-12400 processor and 32 GB of RAM. Running ./ranges_shift_left.libcxx.out
Run on (12 X 2496 MHz CPU s)
CPU Caches:
L1 Data 48 KiB (x6)
L1 Instruction 32 KiB (x6)
L2 Unified 1280 KiB (x6)
L3 Unified 18432 KiB (x1)
Load Average: 0.21, 0.27, 0.27
---------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------------------------------------------
bm_shift_left_random_access_range_with_sized_sentinel/16 83.1 ns 83.1 ns 8309315
bm_shift_left_random_access_range_with_sized_sentinel/256 538 ns 538 ns 1313373
bm_shift_left_random_access_range_with_sized_sentinel/4096 7806 ns 7806 ns 89810
bm_shift_left_random_access_range_with_sized_sentinel/65536 133282 ns 133283 ns 5350
bm_shift_left_random_access_range_with_sized_sentinel/1048576 2105713 ns 2105700 ns 329
bm_shift_left_random_access_range_with_sized_sentinel/16777216 35178000 ns 35177443 ns 21
bm_shift_left_forward_range_with_sized_sentinel/16 119 ns 119 ns 6205162
bm_shift_left_forward_range_with_sized_sentinel/256 823 ns 823 ns 713098
bm_shift_left_forward_range_with_sized_sentinel/4096 11396 ns 11396 ns 57800
bm_shift_left_forward_range_with_sized_sentinel/65536 187637 ns 187633 ns 3674
bm_shift_left_forward_range_with_sized_sentinel/1048576 3061067 ns 3061066 ns 224
bm_shift_left_forward_range_with_sized_sentinel/16777216 48388067 ns 48388060 ns 15
bm_shift_left_forward_range/16 127 ns 127 ns 5334512
bm_shift_left_forward_range/256 1103 ns 1103 ns 639868
bm_shift_left_forward_range/4096 16228 ns 16225 ns 44339
bm_shift_left_forward_range/65536 254785 ns 254786 ns 2763
bm_shift_left_forward_range/1048576 4355744 ns 4355753 ns 151
bm_shift_left_forward_range/16777216 69017411 ns 69015670 ns 10Reference
Patch is 22.82 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/83231.diff 14 Files Affected:
diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt
index b436e96f178b70..6dc3dda3c4b2b3 100644
--- a/libcxx/benchmarks/CMakeLists.txt
+++ b/libcxx/benchmarks/CMakeLists.txt
@@ -191,6 +191,7 @@ set(BENCHMARK_TESTS
algorithms/ranges_make_heap_then_sort_heap.bench.cpp
algorithms/ranges_pop_heap.bench.cpp
algorithms/ranges_push_heap.bench.cpp
+ algorithms/ranges_shift_left.bench.cpp
algorithms/ranges_sort.bench.cpp
algorithms/ranges_sort_heap.bench.cpp
algorithms/ranges_stable_sort.bench.cpp
diff --git a/libcxx/benchmarks/algorithms/ranges_shift_left.bench.cpp b/libcxx/benchmarks/algorithms/ranges_shift_left.bench.cpp
new file mode 100644
index 00000000000000..8f20f87f558660
--- /dev/null
+++ b/libcxx/benchmarks/algorithms/ranges_shift_left.bench.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
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+#include <benchmark/benchmark.h>
+#include <iterator>
+#include <vector>
+
+#include "test_iterators.h"
+
+static void bm_shift_left_random_access_range_with_sized_sentinel(benchmark::State& state) {
+ std::vector<int> a(state.range(), 1);
+
+ for (auto _ : state) {
+ benchmark::DoNotOptimize(a);
+
+ auto begin = random_access_iterator(a.data());
+ auto end = random_access_iterator(a.data() + a.size());
+
+ static_assert(std::random_access_iterator<decltype(begin)>);
+ static_assert(std::sized_sentinel_for<decltype(end), decltype(begin)>);
+
+ benchmark::DoNotOptimize(std::ranges::shift_left(begin, end, a.size() / 2));
+ }
+}
+BENCHMARK(bm_shift_left_random_access_range_with_sized_sentinel)->RangeMultiplier(16)->Range(16, 16 << 20);
+
+static void bm_shift_left_forward_range_with_sized_sentinel(benchmark::State& state) {
+ std::vector<int> a(state.range(), 1);
+
+ for (auto _ : state) {
+ benchmark::DoNotOptimize(a);
+
+ auto begin = forward_iterator(a.data());
+ auto end = sized_sentinel(forward_iterator(a.data() + a.size()));
+
+ static_assert(!std::random_access_iterator<decltype(begin)>);
+ static_assert(std::sized_sentinel_for<decltype(end), decltype(begin)>);
+
+ benchmark::DoNotOptimize(std::ranges::shift_left(begin, end, a.size() / 2));
+ }
+}
+BENCHMARK(bm_shift_left_forward_range_with_sized_sentinel)->RangeMultiplier(16)->Range(16, 16 << 20);
+
+static void bm_shift_left_forward_range(benchmark::State& state) {
+ std::vector<int> a(state.range(), 1);
+
+ for (auto _ : state) {
+ benchmark::DoNotOptimize(a);
+
+ auto begin = forward_iterator(a.data());
+ auto end = forward_iterator(a.data() + a.size());
+
+ static_assert(!std::random_access_iterator<decltype(begin)>);
+ static_assert(!std::sized_sentinel_for<decltype(end), decltype(begin)>);
+
+ benchmark::DoNotOptimize(std::ranges::shift_left(begin, end, a.size() / 2));
+ }
+}
+BENCHMARK(bm_shift_left_forward_range)->RangeMultiplier(16)->Range(16, 16 << 20);
+
+BENCHMARK_MAIN();
diff --git a/libcxx/docs/Status/Cxx23Papers.csv b/libcxx/docs/Status/Cxx23Papers.csv
index 56e1468b4ca1a3..2ed597c5b80f50 100644
--- a/libcxx/docs/Status/Cxx23Papers.csv
+++ b/libcxx/docs/Status/Cxx23Papers.csv
@@ -46,7 +46,7 @@
"`P2255R2 <https://wg21.link/P2255R2>`__","LWG","A type trait to detect reference binding to temporary","February 2022","",""
"`P2273R3 <https://wg21.link/P2273R3>`__","LWG","Making ``std::unique_ptr`` constexpr","February 2022","|Complete|","16.0"
"`P2387R3 <https://wg21.link/P2387R3>`__","LWG","Pipe support for user-defined range adaptors","February 2022","","","|ranges|"
-"`P2440R1 <https://wg21.link/P2440R1>`__","LWG","``ranges::iota``, ``ranges::shift_left`` and ``ranges::shift_right``","February 2022","","","|ranges|"
+"`P2440R1 <https://wg21.link/P2440R1>`__","LWG","``ranges::iota``, ``ranges::shift_left`` and ``ranges::shift_right``","February 2022","|In progress|","","|ranges|"
"`P2441R2 <https://wg21.link/P2441R2>`__","LWG","``views::join_with``","February 2022","|In Progress|","","|ranges|"
"`P2442R1 <https://wg21.link/P2442R1>`__","LWG","Windowing range adaptors: ``views::chunk`` and ``views::slide``","February 2022","","","|ranges|"
"`P2443R1 <https://wg21.link/P2443R1>`__","LWG","``views::chunk_by``","February 2022","|Complete|","18.0","|ranges|"
diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv
index f7a51f732c4b14..1d9582373ea8a0 100644
--- a/libcxx/docs/Status/RangesAlgorithms.csv
+++ b/libcxx/docs/Status/RangesAlgorithms.csv
@@ -5,7 +5,7 @@ C++23,`find_last_if <https://wg21.link/P1223R5>`_,Unassigned,No patch yet,Not st
C++23,`find_last_if_not <https://wg21.link/P1223R5>`_,Unassigned,No patch yet,Not started
C++23,`starts_with <https://wg21.link/P1659R3>`_,Zijun Zhao,`D150735 <https://llvm.org/D150735>`_,Complete
C++23,`ends_with <https://wg21.link/P1659R3>`_,Zijun Zhao, `D150831 <https://llvm.org/D150831>`_,Complete
-C++23,`shift_left <https://wg21.link/p2440r1>`_,Unassigned,No patch yet,Not started
+C++23,`shift_left <https://wg21.link/p2440r1>`_,Xiaoyang Liu,`83231 <https://github.com/llvm/llvm-project/pull/83231>`,✅
C++23,`shift_right <https://wg21.link/p2440r1>`_,Unassigned,No patch yet,Not started
C++23,`iota (algorithm) <https://wg21.link/p2440r1>`_,Unassigned,No patch yet,Not started
C++23,`fold <https://wg21.link/p2322r5>`_,Unassigned,No patch yet,Not started
diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index 3ea3360186dc56..69d46566df39ce 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -183,6 +183,7 @@ set(files
__algorithm/ranges_set_intersection.h
__algorithm/ranges_set_symmetric_difference.h
__algorithm/ranges_set_union.h
+ __algorithm/ranges_shift_left.h
__algorithm/ranges_shuffle.h
__algorithm/ranges_sort.h
__algorithm/ranges_sort_heap.h
diff --git a/libcxx/include/__algorithm/ranges_shift_left.h b/libcxx/include/__algorithm/ranges_shift_left.h
new file mode 100644
index 00000000000000..439d4955edfa60
--- /dev/null
+++ b/libcxx/include/__algorithm/ranges_shift_left.h
@@ -0,0 +1,68 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_SHIFT_LEFT_H
+#define _LIBCPP___ALGORITHM_RANGES_SHIFT_LEFT_H
+
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/shift_left.h>
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/incrementable_traits.h>
+#include <__iterator/permutable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/subrange.h>
+#include <__utility/move.h>
+#include <__utility/pair.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+#if _LIBCPP_STD_VER >= 23
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __shift_left {
+
+struct __fn {
+ template <permutable _Iter, sentinel_for<_Iter> _Sent>
+ _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter>
+ operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __n) {
+ auto __ret = std::__shift_left<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__n));
+ return {std::move(__ret.first), std::move(__ret.second)};
+ }
+
+ template <forward_range _Range>
+ requires permutable<iterator_t<_Range>>
+ _LIBCPP_HIDE_FROM_ABI static constexpr borrowed_subrange_t<_Range>
+ operator()(_Range&& __range, range_difference_t<_Range> __n) {
+ auto __ret = std::__shift_left<_RangeAlgPolicy>(ranges::begin(__range), ranges::end(__range), std::move(__n));
+ return {std::move(__ret.first), std::move(__ret.second)};
+ }
+};
+
+} // namespace __shift_left
+
+inline namespace __cpo {
+inline constexpr auto shift_left = __shift_left::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER >= 23
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_RANGES_SHIFT_LEFT_H
diff --git a/libcxx/include/__algorithm/shift_left.h b/libcxx/include/__algorithm/shift_left.h
index 06cd7c5f87644e..cfab41e56c2c87 100644
--- a/libcxx/include/__algorithm/shift_left.h
+++ b/libcxx/include/__algorithm/shift_left.h
@@ -9,9 +9,12 @@
#ifndef _LIBCPP___ALGORITHM_SHIFT_LEFT_H
#define _LIBCPP___ALGORITHM_SHIFT_LEFT_H
+#include <__algorithm/iterator_operations.h>
#include <__algorithm/move.h>
+#include <__assert>
#include <__config>
#include <__iterator/iterator_traits.h>
+#include <__utility/pair.h>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
@@ -24,30 +27,42 @@ _LIBCPP_BEGIN_NAMESPACE_STD
#if _LIBCPP_STD_VER >= 20
-template <class _ForwardIterator>
-inline _LIBCPP_HIDE_FROM_ABI constexpr _ForwardIterator
-shift_left(_ForwardIterator __first,
- _ForwardIterator __last,
- typename iterator_traits<_ForwardIterator>::difference_type __n) {
+template <class _AlgPolicy, class _Iter, class _Sent>
+_LIBCPP_HIDE_FROM_ABI constexpr pair<_Iter, _Iter>
+__shift_left(_Iter __first, _Sent __last, typename _IterOps<_AlgPolicy>::template __difference_type<_Iter> __n) {
+ _LIBCPP_ASSERT_UNCATEGORIZED(__n >= 0, "__n must be greater than or equal to 0");
+
if (__n == 0) {
- return __last;
+ _Iter __end = _IterOps<_AlgPolicy>::next(__first, __last);
+ return {std::move(__first), std::move(__end)};
}
- _ForwardIterator __m = __first;
- if constexpr (__has_random_access_iterator_category<_ForwardIterator>::value) {
- if (__n >= __last - __first) {
- return __first;
+ _Iter __m = __first;
+ if constexpr (sized_sentinel_for<_Sent, _Iter>) {
+ auto __size = _IterOps<_AlgPolicy>::distance(__first, __last);
+ if (__n >= __size) {
+ return {std::move(__first), std::move(__first)};
}
- __m += __n;
+ _IterOps<_AlgPolicy>::advance(__m, __n);
} else {
for (; __n > 0; --__n) {
if (__m == __last) {
- return __first;
+ return {std::move(__first), std::move(__first)};
}
++__m;
}
}
- return std::move(__m, __last, __first);
+
+ _Iter __result = std::__move<_AlgPolicy>(__m, __last, __first).second;
+ return {std::move(__first), std::move(__result)};
+}
+
+template <class _ForwardIterator>
+inline _LIBCPP_HIDE_FROM_ABI constexpr _ForwardIterator
+shift_left(_ForwardIterator __first,
+ _ForwardIterator __last,
+ typename iterator_traits<_ForwardIterator>::difference_type __n) {
+ return std::__shift_left<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __n).second;
}
#endif // _LIBCPP_STD_VER >= 20
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
index 0f62de7fa83f98..76f8935ea31d2e 100644
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -843,6 +843,13 @@ namespace ranges {
uniform_random_bit_generator<remove_reference_t<Gen>>
O sample(R&& r, O out, range_difference_t<R> n, Gen&& g); // since C++20
+ template<permutable I, sentinel_for<I> S>
+ constexpr subrange<I> ranges::shift_left(I first, S last, iter_difference_t<I> n); // since C++23
+
+ template<forward_range R>
+ requires permutable<iterator_t<R>>
+ constexpr borrowed_subrange_t<R> ranges::shift_left(R&& r, range_difference_t<R> n) // since C++23
+
template<random_access_iterator I, sentinel_for<I> S, class Gen>
requires permutable<I> &&
uniform_random_bit_generator<remove_reference_t<Gen>>
@@ -1959,6 +1966,7 @@ template <class BidirectionalIterator, class Compare>
#include <__algorithm/ranges_set_intersection.h>
#include <__algorithm/ranges_set_symmetric_difference.h>
#include <__algorithm/ranges_set_union.h>
+#include <__algorithm/ranges_shift_left.h>
#include <__algorithm/ranges_shuffle.h>
#include <__algorithm/ranges_sort.h>
#include <__algorithm/ranges_sort_heap.h>
diff --git a/libcxx/include/libcxx.imp b/libcxx/include/libcxx.imp
index cdbb0a63fc0eae..0c8655ccdb02cb 100644
--- a/libcxx/include/libcxx.imp
+++ b/libcxx/include/libcxx.imp
@@ -183,6 +183,7 @@
{ include: [ "<__algorithm/ranges_set_intersection.h>", "private", "<algorithm>", "public" ] },
{ include: [ "<__algorithm/ranges_set_symmetric_difference.h>", "private", "<algorithm>", "public" ] },
{ include: [ "<__algorithm/ranges_set_union.h>", "private", "<algorithm>", "public" ] },
+ { include: [ "<__algorithm/ranges_shift_left.h>", "private", "<algorithm>", "public" ] },
{ include: [ "<__algorithm/ranges_shuffle.h>", "private", "<algorithm>", "public" ] },
{ include: [ "<__algorithm/ranges_sort.h>", "private", "<algorithm>", "public" ] },
{ include: [ "<__algorithm/ranges_sort_heap.h>", "private", "<algorithm>", "public" ] },
diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap
index b247f97c1804d9..72d3948aeb4520 100644
--- a/libcxx/include/module.modulemap
+++ b/libcxx/include/module.modulemap
@@ -987,6 +987,7 @@ module std_private_algorithm_ranges_set_union [system
export std_private_algorithm_in_in_out_result
export std_private_functional_ranges_operations
}
+module std_private_algorithm_ranges_shift_left [system] { header "__algorithm/ranges_shift_left.h" }
module std_private_algorithm_ranges_shuffle [system] { header "__algorithm/ranges_shuffle.h" }
module std_private_algorithm_ranges_sort [system] {
header "__algorithm/ranges_sort.h"
diff --git a/libcxx/modules/std/algorithm.inc b/libcxx/modules/std/algorithm.inc
index e7796bfa26af81..2364899c1e0315 100644
--- a/libcxx/modules/std/algorithm.inc
+++ b/libcxx/modules/std/algorithm.inc
@@ -353,9 +353,11 @@ export namespace std {
// [alg.shift], shift
using std::shift_left;
+#if _LIBCPP_STD_VER >= 23
namespace ranges {
- // using std::ranges::shift_left;
+ using std::ranges::shift_left;
}
+#endif // _LIBCPP_STD_VER >= 23
using std::shift_right;
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/ranges.shift_left.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/ranges.shift_left.pass.cpp
new file mode 100644
index 00000000000000..70a909736b841e
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/ranges.shift_left.pass.cpp
@@ -0,0 +1,187 @@
+//===----------------------------------------------------------------------===//
+//
+// 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>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+// template<permutable I, sentinel_for<I> S>
+// constexpr subrange<I> ranges::shift_left(I first, S last, iter_difference_t<I> n);
+
+// template<forward_range R>
+// requires permutable<iterator_t<R>>
+// constexpr borrowed_subrange_t<R> ranges::shift_left(R&& r, range_difference_t<R> n)
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+#include <iterator>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
+
+template <class Iter, class Sent = Iter>
+concept HasShiftLeftIt = requires(Iter iter, Sent sent, std::size_t n) { std::ranges::shift_left(iter, sent, n); };
+
+static_assert(HasShiftLeftIt<int*>);
+static_assert(!HasShiftLeftIt<ForwardIteratorNotDerivedFrom>);
+static_assert(!HasShiftLeftIt<PermutableNotForwardIterator>);
+static_assert(!HasShiftLeftIt<PermutableNotSwappable>);
+
+template <class Range>
+concept HasShiftLeftR = requires(Range range, std::size_t n) { std::ranges::shift_left(range, n); };
+
+static_assert(HasShiftLeftR<UncheckedRange<int*>>);
+static_assert(!HasShiftLeftR<ForwardRangeNotDerivedFrom>);
+static_assert(!HasShiftLeftR<PermutableRangeNotForwardIterator>);
+static_assert(!HasShiftLeftR<PermutableRangeNotSwappable>);
+
+template <class Iter, class Sent>
+constexpr void test_iter_sent() {
+ {
+ const std::array<int, 8> original = {3, 1, 4, 1, 5, 9, 2, 6};
+ std::array<int, 8> scratch;
+
+ // (iterator, sentinel) overload
+ for (size_t n = 0; n <= original.size(); ++n) {
+ for (size_t k = 0; k <= n + 2; ++k) {
+ auto begin = Iter(scratch.data());
+ auto end = Sent(Iter(scratch.data() + n));
+ std::ranges::copy(original.begin(), original.begin() + n, begin);
+ auto result = std::ranges::shift_left(begin, end, k);
+
+ assert(result.begin() == begin);
+ if (k < n) {
+ assert(result.end() == Iter(scratch.data() + n - k));
+ assert(std::ranges::equal(original.begin() + k, original.begin() + n, result.begin(), result.end()));
+ } else {
+ assert(result.end() == begin);
+ assert(std::ranges::equal(original.begin(), original.begin() + n, begin, end));
+ }
+ }
+ }
+
+ // (range) overload
+ for (size_t n = 0; n <= original.size(); ++n) {
+ for (size_t k = 0; k <= n + 2; ++k) {
+ auto begin = Iter(scratch.data());
+ auto end = Sent(Iter(scratch.data() + n));
+ std::ranges::copy(original.begin(), original.begin() + n, begin);
+ auto range = std::ranges::subrange(begin, end);
+ auto result = std::ranges::shift_left(range, k);
+
+ assert(result.begin() == begin);
+ if (k < n) {
+ assert(result.end() == Iter(scratch.data() + n - k));
+ assert(std::ranges::equal(original.begin() + k, original.begin() + n, begin, result.end()));
+ } else {
+ assert(result.end() == begin);
+ assert(std::ranges::equal(original.begin(), original.begin() + n, begin, end));
+ }
+ }
+ }
+ }
+
+ // n == 0
+ {
+ std::array<int, 3> input = {0, 1, 2};
+ const std::array<int, 3> expected = {0, 1, 2};
+
+ { // (iterator, sentinel) overload
+ auto in = input;
+ auto begin = Iter(in.data());
+ auto end = Sent(Iter(in.data() + in.size()));
+ auto result = std::ranges::shift_left(begin, end, 0);
+ assert(std::ranges::equal(expected, result));
+ assert(result.begin() == begin);
+ assert(result.end() == end);
+ }
+
+ { // (range) overload
+ auto in = input;
+ auto begin = Iter(in.data());
+ auto end = Sent(Iter(in.data() + in.size()));
+ auto range = std::ranges::subrange(begin, end);
+ auto result = std::ranges::shift_left(range, 0);
+ assert(std::ranges::equal(expected, result));
+ assert(result.begin() == begin);
+ assert(result.end() == end);
+ }
+ }
+
+ // n == len
+ {
+ std::array<int, 3> input = {0, 1, 2};
+ const std::array<int, 3> expected = {0, 1, 2};
+
+ { // (iterator, sentinel) overload
+ auto in = input;
+ auto begin = Iter(in.data());
+ auto end = Sent(Iter(in.data() + in.size()));
+ auto result = std::ranges::shift_left(begin, end, input.size());
+ assert(std::ranges::equal(expected, input));
+ assert(result.begin() == begin);
+ assert(result.end() == begin);
+ }
+
+ { // (range) overload
+ auto in = input;
+ auto begin = Iter(in.data());
+ auto end = Sent(Iter(in.data() + in.size()));
+ auto range = std::ranges::subrange(begin, end);
+ auto result = std::ranges::shift_left(range, input.size());
+ assert(std::ranges::equal(expected, input));
+ assert(result.begin() == begin);
+ assert(result.end() == begin);
+ }
+ }
+
+ // n > len
+ {
+ std::array<int, 3> input = {0, 1, 2};
+ const std::array<int, 3> expected = {0, 1, 2};
+
+ { /...
[truncated]
|
added 8 commits
December 23, 2024 23:55
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Introduction
This pull request implements the
ranges::shift_leftalgorithm from P2440R1.Implementation
shift_leftalgorithm inlibcxx/include/__algorithm/shift_left.his refactored. The shared logic has been extracted into a separated function called__shift_left. This function takes an iterator__first, a sentinel__last, and__nas parameters, and returns the{__first, NEW_LAST}, whereNEW_LASTis defined in [alg.shift]/3.ranges::shift_leftniebloid inlibcxx/include/__algorithm/ranges_shift_left.his implemented based on the__shift_leftfunction. This approach helps avoid duplicating the algorithm logic, a common pattern seen in ranges algorithms likelibcxx/include/__algorithm/ranges_shuffle.h.Testing
libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/ranges.shift_left.pass.cppare adopted from those cases ofshift_left. These cases attempt to ensure correctness of both the algorithm and the interface.Benchmarking
The performance characteristics of this algorithm depends on whether the iterator-sentinel pair
[first, last)modelsstd::sized_sentinel_forand iffirstadheres tostd::random_access_iterator.first + nis out-of-bound in constant time.first + nin constant time.Reference
ranges::iota,ranges::shift_left, andranges::shift_rightCloses: #134061