diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -69,7 +69,7 @@ Permutation,remove_if,Nikolas Klauser,`D128618 `_,✅ Permutation,reverse,Nikolas Klauser,`D125752 `_,✅ Permutation,rotate,Nikolas Klauser,`D124122 `_,Under review -Permutation,shuffle,Not assigned,n/a,Not started +Permutation,shuffle,Konstantin Varlamov,`D130321 `_,✅ Permutation,unique,Not assigned,n/a,Not started Permutation,partition,Konstantin Varlamov,`D129624 `_,✅ Permutation,stable_partition,Konstantin Varlamov,`D129624 `_,✅ diff --git a/libcxx/include/__algorithm/partial_sort.h b/libcxx/include/__algorithm/partial_sort.h --- a/libcxx/include/__algorithm/partial_sort.h +++ b/libcxx/include/__algorithm/partial_sort.h @@ -54,14 +54,6 @@ return __i; } -// TODO(ranges): once `ranges::shuffle` is implemented, remove this helper and make `__debug_randomize_range` support -// sentinels. -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -void __maybe_randomize(_RandomAccessIterator __first, _Sentinel __last) { - std::__debug_randomize_range<_AlgPolicy>(__first, _IterOps<_AlgPolicy>::next(__first, __last)); -} - template _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last, @@ -69,12 +61,12 @@ if (__first == __middle) return _IterOps<_AlgPolicy>::next(__middle, __last); - std::__maybe_randomize<_AlgPolicy>(__first, __last); + std::__debug_randomize_range<_AlgPolicy>(__first, __last); using _Comp_ref = typename __comp_ref_type<_Compare>::type; auto __last_iter = std::__partial_sort_impl<_AlgPolicy, _Comp_ref>(__first, __middle, __last, __comp); - std::__maybe_randomize<_AlgPolicy>(__middle, __last); + std::__debug_randomize_range<_AlgPolicy>(__middle, __last); return __last_iter; } diff --git a/libcxx/include/__algorithm/ranges_shuffle.h b/libcxx/include/__algorithm/ranges_shuffle.h --- a/libcxx/include/__algorithm/ranges_shuffle.h +++ b/libcxx/include/__algorithm/ranges_shuffle.h @@ -9,23 +9,22 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H #define _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H -#include <__algorithm/make_projected.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/shuffle.h> #include <__config> -#include <__functional/identity.h> #include <__functional/invoke.h> #include <__functional/ranges_operations.h> #include <__iterator/concepts.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> #include <__iterator/permutable.h> -#include <__iterator/projected.h> #include <__random/uniform_random_bit_generator.h> #include <__ranges/access.h> #include <__ranges/concepts.h> #include <__ranges/dangling.h> -#include <__type_traits/remove_reference.h> #include <__utility/forward.h> #include <__utility/move.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -33,29 +32,57 @@ #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + _LIBCPP_BEGIN_NAMESPACE_STD namespace ranges { namespace __shuffle { struct __fn { + // `std::shuffle` is more constrained than `std::ranges::shuffle`. `std::ranges::shuffle` only requires the given + // generator to satisfy the `std::uniform_random_bit_generator` concept. `std::shuffle` requires the given + // generator to meet the uniform random bit generator requirements; these requirements include satisfying + // `std::uniform_random_bit_generator` and add a requirement for the generator to provide a nested `result_type` + // typedef (see `[rand.req.urng]`). + // + // To reuse the implementation from `std::shuffle`, make the given generator meet the classic requirements by wrapping + // it into an adaptor type that forwards all of its interface and adds the required typedef. + template + class _ClassicGenAdaptor { + private: + // The generator is not required to be copyable or movable, so it has to be stored as a reference. + _Gen& __gen; + + public: + using result_type = invoke_result_t<_Gen&>; + + _LIBCPP_HIDE_FROM_ABI + static constexpr auto min() { return __uncvref_t<_Gen>::min(); } + _LIBCPP_HIDE_FROM_ABI + static constexpr auto max() { return __uncvref_t<_Gen>::max(); } + + _LIBCPP_HIDE_FROM_ABI + constexpr explicit _ClassicGenAdaptor(_Gen& __g) : __gen(__g) {} + + _LIBCPP_HIDE_FROM_ABI + constexpr auto operator()() const { return __gen(); } + }; template _Sent, class _Gen> requires permutable<_Iter> && uniform_random_bit_generator> _LIBCPP_HIDE_FROM_ABI _Iter operator()(_Iter __first, _Sent __last, _Gen&& __gen) const { - // TODO: implement - (void)__first; (void)__last; (void)__gen; - return {}; + _ClassicGenAdaptor<_Gen> __adapted_gen(__gen); + return std::__shuffle<_RangeAlgPolicy>(std::move(__first), std::move(__last), __adapted_gen); } template requires permutable> && uniform_random_bit_generator> _LIBCPP_HIDE_FROM_ABI borrowed_iterator_t<_Range> operator()(_Range&& __range, _Gen&& __gen) const { - // TODO: implement - (void)__range; (void)__gen; - return {}; + return (*this)(ranges::begin(__range), ranges::end(__range), std::forward<_Gen>(__gen)); } }; @@ -69,6 +96,8 @@ _LIBCPP_END_NAMESPACE_STD +_LIBCPP_POP_MACROS + #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) #endif // _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H diff --git a/libcxx/include/__algorithm/shuffle.h b/libcxx/include/__algorithm/shuffle.h --- a/libcxx/include/__algorithm/shuffle.h +++ b/libcxx/include/__algorithm/shuffle.h @@ -136,11 +136,15 @@ } #endif -template -void __shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) { +template +_RandomAccessIterator __shuffle( + _RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef uniform_int_distribution _Dp; typedef typename _Dp::param_type _Pp; + + auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel); + auto __last = __original_last; difference_type __d = __last - __first; if (__d > 1) { @@ -152,12 +156,14 @@ _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i); } } + + return __original_last; } template void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) { - std::__shuffle<_ClassicAlgPolicy>( + (void)std::__shuffle<_ClassicAlgPolicy>( std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g)); } diff --git a/libcxx/include/__debug_utils/randomize_range.h b/libcxx/include/__debug_utils/randomize_range.h --- a/libcxx/include/__debug_utils/randomize_range.h +++ b/libcxx/include/__debug_utils/randomize_range.h @@ -22,8 +22,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 void __debug_randomize_range(_Iterator __first, _Iterator __last) { +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __debug_randomize_range(_Iterator __first, _Sentinel __last) { #ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY # ifdef _LIBCPP_CXX03_LANG # error Support for unspecified stability is only for C++11 and higher diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -710,6 +710,16 @@ constexpr ranges::rotate_copy_result, O> ranges::rotate_copy(R&& r, iterator_t middle, O result); // since C++20 + template S, class Gen> + requires permutable && + uniform_random_bit_generator> + I shuffle(I first, S last, Gen&& g); // Since C++20 + + template + requires permutable> && + uniform_random_bit_generator> + borrowed_iterator_t shuffle(R&& r, Gen&& g); // Since C++20 + template S1, forward_iterator I2, sentinel_for S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> @@ -1576,6 +1586,7 @@ #include <__algorithm/ranges_set_intersection.h> #include <__algorithm/ranges_set_symmetric_difference.h> #include <__algorithm/ranges_set_union.h> +#include <__algorithm/ranges_shuffle.h> #include <__algorithm/ranges_sort.h> #include <__algorithm/ranges_sort_heap.h> #include <__algorithm/ranges_stable_partition.h> diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_random_shuffle.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_random_shuffle.pass.cpp deleted file mode 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_random_shuffle.pass.cpp +++ /dev/null @@ -1,48 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// 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 -// -//===----------------------------------------------------------------------===// - -// UNSUPPORTED: c++03, c++11, c++14, c++17 -// UNSUPPORTED: libcpp-has-no-incomplete-ranges - -// - -// template S, class Gen> -// requires permutable && -// uniform_random_bit_generator> -// I shuffle(I first, S last, Gen&& g); // Since C++20 -// -// template -// requires permutable> && -// uniform_random_bit_generator> -// borrowed_iterator_t shuffle(R&& r, Gen&& g); // Since C++20 - -#include -#include -#include -#include -#include - -#include "almost_satisfies_types.h" -#include "test_iterators.h" - -// TODO: SFINAE tests. - -constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. - - return true; -} - -int main(int, char**) { - test(); - static_assert(test()); - - return 0; -} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.pass.cpp @@ -0,0 +1,269 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// + +// template S, class Gen> +// requires permutable && +// uniform_random_bit_generator> +// I shuffle(I first, S last, Gen&& g); // Since C++20 +// +// template +// requires permutable> && +// uniform_random_bit_generator> +// borrowed_iterator_t shuffle(R&& r, Gen&& g); // Since C++20 + +#include +#include +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" +#include "test_macros.h" + +class RandGen { +public: + constexpr static size_t min() { return 0; } + constexpr static size_t max() { return 255; } + + constexpr size_t operator()() { + flip = !flip; + return flip; + } + +private: + bool flip = false; +}; + +static_assert(std::uniform_random_bit_generator); +// `std::uniform_random_bit_generator` is a subset of requirements of `__libcpp_random_is_valid_urng`. Make sure that +// a type satisfying the required minimum is still accepted by `ranges::shuffle`. +LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng::value); + +struct BadGen { + constexpr static size_t min() { return 255; } + constexpr static size_t max() { return 0; } + constexpr size_t operator()() const; +}; +static_assert(!std::uniform_random_bit_generator); + +// Test constraints of the (iterator, sentinel) overload. +// ====================================================== + +template +concept HasShuffleIter = + requires(Iter&& iter, Sent&& sent, Gen&& gen) { + std::ranges::shuffle(std::forward(iter), std::forward(sent), std::forward(gen)); + }; + +static_assert(HasShuffleIter); + +// !random_access_iterator +static_assert(!HasShuffleIter); +static_assert(!HasShuffleIter); + +// !sentinel_for +static_assert(!HasShuffleIter); +static_assert(!HasShuffleIter); + +// !permutable +static_assert(!HasShuffleIter); +static_assert(!HasShuffleIter); + +// !uniform_random_bit_generator> +static_assert(!HasShuffleIter); + +// Test constraints of the (range) overload. +// ========================================= + +template +concept HasShuffleRange = + requires(Range&& range, Gen&& gen) { + std::ranges::shuffle(std::forward(range), std::forward(gen)); + }; + +template +using R = UncheckedRange; + +static_assert(HasShuffleRange, RandGen>); + +// !random_access_range +static_assert(!HasShuffleRange); +static_assert(!HasShuffleRange); + +// !permutable> +static_assert(!HasShuffleRange); +static_assert(!HasShuffleRange); + +// !uniform_random_bit_generator> +static_assert(!HasShuffleRange, BadGen>); + +template +void test_one(const std::array input, Gen gen) { + { // (iterator, sentinel) overload. + auto shuffled = input; + auto begin = Iter(shuffled.data()); + auto end = Sent(Iter(shuffled.data() + shuffled.size())); + + std::same_as decltype(auto) result = std::ranges::shuffle(begin, end, gen); + + assert(result == Iter(shuffled.data() + shuffled.size())); + // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting. + //assert(std::ranges::is_permutation(shuffled, input); + { + auto shuffled_sorted = shuffled; + std::ranges::sort(shuffled_sorted); + auto original_sorted = input; + std::ranges::sort(original_sorted); + assert(shuffled_sorted == original_sorted); + } + } + + { // (range) overload. + auto shuffled = input; + auto begin = Iter(shuffled.data()); + auto end = Sent(Iter(shuffled.data() + shuffled.size())); + auto range = std::ranges::subrange(begin, end); + + std::same_as decltype(auto) result = std::ranges::shuffle(range, gen); + + assert(result == Iter(shuffled.data() + shuffled.size())); + // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting. + //assert(std::ranges::is_permutation(shuffled, input); + { + auto shuffled_sorted = shuffled; + std::ranges::sort(shuffled_sorted); + auto original_sorted = input; + std::ranges::sort(original_sorted); + assert(shuffled_sorted == original_sorted); + } + } +} + +template +void test_iterators_iter_sent() { + RandGen gen; + + // Empty sequence. + test_one({}, gen); + // 1-element sequence. + test_one({1}, gen); + // 2-element sequence. + test_one({2, 1}, gen); + // 3-element sequence. + test_one({2, 1, 3}, gen); + // Longer sequence. + test_one({2, 1, 3, 6, 8, 4, 11, 5}, gen); + // Longer sequence with duplicates. + test_one({2, 1, 3, 6, 2, 8, 1, 6}, gen); + // All elements are the same. + test_one({1, 1, 1}, gen); +} + +template +void test_iterators_iter() { + test_iterators_iter_sent(); + test_iterators_iter_sent>(); +} + +void test_iterators() { + test_iterators_iter>(); + test_iterators_iter>(); + test_iterators_iter(); +} + +// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of the value category of +// the given generator object. +template +void test_generator() { + std::array in = {1, 2, 3, 4, 5, 6, 7, 8}; + auto begin = in.begin(); + auto end = in.end(); + + { // Lvalue. + Gen g; + std::ranges::shuffle(begin, end, g); + std::ranges::shuffle(in, g); + } + + if constexpr (CheckConst) { // Const lvalue. + const Gen g; + std::ranges::shuffle(begin, end, g); + std::ranges::shuffle(in, g); + } + + { // Prvalue. + std::ranges::shuffle(begin, end, Gen()); + std::ranges::shuffle(in, Gen()); + } + + { // Xvalue. + Gen g1, g2; + std::ranges::shuffle(begin, end, std::move(g1)); + std::ranges::shuffle(in, std::move(g2)); + } +} + +// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of whether the given +// generator class has a const or non-const invocation operator (or both). +void test_generators() { + struct GenBase { + constexpr static size_t min() { return 0; } + constexpr static size_t max() { return 255; } + }; + struct NonconstGen : GenBase { + size_t operator()() { return 1; } + }; + struct ConstGen : GenBase { + size_t operator()() const { return 1; } + }; + struct ConstAndNonconstGen : GenBase { + size_t operator()() { return 1; } + size_t operator()() const { return 1; } + }; + + test_generator(); + test_generator(); + test_generator(); +} + +void test() { + test_iterators(); + test_generators(); + + { // Complexity: Exactly `(last - first) - 1` swaps. + { + std::array in = {-2, -5, -8, -11, -10, -5, 1, 3, 9, 6, 8, 2, 4, 2}; //14 + + int swaps = 0; + auto begin = adl::Iterator::TrackSwaps(in.data(), swaps); + auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps); + + std::ranges::shuffle(begin, end, RandGen()); + int expected = in.size() - 1; + // Note: our implementation doesn't perform a swap when the distribution returns 0, so the actual number of swaps + // might be less than specified in the standard. + assert(swaps <= expected); + swaps = 0; + } + } +} + +int main(int, char**) { + test(); + // Note: `ranges::shuffle` is not `constexpr`. + + return 0; +} diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp @@ -60,6 +60,8 @@ static_assert(std::same_as); } +std::mt19937 rand_gen() { return std::mt19937(); } + // TODO: also check the iterator values for algorithms that return `*_result` types. constexpr bool test_all() { using std::ranges::dangling; @@ -91,7 +93,6 @@ auto unary_pred = [](int i) { return i > 0; }; auto binary_pred = [](int i, int j) { return i < j; }; //auto gen = [] { return 42; }; - //std::mt19937 rand_gen; std::array in = {1, 2, 3}; std::array in2 = {4, 5, 6}; @@ -181,7 +182,8 @@ dangling_1st(std::ranges::remove_if, in, unary_pred); dangling_1st(std::ranges::reverse, in); //dangling_1st(std::ranges::rotate, in, mid); - //dangling_1st(std::ranges::shuffle, in, rand_gen); + if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`. + dangling_1st(std::ranges::shuffle, in, rand_gen()); //dangling_1st(std::ranges::unique, in); dangling_1st(std::ranges::partition, in, unary_pred); if (!std::is_constant_evaluated()) diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -48,6 +48,8 @@ func(in, mid, std::forward(args)...); } +std::mt19937 rand_gen() { return std::mt19937(); } + template constexpr void run_tests() { std::array input = {T{1}, T{2}, T{3}}; @@ -69,7 +71,6 @@ //auto binary_pred = [](const Proxy&, const Proxy&) { return return false; }; auto binary_func = [](const Proxy&, const Proxy&) -> Proxy { return Proxy(T()); }; //auto gen = [] { return Proxy(T{42}); }; - //std::mt19937 rand_gen; test(std::ranges::any_of, in, unary_pred); test(std::ranges::all_of, in, unary_pred); @@ -148,8 +149,10 @@ test(std::ranges::remove_if, in, unary_pred); test(std::ranges::reverse, in); //test_mid(std::ranges::rotate, in, mid); - //test(std::ranges::shuffle, in, rand_gen); - //test(std::ranges::sample, in, out, count, rand_gen); + if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`. + test(std::ranges::shuffle, in, rand_gen()); + //if (!std::is_constant_evaluated()) + // test(std::ranges::sample, in, out, count, rand_gen()); //test(std::ranges::unique, in); test(std::ranges::partition, in, unary_pred); // TODO(ranges): `stable_partition` requires `ranges::rotate` to be implemented. diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -57,7 +57,7 @@ auto triple = [](int x) { return 3*x; }; //auto gen = [] { return 42; }; //auto plus = [](int x, int y) { return x == y; }; -//std::mt19937 g; +std::mt19937 g; // [algorithm.syn] @@ -137,7 +137,7 @@ static_assert(test(std::ranges::set_intersection, a, a, a)); static_assert(test(std::ranges::set_symmetric_difference, a, a, a)); static_assert(test(std::ranges::set_union, a, a, a)); -//static_assert(test(std::ranges::shuffle, a, g)); +static_assert(test(std::ranges::shuffle, a, g)); static_assert(test(std::ranges::sort, a)); static_assert(test(std::ranges::sort_heap, a)); static_assert(test(std::ranges::stable_partition, a, odd)); diff --git a/libcxx/test/support/test_iterators.h b/libcxx/test/support/test_iterators.h --- a/libcxx/test/support/test_iterators.h +++ b/libcxx/test/support/test_iterators.h @@ -758,6 +758,7 @@ class Iterator { public: using value_type = int; + using reference = int&; using difference_type = ptrdiff_t; private: @@ -786,9 +787,27 @@ constexpr int iter_swaps() const { assert(iter_swaps_); return *iter_swaps_; } constexpr value_type& operator*() const { return *ptr_; } + constexpr reference operator[](difference_type n) const { return ptr_[n]; } - constexpr Iterator operator+(difference_type n) const { - return Iterator(ptr_ + n, iter_moves_, iter_swaps_); + friend constexpr Iterator operator+(Iterator i, difference_type n) { + return Iterator(i.ptr_ + n, i.iter_moves_, i.iter_swaps_); + } + friend constexpr Iterator operator+(difference_type n, Iterator i) { + return i + n; + } + constexpr Iterator operator-(difference_type n) const { + return Iterator(ptr_ - n, iter_moves_, iter_swaps_); + } + constexpr difference_type operator-(Iterator rhs) const { + return ptr_ - rhs.ptr_; + } + constexpr Iterator& operator+=(difference_type n) { + ptr_ += n; + return *this; + } + constexpr Iterator& operator-=(difference_type n) { + ptr_ -= n; + return *this; } constexpr Iterator& operator++() { ++ptr_; return *this; } @@ -805,7 +824,8 @@ return prev; } - constexpr friend void iter_swap(Iterator a, Iterator) { + constexpr friend void iter_swap(Iterator a, Iterator b) { + std::swap(a.ptr_, b.ptr_); if (a.iter_swaps_) { ++(*a.iter_swaps_); } @@ -818,7 +838,12 @@ return std::move(*iter); } - constexpr friend bool operator==(const Iterator& lhs, const Iterator& rhs) { return lhs.ptr_ == rhs.ptr_; } + constexpr friend bool operator==(const Iterator& lhs, const Iterator& rhs) { + return lhs.ptr_ == rhs.ptr_; + } + constexpr friend auto operator<=>(const Iterator& lhs, const Iterator& rhs) { + return lhs.ptr_ <=> rhs.ptr_; + } }; } // namespace adl