Skip to content
Permalink
main
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

STL/stl/inc/algorithm

Go to file
 
 
Cannot retrieve contributors at this time
10683 lines (9181 sloc) 490 KB
Raw Blame
Open in GitHub Desktop
// algorithm standard header
// Copyright (c) Microsoft Corporation.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
#pragma once
#ifndef _ALGORITHM_
#define _ALGORITHM_
#include <yvals_core.h>
#if _STL_COMPILER_PREPROCESSOR
#include <xmemory>
#if _HAS_CXX23
#include <optional>
#endif // _HAS_CXX23
#pragma pack(push, _CRT_PACKING)
#pragma warning(push, _STL_WARNING_LEVEL)
#pragma warning(disable : _STL_DISABLED_WARNINGS)
_STL_DISABLE_CLANG_WARNINGS
#pragma push_macro("new")
#undef new
#if _USE_STD_VECTOR_ALGORITHMS
_EXTERN_C
struct _Min_max_element_t {
const void* _Min;
const void* _Max;
};
// The "noalias" attribute tells the compiler optimizer that pointers going into these hand-vectorized algorithms
// won't be stored beyond the lifetime of the function, and that the function will only reference arrays denoted by
// those pointers. The optimizer also assumes in that case that a pointer parameter is not returned to the caller via
// the return value, so functions using "noalias" must usually return void. This attribute is valuable because these
// functions are in native code objects that the compiler cannot analyze. In the absence of the noalias attribute, the
// compiler has to assume that the denoted arrays are "globally address taken", and that any later calls to
// unanalyzable routines may modify those arrays.
__declspec(noalias) void __cdecl __std_reverse_copy_trivially_copyable_1(
const void* _First, const void* _Last, void* _Dest) noexcept;
__declspec(noalias) void __cdecl __std_reverse_copy_trivially_copyable_2(
const void* _First, const void* _Last, void* _Dest) noexcept;
__declspec(noalias) void __cdecl __std_reverse_copy_trivially_copyable_4(
const void* _First, const void* _Last, void* _Dest) noexcept;
__declspec(noalias) void __cdecl __std_reverse_copy_trivially_copyable_8(
const void* _First, const void* _Last, void* _Dest) noexcept;
_Min_max_element_t __stdcall __std_minmax_element_1(const void* _First, const void* _Last, bool _Signed) noexcept;
_Min_max_element_t __stdcall __std_minmax_element_2(const void* _First, const void* _Last, bool _Signed) noexcept;
_Min_max_element_t __stdcall __std_minmax_element_4(const void* _First, const void* _Last, bool _Signed) noexcept;
_Min_max_element_t __stdcall __std_minmax_element_8(const void* _First, const void* _Last, bool _Signed) noexcept;
_END_EXTERN_C
template <class _Ty>
_STD pair<_Ty*, _Ty*> __std_minmax_element(_Ty* _First, _Ty* _Last) noexcept {
constexpr bool _Signed = _STD is_signed_v<_Ty>;
_Min_max_element_t _Res;
if constexpr (sizeof(_Ty) == 1) {
_Res = __std_minmax_element_1(_First, _Last, _Signed);
} else if constexpr (sizeof(_Ty) == 2) {
_Res = __std_minmax_element_2(_First, _Last, _Signed);
} else if constexpr (sizeof(_Ty) == 4) {
_Res = __std_minmax_element_4(_First, _Last, _Signed);
} else if constexpr (sizeof(_Ty) == 8) {
_Res = __std_minmax_element_8(_First, _Last, _Signed);
} else {
static_assert(_STD _Always_false<_Ty>, "Unexpected size");
}
return {const_cast<_Ty*>(static_cast<const _Ty*>(_Res._Min)), const_cast<_Ty*>(static_cast<const _Ty*>(_Res._Max))};
}
#endif // _USE_STD_VECTOR_ALGORITHMS
_STD_BEGIN
_INLINE_VAR constexpr int _ISORT_MAX = 32; // maximum size for insertion sort
template <class _It>
_INLINE_VAR constexpr _Iter_diff_t<_It> _Isort_max{_ISORT_MAX};
template <class _Diff>
constexpr ptrdiff_t _Temporary_buffer_size(const _Diff _Value) noexcept {
// convert an iterator difference_type to a ptrdiff_t for use in temporary buffers
using _CT = common_type_t<ptrdiff_t, _Diff>;
return static_cast<ptrdiff_t>((_STD min)(static_cast<_CT>(PTRDIFF_MAX), static_cast<_CT>(_Value)));
}
template <class _Ty>
struct _Optimistic_temporary_buffer { // temporary storage with _alloca-like attempt
static constexpr size_t _Optimistic_size = 4096; // default to ~1 page
static constexpr size_t _Optimistic_count = (_STD max)(static_cast<size_t>(1), _Optimistic_size / sizeof(_Ty));
template <class _Diff>
explicit _Optimistic_temporary_buffer(const _Diff _Requested_size) noexcept { // get temporary storage
const auto _Attempt = _Temporary_buffer_size(_Requested_size);
// Since _Diff is a count of elements in a forward range, and forward iterators must denote objects in memory,
// it must fit in a size_t.
if (static_cast<size_t>(_Requested_size) <= _Optimistic_count) { // unconditionally engage stack space
_Data = reinterpret_cast<_Ty*>(&_Stack_space[0]);
_Capacity = static_cast<ptrdiff_t>(_Requested_size); // in bounds due to if condition
return;
}
const pair<_Ty*, ptrdiff_t> _Raw = _Get_temporary_buffer<_Ty>(_Attempt);
if (static_cast<size_t>(_Raw.second) > _Optimistic_count) { // engage heap space
_Data = _Raw.first;
_Capacity = _Raw.second;
return;
}
// less heap space than stack space, give up and use stack instead
_Return_temporary_buffer(_Raw.first);
_Data = reinterpret_cast<_Ty*>(&_Stack_space[0]);
_Capacity = _Optimistic_count;
}
_Optimistic_temporary_buffer(const _Optimistic_temporary_buffer&) = delete;
_Optimistic_temporary_buffer& operator=(const _Optimistic_temporary_buffer&) = delete;
~_Optimistic_temporary_buffer() noexcept {
if (static_cast<size_t>(_Capacity) > _Optimistic_count) {
_Return_temporary_buffer(_Data);
}
}
_Ty* _Data; // points to heap memory iff _Capacity > _Optimistic_count
ptrdiff_t _Capacity;
_Aligned_storage_t<sizeof(_Ty), alignof(_Ty)> _Stack_space[_Optimistic_count];
};
#ifdef __cpp_lib_concepts
namespace ranges {
_EXPORT_STD template <class _In, class _Fun>
struct in_fun_result {
/* [[no_unique_address]] */ _In in;
/* [[no_unique_address]] */ _Fun fun;
template <_Convertible_from<const _In&> _IIn, _Convertible_from<const _Fun&> _FFun>
constexpr operator in_fun_result<_IIn, _FFun>() const& {
return {in, fun};
}
template <_Convertible_from<_In> _IIn, _Convertible_from<_Fun> _FFun>
constexpr operator in_fun_result<_IIn, _FFun>() && {
return {_STD move(in), _STD move(fun)};
}
};
_EXPORT_STD template <class _In1, class _In2, class _Out>
struct in_in_out_result {
/* [[no_unique_address]] */ _In1 in1;
/* [[no_unique_address]] */ _In2 in2;
/* [[no_unique_address]] */ _Out out;
template <_Convertible_from<const _In1&> _IIn1, _Convertible_from<const _In2&> _IIn2,
_Convertible_from<const _Out&> _OOut>
constexpr operator in_in_out_result<_IIn1, _IIn2, _OOut>() const& {
return {in1, in2, out};
}
template <_Convertible_from<_In1> _IIn1, _Convertible_from<_In2> _IIn2, _Convertible_from<_Out> _OOut>
constexpr operator in_in_out_result<_IIn1, _IIn2, _OOut>() && {
return {_STD move(in1), _STD move(in2), _STD move(out)};
}
};
_EXPORT_STD template <class _In, class _Out1, class _Out2>
struct in_out_out_result {
/* [[no_unique_address]] */ _In in;
/* [[no_unique_address]] */ _Out1 out1;
/* [[no_unique_address]] */ _Out2 out2;
template <_Convertible_from<const _In&> _IIn, _Convertible_from<const _Out1&> _OOut1,
_Convertible_from<const _Out2&> _OOut2>
constexpr operator in_out_out_result<_IIn, _OOut1, _OOut2>() const& {
return {in, out1, out2};
}
template <_Convertible_from<_In> _IIn, _Convertible_from<_Out1> _OOut1, _Convertible_from<_Out2> _OOut2>
constexpr operator in_out_out_result<_IIn, _OOut1, _OOut2>() && {
return {_STD move(in), _STD move(out1), _STD move(out2)};
}
};
_EXPORT_STD template <class _Ty>
struct min_max_result {
/* [[no_unique_address]] */ _Ty min;
/* [[no_unique_address]] */ _Ty max;
template <_Convertible_from<const _Ty&> _Ty2>
constexpr operator min_max_result<_Ty2>() const& {
return {min, max};
}
template <_Convertible_from<_Ty> _Ty2>
constexpr operator min_max_result<_Ty2>() && {
return {_STD move(min), _STD move(max)};
}
};
_EXPORT_STD template <class _In>
struct in_found_result {
/* [[no_unique_address]] */ _In in;
bool found;
template <_Convertible_from<const _In&> _IIn>
constexpr operator in_found_result<_IIn>() const& {
return {in, found};
}
template <_Convertible_from<_In> _IIn>
constexpr operator in_found_result<_IIn>() && {
return {_STD move(in), found};
}
};
#if _HAS_CXX23
_EXPORT_STD template <class _In, class _Ty>
struct in_value_result {
/* [[no_unique_address]] */ _In in;
/* [[no_unique_address]] */ _Ty value;
template <class _IIn, class _TTy>
requires convertible_to<const _In&, _IIn> && convertible_to<const _Ty&, _TTy>
constexpr operator in_value_result<_IIn, _TTy>() const& {
return {in, value};
}
template <class _IIn, class _TTy>
requires convertible_to<_In, _IIn> && convertible_to<_Ty, _TTy>
constexpr operator in_value_result<_IIn, _TTy>() && {
return {_STD move(in), _STD move(value)};
}
};
#endif // _HAS_CXX23
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _InIt, class _Fn>
_CONSTEXPR20 _Fn for_each(_InIt _First, _InIt _Last, _Fn _Func) { // perform function for each element [_First, _Last)
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
for (; _UFirst != _ULast; ++_UFirst) {
_Func(*_UFirst);
}
return _Func;
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Fn, _Enable_if_execution_policy_t<_ExPo> = 0>
void for_each(_ExPo&& _Exec, _FwdIt _First, _FwdIt _Last, _Fn _Func) noexcept; // terminates
_EXPORT_STD template <class _InIt, class _Diff, class _Fn>
_CONSTEXPR20 _InIt for_each_n(_InIt _First, const _Diff _Count_raw, _Fn _Func) {
// perform function for each element [_First, _First + _Count)
_Algorithm_int_t<_Diff> _Count = _Count_raw;
if (0 < _Count) {
auto _UFirst = _Get_unwrapped_n(_First, _Count);
do {
_Func(*_UFirst);
--_Count;
++_UFirst;
} while (0 < _Count);
_Seek_wrapped(_First, _UFirst);
}
return _First;
}
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Diff, class _Fn, _Enable_if_execution_policy_t<_ExPo> = 0>
_FwdIt for_each_n(_ExPo&& _Exec, _FwdIt _First, _Diff _Count_raw, _Fn _Func) noexcept; // terminates
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
_EXPORT_STD template <class _In, class _Fun>
using for_each_result = in_fun_result<_In, _Fun>;
class _For_each_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, class _Pj = identity,
indirectly_unary_invocable<projected<_It, _Pj>> _Fn>
constexpr for_each_result<_It, _Fn> operator()(_It _First, _Se _Last, _Fn _Func, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
auto _UResult = _For_each_unchecked(_Unwrap_iter<_Se>(_STD move(_First)),
_Unwrap_sent<_It>(_STD move(_Last)), _STD move(_Func), _Pass_fn(_Proj));
_Seek_wrapped(_First, _STD move(_UResult.in));
return {_STD move(_First), _STD move(_UResult.fun)};
}
template <input_range _Rng, class _Pj = identity,
indirectly_unary_invocable<projected<iterator_t<_Rng>, _Pj>> _Fn>
constexpr for_each_result<borrowed_iterator_t<_Rng>, _Fn> operator()(
_Rng&& _Range, _Fn _Func, _Pj _Proj = {}) const {
auto _First = _RANGES begin(_Range);
auto _UResult = _For_each_unchecked(
_Unwrap_range_iter<_Rng>(_STD move(_First)), _Uend(_Range), _STD move(_Func), _Pass_fn(_Proj));
_Seek_wrapped(_First, _STD move(_UResult.in));
return {_STD move(_First), _STD move(_UResult.fun)};
}
private:
template <class _It, class _Se, class _Pj, class _Fn>
_NODISCARD static constexpr for_each_result<_It, _Fn> _For_each_unchecked(
_It _First, const _Se _Last, _Fn _Func, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_unary_invocable<_Fn, projected<_It, _Pj>>);
for (; _First != _Last; ++_First) {
_STD invoke(_Func, _STD invoke(_Proj, *_First));
}
return {_STD move(_First), _STD move(_Func)};
}
};
_EXPORT_STD inline constexpr _For_each_fn for_each{_Not_quite_object::_Construct_tag{}};
_EXPORT_STD template <class _In, class _Fun>
using for_each_n_result = in_fun_result<_In, _Fun>;
class _For_each_n_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, class _Pj = identity, indirectly_unary_invocable<projected<_It, _Pj>> _Fn>
constexpr for_each_n_result<_It, _Fn> operator()(
_It _First, iter_difference_t<_It> _Count, _Fn _Func, _Pj _Proj = {}) const {
if (0 < _Count) {
auto _UFirst = _Get_unwrapped_n(_STD move(_First), _Count);
do {
_STD invoke(_Func, _STD invoke(_Proj, *_UFirst));
--_Count;
++_UFirst;
} while (0 < _Count);
_Seek_wrapped(_First, _STD move(_UFirst));
}
return {_STD move(_First), _STD move(_Func)};
}
};
_EXPORT_STD inline constexpr _For_each_n_fn for_each_n{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdIt find_if(_ExPo&& _Exec, _FwdIt _First, _FwdIt _Last, _Pr _Pred) noexcept; // terminates
#endif // _HAS_CXX17
_EXPORT_STD template <class _InIt, class _Pr>
_NODISCARD _CONSTEXPR20 _InIt find_if_not(_InIt _First, const _InIt _Last, _Pr _Pred) {
// find first element that satisfies !_Pred
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
for (; _UFirst != _ULast; ++_UFirst) {
if (!_Pred(*_UFirst)) {
break;
}
}
_Seek_wrapped(_First, _UFirst);
return _First;
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdIt find_if_not(_ExPo&& _Exec, _FwdIt _First, _FwdIt _Last, _Pr _Pred) noexcept; // terminates
#endif // _HAS_CXX17
_EXPORT_STD template <class _FwdIt, class _Pr>
_NODISCARD _CONSTEXPR20 _FwdIt adjacent_find(const _FwdIt _First, _FwdIt _Last, _Pr _Pred) {
// find first satisfying _Pred with successor
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
auto _ULast = _Get_unwrapped(_Last);
if (_UFirst != _ULast) {
for (auto _UNext = _UFirst; ++_UNext != _ULast; _UFirst = _UNext) {
if (_Pred(*_UFirst, *_UNext)) {
_ULast = _UFirst;
break;
}
}
}
_Seek_wrapped(_Last, _ULast);
return _Last;
}
_EXPORT_STD template <class _FwdIt>
_NODISCARD _CONSTEXPR20 _FwdIt adjacent_find(const _FwdIt _First, const _FwdIt _Last) { // find first matching successor
return _STD adjacent_find(_First, _Last, equal_to<>{});
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdIt adjacent_find(_ExPo&& _Exec, _FwdIt _First, _FwdIt _Last, _Pr _Pred) noexcept; // terminates
_EXPORT_STD template <class _ExPo, class _FwdIt, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdIt adjacent_find(_ExPo&& _Exec, const _FwdIt _First, const _FwdIt _Last) noexcept /* terminates */ {
// find first matching successor
return _STD adjacent_find(_STD forward<_ExPo>(_Exec), _First, _Last, equal_to{});
}
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
class _Count_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, class _Ty, class _Pj = identity>
requires indirect_binary_predicate<ranges::equal_to, projected<_It, _Pj>, const _Ty*>
_NODISCARD constexpr iter_difference_t<_It> operator()(
_It _First, _Se _Last, const _Ty& _Val, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
return _Count_unchecked(
_Unwrap_iter<_Se>(_STD move(_First)), _Unwrap_sent<_It>(_STD move(_Last)), _Val, _Pass_fn(_Proj));
}
template <input_range _Rng, class _Ty, class _Pj = identity>
requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Rng>, _Pj>, const _Ty*>
_NODISCARD constexpr range_difference_t<_Rng> operator()(_Rng&& _Range, const _Ty& _Val, _Pj _Proj = {}) const {
return _Count_unchecked(_Ubegin(_Range), _Uend(_Range), _Val, _Pass_fn(_Proj));
}
private:
template <class _It, class _Se, class _Ty, class _Pj>
_NODISCARD static constexpr iter_difference_t<_It> _Count_unchecked(
_It _First, const _Se _Last, const _Ty& _Val, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirect_binary_predicate<ranges::equal_to, projected<_It, _Pj>, const _Ty*>);
#if _USE_STD_VECTOR_ALGORITHMS
if constexpr (is_same_v<_Pj, identity> && _Vector_alg_in_find_is_safe<_It, _Ty>
&& sized_sentinel_for<_Se, _It>) {
if (!_STD is_constant_evaluated()) {
if (!_STD _Could_compare_equal_to_value_type<_It>(_Val)) {
return 0;
}
const auto _First_ptr = _To_address(_First);
const auto _Last_ptr = _First_ptr + (_Last - _First);
return static_cast<iter_difference_t<_It>>(__std_count_trivial(_First_ptr, _Last_ptr, _Val));
}
}
#endif // _USE_STD_VECTOR_ALGORITHMS
iter_difference_t<_It> _Count = 0;
for (; _First != _Last; ++_First) {
if (_STD invoke(_Proj, *_First) == _Val) {
++_Count;
}
}
return _Count;
}
};
_EXPORT_STD inline constexpr _Count_fn count{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _InIt, class _Pr>
_NODISCARD _CONSTEXPR20 _Iter_diff_t<_InIt> count_if(_InIt _First, _InIt _Last, _Pr _Pred) {
// count elements satisfying _Pred
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
_Iter_diff_t<_InIt> _Count = 0;
for (; _UFirst != _ULast; ++_UFirst) {
if (_Pred(*_UFirst)) {
++_Count;
}
}
return _Count;
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _Iter_diff_t<_FwdIt> count_if(_ExPo&& _Exec, _FwdIt _First, _FwdIt _Last, _Pr _Pred) noexcept; // terminates
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
class _Count_if_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, class _Pj = identity,
indirect_unary_predicate<projected<_It, _Pj>> _Pr>
_NODISCARD constexpr iter_difference_t<_It> operator()(_It _First, _Se _Last, _Pr _Pred, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
return _Count_if_unchecked(_Unwrap_iter<_Se>(_STD move(_First)), _Unwrap_sent<_It>(_STD move(_Last)),
_Pass_fn(_Pred), _Pass_fn(_Proj));
}
template <input_range _Rng, class _Pj = identity,
indirect_unary_predicate<projected<iterator_t<_Rng>, _Pj>> _Pr>
_NODISCARD constexpr range_difference_t<_Rng> operator()(_Rng&& _Range, _Pr _Pred, _Pj _Proj = {}) const {
return _Count_if_unchecked(_Ubegin(_Range), _Uend(_Range), _Pass_fn(_Pred), _Pass_fn(_Proj));
}
private:
template <class _It, class _Se, class _Pj, class _Pr>
_NODISCARD static constexpr iter_difference_t<_It> _Count_if_unchecked(
_It _First, const _Se _Last, _Pr _Pred, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirect_unary_predicate<_Pr, projected<_It, _Pj>>);
iter_difference_t<_It> _Count = 0;
for (; _First != _Last; ++_First) {
if (_STD invoke(_Pred, _STD invoke(_Proj, *_First))) {
++_Count;
}
}
return _Count;
}
};
_EXPORT_STD inline constexpr _Count_if_fn count_if{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _InIt1, class _InIt2, class _Pr>
_NODISCARD _CONSTEXPR20 pair<_InIt1, _InIt2> mismatch(_InIt1 _First1, const _InIt1 _Last1, _InIt2 _First2, _Pr _Pred) {
// return [_First1, _Last1)/[_First2, ...) mismatch
_Adl_verify_range(_First1, _Last1);
auto _UFirst1 = _Get_unwrapped(_First1);
const auto _ULast1 = _Get_unwrapped(_Last1);
auto _UFirst2 = _Get_unwrapped_n(_First2, _Idl_distance<_InIt1>(_UFirst1, _ULast1));
while (_UFirst1 != _ULast1 && _Pred(*_UFirst1, *_UFirst2)) {
++_UFirst1;
++_UFirst2;
}
_Seek_wrapped(_First2, _UFirst2);
_Seek_wrapped(_First1, _UFirst1);
return {_First1, _First2};
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt1, class _FwdIt2, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD pair<_FwdIt1, _FwdIt2> mismatch(
_ExPo&& _Exec, _FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _Pr _Pred) noexcept; // terminates
#endif // _HAS_CXX17
_EXPORT_STD template <class _InIt1, class _InIt2>
_NODISCARD _CONSTEXPR20 pair<_InIt1, _InIt2> mismatch(const _InIt1 _First1, const _InIt1 _Last1, const _InIt2 _First2) {
// return [_First1, _Last1)/[_First2, ...) mismatch
return _STD mismatch(_First1, _Last1, _First2, equal_to<>{});
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt1, class _FwdIt2, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD pair<_FwdIt1, _FwdIt2> mismatch(
_ExPo&& _Exec, const _FwdIt1 _First1, const _FwdIt1 _Last1, const _FwdIt2 _First2) noexcept /* terminates */ {
// return [_First1, _Last1)/[_First2, ...) mismatch
_REQUIRE_PARALLEL_ITERATOR(_FwdIt1);
_REQUIRE_PARALLEL_ITERATOR(_FwdIt2);
return _STD mismatch(_STD forward<_ExPo>(_Exec), _First1, _Last1, _First2, equal_to{});
}
#endif // _HAS_CXX17
_EXPORT_STD template <class _InIt1, class _InIt2, class _Pr>
_NODISCARD _CONSTEXPR20 pair<_InIt1, _InIt2> mismatch(
_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _Pr _Pred) {
// return [_First1, _Last1)/[_First2, _Last2) mismatch
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);
auto _UFirst1 = _Get_unwrapped(_First1);
auto _ULast1 = _Get_unwrapped(_Last1);
auto _UFirst2 = _Get_unwrapped(_First2);
const auto _ULast2 = _Get_unwrapped(_Last2);
if constexpr (_Is_ranges_random_iter_v<_InIt1> && _Is_ranges_random_iter_v<_InIt2>) {
using _CT = _Common_diff_t<_InIt1, _InIt2>;
const _CT _Count1 = _ULast1 - _UFirst1;
const _CT _Count2 = _ULast2 - _UFirst2;
const auto _Count = static_cast<_Iter_diff_t<_InIt1>>((_STD min)(_Count1, _Count2));
_ULast1 = _UFirst1 + _Count;
while (_UFirst1 != _ULast1 && _Pred(*_UFirst1, *_UFirst2)) {
++_UFirst1;
++_UFirst2;
}
} else {
while (_UFirst1 != _ULast1 && _UFirst2 != _ULast2 && _Pred(*_UFirst1, *_UFirst2)) {
++_UFirst1;
++_UFirst2;
}
}
_Seek_wrapped(_First2, _UFirst2);
_Seek_wrapped(_First1, _UFirst1);
return {_First1, _First2};
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt1, class _FwdIt2, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD pair<_FwdIt1, _FwdIt2> mismatch(
_ExPo&& _Exec, _FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred) noexcept; // terminates
#endif // _HAS_CXX17
_EXPORT_STD template <class _InIt1, class _InIt2>
_NODISCARD _CONSTEXPR20 pair<_InIt1, _InIt2> mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2) {
// return [_First1, _Last1)/[_First2, _Last2) mismatch
return _STD mismatch(_First1, _Last1, _First2, _Last2, equal_to<>{});
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt1, class _FwdIt2, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD pair<_FwdIt1, _FwdIt2> mismatch(
_ExPo&& _Exec, _FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2) noexcept /* terminates */ {
// return [_First1, _Last1)/[_First2, _Last2) mismatch
_REQUIRE_PARALLEL_ITERATOR(_FwdIt1);
_REQUIRE_PARALLEL_ITERATOR(_FwdIt2);
return _STD mismatch(_STD forward<_ExPo>(_Exec), _First1, _Last1, _First2, _Last2, equal_to{});
}
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
template <input_iterator _It1, input_iterator _It2, _Integer_like _Size, class _Pr, class _Pj1, class _Pj2>
requires indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr bool _Equal_count(
_It1 _First1, _It2 _First2, _Size _Count, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_CHECK(_Count >= 0);
if constexpr (_Equal_memcmp_is_safe<_It1, _It2, _Pr> && same_as<_Pj1, identity> && same_as<_Pj2, identity>) {
if (!_STD is_constant_evaluated()) {
return _Memcmp_count(_First1, _First2, static_cast<size_t>(_Count)) == 0;
}
}
for (; _Count != 0; ++_First1, (void) ++_First2, --_Count) {
if (!_STD invoke(_Pred, _STD invoke(_Proj1, *_First1), _STD invoke(_Proj2, *_First2))) {
return false;
}
}
return true;
}
class _Equal_fn : private _Not_quite_object {
private:
template <class _It1, class _Se1, class _It2, class _Se2, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr bool _Equal_4(
_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se1, _It1>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se2, _It2>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>);
for (;;) {
if (_First1 == _Last1) {
return _First2 == _Last2;
} else if (_First2 == _Last2) {
return false;
}
if (!_STD invoke(_Pred, _STD invoke(_Proj1, *_First1), _STD invoke(_Proj2, *_First2))) {
return false;
}
++_First1;
++_First2;
}
}
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It1, sentinel_for<_It1> _Se1, input_iterator _It2, sentinel_for<_It2> _Se2,
class _Pr = ranges::equal_to, class _Pj1 = identity, class _Pj2 = identity>
requires indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr bool operator()(_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2, _Pr _Pred = {},
_Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);
auto _UFirst1 = _Unwrap_iter<_Se1>(_STD move(_First1));
auto _ULast1 = _Unwrap_sent<_It1>(_STD move(_Last1));
auto _UFirst2 = _Unwrap_iter<_Se2>(_STD move(_First2));
auto _ULast2 = _Unwrap_sent<_It2>(_STD move(_Last2));
if constexpr (sized_sentinel_for<_Se1, _It1> && sized_sentinel_for<_Se2, _It2>) {
const auto _Count = _ULast1 - _UFirst1;
if (_Count != _ULast2 - _UFirst2) {
return false;
}
return _RANGES _Equal_count(_STD move(_UFirst1), _STD move(_UFirst2), _Count, _Pass_fn(_Pred),
_Pass_fn(_Proj1), _Pass_fn(_Proj2));
} else {
return _Equal_4(_STD move(_UFirst1), _STD move(_ULast1), _STD move(_UFirst2), _STD move(_ULast2),
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
}
}
template <input_range _Rng1, input_range _Rng2, class _Pr = ranges::equal_to, class _Pj1 = identity,
class _Pj2 = identity>
requires indirectly_comparable<iterator_t<_Rng1>, iterator_t<_Rng2>, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr bool operator()(
_Rng1&& _Range1, _Rng2&& _Range2, _Pr _Pred = {}, _Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
if constexpr (sized_range<_Rng1> && sized_range<_Rng2>) {
using _Size1 = _Make_unsigned_like_t<range_size_t<_Rng1>>;
const auto _Count = static_cast<_Size1>(_RANGES size(_Range1));
using _Size2 = _Make_unsigned_like_t<range_size_t<_Rng2>>;
if (_Count != static_cast<_Size2>(_RANGES size(_Range2))) {
return false;
}
return _RANGES _Equal_count(
_Ubegin(_Range1), _Ubegin(_Range2), _Count, _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
} else {
return _Equal_4(_Ubegin(_Range1), _Uend(_Range1), _Ubegin(_Range2), _Uend(_Range2), _Pass_fn(_Pred),
_Pass_fn(_Proj1), _Pass_fn(_Proj2));
}
}
};
_EXPORT_STD inline constexpr _Equal_fn equal{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _FwdIt1, class _FwdIt2, class _Pr>
_NODISCARD _CONSTEXPR20 bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _Pr _Pred) {
// test if [_First1, _Last1) == permuted [_First2, ...)
_Adl_verify_range(_First1, _Last1);
auto _UFirst1 = _Get_unwrapped(_First1);
const auto _ULast1 = _Get_unwrapped(_Last1);
auto _UFirst2 = _Get_unwrapped_n(_First2, _Idl_distance<_FwdIt1>(_UFirst1, _ULast1));
for (;; ++_UFirst1, (void) ++_UFirst2) { // trim matching prefix
if (_UFirst1 == _ULast1) { // everything matched
return true;
}
if (!_Pred(*_UFirst1, *_UFirst2)) { // found first inequality, check match counts in suffix
break;
}
}
// Narrowing _Iter_diff_t<_FwdIt1> to _Iter_diff_t<_FwdIt2> is OK because the second range must be at least as long
// as the first.
const auto _Dist2 = static_cast<_Iter_diff_t<_FwdIt2>>(_STD distance(_UFirst1, _ULast1));
return _Check_match_counts(_UFirst1, _ULast1, _UFirst2, _STD next(_UFirst2, _Dist2), _Pass_fn(_Pred));
}
_EXPORT_STD template <class _FwdIt1, class _FwdIt2>
_NODISCARD _CONSTEXPR20 bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2) {
// test if [_First1, _Last1) == permuted [_First2, ...)
return _STD is_permutation(_First1, _Last1, _First2, equal_to<>{});
}
_EXPORT_STD template <class _FwdIt1, class _FwdIt2, class _Pr>
_NODISCARD _CONSTEXPR20 bool is_permutation(
_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred) {
// test if [_First1, _Last1) == permuted [_First2, _Last2)
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);
auto _UFirst1 = _Get_unwrapped(_First1);
auto _ULast1 = _Get_unwrapped(_Last1);
auto _UFirst2 = _Get_unwrapped(_First2);
auto _ULast2 = _Get_unwrapped(_Last2);
if constexpr (_Is_ranges_random_iter_v<_FwdIt1> && _Is_ranges_random_iter_v<_FwdIt2>) {
if (_ULast1 - _UFirst1 != _ULast2 - _UFirst2) {
return false;
}
for (; _UFirst1 != _ULast1; ++_UFirst1, (void) ++_UFirst2) { // trim matching prefix
if (!_Pred(*_UFirst1, *_UFirst2)) {
// found first inequality, check match counts in suffix
return _Check_match_counts(_UFirst1, _ULast1, _UFirst2, _ULast2, _Pass_fn(_Pred));
}
}
return true;
} else {
static_assert(_Is_ranges_fwd_iter_v<_FwdIt1> && _Is_ranges_fwd_iter_v<_FwdIt2>,
"Iterators must be at least forward iterators");
for (;; ++_UFirst1, (void) ++_UFirst2) { // trim matching prefix
if (_UFirst1 == _ULast1) {
return _UFirst2 == _ULast2;
}
if (_UFirst2 == _ULast2) {
return false;
}
if (!_Pred(*_UFirst1, *_UFirst2)) { // found first inequality, check match counts in suffix
break;
}
}
auto _Next1 = _UFirst1;
auto _Next2 = _UFirst2;
for (;; ++_Next1, (void) ++_Next2) { // check for same lengths
if (_Next1 == _ULast1) {
if (_Next2 == _ULast2) {
return _Check_match_counts(_UFirst1, _ULast1, _UFirst2, _ULast2, _Pass_fn(_Pred));
}
return false; // sequence 1 is shorter than sequence 2, not a permutation
}
if (_Next2 == _ULast2) {
return false; // sequence 1 is longer than sequence 2, not a permutation
}
}
}
}
_EXPORT_STD template <class _FwdIt1, class _FwdIt2>
_NODISCARD _CONSTEXPR20 bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2) {
// test if [_First1, _Last1) == permuted [_First2, _Last2)
return _STD is_permutation(_First1, _Last1, _First2, _Last2, equal_to<>{});
}
#ifdef __cpp_lib_concepts
namespace ranges {
class _Is_permutation_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <forward_iterator _It1, sentinel_for<_It1> _Se1, forward_iterator _It2, sentinel_for<_It2> _Se2,
class _Pj1 = identity, class _Pj2 = identity,
indirect_equivalence_relation<projected<_It1, _Pj1>, projected<_It2, _Pj2>> _Pr = ranges::equal_to>
_NODISCARD constexpr bool operator()(_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2, _Pr _Pred = {},
_Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);
auto _UFirst1 = _Unwrap_iter<_Se1>(_STD move(_First1));
auto _ULast1 = _Unwrap_sent<_It1>(_STD move(_Last1));
auto _UFirst2 = _Unwrap_iter<_Se2>(_STD move(_First2));
auto _ULast2 = _Unwrap_sent<_It2>(_STD move(_Last2));
if constexpr (sized_sentinel_for<_Se1, _It1> && sized_sentinel_for<_Se2, _It2>) {
const auto _Count = _ULast1 - _UFirst1;
if (_ULast2 - _UFirst2 != _Count) {
return false;
}
return _Is_permutation_sized(_STD move(_UFirst1), _STD move(_ULast1), _STD move(_UFirst2),
_STD move(_ULast2), _Count, _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
} else {
return _Is_permutation_unsized(_STD move(_UFirst1), _STD move(_ULast1), _STD move(_UFirst2),
_STD move(_ULast2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
}
}
template <forward_range _Rng1, forward_range _Rng2, class _Pj1 = identity, class _Pj2 = identity,
indirect_equivalence_relation<projected<iterator_t<_Rng1>, _Pj1>, projected<iterator_t<_Rng2>, _Pj2>> _Pr =
ranges::equal_to>
_NODISCARD constexpr bool operator()(
_Rng1&& _Range1, _Rng2&& _Range2, _Pr _Pred = {}, _Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
if constexpr (sized_range<_Rng1> && sized_range<_Rng2>) {
const auto _Count = _RANGES distance(_Range1);
if (_RANGES distance(_Range2) != _Count) {
return false;
}
return _Is_permutation_sized(_Ubegin(_Range1), _Uend(_Range1), _Ubegin(_Range2), _Uend(_Range2), _Count,
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
} else {
return _Is_permutation_unsized(_Ubegin(_Range1), _Uend(_Range1), _Ubegin(_Range2), _Uend(_Range2),
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
}
}
private:
template <class _It1, class _Se1, class _It2, class _Se2, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr bool _Is_permutation_sized(_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2,
iter_difference_t<_It1> _Count, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It1>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se1, _It1>);
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It2>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se2, _It2>);
_STL_INTERNAL_STATIC_ASSERT(
indirect_equivalence_relation<_Pr, projected<_It1, _Pj1>, projected<_It2, _Pj2>>);
_STL_INTERNAL_CHECK(_RANGES distance(_First1, _Last1) == _Count);
_STL_INTERNAL_CHECK(_RANGES distance(_First2, _Last2) == _Count);
for (;; ++_First1, (void) ++_First2, --_Count) { // trim matching prefixes
if (_Count == 0) { // everything matched
return true;
}
if (!_STD invoke(_Pred, _STD invoke(_Proj1, *_First1), _STD invoke(_Proj2, *_First2))) { // mismatch
break;
}
}
if (_Count == 1) { // single non-matching elements remain; not a permutation
return false;
}
// If we get here, _Count > 1 and initial elements do not match.
if constexpr (bidirectional_iterator<_It1> && bidirectional_iterator<_It2>) {
// determine final iterator values
auto _Final1 = _Find_last_iterator(_First1, _Last1, _Count);
auto _Final2 = _Find_last_iterator(_First2, _Last2, _Count);
for (;;) { // trim matching suffixes
--_Final1;
--_Final2;
if (!_STD invoke(_Pred, _STD invoke(_Proj1, *_Final1), _STD invoke(_Proj2, *_Final2))) { // mismatch
break;
}
if (--_Count == 1) {
return false; // initial elements still do not match
}
}
// If we get here, _Count > 1, initial elements do not match, and final elements do not match.
// We've trimmed matching prefixes and matching suffixes.
// Now we need to compare each range's prefix to the other range's suffix.
const auto _ProjectedPred = [&]<class _Ty1, class _Ty2>(_Ty1&& _Left, _Ty2&& _Right) -> bool {
return _STD invoke(_Pred, _STD invoke(_Proj1, _STD forward<_Ty1>(_Left)),
_STD invoke(_Proj2, _STD forward<_Ty2>(_Right)));
};
const _TrimResult _Res = _Trim_completely(_First1, _Final1, _First2, _Final2, _ProjectedPred);
if (_Res != _TrimResult::_HaveWorkAfterTrimming) {
return _Res == _TrimResult::_ReturnTrue;
}
++_Final1;
++_Final2;
// If we get here, initial elements do not match, final elements do not match, and ranges have length
// at least 2 and at most _Count.
// We've trimmed matching prefixes, matching suffixes,
// and each range's prefix matching the other range's suffix. That is, given:
// Range 1: [A, ..., B]
// Range 2: [X, ..., Y]
// we know that A != X, A != Y, B != X, and B != Y.
// (A == B and X == Y are possible but irrelevant.)
return _Match_counts(_STD move(_First1), _STD move(_Final1), _STD move(_First2), _STD move(_Final2),
_Pred, _Proj1, _Proj2);
} else {
return _Match_counts(_STD move(_First1), _STD move(_Last1), _STD move(_First2), _STD move(_Last2),
_Pred, _Proj1, _Proj2);
}
}
template <class _It1, class _Se1, class _It2, class _Se2, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr bool _Is_permutation_unsized(
_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It1>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se1, _It1>);
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It2>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se2, _It2>);
_STL_INTERNAL_STATIC_ASSERT(
indirect_equivalence_relation<_Pr, projected<_It1, _Pj1>, projected<_It2, _Pj2>>);
for (;; ++_First1, (void) ++_First2) { // trim matching prefixes
if (_First1 == _Last1) { // first range is a prefix of second
return _First2 == _Last2;
} else if (_First2 == _Last2) { // second range is a proper prefix of first
return false;
}
if (!_STD invoke(_Pred, _STD invoke(_Proj1, *_First1), _STD invoke(_Proj2, *_First2))) { // mismatch
break;
}
}
// If we get here, initial elements do not match.
// determine final iterator values and validate lengths
auto _Final1 = _First1;
auto _Final2 = _First2;
for (;;) {
++_Final1;
++_Final2;
if (_Final1 == _Last1) {
if (_Final2 == _Last2) {
break; // equal lengths
}
return false; // different lengths; not a permutation
} else if (_Final2 == _Last2) {
return false; // ditto different lengths
}
}
// If we get here, initial elements do not match and ranges have equal lengths.
if constexpr (bidirectional_iterator<_It1> && bidirectional_iterator<_It2>) {
for (;;) { // trim matching suffixes
if (--_Final1 == _First1) {
return false; // initial elements still do not match
}
--_Final2; // since ranges have equal lengths, _Final2 cannot equal _First2
if (!_STD invoke(_Pred, _STD invoke(_Proj1, *_Final1), _STD invoke(_Proj2, *_Final2))) { // mismatch
break;
}
}
// If we get here, initial elements do not match, final elements do not match, and ranges have length
// at least 2.
// We've trimmed matching prefixes and matching suffixes.
// Now we need to compare each range's prefix to the other range's suffix.
const auto _ProjectedPred = [&]<class _Ty1, class _Ty2>(_Ty1&& _Left, _Ty2&& _Right) -> bool {
return _STD invoke(_Pred, _STD invoke(_Proj1, _STD forward<_Ty1>(_Left)),
_STD invoke(_Proj2, _STD forward<_Ty2>(_Right)));
};
const _TrimResult _Res = _Trim_completely(_First1, _Final1, _First2, _Final2, _ProjectedPred);
if (_Res != _TrimResult::_HaveWorkAfterTrimming) {
return _Res == _TrimResult::_ReturnTrue;
}
++_Final1;
++_Final2;
// If we get here, initial elements do not match, final elements do not match, and ranges have length
// at least 2.
// We've trimmed matching prefixes, matching suffixes,
// and each range's prefix matching the other range's suffix. That is, given:
// Range 1: [A, ..., B]
// Range 2: [X, ..., Y]
// we know that A != X, A != Y, B != X, and B != Y.
// (A == B and X == Y are possible but irrelevant.)
}
return _Match_counts(
_STD move(_First1), _STD move(_Final1), _STD move(_First2), _STD move(_Final2), _Pred, _Proj1, _Proj2);
}
template <class _It1, class _Se1, class _It2, class _Se2, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr bool _Match_counts(const _It1 _First1, const _Se1 _Last1, const _It2 _First2,
const _Se2 _Last2, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It1>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se1, _It1>);
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It2>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se2, _It2>);
_STL_INTERNAL_STATIC_ASSERT(
indirect_equivalence_relation<_Pr, projected<_It1, _Pj1>, projected<_It2, _Pj2>>);
for (auto _Current = _First1; _Current != _Last1; ++_Current) {
bool _Found = false;
auto _Mid1 = _First1;
for (; _Mid1 != _Current; ++_Mid1) {
if (_STD invoke(_Pred, _STD invoke(_Proj1, *_Current), _STD invoke(_Proj1, *_Mid1))) {
// this value appears earlier in the first range so we've already counted occurrences
_Found = true;
break;
}
}
if (_Found) {
continue;
}
// count occurrences of this value in the first range
iter_difference_t<_It1> _Occurrences = 1;
while (++_Mid1 != _Last1) {
if (_STD invoke(_Pred, _STD invoke(_Proj1, *_Current), _STD invoke(_Proj1, *_Mid1))) {
++_Occurrences;
}
}
// subtract occurrences in the second range
for (auto _Mid2 = _First2; _Mid2 != _Last2; ++_Mid2) {
if (_STD invoke(_Pred, _STD invoke(_Proj1, *_Current), _STD invoke(_Proj2, *_Mid2))) {
if (--_Occurrences < 0) {
// value appears more in second range than first; not a permutation
return false;
}
}
}
if (_Occurrences != 0) {
// value appears more in first range than second; not a permutation
return false;
}
}
return true;
}
};
_EXPORT_STD inline constexpr _Is_permutation_fn is_permutation{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _InIt, class _Pr>
_NODISCARD _CONSTEXPR20 bool all_of(_InIt _First, _InIt _Last, _Pr _Pred) { // test if all elements satisfy _Pred
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
for (; _UFirst != _ULast; ++_UFirst) {
if (!_Pred(*_UFirst)) {
return false;
}
}
return true;
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD bool all_of(_ExPo&&, _FwdIt _First, _FwdIt _Last, _Pr _Pred) noexcept; // terminates
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
class _All_of_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, class _Pj = identity,
indirect_unary_predicate<projected<_It, _Pj>> _Pr>
_NODISCARD constexpr bool operator()(_It _First, _Se _Last, _Pr _Pred, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
return _All_of_unchecked(_Unwrap_iter<_Se>(_STD move(_First)), _Unwrap_sent<_It>(_STD move(_Last)),
_Pass_fn(_Pred), _Pass_fn(_Proj));
}
template <input_range _Rng, class _Pj = identity,
indirect_unary_predicate<projected<iterator_t<_Rng>, _Pj>> _Pr>
_NODISCARD constexpr bool operator()(_Rng&& _Range, _Pr _Pred, _Pj _Proj = {}) const {
return _All_of_unchecked(_Ubegin(_Range), _Uend(_Range), _Pass_fn(_Pred), _Pass_fn(_Proj));
}
private:
template <class _It, class _Se, class _Pj, class _Pr>
_NODISCARD static constexpr bool _All_of_unchecked(_It _First, const _Se _Last, _Pr _Pred, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirect_unary_predicate<_Pr, projected<_It, _Pj>>);
for (; _First != _Last; ++_First) {
if (!_STD invoke(_Pred, _STD invoke(_Proj, *_First))) {
return false;
}
}
return true;
}
};
_EXPORT_STD inline constexpr _All_of_fn all_of{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _InIt, class _Pr>
_NODISCARD _CONSTEXPR20 bool any_of(const _InIt _First, const _InIt _Last, _Pr _Pred) {
// test if any element satisfies _Pred
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
for (; _UFirst != _ULast; ++_UFirst) {
if (_Pred(*_UFirst)) {
return true;
}
}
return false;
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD bool any_of(_ExPo&&, _FwdIt _First, _FwdIt _Last, _Pr _Pred) noexcept; // terminates
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
class _Any_of_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, class _Pj = identity,
indirect_unary_predicate<projected<_It, _Pj>> _Pr>
_NODISCARD constexpr bool operator()(_It _First, _Se _Last, _Pr _Pred, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
return _Any_of_unchecked(_Unwrap_iter<_Se>(_STD move(_First)), _Unwrap_sent<_It>(_STD move(_Last)),
_Pass_fn(_Pred), _Pass_fn(_Proj));
}
template <input_range _Rng, class _Pj = identity,
indirect_unary_predicate<projected<iterator_t<_Rng>, _Pj>> _Pr>
_NODISCARD constexpr bool operator()(_Rng&& _Range, _Pr _Pred, _Pj _Proj = {}) const {
return _Any_of_unchecked(_Ubegin(_Range), _Uend(_Range), _Pass_fn(_Pred), _Pass_fn(_Proj));
}
private:
template <class _It, class _Se, class _Pj, class _Pr>
_NODISCARD static constexpr bool _Any_of_unchecked(_It _First, const _Se _Last, _Pr _Pred, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirect_unary_predicate<_Pr, projected<_It, _Pj>>);
for (; _First != _Last; ++_First) {
if (_STD invoke(_Pred, _STD invoke(_Proj, *_First))) {
return true;
}
}
return false;
}
};
_EXPORT_STD inline constexpr _Any_of_fn any_of{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _InIt, class _Pr>
_NODISCARD _CONSTEXPR20 bool none_of(const _InIt _First, const _InIt _Last, _Pr _Pred) {
// test if no elements satisfy _Pred
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
for (; _UFirst != _ULast; ++_UFirst) {
if (_Pred(*_UFirst)) {
return false;
}
}
return true;
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD bool none_of(_ExPo&&, _FwdIt _First, _FwdIt _Last, _Pr _Pred) noexcept; // terminates
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
class _None_of_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, class _Pj = identity,
indirect_unary_predicate<projected<_It, _Pj>> _Pr>
_NODISCARD constexpr bool operator()(_It _First, _Se _Last, _Pr _Pred, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
return _None_of_unchecked(_Unwrap_iter<_Se>(_STD move(_First)), _Unwrap_sent<_It>(_STD move(_Last)),
_Pass_fn(_Pred), _Pass_fn(_Proj));
}
template <input_range _Rng, class _Pj = identity,
indirect_unary_predicate<projected<iterator_t<_Rng>, _Pj>> _Pr>
_NODISCARD constexpr bool operator()(_Rng&& _Range, _Pr _Pred, _Pj _Proj = {}) const {
return _None_of_unchecked(_Ubegin(_Range), _Uend(_Range), _Pass_fn(_Pred), _Pass_fn(_Proj));
}
private:
template <class _It, class _Se, class _Pj, class _Pr>
_NODISCARD static constexpr bool _None_of_unchecked(_It _First, const _Se _Last, _Pr _Pred, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirect_unary_predicate<_Pr, projected<_It, _Pj>>);
for (; _First != _Last; ++_First) {
if (_STD invoke(_Pred, _STD invoke(_Proj, *_First))) {
return false;
}
}
return true;
}
};
_EXPORT_STD inline constexpr _None_of_fn none_of{_Not_quite_object::_Construct_tag{}};
#if _HAS_CXX23
class _Contains_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, class _Ty, class _Pj = identity>
requires indirect_binary_predicate<ranges::equal_to, projected<_It, _Pj>, const _Ty*>
_NODISCARD constexpr bool operator()(_It _First, _Se _Last, const _Ty& _Val, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
const auto _ULast = _Unwrap_sent<_It>(_STD move(_Last));
const auto _UResult =
_RANGES _Find_unchecked(_Unwrap_iter<_Se>(_STD move(_First)), _ULast, _Val, _Pass_fn(_Proj));
return _UResult != _ULast;
}
template <input_range _Rng, class _Ty, class _Pj = identity>
requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Rng>, _Pj>, const _Ty*>
_NODISCARD constexpr bool operator()(_Rng&& _Range, const _Ty& _Val, _Pj _Proj = {}) const {
const auto _UResult = _RANGES _Find_unchecked(_Ubegin(_Range), _Uend(_Range), _Val, _Pass_fn(_Proj));
return _UResult != _Uend(_Range);
}
};
_EXPORT_STD inline constexpr _Contains_fn contains{_Not_quite_object::_Construct_tag{}};
class _Contains_subrange_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <forward_iterator _It1, sentinel_for<_It1> _Se1, forward_iterator _It2, sentinel_for<_It2> _Se2,
class _Pr = ranges::equal_to, class _Pj1 = identity, class _Pj2 = identity>
requires indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr bool operator()(_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2, _Pr _Pred = {},
_Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
_Adl_verify_range(_First2, _Last2);
auto _UFirst2 = _Unwrap_iter<_Se2>(_STD move(_First2));
auto _ULast2 = _Unwrap_sent<_It2>(_STD move(_Last2));
if (_UFirst2 == _ULast2) {
return true;
}
const auto _Match = _RANGES search(_STD move(_First1), _STD move(_Last1), _STD move(_UFirst2),
_STD move(_ULast2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return !_Match.empty();
}
template <forward_range _Rng1, forward_range _Rng2, class _Pr = ranges::equal_to, class _Pj1 = identity,
class _Pj2 = identity>
requires indirectly_comparable<iterator_t<_Rng1>, iterator_t<_Rng2>, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr bool operator()(
_Rng1&& _Range1, _Rng2&& _Range2, _Pr _Pred = {}, _Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
if (_RANGES empty(_Range2)) {
return true;
}
const auto _Match = _RANGES search(_Range1, _Range2, _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return !_Match.empty();
}
};
_EXPORT_STD inline constexpr _Contains_subrange_fn contains_subrange{_Not_quite_object::_Construct_tag{}};
#endif // _HAS_CXX23
_EXPORT_STD template <class _In, class _Out>
using copy_n_result = in_out_result<_In, _Out>;
class _Copy_n_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, weakly_incrementable _Out>
requires indirectly_copyable<_It, _Out>
constexpr copy_n_result<_It, _Out> operator()(_It _First, iter_difference_t<_It> _Count, _Out _Result) const {
auto _UFirst = _Get_unwrapped_n(_STD move(_First), _Count);
if constexpr (_Iter_copy_cat<decltype(_UFirst), _Out>::_Bitcopy_assignable) {
if (!_STD is_constant_evaluated()) {
_Result = _Copy_memmove_n(_UFirst, static_cast<size_t>(_Count), _STD move(_Result));
_UFirst += _Count;
_Seek_wrapped(_First, _STD move(_UFirst));
return {_STD move(_First), _STD move(_Result)};
}
}
for (; _Count > 0; ++_UFirst, (void) ++_Result, --_Count) {
*_Result = *_UFirst;
}
_Seek_wrapped(_First, _STD move(_UFirst));
return {_STD move(_First), _STD move(_Result)};
}
};
_EXPORT_STD inline constexpr _Copy_n_fn copy_n{_Not_quite_object::_Construct_tag{}};
_EXPORT_STD template <class _In, class _Out>
using copy_backward_result = in_out_result<_In, _Out>;
class _Copy_backward_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <bidirectional_iterator _It1, sentinel_for<_It1> _Se1, bidirectional_iterator _It2>
requires indirectly_copyable<_It1, _It2>
constexpr copy_backward_result<_It1, _It2> operator()(_It1 _First, _Se1 _Last, _It2 _Result) const {
_Adl_verify_range(_First, _Last);
auto _UFirst = _Unwrap_iter<_Se1>(_STD move(_First));
auto _ULast = _Get_final_iterator_unwrapped<_It1>(_UFirst, _STD move(_Last));
_Seek_wrapped(_First, _ULast);
_Result = _Copy_backward_unchecked(_STD move(_UFirst), _STD move(_ULast), _STD move(_Result));
return {_STD move(_First), _STD move(_Result)};
}
template <bidirectional_range _Rng, bidirectional_iterator _It>
requires indirectly_copyable<iterator_t<_Rng>, _It>
constexpr copy_backward_result<borrowed_iterator_t<_Rng>, _It> operator()(_Rng&& _Range, _It _Result) const {
auto _ULast = _Get_final_iterator_unwrapped(_Range);
_Result = _Copy_backward_unchecked(_Ubegin(_Range), _ULast, _STD move(_Result));
return {_Rewrap_iterator(_Range, _STD move(_ULast)), _STD move(_Result)};
}
};
_EXPORT_STD inline constexpr _Copy_backward_fn copy_backward{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _InIt, class _OutIt, class _Pr>
_CONSTEXPR20 _OutIt copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred) { // copy each satisfying _Pred
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
auto _UDest = _Get_unwrapped_unverified(_Dest);
for (; _UFirst != _ULast; ++_UFirst) {
if (_Pred(*_UFirst)) {
*_UDest = *_UFirst;
++_UDest;
}
}
_Seek_wrapped(_Dest, _UDest);
return _Dest;
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt1, class _FwdIt2, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_FwdIt2 copy_if(_ExPo&&, _FwdIt1 _First, _FwdIt1 _Last, _FwdIt2 _Dest, _Pr _Pred) noexcept /* terminates */ {
// copy each satisfying _Pred
// not parallelized at present, parallelism expected to be feasible in a future release
_REQUIRE_PARALLEL_ITERATOR(_FwdIt1);
_REQUIRE_CPP17_MUTABLE_ITERATOR(_FwdIt2);
return _STD copy_if(_First, _Last, _Dest, _Pass_fn(_Pred));
}
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
_EXPORT_STD template <class _In, class _Out>
using copy_if_result = in_out_result<_In, _Out>;
class _Copy_if_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, weakly_incrementable _Out, class _Pj = identity,
indirect_unary_predicate<projected<_It, _Pj>> _Pr>
requires indirectly_copyable<_It, _Out>
constexpr copy_if_result<_It, _Out> operator()(
_It _First, _Se _Last, _Out _Result, _Pr _Pred, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
auto _UResult = _Copy_if_unchecked(_Unwrap_iter<_Se>(_STD move(_First)),
_Unwrap_sent<_It>(_STD move(_Last)), _STD move(_Result), _Pass_fn(_Pred), _Pass_fn(_Proj));
_Seek_wrapped(_First, _STD move(_UResult.in));
return {_STD move(_First), _STD move(_UResult.out)};
}
template <input_range _Rng, weakly_incrementable _Out, class _Pj = identity,
indirect_unary_predicate<projected<iterator_t<_Rng>, _Pj>> _Pr>
requires indirectly_copyable<iterator_t<_Rng>, _Out>
constexpr copy_if_result<borrowed_iterator_t<_Rng>, _Out> operator()(
_Rng&& _Range, _Out _Result, _Pr _Pred, _Pj _Proj = {}) const {
auto _First = _RANGES begin(_Range);
auto _UResult = _Copy_if_unchecked(_Unwrap_range_iter<_Rng>(_STD move(_First)), _Uend(_Range),
_STD move(_Result), _Pass_fn(_Pred), _Pass_fn(_Proj));
_Seek_wrapped(_First, _STD move(_UResult.in));
return {_STD move(_First), _STD move(_UResult.out)};
}
private:
template <class _It, class _Se, class _Out, class _Pj, class _Pr>
_NODISCARD static constexpr copy_if_result<_It, _Out> _Copy_if_unchecked(
_It _First, const _Se _Last, _Out _Result, _Pr _Pred, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirect_unary_predicate<_Pr, projected<_It, _Pj>>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_copyable<_It, _Out>);
for (; _First != _Last; ++_First) {
if (_STD invoke(_Pred, _STD invoke(_Proj, *_First))) {
*_Result = *_First;
++_Result;
}
}
return {_STD move(_First), _STD move(_Result)};
}
};
_EXPORT_STD inline constexpr _Copy_if_fn copy_if{_Not_quite_object::_Construct_tag{}};
_EXPORT_STD template <class _In, class _Out>
using move_result = in_out_result<_In, _Out>;
template <input_iterator _It, sentinel_for<_It> _Se, weakly_incrementable _Out>
requires indirectly_movable<_It, _Out>
constexpr move_result<_It, _Out> _Move_unchecked(_It _First, _Se _Last, _Out _Result) {
if constexpr (_Iter_move_cat<_It, _Out>::_Bitcopy_assignable) {
if (!_STD is_constant_evaluated()) {
auto _Final = _RANGES next(_First, _STD move(_Last));
_Result = _Copy_memmove(_STD move(_First), _Final, _STD move(_Result));
return {_STD move(_Final), _STD move(_Result)};
}
}
for (; _First != _Last; ++_First, (void) ++_Result) {
*_Result = _RANGES iter_move(_First);
}
return {_STD move(_First), _STD move(_Result)};
}
class _Move_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, weakly_incrementable _Out>
requires indirectly_movable<_It, _Out>
constexpr move_result<_It, _Out> operator()(_It _First, _Se _Last, _Out _Result) const {
_Adl_verify_range(_First, _Last);
auto _UResult = _RANGES _Move_unchecked(
_Unwrap_iter<_Se>(_STD move(_First)), _Unwrap_sent<_It>(_STD move(_Last)), _STD move(_Result));
_Seek_wrapped(_First, _STD move(_UResult.in));
return {_STD move(_First), _STD move(_UResult.out)};
}
template <input_range _Rng, weakly_incrementable _Out>
requires indirectly_movable<iterator_t<_Rng>, _Out>
constexpr move_result<borrowed_iterator_t<_Rng>, _Out> operator()(_Rng&& _Range, _Out _Result) const {
auto _First = _RANGES begin(_Range);
auto _UResult =
_RANGES _Move_unchecked(_Unwrap_range_iter<_Rng>(_STD move(_First)), _Uend(_Range), _STD move(_Result));
_Seek_wrapped(_First, _STD move(_UResult.in));
return {_STD move(_First), _STD move(_UResult.out)};
}
};
_EXPORT_STD inline constexpr _Move_fn move{_Not_quite_object::_Construct_tag{}};
_EXPORT_STD template <class _In, class _Out>
using move_backward_result = in_out_result<_In, _Out>;
// concept-constrained for strict enforcement as it is used by several algorithms
template <bidirectional_iterator _It1, bidirectional_iterator _It2>
requires indirectly_movable<_It1, _It2>
constexpr _It2 _Move_backward_common(const _It1 _First, _It1 _Last, _It2 _Result) {
if constexpr (_Iter_move_cat<_It1, _It2>::_Bitcopy_assignable) {
if (!_STD is_constant_evaluated()) {
return _Copy_backward_memmove(_First, _Last, _Result);
}
}
while (_First != _Last) {
*--_Result = _RANGES iter_move(--_Last);
}
return _Result;
}
class _Move_backward_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <bidirectional_iterator _It1, sentinel_for<_It1> _Se1, bidirectional_iterator _It2>
requires indirectly_movable<_It1, _It2>
constexpr move_backward_result<_It1, _It2> operator()(_It1 _First, _Se1 _Last, _It2 _Result) const {
_Adl_verify_range(_First, _Last);
auto _UFirst = _Unwrap_iter<_Se1>(_STD move(_First));
auto _ULast = _Get_final_iterator_unwrapped<_It1>(_UFirst, _STD move(_Last));
_Seek_wrapped(_First, _ULast);
_Result = _RANGES _Move_backward_common(_STD move(_UFirst), _STD move(_ULast), _STD move(_Result));
return {_STD move(_First), _STD move(_Result)};
}
template <bidirectional_range _Rng, bidirectional_iterator _It>
requires indirectly_movable<iterator_t<_Rng>, _It>
constexpr move_backward_result<borrowed_iterator_t<_Rng>, _It> operator()(_Rng&& _Range, _It _Result) const {
auto _ULast = _Get_final_iterator_unwrapped(_Range);
_Result = _RANGES _Move_backward_common(_Ubegin(_Range), _ULast, _STD move(_Result));
return {_Rewrap_iterator(_Range, _STD move(_ULast)), _STD move(_Result)};
}
};
_EXPORT_STD inline constexpr _Move_backward_fn move_backward{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _InIt, class _OutIt1, class _OutIt2, class _Pr>
_CONSTEXPR20 pair<_OutIt1, _OutIt2> partition_copy(
_InIt _First, _InIt _Last, _OutIt1 _Dest_true, _OutIt2 _Dest_false, _Pr _Pred) {
// copy true partition to _Dest_true, false to _Dest_false
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
auto _UDest_true = _Get_unwrapped_unverified(_Dest_true);
auto _UDest_false = _Get_unwrapped_unverified(_Dest_false);
for (; _UFirst != _ULast; ++_UFirst) {
if (_Pred(*_UFirst)) {
*_UDest_true = *_UFirst;
++_UDest_true;
} else {
*_UDest_false = *_UFirst;
++_UDest_false;
}
}
_Seek_wrapped(_Dest_false, _UDest_false);
_Seek_wrapped(_Dest_true, _UDest_true);
return {_Dest_true, _Dest_false};
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt1, class _FwdIt2, class _FwdIt3, class _Pr,
_Enable_if_execution_policy_t<_ExPo> = 0>
pair<_FwdIt2, _FwdIt3> partition_copy(_ExPo&&, _FwdIt1 _First, _FwdIt1 _Last, _FwdIt2 _Dest_true, _FwdIt3 _Dest_false,
_Pr _Pred) noexcept /* terminates */ {
// copy true partition to _Dest_true, false to _Dest_false
// not parallelized at present, parallelism expected to be feasible in a future release
_REQUIRE_PARALLEL_ITERATOR(_FwdIt1);
_REQUIRE_CPP17_MUTABLE_ITERATOR(_FwdIt2);
_REQUIRE_CPP17_MUTABLE_ITERATOR(_FwdIt3);
return _STD partition_copy(_First, _Last, _Dest_true, _Dest_false, _Pass_fn(_Pred));
}
#ifdef __cpp_lib_concepts
namespace ranges {
_EXPORT_STD template <class _In, class _Out1, class _Out2>
using partition_copy_result = in_out_out_result<_In, _Out1, _Out2>;
class _Partition_copy_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, weakly_incrementable _Out1, weakly_incrementable _Out2,
class _Pj = identity, indirect_unary_predicate<projected<_It, _Pj>> _Pr>
requires indirectly_copyable<_It, _Out1> && indirectly_copyable<_It, _Out2>
constexpr partition_copy_result<_It, _Out1, _Out2> operator()(
_It _First, _Se _Last, _Out1 _Dest_true, _Out2 _Dest_false, _Pr _Pred, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
auto _UResult = _Partition_copy_unchecked(_Unwrap_iter<_Se>(_STD move(_First)),
_Unwrap_sent<_It>(_STD move(_Last)), _Get_unwrapped_unverified(_STD move(_Dest_true)),
_Get_unwrapped_unverified(_STD move(_Dest_false)), _Pass_fn(_Pred), _Pass_fn(_Proj));
_Seek_wrapped(_First, _STD move(_UResult.in));
_Seek_wrapped(_Dest_true, _STD move(_UResult.out1));
_Seek_wrapped(_Dest_false, _STD move(_UResult.out2));
return {_STD move(_First), _STD move(_Dest_true), _STD move(_Dest_false)};
}
template <input_range _Rng, weakly_incrementable _Out1, weakly_incrementable _Out2, class _Pj = identity,
indirect_unary_predicate<projected<iterator_t<_Rng>, _Pj>> _Pr>
requires indirectly_copyable<iterator_t<_Rng>, _Out1> && indirectly_copyable<iterator_t<_Rng>, _Out2>
constexpr partition_copy_result<borrowed_iterator_t<_Rng>, _Out1, _Out2> operator()(
_Rng&& _Range, _Out1 _Dest_true, _Out2 _Dest_false, _Pr _Pred, _Pj _Proj = {}) const {
auto _First = _RANGES begin(_Range);
auto _UResult = _Partition_copy_unchecked(_Unwrap_range_iter<_Rng>(_STD move(_First)), _Uend(_Range),
_Get_unwrapped_unverified(_STD move(_Dest_true)), _Get_unwrapped_unverified(_STD move(_Dest_false)),
_Pass_fn(_Pred), _Pass_fn(_Proj));
_Seek_wrapped(_First, _STD move(_UResult.in));
_Seek_wrapped(_Dest_true, _STD move(_UResult.out1));
_Seek_wrapped(_Dest_false, _STD move(_UResult.out2));
return {_STD move(_First), _STD move(_Dest_true), _STD move(_Dest_false)};
}
private:
template <class _It, class _Se, class _Out1, class _Out2, class _Pr, class _Pj>
_NODISCARD static constexpr partition_copy_result<_It, _Out1, _Out2> _Partition_copy_unchecked(
_It _First, const _Se _Last, _Out1 _Dest_true, _Out2 _Dest_false, _Pr _Pred, _Pj _Proj) {
// copy true partition to _Dest_true, false to _Dest_false
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(weakly_incrementable<_Out1> && weakly_incrementable<_Out2>);
_STL_INTERNAL_STATIC_ASSERT(indirect_unary_predicate<_Pr, projected<_It, _Pj>>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_copyable<_It, _Out1> && indirectly_copyable<_It, _Out2>);
for (; _First != _Last; ++_First) {
if (_STD invoke(_Pred, _STD invoke(_Proj, *_First))) {
*_Dest_true = *_First;
++_Dest_true;
} else {
*_Dest_false = *_First;
++_Dest_false;
}
}
return {_STD move(_First), _STD move(_Dest_true), _STD move(_Dest_false)};
}
};
_EXPORT_STD inline constexpr _Partition_copy_fn partition_copy{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
#endif // _HAS_CXX17
_EXPORT_STD template <class _InIt, class _Pr>
_NODISCARD _CONSTEXPR20 bool is_partitioned(const _InIt _First, const _InIt _Last, _Pr _Pred) {
// test if [_First, _Last) partitioned by _Pred
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
for (;; ++_UFirst) { // skip true partition
if (_UFirst == _ULast) {
return true;
}
if (!_Pred(*_UFirst)) {
break;
}
}
while (++_UFirst != _ULast) { // verify false partition
if (_Pred(*_UFirst)) {
return false; // found out of place element
}
}
return true;
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD bool is_partitioned(_ExPo&&, _FwdIt _First, _FwdIt _Last, _Pr _Pred) noexcept; // terminates
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
class _Is_partitioned_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, class _Pj = identity,
indirect_unary_predicate<projected<_It, _Pj>> _Pr>
_NODISCARD constexpr bool operator()(_It _First, _Se _Last, _Pr _Pred, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
return _Is_partitioned_unchecked(_Unwrap_iter<_Se>(_STD move(_First)), _Unwrap_sent<_It>(_STD move(_Last)),
_Pass_fn(_Pred), _Pass_fn(_Proj));
}
template <input_range _Rng, class _Pj = identity,
indirect_unary_predicate<projected<iterator_t<_Rng>, _Pj>> _Pr>
_NODISCARD constexpr bool operator()(_Rng&& _Range, _Pr _Pred, _Pj _Proj = {}) const {
return _Is_partitioned_unchecked(_Ubegin(_Range), _Uend(_Range), _Pass_fn(_Pred), _Pass_fn(_Proj));
}
private:
template <class _It, class _Se, class _Pr, class _Pj>
_NODISCARD static constexpr bool _Is_partitioned_unchecked(_It _First, const _Se _Last, _Pr _Pred, _Pj _Proj) {
// test if [_First, _Last) is partitioned with respect to _Pred and _Proj
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirect_unary_predicate<_Pr, projected<_It, _Pj>>);
for (;; ++_First) { // skip true partition
if (_First == _Last) {
return true;
}
if (!_STD invoke(_Pred, _STD invoke(_Proj, *_First))) {
break;
}
}
while (++_First != _Last) { // verify false partition
if (_STD invoke(_Pred, _STD invoke(_Proj, *_First))) {
return false; // found out of place element
}
}
return true;
}
};
_EXPORT_STD inline constexpr _Is_partitioned_fn is_partitioned{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _FwdIt, class _Pr>
_NODISCARD _CONSTEXPR20 _FwdIt partition_point(_FwdIt _First, _FwdIt _Last, _Pr _Pred) {
// find beginning of false partition in [_First, _Last)
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
auto _Count = _STD distance(_UFirst, _ULast);
while (0 < _Count) { // divide and conquer, find half that contains answer
const auto _Count2 = static_cast<_Iter_diff_t<_FwdIt>>(_Count / 2);
const auto _UMid = _STD next(_UFirst, _Count2);
if (_Pred(*_UMid)) { // try top half
_UFirst = _Next_iter(_UMid);
_Count -= _Count2;
--_Count;
} else {
_Count = _Count2;
}
}
_Seek_wrapped(_First, _UFirst);
return _First;
}
#ifdef __cpp_lib_concepts
namespace ranges {
class _Partition_point_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <forward_iterator _It, sentinel_for<_It> _Se, class _Pj = identity,
indirect_unary_predicate<projected<_It, _Pj>> _Pr>
_NODISCARD constexpr _It operator()(_It _First, _Se _Last, _Pr _Pred, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
auto _UFirst = _Unwrap_iter<_Se>(_STD move(_First));
if constexpr (sized_sentinel_for<_Se, _It>) {
const auto _Length = _Unwrap_sent<_It>(_STD move(_Last)) - _UFirst;
_UFirst = _Partition_point_n_unchecked(_STD move(_UFirst), _Length, _Pass_fn(_Pred), _Pass_fn(_Proj));
} else {
_UFirst = _Partition_point_unchecked(
_STD move(_UFirst), _Unwrap_sent<_It>(_STD move(_Last)), _Pass_fn(_Pred), _Pass_fn(_Proj));
}
_Seek_wrapped(_First, _STD move(_UFirst));
return _First;
}
template <forward_range _Rng, class _Pj = identity,
indirect_unary_predicate<projected<iterator_t<_Rng>, _Pj>> _Pr>
_NODISCARD constexpr borrowed_iterator_t<_Rng> operator()(_Rng&& _Range, _Pr _Pred, _Pj _Proj = {}) const {
if constexpr (sized_range<_Rng>) {
const auto _Length = _RANGES distance(_Range);
auto _UFirst = _Partition_point_n_unchecked(_Ubegin(_Range), _Length, _Pass_fn(_Pred), _Pass_fn(_Proj));
return _Rewrap_iterator(_Range, _STD move(_UFirst));
} else {
auto _UFirst =
_Partition_point_unchecked(_Ubegin(_Range), _Uend(_Range), _Pass_fn(_Pred), _Pass_fn(_Proj));
return _Rewrap_iterator(_Range, _STD move(_UFirst));
}
}
private:
template <class _It, class _Pr, class _Pj>
_NODISCARD static constexpr _It _Partition_point_n_unchecked(
_It _First, iter_difference_t<_It> _Length, _Pr _Pred, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(indirect_unary_predicate<_Pr, projected<_It, _Pj>>);
_STL_INTERNAL_CHECK(_Length >= 0);
while (_Length > 0) {
const auto _Half = static_cast<iter_difference_t<_It>>(_Length / 2);
auto _Mid = _RANGES next(_First, _Half);
if (_STD invoke(_Pred, _STD invoke(_Proj, *_Mid))) { // _Mid is before the partition point
_First = _STD move(_Mid);
++_First;
_Length -= _Half;
--_Length;
} else { // _Mid is at or past the partition point
_Length = _Half;
}
}
return _First;
}
template <class _It, class _Se, class _Pr, class _Pj>
_NODISCARD static constexpr _It _Partition_point_unchecked(_It _First, const _Se _Last, _Pr _Pred, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirect_unary_predicate<_Pr, projected<_It, _Pj>>);
// Instead of blindly seeking the end of the range, probe elements at exponentially increasing intervals to
// find an element past the partition point.
iter_difference_t<_It> _Skip = 2;
for (;;) {
auto _Mid = _First;
_Skip -= _RANGES advance(_Mid, _Skip, _Last);
if (_Mid == _Last) { // we've located the end of the range
break;
}
if (!_STD invoke(_Pred, _STD invoke(_Proj, *_Mid))) { // _Mid is at or past the partition point
break;
}
_First = _STD move(_Mid);
++_First;
using _Uty = _Make_unsigned_like_t<iter_difference_t<_It>>;
if (static_cast<_Uty>(_Skip) <= (static_cast<_Uty>(-1) >> 1)) {
_Skip <<= 1;
}
}
return _Partition_point_n_unchecked(_STD move(_First), _Skip, _Pred, _Proj);
}
};
_EXPORT_STD inline constexpr _Partition_point_fn partition_point{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
template <class _InIt1, class _InIt2, class _Pr>
_NODISCARD _CONSTEXPR20 bool _Equal_rev_pred_unchecked(_InIt1 _First1, _InIt2 _First2, const _InIt2 _Last2, _Pr _Pred) {
// compare [_First1, ...) to [_First2, _Last2)
if constexpr (_Equal_memcmp_is_safe<_InIt1, _InIt2, _Pr>) {
#if _HAS_CXX20
if (!_STD is_constant_evaluated())
#endif // _HAS_CXX20
{
return _Memcmp_ranges(_First2, _Last2, _First1) == 0;
}
}
for (; _First2 != _Last2; ++_First1, (void) ++_First2) {
if (!_Pred(*_First1, *_First2)) {
return false;
}
}
return true;
}
_EXPORT_STD template <class _FwdItHaystack, class _FwdItPat, class _Pr>
_NODISCARD _CONSTEXPR20 _FwdItHaystack search(_FwdItHaystack _First1, _FwdItHaystack _Last1, const _FwdItPat _First2,
const _FwdItPat _Last2, _Pr _Pred) { // find first [_First2, _Last2) satisfying _Pred
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);
auto _UFirst1 = _Get_unwrapped(_First1);
const auto _ULast1 = _Get_unwrapped(_Last1);
const auto _UFirst2 = _Get_unwrapped(_First2);
const auto _ULast2 = _Get_unwrapped(_Last2);
if constexpr (_Is_ranges_random_iter_v<_FwdItHaystack> && _Is_ranges_random_iter_v<_FwdItPat>) {
const _Iter_diff_t<_FwdItPat> _Count2 = _ULast2 - _UFirst2;
if (_ULast1 - _UFirst1 >= _Count2) {
const auto _Last_possible = _ULast1 - static_cast<_Iter_diff_t<_FwdItHaystack>>(_Count2);
for (;; ++_UFirst1) {
if (_Equal_rev_pred_unchecked(_UFirst1, _UFirst2, _ULast2, _Pass_fn(_Pred))) {
_Seek_wrapped(_Last1, _UFirst1);
break;
}
if (_UFirst1 == _Last_possible) {
break;
}
}
}
} else {
for (;; ++_UFirst1) { // loop until match or end of a sequence
auto _UMid1 = _UFirst1;
for (auto _UMid2 = _UFirst2;; ++_UMid1, (void) ++_UMid2) {
if (_UMid2 == _ULast2) {
_Seek_wrapped(_Last1, _UFirst1);
return _Last1;
} else if (_UMid1 == _ULast1) {
return _Last1;
} else if (!_Pred(*_UMid1, *_UMid2)) {
break;
}
}
}
}
return _Last1;
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdItHaystack, class _FwdItPat, class _Pr,
_Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdItHaystack search(_ExPo&& _Exec, _FwdItHaystack _First1, _FwdItHaystack _Last1, _FwdItPat _First2,
_FwdItPat _Last2, _Pr _Pred) noexcept; // terminates
#endif // _HAS_CXX17
_EXPORT_STD template <class _FwdItHaystack, class _FwdItPat>
_NODISCARD _CONSTEXPR20 _FwdItHaystack search(
const _FwdItHaystack _First1, const _FwdItHaystack _Last1, const _FwdItPat _First2, const _FwdItPat _Last2) {
// find first [_First2, _Last2) match
return _STD search(_First1, _Last1, _First2, _Last2, equal_to<>{});
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdItHaystack, class _FwdItPat, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdItHaystack search(_ExPo&& _Exec, const _FwdItHaystack _First1, const _FwdItHaystack _Last1,
const _FwdItPat _First2, const _FwdItPat _Last2) noexcept /* terminates */ {
// find first [_First2, _Last2) match
return _STD search(_STD forward<_ExPo>(_Exec), _First1, _Last1, _First2, _Last2, equal_to{});
}
#endif // _HAS_CXX17
_EXPORT_STD template <class _FwdItHaystack, class _Searcher>
_NODISCARD _CONSTEXPR20 _FwdItHaystack search(
const _FwdItHaystack _First, const _FwdItHaystack _Last, const _Searcher& _Search) {
// find _Search's pattern in [_First, _Last)
return _Search(_First, _Last).first;
}
_EXPORT_STD template <class _FwdIt, class _Diff, class _Ty, class _Pr>
_NODISCARD _CONSTEXPR20 _FwdIt search_n(
const _FwdIt _First, _FwdIt _Last, const _Diff _Count_raw, const _Ty& _Val, _Pr _Pred) {
// find first _Count * _Val satisfying _Pred
const _Algorithm_int_t<_Diff> _Count = _Count_raw;
if (_Count <= 0) {
return _First;
}
if (static_cast<uintmax_t>(_Count) > static_cast<uintmax_t>((numeric_limits<_Iter_diff_t<_FwdIt>>::max)())) {
// if the number of _Vals searched for is larger than the longest possible sequence, we can't find it
return _Last;
}
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
if constexpr (_Is_ranges_random_iter_v<_FwdIt>) {
const auto _Count_diff = static_cast<_Iter_diff_t<_FwdIt>>(_Count);
auto _UOld_first = _UFirst;
for (_Iter_diff_t<_FwdIt> _Inc = 0; _Count_diff <= _ULast - _UOld_first;) { // enough room, look for a match
_UFirst = _UOld_first + _Inc;
if (_Pred(*_UFirst, _Val)) { // found part of possible match, check it out
_Iter_diff_t<_FwdIt> _Count1 = _Count_diff;
auto _UMid = _UFirst;
while (_UOld_first != _UFirst && _Pred(*_Prev_iter(_UFirst), _Val)) { // back up over any skipped prefix
--_Count1;
--_UFirst;
}
if (_Count1 <= _ULast - _UMid) {
for (;;) { // enough left, test suffix
if (--_Count1 == 0) {
_Seek_wrapped(_Last, _UFirst); // found rest of match, report it
return _Last;
} else if (!_Pred(*++_UMid, _Val)) { // short match not at end
break;
}
}
}
_UOld_first = ++_UMid; // failed match, take small jump
_Inc = 0;
} else { // no match, take big jump and back up as needed
_UOld_first = _Next_iter(_UFirst);
_Inc = _Count_diff - 1;
}
}
} else {
for (; _UFirst != _ULast; ++_UFirst) {
if (_Pred(*_UFirst, _Val)) { // found start of possible match, check it out
auto _UMid = _UFirst;
for (_Algorithm_int_t<_Diff> _Count1 = _Count;;) {
if (--_Count1 == 0) {
_Seek_wrapped(_Last, _UFirst); // found rest of match, report it
return _Last;
} else if (++_UMid == _ULast) {
return _Last; // short match at end
} else if (!_Pred(*_UMid, _Val)) { // short match not at end
break;
}
}
_UFirst = _UMid; // pick up just beyond failed match
}
}
}
return _Last;
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Diff, class _Ty, class _Pr,
_Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdIt search_n(_ExPo&& _Exec, _FwdIt _First, _FwdIt _Last, _Diff _Count_raw, const _Ty& _Val,
_Pr _Pred) noexcept; // terminates
#endif // _HAS_CXX17
_EXPORT_STD template <class _FwdIt, class _Diff, class _Ty>
_NODISCARD _CONSTEXPR20 _FwdIt search_n(const _FwdIt _First, const _FwdIt _Last, const _Diff _Count, const _Ty& _Val) {
// find first _Count * _Val match
return _STD search_n(_First, _Last, _Count, _Val, equal_to<>{});
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt, class _Diff, class _Ty, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdIt search_n(_ExPo&& _Exec, const _FwdIt _First, const _FwdIt _Last, const _Diff _Count,
const _Ty& _Val) noexcept /* terminates */ { // find first _Count * _Val match
return _STD search_n(_STD forward<_ExPo>(_Exec), _First, _Last, _Count, _Val, equal_to{});
}
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
class _Search_n_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <forward_iterator _It, sentinel_for<_It> _Se, class _Ty, class _Pr = ranges::equal_to,
class _Pj = identity>
requires indirectly_comparable<_It, const _Ty*, _Pr, _Pj>
_NODISCARD constexpr subrange<_It> operator()(_It _First, _Se _Last, const iter_difference_t<_It> _Count,
const _Ty& _Val, _Pr _Pred = {}, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
if (_Count <= 0) {
return {_First, _First};
}
auto _UFirst = _Unwrap_iter<_Se>(_STD move(_First));
auto _ULast = _Unwrap_sent<_It>(_STD move(_Last));
if constexpr (sized_sentinel_for<_Se, _It>) {
const auto _Dist = _ULast - _UFirst;
auto _UResult =
_Search_n_sized(_STD move(_UFirst), _Dist, _Val, _Count, _Pass_fn(_Pred), _Pass_fn(_Proj));
return _Rewrap_subrange<subrange<_It>>(_First, _STD move(_UResult));
} else {
auto _UResult = _Search_n_unsized(
_STD move(_UFirst), _STD move(_ULast), _Val, _Count, _Pass_fn(_Pred), _Pass_fn(_Proj));
return _Rewrap_subrange<subrange<_It>>(_First, _STD move(_UResult));
}
}
template <forward_range _Rng, class _Ty, class _Pr = ranges::equal_to, class _Pj = identity>
requires indirectly_comparable<iterator_t<_Rng>, const _Ty*, _Pr, _Pj>
_NODISCARD constexpr borrowed_subrange_t<_Rng> operator()(_Rng&& _Range, const range_difference_t<_Rng> _Count,
const _Ty& _Val, _Pr _Pred = {}, _Pj _Proj = {}) const {
auto _First = _RANGES begin(_Range);
if (_Count <= 0) {
return {_First, _First};
}
if constexpr (sized_range<_Rng>) {
const auto _Dist = _RANGES distance(_Range);
auto _UResult =
_Search_n_sized(_Get_unwrapped(_First), _Dist, _Val, _Count, _Pass_fn(_Pred), _Pass_fn(_Proj));
return _Rewrap_subrange<borrowed_subrange_t<_Rng>>(_First, _STD move(_UResult));
} else {
auto _UResult = _Search_n_unsized(
_Unwrap_range_iter<_Rng>(_First), _Uend(_Range), _Val, _Count, _Pass_fn(_Pred), _Pass_fn(_Proj));
return _Rewrap_subrange<borrowed_subrange_t<_Rng>>(_First, _STD move(_UResult));
}
}
private:
template <class _It, class _Ty, class _Pr, class _Pj>
_NODISCARD static constexpr subrange<_It> _Search_n_sized(_It _First, iter_difference_t<_It> _Dist,
const _Ty& _Val, const iter_difference_t<_It> _Count, _Pr _Pred, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_comparable<_It, const _Ty*, _Pr, _Pj>);
_STL_INTERNAL_CHECK(_Count > 0);
// pre: _First + [0, _Dist) is a valid counted range
if constexpr (bidirectional_iterator<_It>) {
if (_Dist < _Count) {
_RANGES advance(_First, _Dist);
return {_First, _First};
}
auto _Last = _RANGES next(_First, _Count);
auto _Mid1 = _First;
auto _Mid2 = _Last;
for (;;) {
// Invariants: _Last - _First == _Count, [_First, _Mid1) and [_Mid2, _Last) match _Val:
//
// _First _Mid1 _Mid2 _Last
// |=======|????????|========|??????...
--_Mid2;
if (!_STD invoke(_Pred, _STD invoke(_Proj, *_Mid2), _Val)) { // mismatch; skip past it
++_Mid2;
const auto _Delta = _RANGES distance(_First, _Mid2);
if (_Dist - _Delta < _Count) { // not enough space left
_First = _STD move(_Last);
_Dist -= _Count;
break;
}
_First = _STD move(_Mid2);
_Dist -= _Delta;
_Mid1 = _Last;
_RANGES advance(_Last, _Delta);
_Mid2 = _Last;
continue;
}
if (_Mid2 == _Mid1) { // [_Mid1, _Mid2) is empty, so [_First, _Last) all match
return {_STD move(_First), _STD move(_Last)};
}
}
} else {
for (; _Dist >= _Count; ++_First, (void) --_Dist) {
if (_STD invoke(_Pred, _STD invoke(_Proj, *_First), _Val)) {
auto _Saved = _First;
for (iter_difference_t<_It> _Len = 0;;) {
++_First;
if (++_Len == _Count) { // match
return {_STD move(_Saved), _STD move(_First)};
}
if (!_STD invoke(_Pred, _STD invoke(_Proj, *_First), _Val)) { // mismatch
_Dist -= _Len;
break;
}
}
}
}
}
_RANGES advance(_First, _Dist);
return {_First, _First};
}
template <class _It, class _Se, class _Ty, class _Pr, class _Pj>
_NODISCARD static constexpr subrange<_It> _Search_n_unsized(
_It _First, const _Se _Last, const _Ty& _Val, const iter_difference_t<_It> _Count, _Pr _Pred, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_comparable<_It, const _Ty*, _Pr, _Pj>);
_STL_INTERNAL_CHECK(_Count > 0);
for (; _First != _Last; ++_First) {
if (_STD invoke(_Pred, _STD invoke(_Proj, *_First), _Val)) {
auto _Saved = _First;
for (auto _Len = _Count;;) {
++_First;
if (--_Len == 0) { // match
return {_STD move(_Saved), _STD move(_First)};
}
if (_First == _Last) { // no more to match against
return {_First, _First};
}
if (!_STD invoke(_Pred, _STD invoke(_Proj, *_First), _Val)) { // mismatch
break;
}
}
}
}
return {_First, _First};
}
};
_EXPORT_STD inline constexpr _Search_n_fn search_n{_Not_quite_object::_Construct_tag{}};
#if _HAS_CXX23
class _Starts_with_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It1, sentinel_for<_It1> _Se1, input_iterator _It2, sentinel_for<_It2> _Se2,
class _Pr = ranges::equal_to, class _Pj1 = identity, class _Pj2 = identity>
requires indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr bool operator()(_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2, _Pr _Pred = {},
_Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);
auto _UFirst1 = _Unwrap_iter<_Se1>(_STD move(_First1));
auto _ULast1 = _Unwrap_sent<_It1>(_STD move(_Last1));
auto _UFirst2 = _Unwrap_iter<_Se2>(_STD move(_First2));
const auto _ULast2 = _Unwrap_sent<_It2>(_STD move(_Last2));
if constexpr (_Sized_or_unreachable_sentinel_for<_Se1, _It1> && sized_sentinel_for<_Se2, _It2>) {
const iter_difference_t<_It2> _Count2 = _ULast2 - _UFirst2;
if constexpr (sized_sentinel_for<_Se1, _It1>) {
if (_Count2 > _ULast1 - _UFirst1) {
return false;
}
}
return _RANGES _Equal_count(_STD move(_UFirst1), _STD move(_UFirst2),
static_cast<iter_difference_t<_It1>>(_Count2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
} else {
const auto _Result = _RANGES _Mismatch_4(_STD move(_UFirst1), _STD move(_ULast1), _STD move(_UFirst2),
_ULast2, _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Result.in2 == _ULast2;
}
}
template <input_range _Rng1, input_range _Rng2, class _Pr = ranges::equal_to, class _Pj1 = identity,
class _Pj2 = identity>
requires indirectly_comparable<iterator_t<_Rng1>, iterator_t<_Rng2>, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr bool operator()(
_Rng1&& _Range1, _Rng2&& _Range2, _Pr _Pred = {}, _Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
if constexpr (_Sized_or_infinite_range<_Rng1> && sized_range<_Rng2>) {
const range_difference_t<_Rng2> _Count2 = _RANGES distance(_Range2);
if constexpr (sized_range<_Rng1>) {
if (_Count2 > _RANGES distance(_Range1)) {
return false;
}
}
return _RANGES _Equal_count(_Ubegin(_Range1), _Ubegin(_Range2),
static_cast<range_difference_t<_Rng1>>(_Count2), _Pass_fn(_Pred), _Pass_fn(_Proj1),
_Pass_fn(_Proj2));
} else {
const auto _ULast2 = _Uend(_Range2);
const auto _Result = _RANGES _Mismatch_4(_Ubegin(_Range1), _Uend(_Range1), _Ubegin(_Range2), _ULast2,
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Result.in2 == _ULast2;
}
}
};
_EXPORT_STD inline constexpr _Starts_with_fn starts_with{_Not_quite_object::_Construct_tag{}};
class _Ends_with_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It1, sentinel_for<_It1> _Se1, input_iterator _It2, sentinel_for<_It2> _Se2,
class _Pr = ranges::equal_to, class _Pj1 = identity, class _Pj2 = identity>
requires (forward_iterator<_It1> || sized_sentinel_for<_Se1, _It1>)
&& (forward_iterator<_It2> || sized_sentinel_for<_Se2, _It2>)
&& indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr bool operator()(_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2, _Pr _Pred = {},
_Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);
auto _UFirst1 = _Unwrap_iter<_Se1>(_STD move(_First1));
auto _ULast1 = _Unwrap_sent<_It1>(_STD move(_Last1));
auto _UFirst2 = _Unwrap_iter<_Se2>(_STD move(_First2));
auto _ULast2 = _Unwrap_sent<_It2>(_STD move(_Last2));
const auto _Count1 = _Distance_helper(_UFirst1, _ULast1);
const auto _Count2 = _Distance_helper(_UFirst2, _ULast2);
return _Ends_with_impl(_STD move(_UFirst1), _STD move(_ULast1), _Count1, _STD move(_UFirst2),
_STD move(_ULast2), _Count2, _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
}
template <input_range _Rng1, input_range _Rng2, class _Pr = ranges::equal_to, class _Pj1 = identity,
class _Pj2 = identity>
requires (forward_range<_Rng1> || sized_range<_Rng1>) && (forward_range<_Rng2> || sized_range<_Rng2>)
&& indirectly_comparable<iterator_t<_Rng1>, iterator_t<_Rng2>, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr bool operator()(
_Rng1&& _Range1, _Rng2&& _Range2, _Pr _Pred = {}, _Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
const auto _Count1 = _Distance_helper(_Range1);
const auto _Count2 = _Distance_helper(_Range2);
return _Ends_with_impl(_Ubegin(_Range1), _Uend(_Range1), _Count1, _Ubegin(_Range2), _Uend(_Range2), _Count2,
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
}
private:
struct _Not_a_difference {};
template <class _It, class _Se>
_NODISCARD static constexpr auto _Distance_helper(const _It& _First, const _Se& _Last) {
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
if constexpr (sized_sentinel_for<_Se, _It>) {
return _Last - _First;
} else {
return _Not_a_difference{};
}
}
template <class _Rng>
_NODISCARD static constexpr auto _Distance_helper(_Rng&& _Range) {
_STL_INTERNAL_STATIC_ASSERT(range<_Rng>);
if constexpr (sized_range<_Rng>) {
return _RANGES distance(_Range);
} else {
return _Not_a_difference{};
}
}
template <class _Ty, class _It1, class _It2, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr bool _Match_backwards(
const _Ty _First1, _It1 _Last1, const _It2 _First2, _It2 _Last2, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_STATIC_ASSERT(same_as<_Ty, _It1> || same_as<_Ty, unreachable_sentinel_t>);
_STL_INTERNAL_STATIC_ASSERT(bidirectional_iterator<_It1>);
_STL_INTERNAL_STATIC_ASSERT(bidirectional_iterator<_It2>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>);
for (;;) {
if (_First2 == _Last2) { // needle exhausted - match
return true;
}
if (_First1 == _Last1) { // haystack exhausted - no match
return false;
}
--_Last1;
--_Last2;
if (!_STD invoke(_Pred, _STD invoke(_Proj1, *_Last1), _STD invoke(_Proj2, *_Last2))) {
return false; // non-equal elements - no match
}
}
}
template <class _It1, class _Se1, class _Diff1, class _It2, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr bool _Ends_with_sized_needle(_It1 _First1, _Se1 _Last1, _Diff1 _Count1,
_It2 _First2, iter_difference_t<_It2> _Count2, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It1> && sentinel_for<_Se1, _It1>);
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It1> || same_as<_Diff1, iter_difference_t<_It1>>);
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It2>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>);
constexpr bool _Sized1 = !same_as<_Diff1, _Not_a_difference>;
if constexpr (random_access_iterator<_It1> && _Sized1) {
_First1 += static_cast<iter_difference_t<_It1>>(_Count1 - _Count2);
} else if constexpr (_Bidi_common<_It1, _Se1>) {
if constexpr (_Sized1) {
if ((_Count1 >> 1) >= _Count2) { // beginning of potential match is closer to _Last1
_RANGES advance(_Last1, static_cast<iter_difference_t<_It1>>(-_Count2));
_First1 = _STD move(_Last1);
} else { // beginning of potential match is closer to _First1
_RANGES advance(_First1, static_cast<iter_difference_t<_It1>>(_Count1 - _Count2));
}
} else { // Only second range is sized
if (_RANGES advance(_Last1, static_cast<iter_difference_t<_It1>>(-_Count2), _First1) != 0) {
// distance(_First1, _Last1) < _Count2
return false;
}
_First1 = _STD move(_Last1);
}
} else if constexpr (forward_iterator<_It1>) {
auto _Mid1 = _First1;
auto _Count = _Count2;
do {
if (_Mid1 == _Last1) { // distance(_First1, _Last1) < _Count2
return false;
}
++_Mid1;
} while (--_Count != 0);
// At this point, distance(_First1, _Mid1) == _Count2
while (_Mid1 != _Last1) {
++_First1;
++_Mid1;
}
} else {
_RANGES advance(_First1, static_cast<iter_difference_t<_It1>>(_Count1 - _Count2));
}
return _RANGES _Equal_count(_STD move(_First1), _STD move(_First2),
static_cast<iter_difference_t<_It1>>(_Count2), _Pred, _Proj1, _Proj2);
}
template <class _It1, class _Se1, class _Diff1, class _It2, class _Se2, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr bool _Ends_with_unsized_needle(
_It1 _First1, _Se1 _Last1, _Diff1 _Count1, _It2 _First2, _Se2 _Last2, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It1> && sentinel_for<_Se1, _It1>);
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It1> || same_as<_Diff1, iter_difference_t<_It1>>);
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It2> && sentinel_for<_Se2, _It2>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>);
constexpr bool _Sized1 = !same_as<_Diff1, _Not_a_difference>;
iter_difference_t<_It2> _Count2 = 0;
if constexpr (_Sized1) {
for (auto _Mid2 = _First2; _Mid2 != _Last2; ++_Mid2, (void) ++_Count2) {
if (_Count2 == _Count1) { // distance(_First1, _Last1) < distance(_First2, _Last2)
return false;
}
}
_RANGES advance(_First1, static_cast<iter_difference_t<_It1>>(_Count1 - _Count2));
} else { // first range isn't sized, so must be forward
auto _Mid1 = _First1;
for (auto _Mid2 = _First2; _Mid2 != _Last2; ++_Mid1, (void) ++_Mid2, ++_Count2) {
if (_Mid1 == _Last1) { // distance(_First1, _Last1) < distance(_First2, _Last2)
return false;
}
}
// distance(_First1, _Mid1) == distance(_First2, _Last2) == _Count2
while (_Mid1 != _Last1) {
++_First1;
++_Mid1;
}
}
return _RANGES _Equal_count(_STD move(_First1), _STD move(_First2),
static_cast<iter_difference_t<_It1>>(_Count2), _Pred, _Proj1, _Proj2);
}
template <class _It1, class _Se1, class _Diff1, class _It2, class _Se2, class _Diff2, class _Pr, class _Pj1,
class _Pj2>
_NODISCARD static constexpr bool _Ends_with_impl(_It1 _First1, _Se1 _Last1, _Diff1 _Count1, _It2 _First2,
_Se2 _Last2, _Diff2 _Count2, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se1, _It1>);
_STL_INTERNAL_STATIC_ASSERT(_Is_any_of_v<_Diff1, iter_difference_t<_It1>, _Not_a_difference>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se2, _It2>);
_STL_INTERNAL_STATIC_ASSERT(_Is_any_of_v<_Diff2, iter_difference_t<_It2>, _Not_a_difference>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>);
constexpr bool _Sized1 = !same_as<_Diff1, _Not_a_difference>;
constexpr bool _Sized2 = !same_as<_Diff2, _Not_a_difference>;
constexpr bool _Both_sized = _Sized1 && _Sized2;
constexpr bool _Both_bidi_common = _Bidi_common<_It1, _Se1> && _Bidi_common<_It2, _Se2>;
if constexpr (_Both_sized) {
if (_Count2 > _Count1) {
return false;
}
}
if constexpr (_Sized2) {
if (_Count2 == 0) {
return true;
}
}
if constexpr (_Both_bidi_common && !(random_access_iterator<_It1> && _Both_sized)) {
if constexpr (_Both_sized) {
return _Match_backwards(unreachable_sentinel, _STD move(_Last1), _STD move(_First2),
_STD move(_Last2), _Pred, _Proj1, _Proj2);
} else {
return _Match_backwards(_STD move(_First1), _STD move(_Last1), _STD move(_First2),
_STD move(_Last2), _Pred, _Proj1, _Proj2);
}
} else if constexpr (_Sized2) {
return _Ends_with_sized_needle(
_STD move(_First1), _STD move(_Last1), _Count1, _STD move(_First2), _Count2, _Pred, _Proj1, _Proj2);
} else {
return _Ends_with_unsized_needle(_STD move(_First1), _STD move(_Last1), _Count1, _STD move(_First2),
_STD move(_Last2), _Pred, _Proj1, _Proj2);
}
}
};
_EXPORT_STD inline constexpr _Ends_with_fn ends_with{_Not_quite_object::_Construct_tag{}};
template <class _Fn>
class _Flipped {
private:
_Fn _Func;
public:
template <class _Ty, class _Uty>
requires invocable<_Fn&, _Uty, _Ty>
invoke_result_t<_Fn&, _Uty, _Ty> operator()(_Ty&&, _Uty&&);
};
template <class _Fn, class _Ty, class _It, class _Uty>
concept _Indirectly_binary_left_foldable_impl =
movable<_Ty> && movable<_Uty> && convertible_to<_Ty, _Uty> && invocable<_Fn&, _Uty, iter_reference_t<_It>>
&& assignable_from<_Uty&, invoke_result_t<_Fn&, _Uty, iter_reference_t<_It>>>;
template <class _Fn, class _Ty, class _It>
concept _Indirectly_binary_left_foldable =
copy_constructible<_Fn> && indirectly_readable<_It> && invocable<_Fn&, _Ty, iter_reference_t<_It>>
&& convertible_to<invoke_result_t<_Fn&, _Ty, iter_reference_t<_It>>,
decay_t<invoke_result_t<_Fn&, _Ty, iter_reference_t<_It>>>>
&& _Indirectly_binary_left_foldable_impl<_Fn, _Ty, _It,
decay_t<invoke_result_t<_Fn&, _Ty, iter_reference_t<_It>>>>;
template <class _Fn, class _Ty, class _It>
concept _Indirectly_binary_right_foldable = _Indirectly_binary_left_foldable<_Flipped<_Fn>, _Ty, _It>;
_EXPORT_STD template <class _It, class _Ty>
using fold_left_with_iter_result = in_value_result<_It, _Ty>;
_EXPORT_STD template <class _It, class _Ty>
using fold_left_first_with_iter_result = in_value_result<_It, _Ty>;
class _Fold_left_with_iter_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, class _Ty, _Indirectly_binary_left_foldable<_Ty, _It> _Fn>
_NODISCARD constexpr auto operator()(_It _First, _Se _Last, _Ty _Init, _Fn _Func) const {
_Adl_verify_range(_First, _Last);
return _Fold_left_with_iter_impl<_It>(
_STD move(_First), _STD move(_Last), _STD move(_Init), _Pass_fn(_Func));
}
template <input_range _Rng, class _Ty, _Indirectly_binary_left_foldable<_Ty, iterator_t<_Rng>> _Fn>
_NODISCARD constexpr auto operator()(_Rng&& _Range, _Ty _Init, _Fn _Func) const {
return _Fold_left_with_iter_impl<borrowed_iterator_t<_Rng>>(
_RANGES begin(_Range), _RANGES end(_Range), _STD move(_Init), _Pass_fn(_Func));
}
private:
template <class _RetIt, class _It, class _Se, class _Ty, class _Fn>
_NODISCARD constexpr auto _Fold_left_with_iter_impl(_It&& _First, _Se&& _Last, _Ty&& _Init, _Fn _Func) const {
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(_Indirectly_binary_left_foldable<_Fn, _Ty, _It>);
using _Uty = decay_t<invoke_result_t<_Fn&, _Ty, iter_reference_t<_It>>>;
using _Return_type = fold_left_with_iter_result<_RetIt, _Uty>;
if (_First == _Last) {
return _Return_type{_STD move(_First), static_cast<_Uty>(_STD move(_Init))};
} else {
auto _UFirst = _Unwrap_iter<_Se>(_STD move(_First));
auto _ULast = _Unwrap_sent<_It>(_STD move(_Last));
_Uty _Accum = _STD invoke(_Func, _STD move(_Init), *_UFirst);
for (++_UFirst; _UFirst != _ULast; ++_UFirst) {
_Accum = _STD invoke(_Func, _STD move(_Accum), *_UFirst);
}
_Seek_wrapped(_First, _STD move(_UFirst));
return _Return_type{_STD move(_First), _STD move(_Accum)};
}
}
};
_EXPORT_STD inline constexpr _Fold_left_with_iter_fn fold_left_with_iter{_Not_quite_object::_Construct_tag{}};
class _Fold_left_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se, class _Ty, _Indirectly_binary_left_foldable<_Ty, _It> _Fn>
_NODISCARD constexpr auto operator()(_It _First, _Se _Last, _Ty _Init, _Fn _Func) const {
return _RANGES fold_left_with_iter(_STD move(_First), _Last, _STD move(_Init), _Pass_fn(_Func)).value;
}
template <input_range _Rng, class _Ty, _Indirectly_binary_left_foldable<_Ty, iterator_t<_Rng>> _Fn>
_NODISCARD constexpr auto operator()(_Rng&& _Range, _Ty _Init, _Fn _Func) const {
return _RANGES fold_left_with_iter(_STD forward<_Rng>(_Range), _STD move(_Init), _Pass_fn(_Func)).value;
}
};
_EXPORT_STD inline constexpr _Fold_left_fn fold_left{_Not_quite_object::_Construct_tag{}};
class _Fold_left_first_with_iter_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se,
_Indirectly_binary_left_foldable<iter_value_t<_It>, _It> _Fn>
requires constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
_NODISCARD constexpr auto operator()(_It _First, _Se _Last, _Fn _Func) const {
_Adl_verify_range(_First, _Last);
return _Fold_left_first_with_iter_impl<_It>(_STD move(_First), _STD move(_Last), _Pass_fn(_Func));
}
template <input_range _Rng, _Indirectly_binary_left_foldable<range_value_t<_Rng>, iterator_t<_Rng>> _Fn>
requires constructible_from<range_value_t<_Rng>, range_reference_t<_Rng>>
_NODISCARD constexpr auto operator()(_Rng&& _Range, _Fn _Func) const {
return _Fold_left_first_with_iter_impl<borrowed_iterator_t<_Rng>>(
_RANGES begin(_Range), _RANGES end(_Range), _Pass_fn(_Func));
}
private:
template <class _RetIt, class _It, class _Se, class _Fn>
_NODISCARD constexpr auto _Fold_left_first_with_iter_impl(_It&& _First, _Se&& _Last, _Fn _Func) const {
_STL_INTERNAL_STATIC_ASSERT(input_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(_Indirectly_binary_left_foldable<_Fn, iter_value_t<_It>, _It>);
_STL_INTERNAL_STATIC_ASSERT(constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
using _Uty =
decltype(_RANGES fold_left(_STD move(_First), _Last, static_cast<iter_value_t<_It>>(*_First), _Func));
using _Return_type = fold_left_first_with_iter_result<_RetIt, optional<_Uty>>;
if (_First == _Last) {
return _Return_type{_STD move(_First), optional<_Uty>{}};
} else {
auto _UFirst = _Unwrap_iter<_Se>(_STD move(_First));
auto _ULast = _Unwrap_sent<_It>(_STD move(_Last));
optional<_Uty> _Init{in_place, *_UFirst};
_Uty& _Init_ref = *_Init;
for (++_UFirst; _UFirst != _ULast; ++_UFirst) {
_Init_ref = _STD invoke(_Func, _STD move(_Init_ref), *_UFirst);
}
_Seek_wrapped(_First, _STD move(_UFirst));
return _Return_type{_STD move(_First), _STD move(_Init)};
}
}
};
_EXPORT_STD inline constexpr _Fold_left_first_with_iter_fn fold_left_first_with_iter{
_Not_quite_object::_Construct_tag{}};
class _Fold_left_first_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It, sentinel_for<_It> _Se,
_Indirectly_binary_left_foldable<iter_value_t<_It>, _It> _Fn>
requires constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
_NODISCARD constexpr auto operator()(_It _First, _Se _Last, _Fn _Func) const {
return _RANGES fold_left_first_with_iter(_STD move(_First), _STD move(_Last), _Pass_fn(_Func)).value;
}
template <input_range _Rng, _Indirectly_binary_left_foldable<range_value_t<_Rng>, iterator_t<_Rng>> _Fn>
requires constructible_from<range_value_t<_Rng>, range_reference_t<_Rng>>
_NODISCARD constexpr auto operator()(_Rng&& _Range, _Fn _Func) const {
return _RANGES fold_left_first_with_iter(_STD forward<_Rng>(_Range), _Pass_fn(_Func)).value;
}
};
_EXPORT_STD inline constexpr _Fold_left_first_fn fold_left_first{_Not_quite_object::_Construct_tag{}};
template <class _It, class _Se, class _Ty, class _Fn>
_NODISCARD constexpr auto _Fold_right_unchecked(_It _First, _Se _Last, _Ty _Init, _Fn _Func) {
_STL_INTERNAL_STATIC_ASSERT(bidirectional_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(_Indirectly_binary_right_foldable<_Fn, _Ty, _It>);
using _Uty = decay_t<invoke_result_t<_Fn&, iter_reference_t<_It>, _Ty>>;
if (_First == _Last) {
return static_cast<_Uty>(_STD move(_Init));
} else {
_It _Tail = _RANGES next(_First, _Last);
_Uty _Accum = _STD invoke(_Func, *--_Tail, _STD move(_Init));
while (_First != _Tail) {
_Accum = _STD invoke(_Func, *--_Tail, _STD move(_Accum));
}
return _Accum;
}
}
class _Fold_right_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <bidirectional_iterator _It, sentinel_for<_It> _Se, class _Ty,
_Indirectly_binary_right_foldable<_Ty, _It> _Fn>
_NODISCARD constexpr auto operator()(_It _First, _Se _Last, _Ty _Init, _Fn _Func) const {
_Adl_verify_range(_First, _Last);
return _RANGES _Fold_right_unchecked(_Unwrap_iter<_Se>(_STD move(_First)),
_Unwrap_sent<_It>(_STD move(_Last)), _STD move(_Init), _Pass_fn(_Func));
}
template <bidirectional_range _Rng, class _Ty, _Indirectly_binary_right_foldable<_Ty, iterator_t<_Rng>> _Fn>
_NODISCARD constexpr auto operator()(_Rng&& _Range, _Ty _Init, _Fn _Func) const {
return _RANGES _Fold_right_unchecked(_Ubegin(_Range), _Uend(_Range), _STD move(_Init), _Pass_fn(_Func));
}
};
_EXPORT_STD inline constexpr _Fold_right_fn fold_right{_Not_quite_object::_Construct_tag{}};
class _Fold_right_last_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <bidirectional_iterator _It, sentinel_for<_It> _Se,
_Indirectly_binary_right_foldable<iter_value_t<_It>, _It> _Fn>
requires constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
_NODISCARD constexpr auto operator()(_It _First, _Se _Last, _Fn _Func) const {
_Adl_verify_range(_First, _Last);
return _Fold_right_last_unchecked(
_Unwrap_iter<_Se>(_STD move(_First)), _Unwrap_sent<_It>(_STD move(_Last)), _Pass_fn(_Func));
}
template <bidirectional_range _Rng,
_Indirectly_binary_right_foldable<range_value_t<_Rng>, iterator_t<_Rng>> _Fn>
requires constructible_from<range_value_t<_Rng>, range_reference_t<_Rng>>
_NODISCARD constexpr auto operator()(_Rng&& _Range, _Fn _Func) const {
return _Fold_right_last_unchecked(_Ubegin(_Range), _Uend(_Range), _Pass_fn(_Func));
}
private:
template <class _It, class _Se, class _Fn>
_NODISCARD constexpr auto _Fold_right_last_unchecked(_It _First, _Se _Last, _Fn _Func) const {
_STL_INTERNAL_STATIC_ASSERT(bidirectional_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(_Indirectly_binary_right_foldable<_Fn, iter_value_t<_It>, _It>);
_STL_INTERNAL_STATIC_ASSERT(constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
using _Uty = decltype(_RANGES fold_right(_First, _Last, static_cast<iter_value_t<_It>>(*_First), _Func));
if (_First == _Last) {
return optional<_Uty>{};
} else {
_It _Tail = _RANGES prev(_RANGES next(_First, _STD move(_Last)));
return optional<_Uty>{in_place, _RANGES _Fold_right_unchecked(_STD move(_First), _Tail,
static_cast<iter_value_t<_It>>(*_Tail), _STD move(_Func))};
}
}
};
_EXPORT_STD inline constexpr _Fold_right_last_fn fold_right_last{_Not_quite_object::_Construct_tag{}};
class _Find_last_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <forward_iterator _It, sentinel_for<_It> _Se, class _Ty, class _Pj = identity>
requires indirect_binary_predicate<ranges::equal_to, projected<_It, _Pj>, const _Ty*>
_NODISCARD constexpr subrange<_It> operator()(_It _First, _Se _Last, const _Ty& _Value, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
auto _UFirst = _Unwrap_iter<_Se>(_STD move(_First));
if constexpr (bidirectional_iterator<_It>) {
auto _ULast = _Get_final_iterator_unwrapped<_It>(_UFirst, _STD move(_Last));
auto _UResult = _Find_last_unchecked(_STD move(_UFirst), _STD move(_ULast), _Value, _Pass_fn(_Proj));
return _Rewrap_subrange<subrange<_It>>(_First, _STD move(_UResult));
} else {
auto _ULast = _Unwrap_sent<_It>(_STD move(_Last));
auto _UResult = _Find_last_unchecked(_STD move(_UFirst), _STD move(_ULast), _Value, _Pass_fn(_Proj));
return _Rewrap_subrange<subrange<_It>>(_First, _STD move(_UResult));
}
}
template <forward_range _Rng, class _Ty, class _Pj = identity>
requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Rng>, _Pj>, const _Ty*>
_NODISCARD constexpr borrowed_subrange_t<_Rng> operator()(
_Rng&& _Range, const _Ty& _Value, _Pj _Proj = {}) const {
if constexpr (bidirectional_range<_Rng>) {
auto _UResult = _Find_last_unchecked(
_Ubegin(_Range), _Get_final_iterator_unwrapped(_Range), _Value, _Pass_fn(_Proj));
return _Rewrap_subrange<borrowed_subrange_t<_Rng>>(_Range, _STD move(_UResult));
} else {
auto _UResult = _Find_last_unchecked(_Ubegin(_Range), _Uend(_Range), _Value, _Pass_fn(_Proj));
return _Rewrap_subrange<borrowed_subrange_t<_Rng>>(_Range, _STD move(_UResult));
}
}
private:
template <class _It, class _Se, class _Ty, class _Pj>
_NODISCARD static constexpr subrange<_It> _Find_last_unchecked(
_It _First, _Se _Last, const _Ty& _Value, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirect_binary_predicate<ranges::equal_to, projected<_It, _Pj>, const _Ty*>);
if constexpr (_Bidi_common<_It, _Se>) {
for (auto _Result = _Last; _Result != _First;) {
if (_STD invoke(_Proj, *--_Result) == _Value) {
return {_STD move(_Result), _STD move(_Last)};
}
}
return {_Last, _Last};
} else if constexpr (same_as<_It, _Se>) {
auto _Result = _Last;
for (; _First != _Last; ++_First) {
if (_STD invoke(_Proj, *_First) == _Value) {
_Result = _First;
}
}
return {_STD move(_Result), _STD move(_Last)};
} else {
auto _Result = _First;
bool _Found = false;
for (;; ++_First) {
if (_First == _Last) {
if (!_Found) {
_Result = _First;
}
break;
}
if (_STD invoke(_Proj, *_First) == _Value) {
_Result = _First;
_Found = true;
}
}
return {_STD move(_Result), _STD move(_First)};
}
}
};
_EXPORT_STD inline constexpr _Find_last_fn find_last{_Not_quite_object::_Construct_tag{}};
template <bool _Search_for>
class _Find_last_if_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <forward_iterator _It, sentinel_for<_It> _Se, class _Pj = identity,
indirect_unary_predicate<projected<_It, _Pj>> _Pr>
_NODISCARD constexpr subrange<_It> operator()(_It _First, _Se _Last, _Pr _Pred, _Pj _Proj = {}) const {
_Adl_verify_range(_First, _Last);
auto _UFirst = _Unwrap_iter<_Se>(_STD move(_First));
if constexpr (bidirectional_iterator<_It>) {
auto _ULast = _Get_final_iterator_unwrapped<_It>(_UFirst, _STD move(_Last));
auto _UResult =
_Find_last_if_unchecked(_STD move(_UFirst), _STD move(_ULast), _Pass_fn(_Pred), _Pass_fn(_Proj));
return _Rewrap_subrange<subrange<_It>>(_First, _STD move(_UResult));
} else {
auto _ULast = _Unwrap_sent<_It>(_STD move(_Last));
auto _UResult =
_Find_last_if_unchecked(_STD move(_UFirst), _STD move(_ULast), _Pass_fn(_Pred), _Pass_fn(_Proj));
return _Rewrap_subrange<subrange<_It>>(_First, _STD move(_UResult));
}
}
template <forward_range _Rng, class _Pj = identity,
indirect_unary_predicate<projected<iterator_t<_Rng>, _Pj>> _Pr>
_NODISCARD constexpr borrowed_subrange_t<_Rng> operator()(_Rng&& _Range, _Pr _Pred, _Pj _Proj = {}) const {
if constexpr (bidirectional_range<_Rng>) {
auto _UResult = _Find_last_if_unchecked(
_Ubegin(_Range), _Get_final_iterator_unwrapped(_Range), _Pass_fn(_Pred), _Pass_fn(_Proj));
return _Rewrap_subrange<borrowed_subrange_t<_Rng>>(_Range, _STD move(_UResult));
} else {
auto _UResult =
_Find_last_if_unchecked(_Ubegin(_Range), _Uend(_Range), _Pass_fn(_Pred), _Pass_fn(_Proj));
return _Rewrap_subrange<borrowed_subrange_t<_Rng>>(_Range, _STD move(_UResult));
}
}
private:
template <class _It, class _Se, class _Pj, class _Pr>
_NODISCARD static constexpr subrange<_It> _Find_last_if_unchecked(_It _First, _Se _Last, _Pr _Pred, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se, _It>);
_STL_INTERNAL_STATIC_ASSERT(indirect_unary_predicate<_Pr, projected<_It, _Pj>>);
if constexpr (_Bidi_common<_It, _Se>) {
for (auto _Result = _Last; _Result != _First;) {
if (_STD invoke_r<bool>(_Pred, _STD invoke(_Proj, *--_Result)) == _Search_for) {
return {_STD move(_Result), _STD move(_Last)};
}
}
return {_Last, _Last};
} else if constexpr (same_as<_It, _Se>) {
auto _Result = _Last;
for (; _First != _Last; ++_First) {
if (_STD invoke_r<bool>(_Pred, _STD invoke(_Proj, *_First)) == _Search_for) {
_Result = _First;
}
}
return {_STD move(_Result), _STD move(_Last)};
} else {
auto _Result = _First;
bool _Found = false;
for (;; ++_First) {
if (_First == _Last) {
if (!_Found) {
_Result = _First;
}
break;
}
if (_STD invoke_r<bool>(_Pred, _STD invoke(_Proj, *_First)) == _Search_for) {
_Result = _First;
_Found = true;
}
}
return {_STD move(_Result), _STD move(_First)};
}
}
};
_EXPORT_STD inline constexpr _Find_last_if_fn<true> find_last_if{_Not_quite_object::_Construct_tag{}};
_EXPORT_STD inline constexpr _Find_last_if_fn<false> find_last_if_not{_Not_quite_object::_Construct_tag{}};
#endif // _HAS_CXX23
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _FwdIt1, class _FwdIt2, class _Pr>
_NODISCARD _CONSTEXPR20 _FwdIt1 find_end(
_FwdIt1 _First1, const _FwdIt1 _Last1, const _FwdIt2 _First2, const _FwdIt2 _Last2, _Pr _Pred) {
// find last [_First2, _Last2) satisfying _Pred
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);
auto _UFirst1 = _Get_unwrapped(_First1);
const auto _ULast1 = _Get_unwrapped(_Last1);
const auto _UFirst2 = _Get_unwrapped(_First2);
const auto _ULast2 = _Get_unwrapped(_Last2);
if constexpr (_Is_ranges_random_iter_v<_FwdIt1> && _Is_ranges_random_iter_v<_FwdIt2>) {
const _Iter_diff_t<_FwdIt2> _Count2 = _ULast2 - _UFirst2;
if (_Count2 > 0 && _Count2 <= _ULast1 - _UFirst1) {
for (auto _UCandidate = _ULast1 - static_cast<_Iter_diff_t<_FwdIt1>>(_Count2);; --_UCandidate) {
if (_Equal_rev_pred_unchecked(_UCandidate, _UFirst2, _ULast2, _Pass_fn(_Pred))) {
_Seek_wrapped(_First1, _UCandidate);
return _First1;
}
if (_UCandidate == _UFirst1) {
break;
}
}
}
return _Last1;
} else if constexpr (_Is_ranges_bidi_iter_v<_FwdIt1> && _Is_ranges_bidi_iter_v<_FwdIt2>) {
for (auto _UCandidate = _ULast1;; --_UCandidate) { // try a match at _UCandidate
auto _UNext1 = _UCandidate;
auto _UNext2 = _ULast2;
for (;;) { // test if [_UFirst2, _ULast2) is a suffix of [_UFirst1, _UCandidate)
if (_UFirst2 == _UNext2) { // match found
_Seek_wrapped(_First1, _UNext1);
return _First1;
}
if (_UFirst1 == _UNext1) {
// [_UFirst1, _UCandidate) is shorter than [_UFirst2, _ULast2), remaining candidates nonviable
return _Last1;
}
--_UNext1;
--_UNext2;
if (!_Pred(*_UNext1, *_UNext2)) { // counterexample found
break;
}
}
}
} else {
auto _UResult = _ULast1;
for (;;) { // try a match at _UFirst1
auto _UNext1 = _UFirst1;
auto _UNext2 = _UFirst2;
for (;;) { // test if [_UFirst2, _ULast2) is a prefix of [_UFirst1, _ULast1)
const bool _End_of_needle = static_cast<bool>(_UNext2 == _ULast2);
if (_End_of_needle) { // match candidate found
_UResult = _UFirst1;
}
if (_UNext1 == _ULast1) {
// trying the next candidate would make [_UFirst1, _ULast1) shorter than [_UFirst2, _ULast2), done
_Seek_wrapped(_First1, _UResult);
return _First1;
}
if (_End_of_needle || !_Pred(*_UNext1, *_UNext2)) {
break; // end of match or counterexample found, go to the next candidate
}
++_UNext1;
++_UNext2;
}
++_UFirst1;
}
_Seek_wrapped(_First1, _UResult);
return _First1;
}
}
_EXPORT_STD template <class _FwdIt1, class _FwdIt2>
_NODISCARD _CONSTEXPR20 _FwdIt1 find_end(
_FwdIt1 const _First1, const _FwdIt1 _Last1, const _FwdIt2 _First2, const _FwdIt2 _Last2) {
// find last [_First2, _Last2) match
return _STD find_end(_First1, _Last1, _First2, _Last2, equal_to<>{});
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt1, class _FwdIt2, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdIt1 find_end(
_ExPo&& _Exec, _FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred) noexcept; // terminates
_EXPORT_STD template <class _ExPo, class _FwdIt1, class _FwdIt2, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdIt1 find_end(_ExPo&& _Exec, _FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2) noexcept
/* terminates */ { // find last [_First2, _Last2) match
return _STD find_end(_STD forward<_ExPo>(_Exec), _First1, _Last1, _First2, _Last2, equal_to{});
}
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
class _Find_end_fn : private _Not_quite_object {
private:
template <class _It1, class _It2, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr subrange<_It1> _Random_access_sized_ranges(_It1 _First1,
const iter_difference_t<_It1> _Count1, _It2 _First2, const iter_difference_t<_It2> _Count2, _Pr _Pred,
_Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_STATIC_ASSERT(random_access_iterator<_It1>);
_STL_INTERNAL_STATIC_ASSERT(random_access_iterator<_It2>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>);
// pre: _First1 + [0, _Count1) is a valid counted range
// pre: _First2 + [0, _Count2) is a valid counted range
if (_Count2 > 0 && _Count2 <= _Count1) {
const auto _Count2_as1 = static_cast<iter_difference_t<_It1>>(_Count2);
for (auto _Candidate = _First1 + (_Count1 - _Count2_as1);; --_Candidate) {
auto [_Match, _Mid1] =
_RANGES _Equal_rev_pred(_Candidate, _First2, _First2 + _Count2, _Pred, _Proj1, _Proj2);
if (_Match) {
return {_STD move(_Candidate), _STD move(_Mid1)};
}
if (_Candidate == _First1) {
break;
}
}
}
_First1 += _Count1;
return {_First1, _First1};
}
template <class _It1, class _It2, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr subrange<_It1> _Bidi_common_ranges(
_It1 _First1, _It1 _Last1, _It2 _First2, const _It2 _Last2, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_STATIC_ASSERT(bidirectional_iterator<_It1>);
_STL_INTERNAL_STATIC_ASSERT(bidirectional_iterator<_It2>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>);
for (auto _Candidate = _Last1;; --_Candidate) { // try a match at _Candidate
auto _Next1 = _Candidate;
auto _Next2 = _Last2;
for (;;) { // test if [_First2, _Last2) is a suffix of [_First1, _Candidate)
if (_First2 == _Next2) { // match found
return {_STD move(_Next1), _STD move(_Candidate)};
}
if (_First1 == _Next1) {
// [_First1, _Candidate) is shorter than [_First2, _Last2); remaining candidates nonviable
return {_Last1, _Last1};
}
--_Next1;
--_Next2;
if (!_STD invoke(_Pred, _STD invoke(_Proj1, *_Next1), _STD invoke(_Proj2, *_Next2))) {
break; // mismatch
}
}
}
}
template <class _It1, class _Se1, class _It2, class _Se2, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr subrange<_It1> _Forward_ranges(
_It1 _First1, const _Se1 _Last1, _It2 _First2, const _Se2 _Last2, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It1>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se1, _It1>);
_STL_INTERNAL_STATIC_ASSERT(forward_iterator<_It2>);
_STL_INTERNAL_STATIC_ASSERT(sentinel_for<_Se2, _It2>);
_STL_INTERNAL_STATIC_ASSERT(indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>);
subrange<_It1> _Match{};
bool _Found = false;
for (;; ++_First1) { // try a match at _First1
auto _Next1 = _First1;
auto _Next2 = _First2;
for (;; ++_Next1, (void) ++_Next2) { // test if [_First2, _Last2) is a prefix of [_First1, _Last1)
const bool _End_of_needle = _Next2 == _Last2;
if (_End_of_needle) { // match candidate found
_Match = subrange{_First1, _Next1};
_Found = true;
}
if (_Next1 == _Last1) { // haystack exhausted
if (!_Found) {
_Match = subrange{_Next1, _Next1};
}
return _Match;
}
if (_End_of_needle) {
break; // end of match found, go to the next candidate
}
if (!_STD invoke(_Pred, _STD invoke(_Proj1, *_Next1), _STD invoke(_Proj2, *_Next2))) {
break; // mismatch, go to the next candidate
}
}
}
}
public:
using _Not_quite_object::_Not_quite_object;
template <forward_iterator _It1, sentinel_for<_It1> _Se1, forward_iterator _It2, sentinel_for<_It2> _Se2,
class _Pr = ranges::equal_to, class _Pj1 = identity, class _Pj2 = identity>
requires indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr subrange<_It1> operator()(_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2,
_Pr _Pred = {}, _Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);
auto _UFirst1 = _Unwrap_iter<_Se1>(_First1);
auto _ULast1 = _Unwrap_sent<_It1>(_Last1);
auto _UFirst2 = _Unwrap_iter<_Se2>(_First2);
auto _ULast2 = _Unwrap_sent<_It2>(_Last2);
if constexpr (random_access_iterator<_It1> && sized_sentinel_for<_Se1, _It1> && random_access_iterator<_It2>
&& sized_sentinel_for<_Se2, _It2>) {
const auto _Count1 = _ULast1 - _UFirst1;
const auto _Count2 = _ULast2 - _UFirst2;
auto _UResult = _Random_access_sized_ranges(_STD move(_UFirst1), _Count1, _STD move(_UFirst2), _Count2,
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Rewrap_subrange<subrange<_It1>>(_First1, _STD move(_UResult));
} else if constexpr (_Bidi_common<_It1, _Se1> && _Bidi_common<_It2, _Se2>) {
auto _UResult = _Bidi_common_ranges(_STD move(_UFirst1), _STD move(_ULast1), _STD move(_UFirst2),
_STD move(_ULast2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Rewrap_subrange<subrange<_It1>>(_First1, _STD move(_UResult));
} else {
auto _UResult = _Forward_ranges(_STD move(_UFirst1), _STD move(_ULast1), _STD move(_UFirst2),
_STD move(_ULast2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Rewrap_subrange<subrange<_It1>>(_First1, _STD move(_UResult));
}
}
template <forward_range _Rng1, forward_range _Rng2, class _Pr = ranges::equal_to, class _Pj1 = identity,
class _Pj2 = identity>
requires indirectly_comparable<iterator_t<_Rng1>, iterator_t<_Rng2>, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr borrowed_subrange_t<_Rng1> operator()(
_Rng1&& _Range1, _Rng2&& _Range2, _Pr _Pred = {}, _Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
if constexpr (random_access_range<_Rng1> && sized_range<_Rng1> && random_access_range<_Rng2>
&& sized_range<_Rng2>) {
auto _UResult = _Random_access_sized_ranges(_Ubegin(_Range1), _RANGES distance(_Range1),
_Ubegin(_Range2), _RANGES distance(_Range2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Rewrap_subrange<borrowed_subrange_t<_Rng1>>(_Range1, _STD move(_UResult));
} else if constexpr (_Bidi_common_range<_Rng1> && _Bidi_common_range<_Rng2>) {
auto _UResult = _Bidi_common_ranges(_Ubegin(_Range1), _Uend(_Range1), _Ubegin(_Range2), _Uend(_Range2),
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Rewrap_subrange<borrowed_subrange_t<_Rng1>>(_Range1, _STD move(_UResult));
} else {
auto _UResult = _Forward_ranges(_Ubegin(_Range1), _Uend(_Range1), _Ubegin(_Range2), _Uend(_Range2),
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Rewrap_subrange<borrowed_subrange_t<_Rng1>>(_Range1, _STD move(_UResult));
}
}
};
_EXPORT_STD inline constexpr _Find_end_fn find_end{_Not_quite_object::_Construct_tag{}};
} // namespace ranges
#endif // __cpp_lib_concepts
_EXPORT_STD template <class _FwdIt1, class _FwdIt2, class _Pr>
_NODISCARD _CONSTEXPR20 _FwdIt1 find_first_of(
_FwdIt1 _First1, const _FwdIt1 _Last1, const _FwdIt2 _First2, const _FwdIt2 _Last2, _Pr _Pred) {
// look for one of [_First2, _Last2) satisfying _Pred with element
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);
auto _UFirst1 = _Get_unwrapped(_First1);
const auto _ULast1 = _Get_unwrapped(_Last1);
const auto _UFirst2 = _Get_unwrapped(_First2);
const auto _ULast2 = _Get_unwrapped(_Last2);
for (; _UFirst1 != _ULast1; ++_UFirst1) {
for (auto _UMid2 = _UFirst2; _UMid2 != _ULast2; ++_UMid2) {
if (_Pred(*_UFirst1, *_UMid2)) {
_Seek_wrapped(_First1, _UFirst1);
return _First1;
}
}
}
_Seek_wrapped(_First1, _UFirst1);
return _First1;
}
_EXPORT_STD template <class _FwdIt1, class _FwdIt2>
_NODISCARD _CONSTEXPR20 _FwdIt1 find_first_of(const _FwdIt1 _First1, const _FwdIt1 _Last1, const _FwdIt2 _First2,
const _FwdIt2 _Last2) { // look for one of [_First2, _Last2) that matches element
return _STD find_first_of(_First1, _Last1, _First2, _Last2, equal_to<>{});
}
#if _HAS_CXX17
_EXPORT_STD template <class _ExPo, class _FwdIt1, class _FwdIt2, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdIt1 find_first_of(
_ExPo&& _Exec, _FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred) noexcept; // terminates
_EXPORT_STD template <class _ExPo, class _FwdIt1, class _FwdIt2, _Enable_if_execution_policy_t<_ExPo> = 0>
_NODISCARD _FwdIt1 find_first_of(_ExPo&& _Exec, const _FwdIt1 _First1, const _FwdIt1 _Last1, const _FwdIt2 _First2,
const _FwdIt2 _Last2) noexcept /* terminates */ { // look for one of [_First2, _Last2) that matches element
return _STD find_first_of(_STD forward<_ExPo>(_Exec), _First1, _Last1, _First2, _Last2, equal_to{});
}
#endif // _HAS_CXX17
#ifdef __cpp_lib_concepts
namespace ranges {
class _Find_first_of_fn : private _Not_quite_object {
public:
using _Not_quite_object::_Not_quite_object;
template <input_iterator _It1, sentinel_for<_It1> _Se1, forward_iterator _It2, sentinel_for<_It2> _Se2,
class _Pr = ranges::equal_to, class _Pj1 = identity, class _Pj2 = identity>
requires indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr _It1 operator()(_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2, _Pr _Pred = {},
_Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);
auto _UResult = _Find_first_of_unchecked(_Unwrap_iter<_Se1>(_STD move(_First1)),
_Unwrap_sent<_It1>(_STD move(_Last1)), _Unwrap_iter<_Se2>(_STD move(_First2)),
_Unwrap_sent<_It2>(_STD move(_Last2)), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
_Seek_wrapped(_First1, _STD move(_UResult));
return _First1;
}
template <input_range _Rng1, forward_range _Rng2, class _Pr = ranges::equal_to, class _Pj1 = identity,
class _Pj2 = identity>
requires indirectly_comparable<iterator_t<_Rng1>, iterator_t<_Rng2>, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr borrowed_iterator_t<_Rng1> operator()(
_Rng1&& _Range1, _Rng2&& _Range2, _Pr _Pred = {}, _Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
auto