Diff 441812

libcxx/benchmarks/CMakeLists.txt

	Show First 20 Lines • Show All 161 Lines • ▼ Show 20 Lines
	set(BENCHMARK_TESTS			set(BENCHMARK_TESTS
	algorithms/lower_bound.bench.cpp			algorithms/lower_bound.bench.cpp
	algorithms/make_heap.bench.cpp			algorithms/make_heap.bench.cpp
	algorithms/make_heap_then_sort_heap.bench.cpp			algorithms/make_heap_then_sort_heap.bench.cpp
	algorithms/min_max_element.bench.cpp			algorithms/min_max_element.bench.cpp
	algorithms/pop_heap.bench.cpp			algorithms/pop_heap.bench.cpp
	algorithms/push_heap.bench.cpp			algorithms/push_heap.bench.cpp
	algorithms/ranges_sort.bench.cpp			algorithms/ranges_sort.bench.cpp
				algorithms/ranges_stable_sort.bench.cpp
	algorithms/sort.bench.cpp			algorithms/sort.bench.cpp
	algorithms/sort_heap.bench.cpp			algorithms/sort_heap.bench.cpp
	algorithms/stable_sort.bench.cpp			algorithms/stable_sort.bench.cpp
	algorithms.partition_point.bench.cpp			algorithms.partition_point.bench.cpp
	allocation.bench.cpp			allocation.bench.cpp
	deque.bench.cpp			deque.bench.cpp
	filesystem.bench.cpp			filesystem.bench.cpp
	function.bench.cpp			function.bench.cpp
	▲ Show 20 Lines • Show All 54 Lines • Show Last 20 Lines

libcxx/benchmarks/algorithms/ranges_stable_sort.bench.cpp

This file was added.

				//===----------------------------------------------------------------------===//
				//
				// 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 "common.h"

				namespace {
				template <class ValueType, class Order>
				struct StableSort {
				size_t Quantity;

				void run(benchmark::State& state) const {
				runOpOnCopies<ValueType>(
				state, Quantity, Order(), BatchSize::CountElements,
				[](auto& Copy) { std::ranges::stable_sort(Copy); });
				}

				bool skip() const { return Order() == ::Order::Heap; }

				std::string name() const {
				return "BM_RangesStableSort" + ValueType::name() + Order::name() + "_" +
				std::to_string(Quantity);
				}
				};
				} // namespace

				int main(int argc, char** argv) {
				benchmark::Initialize(&argc, argv);
				if (benchmark::ReportUnrecognizedArguments(argc, argv))
				return 1;
				makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>(Quantities);
				benchmark::RunSpecifiedBenchmarks();
				}

libcxx/docs/Status/RangesAlgorithms.csv

Show First 20 Lines • Show All 68 Lines • ▼ Show 20 Lines

Permutation,remove_if,Not assigned,n/a,Not started

Permutation,reverse,Nikolas Klauser,`D125752 <https://llvm.org/D125752>`_,✅

Permutation,rotate,Nikolas Klauser,`D124122 <https://llvm.org/D124122>`_,Under review

Permutation,shuffle,Not assigned,n/a,Not started

Permutation,unique,Not assigned,n/a,Not started

Permutation,partition,Not assigned,n/a,Not started

Permutation,stable_partition,Not assigned,n/a,Not started

Permutation,sort,Konstantin Varlamov,`D127557 <https://llvm.org/D127557>`_,✅

Permutation,stable_sort,Konstantin Varlamov,n/a,In progress

Permutation,stable_sort,Konstantin Varlamov,`D127834 <https://llvm.org/D127834>`_,✅

ldionneUnsubmitted

Done

Permutation,sort,`D127557 <https://llvm.org/D127557>`_,Konstantin Varlamov,✅

- Permutation,stable_sort,Konstantin Varlamov,`D127834 <https://llvm.org/D127834>`_,Under review

+ Permutation,stable_sort,Konstantin Varlamov,`D127834 <https://llvm.org/D127834>`_,✅

Permutation,partial_sort,Konstantin Varlamov,n/a,In progress

Once you commit this, it'll be done, not under review.

ldionne: Once you commit this, it'll be done, not under review.

Permutation,partial_sort,Konstantin Varlamov,n/a,In progress

Permutation,nth_element,Not assigned,n/a,Not started

Permutation,inplace_merge,Not assigned,n/a,Not started

Permutation,make_heap,Not assigned,n/a,Not started

Permutation,push_heap,Not assigned,n/a,Not started

Permutation,pop_heap,Not assigned,n/a,Not started

Permutation,sort_heap,Not assigned,n/a,Not started

Permutation,prev_permutation,Not assigned,n/a,Not started

Show All 15 Lines

libcxx/include/CMakeLists.txt

Show First 20 Lines • Show All 100 Lines • ▼ Show 20 Lines	set(files
__algorithm/ranges_mismatch.h		__algorithm/ranges_mismatch.h
__algorithm/ranges_move.h		__algorithm/ranges_move.h
__algorithm/ranges_move_backward.h		__algorithm/ranges_move_backward.h
__algorithm/ranges_none_of.h		__algorithm/ranges_none_of.h
__algorithm/ranges_replace.h		__algorithm/ranges_replace.h
__algorithm/ranges_replace_if.h		__algorithm/ranges_replace_if.h
__algorithm/ranges_reverse.h		__algorithm/ranges_reverse.h
__algorithm/ranges_sort.h		__algorithm/ranges_sort.h
		__algorithm/ranges_stable_sort.h
__algorithm/ranges_swap_ranges.h		__algorithm/ranges_swap_ranges.h
__algorithm/ranges_transform.h		__algorithm/ranges_transform.h
__algorithm/ranges_upper_bound.h		__algorithm/ranges_upper_bound.h
__algorithm/remove.h		__algorithm/remove.h
__algorithm/remove_copy.h		__algorithm/remove_copy.h
__algorithm/remove_copy_if.h		__algorithm/remove_copy_if.h
__algorithm/remove_if.h		__algorithm/remove_if.h
__algorithm/replace.h		__algorithm/replace.h
▲ Show 20 Lines • Show All 662 Lines • Show Last 20 Lines

libcxx/include/__algorithm/ranges_sort.h

This file was copied to libcxx/include/__algorithm/ranges_stable_sort.h.

	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//
	//			//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.			// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.			// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception			// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//

	#ifndef _LIBCPP___ALGORITHM_RANGES_SORT_H			#ifndef _LIBCPP___ALGORITHM_RANGES_SORT_H
	#define _LIBCPP___ALGORITHM_RANGES_SORT_H			#define _LIBCPP___ALGORITHM_RANGES_SORT_H

	#include <__algorithm/make_projected.h>			#include <__algorithm/make_projected.h>
	#include <__algorithm/sort.h>			#include <__algorithm/sort.h>
	#include <__concepts/same_as.h>
	#include <__config>			#include <__config>
	#include <__functional/identity.h>			#include <__functional/identity.h>
	#include <__functional/invoke.h>			#include <__functional/invoke.h>
	#include <__functional/ranges_operations.h>			#include <__functional/ranges_operations.h>
	#include <__iterator/concepts.h>			#include <__iterator/concepts.h>
	#include <__iterator/iterator_traits.h>			#include <__iterator/iterator_traits.h>
	#include <__iterator/next.h>			#include <__iterator/next.h>
	#include <__iterator/projected.h>			#include <__iterator/projected.h>
	Show All 16 Lines
	namespace __sort {			namespace __sort {

	struct __fn {			struct __fn {
	template <class _Iter, class _Sent, class _Comp, class _Proj>			template <class _Iter, class _Sent, class _Comp, class _Proj>
	_LIBCPP_HIDE_FROM_ABI constexpr static			_LIBCPP_HIDE_FROM_ABI constexpr static
	_Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {			_Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
	auto __last_iter = ranges::next(__first, __last);			auto __last_iter = ranges::next(__first, __last);

	auto&& __projected_comp = __make_projected_comp(__comp, __proj);			auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
	std::__sort_impl(std::move(__first), __last_iter, __projected_comp);			std::__sort_impl(std::move(__first), __last_iter, __projected_comp);

	return __last_iter;			return __last_iter;
	}			}

	template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>			template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
	requires sortable<_Iter, _Comp, _Proj>			requires sortable<_Iter, _Comp, _Proj>
	_LIBCPP_HIDE_FROM_ABI constexpr			_LIBCPP_HIDE_FROM_ABI constexpr
	Show All 24 Lines

libcxx/include/__algorithm/ranges_stable_sort.h

This file was copied from libcxx/include/__algorithm/ranges_sort.h.

//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//

// //

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

// //

//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//

#ifndef _LIBCPP___ALGORITHM_RANGES_SORT_H #ifndef _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H

#define _LIBCPP___ALGORITHM_RANGES_SORT_H #define _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H

#include <__algorithm/make_projected.h> #include <__algorithm/make_projected.h>

#include <__algorithm/sort.h> #include <__algorithm/stable_sort.h>

#include <__concepts/same_as.h>

#include <__config> #include <__config>

#include <__functional/identity.h> #include <__functional/identity.h>

#include <__functional/invoke.h> #include <__functional/invoke.h>

#include <__functional/ranges_operations.h> #include <__functional/ranges_operations.h>

#include <__iterator/concepts.h> #include <__iterator/concepts.h>

#include <__iterator/iterator_traits.h> #include <__iterator/iterator_traits.h>

#include <__iterator/next.h> #include <__iterator/next.h>

#include <__iterator/projected.h> #include <__iterator/projected.h>

#include <__iterator/sortable.h> #include <__iterator/sortable.h>

#include <__ranges/access.h> #include <__ranges/access.h>

#include <__ranges/concepts.h> #include <__ranges/concepts.h>

#include <__ranges/dangling.h> #include <__ranges/dangling.h>

#include <__utility/forward.h> #include <__utility/forward.h>

#include <__utility/move.h> #include <__utility/move.h>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

# pragma GCC system_header # pragma GCC system_header

#endif #endif

#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)

_LIBCPP_BEGIN_NAMESPACE_STD _LIBCPP_BEGIN_NAMESPACE_STD

namespace ranges { namespace ranges {

namespace __sort { namespace __stable_sort {

MordanteUnsubmitted

Done

Please remove the constexpr

Mordante: Please remove the `constexpr`

var-constAuthorUnsubmitted

Done

Thanks!

var-const: Thanks!

struct __fn { struct __fn {

template <class _Iter, class _Sent, class _Comp, class _Proj> template <class _Iter, class _Sent, class _Comp, class _Proj>

_LIBCPP_HIDE_FROM_ABI constexpr static _LIBCPP_HIDE_FROM_ABI

_Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { static _Iter __stable_sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {

philnikUnsubmitted

Done

Maybe name it __ranges_stable_sort_impl?

philnik: Maybe name it `__ranges_stable_sort_impl`?

var-constAuthorUnsubmitted

Done

I somewhat prefer the current version (name of the algorithm + fn to indicate that the function is contained within the function object + impl for disambiguation). I'd keep the current state unless you feel strongly about it.

var-const: I somewhat prefer the current version (name of the algorithm + `fn` to indicate that the…

auto __last_iter = ranges::next(__first, __last); auto __last_iter = ranges::next(__first, __last);

philnikUnsubmitted

Done

Why is this not static but instead marked const?

philnik: Why is this not `static` but instead marked `const`?

var-constAuthorUnsubmitted

Done

Thanks for spotting!

var-const: Thanks for spotting!

auto&& __projected_comp = __make_projected_comp(__comp, __proj); auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);

philnikUnsubmitted

Done

auto __last_iter = ranges::next(__first, __last);

- auto&& __projected_comp = __make_projected_comp(__comp, __proj);

+ auto&& __projected_comp = std::__make_projected_comp(__comp, __proj);

std::__stable_sort_impl(std::move(__first), __last_iter, __projected_comp);

This probably also applies to ranges::sort.

philnik: This probably also applies to `ranges::sort`.

var-constAuthorUnsubmitted

Done

Thanks! Fixed both.

var-const: Thanks! Fixed both.

std::__sort_impl(std::move(__first), __last_iter, __projected_comp); std::__stable_sort_impl(std::move(__first), __last_iter, __projected_comp);

return __last_iter; return __last_iter;

} }

template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity> template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>

requires sortable<_Iter, _Comp, _Proj> requires sortable<_Iter, _Comp, _Proj>

_LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_HIDE_FROM_ABI

_Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

return __sort_fn_impl(std::move(__first), std::move(__last), __comp, __proj); return __stable_sort_fn_impl(std::move(__first), std::move(__last), __comp, __proj);

} }

template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity> template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>

requires sortable<iterator_t<_Range>, _Comp, _Proj> requires sortable<iterator_t<_Range>, _Comp, _Proj>

_LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_HIDE_FROM_ABI

borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const { borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {

return __sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); return __stable_sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);

} }

}; };

} // namespace __sort } // namespace __stable_sort

inline namespace __cpo { inline namespace __cpo {

inline constexpr auto sort = __sort::__fn{}; inline constexpr auto stable_sort = __stable_sort::__fn{};

} // namespace __cpo } // namespace __cpo

} // namespace ranges } // namespace ranges

_LIBCPP_END_NAMESPACE_STD _LIBCPP_END_NAMESPACE_STD

#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)

#endif // _LIBCPP___ALGORITHM_RANGES_SORT_H #endif // _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H

libcxx/include/__algorithm/stable_sort.h

Show All 9 Lines

#define _LIBCPP___ALGORITHM_STABLE_SORT_H #define _LIBCPP___ALGORITHM_STABLE_SORT_H

#include <__algorithm/comp.h> #include <__algorithm/comp.h>

#include <__algorithm/comp_ref_type.h> #include <__algorithm/comp_ref_type.h>

#include <__algorithm/inplace_merge.h> #include <__algorithm/inplace_merge.h>

#include <__algorithm/sort.h> #include <__algorithm/sort.h>

#include <__config> #include <__config>

#include <__iterator/iterator_traits.h> #include <__iterator/iterator_traits.h>

#include <__utility/move.h>

#include <__utility/swap.h> #include <__utility/swap.h>

#include <memory> #include <memory>

#include <type_traits> #include <type_traits>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

# pragma GCC system_header # pragma GCC system_header

#endif #endif

▲ Show 20 Lines • Show All 168 Lines • ▼ Show 20 Lines // __first, __comp);

return; return;

} }

_VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);

_VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);

_VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);

} }

template <class _RandomAccessIterator, class _Compare> template <class _RandomAccessIterator, class _Compare>

inline _LIBCPP_INLINE_VISIBILITY inline _LIBCPP_HIDE_FROM_ABI

void void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {

stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;

{ using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;

typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;

typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

difference_type __len = __last - __first; difference_type __len = __last - __first;

pair<value_type*, ptrdiff_t> __buf(0, 0); pair<value_type*, ptrdiff_t> __buf(0, 0);

unique_ptr<value_type, __return_temporary_buffer> __h; unique_ptr<value_type, __return_temporary_buffer> __h;

if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) {

{

// TODO: Remove the use of std::get_temporary_buffer // TODO: Remove the use of std::get_temporary_buffer

_LIBCPP_SUPPRESS_DEPRECATED_PUSH _LIBCPP_SUPPRESS_DEPRECATED_PUSH

__buf = _VSTD::get_temporary_buffer<value_type>(__len); __buf = std::get_temporary_buffer<value_type>(__len);

_LIBCPP_SUPPRESS_DEPRECATED_POP _LIBCPP_SUPPRESS_DEPRECATED_POP

__h.reset(__buf.first); __h.reset(__buf.first);

} }

typedef typename __comp_ref_type<_Compare>::type _Comp_ref;

_VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); using _Comp_ref = typename __comp_ref_type<_Compare>::type;

std::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);

}

template <class _RandomAccessIterator, class _Compare>

inline _LIBCPP_HIDE_FROM_ABI

MordanteUnsubmitted

Done

if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) {

- __buf = _VSTD::get_temporary_buffer<value_type>(__len);

+ __buf = std::get_temporary_buffer<value_type>(__len);

__h.reset(__buf.first);

While you're at it.

Mordante: While you're at it.

void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {

philnikUnsubmitted

Done

Would you be interested in removing std::get_temporary_buffer and std::return_temporary_buffer in a follow-up patch? It's deprecated and just forwards to new and delete.

philnik: Would you be interested in removing `std::get_temporary_buffer` and `std…

var-constAuthorUnsubmitted

Done

Yes, I can do this in a follow-up (unless you beat me to it :) ).

var-const: Yes, I can do this in a follow-up (unless you beat me to it :) ).

std::__stable_sort_impl(std::move(__first), std::move(__last), __comp);

} }

template <class _RandomAccessIterator> template <class _RandomAccessIterator>

inline _LIBCPP_INLINE_VISIBILITY inline _LIBCPP_HIDE_FROM_ABI

void void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {

stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) std::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

{

_VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

} }

_LIBCPP_END_NAMESPACE_STD _LIBCPP_END_NAMESPACE_STD

#endif // _LIBCPP___ALGORITHM_STABLE_SORT_H #endif // _LIBCPP___ALGORITHM_STABLE_SORT_H

libcxx/include/algorithm

Show First 20 Lines • Show All 281 Lines • ▼ Show 20 Lines	template<input_range R, class Proj = identity,
template<input_iterator I, sentinel_for<I> S, class Proj = identity,		template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>		indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {}); // since C++20		constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {}); // since C++20

template<input_range R, class Proj = identity,		template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>		indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {}); // since C++20		constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {}); // since C++20


template<bidirectional_iterator I, sentinel_for<I> S>		template<bidirectional_iterator I, sentinel_for<I> S>
requires permutable<I>		requires permutable<I>
constexpr I ranges::reverse(I first, S last); // since C++20		constexpr I ranges::reverse(I first, S last); // since C++20

template<bidirectional_range R>		template<bidirectional_range R>
requires permutable<iterator_t<R>>		requires permutable<iterator_t<R>>
constexpr borrowed_iterator_t<R> ranges::reverse(R&& r); // since C++20		constexpr borrowed_iterator_t<R> ranges::reverse(R&& r); // since C++20

template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,		template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>		class Proj = identity>
requires sortable<I, Comp, Proj>		requires sortable<I, Comp, Proj>
constexpr I		constexpr I
sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20		ranges::sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20

template<random_access_range R, class Comp = ranges::less, class Proj = identity>		template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>		requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>		constexpr borrowed_iterator_t<R>
sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20		ranges::sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20

		template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
		class Proj = identity>
		requires sortable<I, Comp, Proj>
		I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20

		template<random_access_range R, class Comp = ranges::less, class Proj = identity>
		requires sortable<iterator_t<R>, Comp, Proj>
		borrowed_iterator_t<R>
		ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20

template<class T, output_iterator<const T&> O, sentinel_for<O> S>		template<class T, output_iterator<const T&> O, sentinel_for<O> S>
constexpr O ranges::fill(O first, S last, const T& value); // since C++20		constexpr O ranges::fill(O first, S last, const T& value); // since C++20

template<class T, output_range<const T&> R>		template<class T, output_range<const T&> R>
constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value); // since C++20		constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value); // since C++20

template<class T, output_iterator<const T&> O>		template<class T, output_iterator<const T&> O>
▲ Show 20 Lines • Show All 930 Lines • ▼ Show 20 Lines
#include <__algorithm/ranges_mismatch.h>		#include <__algorithm/ranges_mismatch.h>
#include <__algorithm/ranges_move.h>		#include <__algorithm/ranges_move.h>
#include <__algorithm/ranges_move_backward.h>		#include <__algorithm/ranges_move_backward.h>
#include <__algorithm/ranges_none_of.h>		#include <__algorithm/ranges_none_of.h>
#include <__algorithm/ranges_replace.h>		#include <__algorithm/ranges_replace.h>
#include <__algorithm/ranges_replace_if.h>		#include <__algorithm/ranges_replace_if.h>
#include <__algorithm/ranges_reverse.h>		#include <__algorithm/ranges_reverse.h>
#include <__algorithm/ranges_sort.h>		#include <__algorithm/ranges_sort.h>
		#include <__algorithm/ranges_stable_sort.h>
#include <__algorithm/ranges_swap_ranges.h>		#include <__algorithm/ranges_swap_ranges.h>
#include <__algorithm/ranges_transform.h>		#include <__algorithm/ranges_transform.h>
#include <__algorithm/ranges_upper_bound.h>		#include <__algorithm/ranges_upper_bound.h>
#include <__algorithm/remove.h>		#include <__algorithm/remove.h>
#include <__algorithm/remove_copy.h>		#include <__algorithm/remove_copy.h>
#include <__algorithm/remove_copy_if.h>		#include <__algorithm/remove_copy_if.h>
#include <__algorithm/remove_if.h>		#include <__algorithm/remove_if.h>
#include <__algorithm/replace.h>		#include <__algorithm/replace.h>
▲ Show 20 Lines • Show All 47 Lines • Show Last 20 Lines

libcxx/include/module.modulemap.in

Show First 20 Lines • Show All 339 Lines • ▼ Show 20 Lines	module __algorithm {
module ranges_mismatch { private header "__algorithm/ranges_mismatch.h" }		module ranges_mismatch { private header "__algorithm/ranges_mismatch.h" }
module ranges_move { private header "__algorithm/ranges_move.h" }		module ranges_move { private header "__algorithm/ranges_move.h" }
module ranges_move_backward { private header "__algorithm/ranges_move_backward.h" }		module ranges_move_backward { private header "__algorithm/ranges_move_backward.h" }
module ranges_none_of { private header "__algorithm/ranges_none_of.h" }		module ranges_none_of { private header "__algorithm/ranges_none_of.h" }
module ranges_replace { private header "__algorithm/ranges_replace.h" }		module ranges_replace { private header "__algorithm/ranges_replace.h" }
module ranges_replace_if { private header "__algorithm/ranges_replace_if.h" }		module ranges_replace_if { private header "__algorithm/ranges_replace_if.h" }
module ranges_reverse { private header "__algorithm/ranges_reverse.h" }		module ranges_reverse { private header "__algorithm/ranges_reverse.h" }
module ranges_sort { private header "__algorithm/ranges_sort.h" }		module ranges_sort { private header "__algorithm/ranges_sort.h" }
		module ranges_stable_sort { private header "__algorithm/ranges_stable_sort.h" }
module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.h" }		module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.h" }
module ranges_transform { private header "__algorithm/ranges_transform.h" }		module ranges_transform { private header "__algorithm/ranges_transform.h" }
module ranges_upper_bound { private header "__algorithm/ranges_upper_bound.h" }		module ranges_upper_bound { private header "__algorithm/ranges_upper_bound.h" }
module remove { private header "__algorithm/remove.h" }		module remove { private header "__algorithm/remove.h" }
module remove_copy { private header "__algorithm/remove_copy.h" }		module remove_copy { private header "__algorithm/remove_copy.h" }
module remove_copy_if { private header "__algorithm/remove_copy_if.h" }		module remove_copy_if { private header "__algorithm/remove_copy_if.h" }
module remove_if { private header "__algorithm/remove_if.h" }		module remove_if { private header "__algorithm/remove_if.h" }
module replace { private header "__algorithm/replace.h" }		module replace { private header "__algorithm/replace.h" }
▲ Show 20 Lines • Show All 966 Lines • Show Last 20 Lines

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

Show First 20 Lines • Show All 207 Lines • ▼ Show 20 Lines	#endif
//(void)std::ranges::set_union(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);		//(void)std::ranges::set_union(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
//(void)std::ranges::set_union(a, b, first2, Less(&copies)); assert(copies == 0);		//(void)std::ranges::set_union(a, b, first2, Less(&copies)); assert(copies == 0);
(void)std::ranges::sort(first, last, Less(&copies)); assert(copies == 0);		(void)std::ranges::sort(first, last, Less(&copies)); assert(copies == 0);
(void)std::ranges::sort(a, Less(&copies)); assert(copies == 0);		(void)std::ranges::sort(a, Less(&copies)); assert(copies == 0);
//(void)std::ranges::sort_heap(first, last, Less(&copies)); assert(copies == 0);		//(void)std::ranges::sort_heap(first, last, Less(&copies)); assert(copies == 0);
//(void)std::ranges::sort_heap(a, Less(&copies)); assert(copies == 0);		//(void)std::ranges::sort_heap(a, Less(&copies)); assert(copies == 0);
//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(&copies)); assert(copies == 0); }		//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(&copies)); assert(copies == 0); }
//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(&copies)); assert(copies == 0); }		//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(&copies)); assert(copies == 0); }
//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(&copies)); assert(copies == 0); }		if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(&copies)); assert(copies == 0); }
//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(&copies)); assert(copies == 0); }		if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(&copies)); assert(copies == 0); }
#if TEST_STD_VER > 20		#if TEST_STD_VER > 20
//(void)std::ranges::starts_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0);		//(void)std::ranges::starts_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
#endif		#endif
(void)std::ranges::transform(first, last, first2, UnaryTransform(&copies)); assert(copies == 0);		(void)std::ranges::transform(first, last, first2, UnaryTransform(&copies)); assert(copies == 0);
(void)std::ranges::transform(a, first2, UnaryTransform(&copies)); assert(copies == 0);		(void)std::ranges::transform(a, first2, UnaryTransform(&copies)); assert(copies == 0);
(void)std::ranges::transform(first, mid, mid, last, first2, BinaryTransform(&copies)); assert(copies == 0);		(void)std::ranges::transform(first, mid, mid, last, first2, BinaryTransform(&copies)); assert(copies == 0);
(void)std::ranges::transform(a, b, first2, BinaryTransform(&copies)); assert(copies == 0);		(void)std::ranges::transform(a, b, first2, BinaryTransform(&copies)); assert(copies == 0);
//(void)std::ranges::unique(first, last, Equal(&copies)); assert(copies == 0);		//(void)std::ranges::unique(first, last, Equal(&copies)); assert(copies == 0);
Show All 16 Lines

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

Show First 20 Lines • Show All 198 Lines • ▼ Show 20 Lines	#endif
//(void)std::ranges::set_union(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);		//(void)std::ranges::set_union(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
//(void)std::ranges::set_union(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);		//(void)std::ranges::set_union(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
(void)std::ranges::sort(first, last, Less(), Proj(&copies)); assert(copies == 0);		(void)std::ranges::sort(first, last, Less(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::sort(a, Less(), Proj(&copies)); assert(copies == 0);		(void)std::ranges::sort(a, Less(), Proj(&copies)); assert(copies == 0);
//(void)std::ranges::sort_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);		//(void)std::ranges::sort_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
//(void)std::ranges::sort_heap(a, Less(), Proj(&copies)); assert(copies == 0);		//(void)std::ranges::sort_heap(a, Less(), Proj(&copies)); assert(copies == 0);
//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); }		//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); }
//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); }		//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); }
//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(), Proj(&copies)); assert(copies == 0); }		if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(), Proj(&copies)); assert(copies == 0); }
//if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(), Proj(&copies)); assert(copies == 0); }		if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(), Proj(&copies)); assert(copies == 0); }
#if TEST_STD_VER > 20		#if TEST_STD_VER > 20
//(void)std::ranges::starts_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);		//(void)std::ranges::starts_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
#endif		#endif
(void)std::ranges::transform(first, last, first2, UnaryTransform(), Proj(&copies)); assert(copies == 0);		(void)std::ranges::transform(first, last, first2, UnaryTransform(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::transform(a, first2, UnaryTransform(), Proj(&copies)); assert(copies == 0);		(void)std::ranges::transform(a, first2, UnaryTransform(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::transform(first, mid, mid, last, first2, BinaryTransform(), Proj(&copies), Proj(&copies)); assert(copies == 0);		(void)std::ranges::transform(first, mid, mid, last, first2, BinaryTransform(), Proj(&copies), Proj(&copies)); assert(copies == 0);
(void)std::ranges::transform(a, b, first2, BinaryTransform(), Proj(&copies), Proj(&copies)); assert(copies == 0);		(void)std::ranges::transform(a, b, first2, BinaryTransform(), Proj(&copies), Proj(&copies)); assert(copies == 0);
//(void)std::ranges::unique(first, last, Equal(), Proj(&copies)); assert(copies == 0);		//(void)std::ranges::unique(first, last, Equal(), Proj(&copies)); assert(copies == 0);
Show All 16 Lines

libcxx/test/libcxx/private_headers.verify.cpp

	Show First 20 Lines • Show All 137 Lines • ▼ Show 20 Lines
	#include <__algorithm/ranges_mismatch.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}			#include <__algorithm/ranges_mismatch.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
	#include <__algorithm/ranges_move.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_move.h'}}			#include <__algorithm/ranges_move.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_move.h'}}
	#include <__algorithm/ranges_move_backward.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}}			#include <__algorithm/ranges_move_backward.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}}
	#include <__algorithm/ranges_none_of.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}}			#include <__algorithm/ranges_none_of.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}}
	#include <__algorithm/ranges_replace.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_replace.h'}}			#include <__algorithm/ranges_replace.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_replace.h'}}
	#include <__algorithm/ranges_replace_if.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}}			#include <__algorithm/ranges_replace_if.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}}
	#include <__algorithm/ranges_reverse.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}			#include <__algorithm/ranges_reverse.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}
	#include <__algorithm/ranges_sort.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_sort.h'}}			#include <__algorithm/ranges_sort.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_sort.h'}}
				#include <__algorithm/ranges_stable_sort.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_stable_sort.h'}}
	#include <__algorithm/ranges_swap_ranges.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}			#include <__algorithm/ranges_swap_ranges.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}
	#include <__algorithm/ranges_transform.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}			#include <__algorithm/ranges_transform.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}
	#include <__algorithm/ranges_upper_bound.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}}			#include <__algorithm/ranges_upper_bound.h> // expected-error@: {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}}
	#include <__algorithm/remove.h> // expected-error@: {{use of private header from outside its module: '__algorithm/remove.h'}}			#include <__algorithm/remove.h> // expected-error@: {{use of private header from outside its module: '__algorithm/remove.h'}}
	#include <__algorithm/remove_copy.h> // expected-error@: {{use of private header from outside its module: '__algorithm/remove_copy.h'}}			#include <__algorithm/remove_copy.h> // expected-error@: {{use of private header from outside its module: '__algorithm/remove_copy.h'}}
	#include <__algorithm/remove_copy_if.h> // expected-error@: {{use of private header from outside its module: '__algorithm/remove_copy_if.h'}}			#include <__algorithm/remove_copy_if.h> // expected-error@: {{use of private header from outside its module: '__algorithm/remove_copy_if.h'}}
	#include <__algorithm/remove_if.h> // expected-error@: {{use of private header from outside its module: '__algorithm/remove_if.h'}}			#include <__algorithm/remove_if.h> // expected-error@: {{use of private header from outside its module: '__algorithm/remove_if.h'}}
	#include <__algorithm/replace.h> // expected-error@: {{use of private header from outside its module: '__algorithm/replace.h'}}			#include <__algorithm/replace.h> // expected-error@: {{use of private header from outside its module: '__algorithm/replace.h'}}
	▲ Show 20 Lines • Show All 434 Lines • Show Last 20 Lines

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp

This file was added.

//===----------------------------------------------------------------------===//

// 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

// <algorithm>

// template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,

// class Proj = identity>

// requires sortable<I, Comp, Proj>

// I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20

// template<random_access_range R, class Comp = ranges::less, class Proj = identity>

// requires sortable<iterator_t<R>, Comp, Proj>

// borrowed_iterator_t<R>

// ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20

#include <algorithm>

#include <array>

#include <concepts>

#include <functional>

#include <ranges>

#include "almost_satisfies_types.h"

#include "boolean_testable.h"

#include "test_iterators.h"

// SFINAE tests.

using BadComparator = ComparatorNotCopyable<int*>;

static_assert(!std::sortable<int*, BadComparator>);

template <class Iter, class Sent = sentinel_wrapper<Iter>, class Comp = std::ranges::less>

concept HasStableSortIt = requires(Iter first, Sent last, Comp comp) { std::ranges::stable_sort(first, last, comp); };

static_assert(HasStableSortIt<int*>);

static_assert(!HasStableSortIt<RandomAccessIteratorNotDerivedFrom>);

static_assert(!HasStableSortIt<RandomAccessIteratorBadIndex>);

static_assert(!HasStableSortIt<int*, SentinelForNotSemiregular>);

static_assert(!HasStableSortIt<int*, SentinelForNotWeaklyEqualityComparableWith>);

static_assert(!HasStableSortIt<int*, int*, BadComparator>);

static_assert(!HasStableSortIt<const int*>); // Doesn't satisfy `sortable`.

template <class Range, class Comp = std::ranges::less>

concept HasStableSortR = requires(Range range, Comp comp) { std::ranges::stable_sort(range, comp); };

static_assert(HasStableSortR<UncheckedRange<int*>>);

static_assert(!HasStableSortR<RandomAccessRangeNotDerivedFrom>);

static_assert(!HasStableSortR<RandomAccessRangeBadIndex>);

static_assert(!HasStableSortR<UncheckedRange<int*, SentinelForNotSemiregular>>);

static_assert(!HasStableSortR<UncheckedRange<int*, SentinelForNotWeaklyEqualityComparableWith>>);

static_assert(!HasStableSortR<UncheckedRange<int*>, BadComparator>);

static_assert(!HasStableSortR<UncheckedRange<const int*>>); // Doesn't satisfy `sortable`.

template <class Iter, class Sent, size_t N>

void test_one(std::array<int, N> input, std::array<int, N> expected) {

{ // (iterator, sentinel) overload.

auto sorted = input;

auto b = Iter(sorted.data());

auto e = Sent(Iter(sorted.data() + sorted.size()));

std::same_as<Iter> decltype(auto) last = std::ranges::stable_sort(b, e);

assert(sorted == expected);

assert(base(last) == sorted.data() + sorted.size());

}

{ // (range) overload.

auto sorted = input;

auto b = Iter(sorted.data());

auto e = Sent(Iter(sorted.data() + sorted.size()));

auto range = std::ranges::subrange(b, e);

std::same_as<Iter> decltype(auto) last = std::ranges::stable_sort(range);

assert(sorted == expected);

assert(base(last) == sorted.data() + sorted.size());

}

template <class Iter, class Sent>

void test_iterators_2() {

// Empty sequence.

test_one<Iter, Sent, 0>({}, {});

// 1-element sequence.

test_one<Iter, Sent, 1>({1}, {1});

// 2-element sequence.

test_one<Iter, Sent, 2>({2, 1}, {1, 2});

// 3-element sequence.

test_one<Iter, Sent, 3>({2, 1, 3}, {1, 2, 3});

// Longer sequence.

test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, {1, 2, 3, 4, 5, 6, 8, 11});

// Longer sequence with duplicates.

test_one<Iter, Sent, 7>({2, 1, 3, 6, 2, 8, 6}, {1, 2, 2, 3, 6, 6, 8});

// All elements are the same.

test_one<Iter, Sent, 3>({1, 1, 1}, {1, 1, 1});

// Already sorted.

test_one<Iter, Sent, 5>({1, 2, 3, 4, 5}, {1, 2, 3, 4, 5});

// Reverse-sorted.

test_one<Iter, Sent, 5>({5, 4, 3, 2, 1}, {1, 2, 3, 4, 5});

// Repeating pattern.

test_one<Iter, Sent, 6>({1, 2, 1, 2, 1, 2}, {1, 1, 1, 2, 2, 2});

}

template <class Iter>

void test_iterators_1() {

test_iterators_2<Iter, Iter>();

test_iterators_2<Iter, sentinel_wrapper<Iter>>();

}

void test_iterators() {

test_iterators_1<random_access_iterator<int*>>();

test_iterators_1<contiguous_iterator<int*>>();

test_iterators_1<int*>();

}

void test() {

test_iterators();

struct OrderedValue {

int value;

double original_order;

bool operator==(const OrderedValue&) const = default;

auto operator<=>(const OrderedValue& rhs) const { return value <=> rhs.value; }

};

{ // The sort is stable (equivalent elements remain in the same order).

using V = OrderedValue;

using Array = std::array<V, 20>;

philnikUnsubmitted

Done

bool operator==(const OrderedValue&) const = default;

- bool operator<(const OrderedValue& rhs) const { return value < rhs.value; }

- bool operator<=(const OrderedValue& rhs) const { return value <= rhs.value; }

- bool operator>(const OrderedValue& rhs) const { return value > rhs.value; }

- bool operator>=(const OrderedValue& rhs) const { return value >= rhs.value; }

+ auto operator<=>(const OrderedValue& rhs) const { return value <=> rhs.value; }

};

using V = OrderedValue;

As always, I think this should work. I'm not yet fluent in spaceship operator.

philnik: As always, I think this //should// work. I'm not yet fluent in spaceship operator.

Array orig_in = {

V{10, 10.1}, {12, 12.1}, {3, 3.1}, {5, 5.1}, {3, 3.2}, {3, 3.3}, {11, 11.1}, {12, 12.2}, {4, 4.1}, {4, 4.2},

{4, 4.3}, {1, 1.1}, {6, 6.1}, {3, 3.4}, {10, 10.2}, {8, 8.1}, {12, 12.3}, {1, 1.2}, {1, 1.3}, {5, 5.2}

};

Array expected = {

philnikUnsubmitted

Done

Does it not work to just use std::array orig_in = {V{10, 101}, ...}?

philnik: Does it not work to just use `std::array orig_in = {V{10, 101}, ...}`?

var-constAuthorUnsubmitted

Done

It does -- it just gives an easy way to make sure both arrays have the same number of elements (since they are long, it's easier to make a mistake).

var-const: It does -- it just gives an easy way to make sure both arrays have the same number of elements…

V{1, 1.1}, {1, 1.2}, {1, 1.3},

var-constAuthorUnsubmitted

Done

For some reason, the compiler fails to parse this construct as an initializer list of OrderedValues without this hint.

var-const: For some reason, the compiler fails to parse this construct as an initializer list of…

{3, 3.1}, {3, 3.2}, {3, 3.3}, {3, 3.4},

MordanteUnsubmitted

Done

I would suggest to make the original_order member a simple integer sequence: 1, 2, 3, etc. That makes it easier to verify whether the output is correct. Identical values will have incrementing values.

Mordante: I would suggest to make the `original_order` member a simple integer sequence: 1, 2, 3, etc.

var-constAuthorUnsubmitted

Done

I started with that, but then I had the idea of enumerating each duplicate value instead (read those 31, 32, 33 as 3.1, 3.2, 3.3, etc.). I think it makes it more readable because following the numbering within a duplicate is much easier than following the numbering across all the elements. What do you think?

var-const: I started with that, but then I had the idea of enumerating each duplicate value instead (read…

MordanteUnsubmitted

Done

How do you feel about making the original_order a double and use 3.1?

Since the same constants written the same in the source there shouldn't be an issue with floating point rounding.

Mordante: How do you feel about making the `original_order` a double and use `3.1`? Since the same…

var-constAuthorUnsubmitted

Done

I really like this, thanks -- makes the intention a lot clearer and looks better, too.

var-const: I really like this, thanks -- makes the intention a lot clearer and looks better, too.

{4, 4.1}, {4, 4.2}, {4, 4.3},

{5, 5.1}, {5, 5.2},

{6, 6.1},

{8, 8.1},

{10, 10.1}, {10, 10.2},

{11, 11.1},

{12, 12.1}, {12, 12.2}, {12, 12.3}

};

{

auto in = orig_in;

MordanteUnsubmitted

Done

Is the trailing comma allowed?

Mordante: Is the trailing comma allowed?

var-constAuthorUnsubmitted

Done

Yes. Removed it for redundancy.

var-const: Yes. Removed it for redundancy.

MordanteUnsubmitted

Done

TIL, fun that it's allowed in some places.

Mordante: TIL, fun that it's allowed in some places.

auto last = std::ranges::stable_sort(in.begin(), in.end());

assert(in == expected);

assert(last == in.end());

}

{

auto in = orig_in;

auto last = std::ranges::stable_sort(in);

assert(in == expected);

assert(last == in.end());

}

{ // A custom comparator works and is stable.

using V = OrderedValue;

using Array = std::array<V, 11>;

Array orig_in = {

MordanteUnsubmitted

Done

It would be good to validate stability in these tests too.

Mordante: It would be good to validate stability in these tests too.

var-constAuthorUnsubmitted

Done

To clarify, do you mean all the tests in test()? Or just the tests with a custom comparator?

var-const: To clarify, do you mean all the tests in `test()`? Or just the tests with a custom comparator?

MordanteUnsubmitted

Done

I think it's mainly important for this test and the ones below.

Mordante: I think it's mainly important for this test and the ones below.

V{1, 1.1}, {2, 2.1}, {2, 2.2}, {3, 3.1}, {2, 2.3}, {3, 3.2}, {4, 4.1}, {5, 5.1}, {2, 2.4}, {5, 5.2}, {1, 1.2}

};

Array expected = {

V{5, 5.1}, {5, 5.2},

{4, 4.1},

{3, 3.1}, {3, 3.2},

{2, 2.1}, {2, 2.2}, {2, 2.3}, {2, 2.4},

{1, 1.1}, {1, 1.2}

};

{

auto in = orig_in;

auto last = std::ranges::stable_sort(in.begin(), in.end(), std::greater{});

assert(in == expected);

assert(last == in.end());

}

{

auto in = orig_in;

philnikUnsubmitted

Done

Isn't this be unnecessary and even counter-productive?

philnik: Isn't this be unnecessary and even counter-productive?

var-constAuthorUnsubmitted

Done

It's used to compare check the in array after it's sorted:

assert((in == std::array{A{1}, A{2}, A{3}}));

Perhaps I'm missing something?

var-const: It's used to compare check the `in` array after it's sorted: ``` assert((in == std::array{A{1}…

philnikUnsubmitted

Not Done

Ah OK, I missed that.

philnik: Ah OK, I missed that.

auto last = std::ranges::stable_sort(in, std::greater{});

assert(in == expected);

assert(last == in.end());

}

{ // A custom projection works.

struct A {

int a;

bool operator==(const A&) const = default;

};

{

std::array in = {A{2}, A{3}, A{1}};

auto last = std::ranges::stable_sort(in.begin(), in.end(), {}, &A::a);

assert((in == std::array{A{1}, A{2}, A{3}}));

assert(last == in.end());

}

{

std::array in = {A{2}, A{3}, A{1}};

auto last = std::ranges::stable_sort(in, {}, &A::a);

assert((in == std::array{A{1}, A{2}, A{3}}));

assert(last == in.end());

}

philnikUnsubmitted

Done

Again, I don't think this should be here.

philnik: Again, I don't think this should be here.

var-constAuthorUnsubmitted

Done

Same -- it's necessary to compare arrays.

var-const: Same -- it's necessary to compare arrays.

{ // `std::invoke` is used in the implementation.

struct S {

int i;

S(int i_) : i(i_) {}

bool comparator(const S& rhs) const { return i < rhs.i; }

const S& projection() const { return *this; }

bool operator==(const S&) const = default;

};

{

std::array in = {S{2}, S{3}, S{1}};

auto last = std::ranges::stable_sort(in.begin(), in.end(), &S::comparator, &S::projection);

assert((in == std::array{S{1}, S{2}, S{3}}));

assert(last == in.end());

}

{

std::array in = {S{2}, S{3}, S{1}};

auto last = std::ranges::stable_sort(in, &S::comparator, &S::projection);

assert((in == std::array{S{1}, S{2}, S{3}}));

assert(last == in.end());

}

{ // The comparator can return any type that's convertible to `bool`.

{

std::array in = {2, 1, 3};

auto last = std::ranges::stable_sort(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; });

assert((in == std::array{1, 2, 3}));

assert(last == in.end());

MordanteUnsubmitted

Done

Here we can validate complexity. Obviously implementations can make different choices regarding when there's not "enough extra memory" but we can test the N log (N) for a small number of items.

Mordante: Here we can validate complexity. Obviously implementations can make different choices regarding…

var-constAuthorUnsubmitted

Done

Similar to the sort patch, I don't think we have a great way of doing this:

we can use the exact number of operations our implementation happens to perform (we have some precedent in e.g. test/libcxx/algorithms/alg.sorting/alg.heap.operations/make.heap/complexity.pass.cpp), but that would make it libc++-specific and, IMO, has limited usefulness;
simply testing for num_operations < N*log(N) isn't going to work because it's actually k*N*log(N), where k is an arbitrary constant;
the "proper" way would be to test with increasingly large inputs and applying some math to calculate the growth factor, but that seems like a sizable project in itself, even assuming it's worth the implementation effort.

var-const: Similar to the `sort` patch, I don't think we have a great way of doing this: - we can use the…

MordanteUnsubmitted

Done

Here http://eel.is/c++draft/stable.sort#5 lists the exact number of comparisons to do and that the number of projections is double of that. So I think we can use that value as an upper bound, for example with N = 10.

Mordante: Here http://eel.is/c++draft/stable.sort#5 lists the exact number of comparisons to do and that…

var-constAuthorUnsubmitted

Done

I'd rather do this in a follow-up. I think perhaps it would be good to have a dedicated test file for this, similar to the robust_against_copying_*.

var-const: I'd rather do this in a follow-up. I think perhaps it would be good to have a dedicated test…

MordanteUnsubmitted

Done

Sounds good to me.

Mordante: Sounds good to me.

}

{

std::array in = {2, 1, 3};

auto last = std::ranges::stable_sort(in, [](int i, int j) { return BooleanTestable{i < j}; });

assert((in == std::array{1, 2, 3}));

assert(last == in.end());

}

MordanteUnsubmitted

Done

Interesting since it's possible to allocate memory in constexpr functions.

Mordante: Interesting since it's possible to allocate memory in `constexpr` functions.

var-constAuthorUnsubmitted

Done

I know that P0202 was adding constexpr to algorithms. At the time (in 2017), making stable_sort constexpr was infeasible:

Algorithms stable_partition, inplace_merge and stable_sort allocate memory, construct variables using placement new, use unique_ptr and do other things not acceptable in constexpr expressions. Making those algorithms constexpr seems to be a hard task that would require a lot of intrinsics. Those algorithms are not marked with constexpr in this wording.

I don't know if there's been any work in that direction since then. Perhaps it's ripe for a new paper?

var-const: I know that [[ http://wg21.link/p0202 | P0202 ]] was adding `constexpr` to algorithms. At the…

MordanteUnsubmitted

Done

I didn't investigate the reason, but this is indeed what I expected :-)

Based on the unanimous consent in this poll https://github.com/cplusplus/papers/issues/1222#issuecomment-1159203566
the time is indeed ripe and a paper is already available.

Mordante: I didn't investigate the reason, but this is indeed what I expected :-) Based on the unanimous…

var-constAuthorUnsubmitted

Done

Thanks for finding that paper!

var-const: Thanks for finding that paper!

{ // `std::ranges::dangling` is returned.

[[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) result =

std::ranges::stable_sort(std::array{1, 2, 3});

}

int main(int, char**) {

test();

// Note: `stable_sort` is not `constexpr`.

return 0;

}

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

	Show First 20 Lines • Show All 134 Lines • ▼ Show 20 Lines
	//static_assert(test(std::ranges::set_difference, a, a, a));			//static_assert(test(std::ranges::set_difference, a, a, a));
	//static_assert(test(std::ranges::set_intersection, a, a, a));			//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_symmetric_difference, a, a, a));
	//static_assert(test(std::ranges::set_union, 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, a));
	//static_assert(test(std::ranges::sort_heap, a));			//static_assert(test(std::ranges::sort_heap, a));
	//static_assert(test(std::ranges::stable_partition, a, odd));			//static_assert(test(std::ranges::stable_partition, a, odd));
	//static_assert(test(std::ranges::stable_sort, a));			static_assert(test(std::ranges::stable_sort, a));
	//static_assert(test(std::ranges::starts_with, a, a));			//static_assert(test(std::ranges::starts_with, a, a));
	static_assert(test(std::ranges::swap_ranges, a, a));			static_assert(test(std::ranges::swap_ranges, a, a));
	static_assert(test(std::ranges::transform, a, a, triple));			static_assert(test(std::ranges::transform, a, a, triple));
	//static_assert(test(std::ranges::unique, a));			//static_assert(test(std::ranges::unique, a));
	//static_assert(test(std::ranges::unique_copy, a, a));			//static_assert(test(std::ranges::unique_copy, a, a));
	static_assert(test(std::ranges::upper_bound, a, 42));			static_assert(test(std::ranges::upper_bound, a, 42));

	// [memory.syn]			// [memory.syn]
	Show All 38 Lines

This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `ranges::stable_sort`.
ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 441812

libcxx/benchmarks/CMakeLists.txt

libcxx/benchmarks/algorithms/ranges_stable_sort.bench.cpp

libcxx/docs/Status/RangesAlgorithms.csv

libcxx/include/CMakeLists.txt

libcxx/include/__algorithm/ranges_sort.h

libcxx/include/__algorithm/ranges_stable_sort.h

libcxx/include/__algorithm/stable_sort.h

libcxx/include/algorithm

libcxx/include/module.modulemap.in

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

libcxx/test/libcxx/private_headers.verify.cpp

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `ranges::stable_sort`.ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 441812

libcxx/benchmarks/CMakeLists.txt

libcxx/benchmarks/algorithms/ranges_stable_sort.bench.cpp

libcxx/docs/Status/RangesAlgorithms.csv

libcxx/include/CMakeLists.txt

libcxx/include/__algorithm/ranges_sort.h

libcxx/include/__algorithm/ranges_stable_sort.h

libcxx/include/__algorithm/stable_sort.h

libcxx/include/algorithm

libcxx/include/module.modulemap.in

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

libcxx/test/libcxx/private_headers.verify.cpp

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

[libc++][ranges] Implement `ranges::stable_sort`.
ClosedPublic