11 Algorithms library [algorithms]
11.1 General [algorithms.general]
This Clause describes components that C++ programs may use to perform algorithmic operations on containers (Clause ISO/IEC 14882:2014 §[containers]) and other sequences.
The following subclauses describe components for non-modifying sequence operations, modifying sequence operations, and sorting and related operations, as summarized in Table [tab:algorithms.summary].
| Subclause | Header(s) | |
| [alg.nonmodifying] | Non-modifying sequence operations | |
| [alg.modifying.operations] | Mutating sequence operations | <experimental/ranges/algorithm> |
| [alg.sorting] | Sorting and related operations | |
To ease transition, implementations provide additional algorithm signatures that are deprecated in this document (Annex [depr.algo.range-and-a-half]).
Header <experimental/ranges/algorithm> synopsis
#include <initializer_list>
namespace std { namespace experimental { namespace ranges { inline namespace v1 {
namespace tag {
// [alg.tagspec], tag specifiers (See [taggedtup.tagged]):
struct in;
struct in1;
struct in2;
struct out;
struct out1;
struct out2;
struct fun;
struct min;
struct max;
struct begin;
struct end;
}
// [alg.nonmodifying], non-modifying sequence operations:
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
bool all_of(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
bool all_of(Rng&& rng, Pred pred, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
bool any_of(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
bool any_of(Rng&& rng, Pred pred, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
bool none_of(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
bool none_of(Rng&& rng, Pred pred, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryInvocable<projected<I, Proj>> Fun>
tagged_pair<tag::in(I), tag::fun(Fun)>
for_each(I first, S last, Fun f, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryInvocable<projected<iterator_t<Rng>, Proj>> Fun>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::fun(Fun)>
for_each(Rng&& rng, Fun f, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class T, class Proj = identity>
requires IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
I find(I first, S last, const T& value, Proj proj = Proj{});
template <InputRange Rng, class T, class Proj = identity>
requires IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
safe_iterator_t<Rng>
find(Rng&& rng, const T& value, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
I find_if(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
safe_iterator_t<Rng>
find_if(Rng&& rng, Pred pred, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
I find_if_not(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
safe_iterator_t<Rng>
find_if_not(Rng&& rng, Pred pred, Proj proj = Proj{});
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
Sentinel<I2> S2, class Proj = identity,
IndirectRelation<I2, projected<I1, Proj>> Pred = equal_to<>>
I1
find_end(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = Pred{}, Proj proj = Proj{});
template <ForwardRange Rng1, ForwardRange Rng2, class Proj = identity,
IndirectRelation<iterator_t<Rng2>,
projected<iterator_t<Rng>, Proj>> Pred = equal_to<>>
safe_iterator_t<Rng1>
find_end(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{}, Proj proj = Proj{});
template <InputIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2,
class Proj1 = identity, class Proj2 = identity,
IndirectRelation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = equal_to<>>
I1
find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, ForwardRange Rng2, class Proj1 = identity,
class Proj2 = identity,
IndirectRelation<projected<iterator_t<Rng1>, Proj1>,
projected<iterator_t<Rng2>, Proj2>> Pred = equal_to<>>
safe_iterator_t<Rng1>
find_first_of(Rng1&& rng1, Rng2&& rng2,
Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectRelation<projected<I, Proj>> Pred = equal_to<>>
I
adjacent_find(I first, S last, Pred pred = Pred{},
Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectRelation<projected<iterator_t<Rng>, Proj>> Pred = equal_to<>>
safe_iterator_t<Rng>
adjacent_find(Rng&& rng, Pred pred = Pred{}, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class T, class Proj = identity>
requires IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
difference_type_t<I>
count(I first, S last, const T& value, Proj proj = Proj{});
template <InputRange Rng, class T, class Proj = identity>
requires IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
difference_type_t<iterator_t<Rng>>
count(Rng&& rng, const T& value, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
difference_type_t<I>
count_if(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
difference_type_t<iterator_t<Rng>>
count_if(Rng&& rng, Pred pred, Proj proj = Proj{});
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
class Proj1 = identity, class Proj2 = identity,
IndirectRelation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = equal_to<>>
tagged_pair<tag::in1(I1), tag::in2(I2)>
mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2,
class Proj1 = identity, class Proj2 = identity,
IndirectRelation<projected<iterator_t<Rng1>, Proj1>,
projected<iterator_t<Rng2>, Proj2>> Pred = equal_to<>>
tagged_pair<tag::in1(safe_iterator_t<Rng1>),
tag::in2(safe_iterator_t<Rng2>)>
mismatch(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
bool equal(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, class Pred = equal_to<>,
class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
bool equal(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
Sentinel<I2> S2, class Pred = equal_to<>, class Proj1 = identity,
class Proj2 = identity>
requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
bool is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
bool is_permutation(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
Sentinel<I2> S2, class Pred = equal_to<>,
class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
I1
search(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
safe_iterator_t<Rng1>
search(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <ForwardIterator I, Sentinel<I> S, class T,
class Pred = equal_to<>, class Proj = identity>
requires IndirectlyComparable<I, const T*, Pred, Proj>
I
search_n(I first, S last, difference_type_t<I> count,
const T& value, Pred pred = Pred{},
Proj proj = Proj{});
template <ForwardRange Rng, class T, class Pred = equal_to<>,
class Proj = identity>
requires IndirectlyComparable<iterator_t<Rng>, const T*, Pred, Proj>
safe_iterator_t<Rng>
search_n(Rng&& rng, difference_type_t<iterator_t<Rng>> count,
const T& value, Pred pred = Pred{}, Proj proj = Proj{});
// [alg.modifying.operations], modifying sequence operations:
// [alg.copy], copy:
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
copy(I first, S last, O result);
template <InputRange Rng, WeaklyIncrementable O>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
copy(Rng&& rng, O result);
template <InputIterator I, WeaklyIncrementable O>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
copy_n(I first, difference_type_t<I> n, O result);
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
copy_if(I first, S last, O result, Pred pred, Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
copy_if(Rng&& rng, O result, Pred pred, Proj proj = Proj{});
template <BidirectionalIterator I1, Sentinel<I1> S1, BidirectionalIterator I2>
requires IndirectlyCopyable<I1, I2>
tagged_pair<tag::in(I1), tag::out(I2)>
copy_backward(I1 first, S1 last, I2 result);
template <BidirectionalRange Rng, BidirectionalIterator I>
requires IndirectlyCopyable<iterator_t<Rng>, I>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(I)>
copy_backward(Rng&& rng, I result);
// [alg.move], move:
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O>
requires IndirectlyMovable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
move(I first, S last, O result);
template <InputRange Rng, WeaklyIncrementable O>
requires IndirectlyMovable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
move(Rng&& rng, O result);
template <BidirectionalIterator I1, Sentinel<I1> S1, BidirectionalIterator I2>
requires IndirectlyMovable<I1, I2>
tagged_pair<tag::in(I1), tag::out(I2)>
move_backward(I1 first, S1 last, I2 result);
template <BidirectionalRange Rng, BidirectionalIterator I>
requires IndirectlyMovable<iterator_t<Rng>, I>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(I)>
move_backward(Rng&& rng, I result);
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2>
requires IndirectlySwappable<I1, I2>
tagged_pair<tag::in1(I1), tag::in2(I2)>
swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2);
template <ForwardRange Rng1, ForwardRange Rng2>
requires IndirectlySwappable<iterator_t<Rng1>, iterator_t<Rng2>>
tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::in2(safe_iterator_t<Rng2>)>
swap_ranges(Rng1&& rng1, Rng2&& rng2);
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
CopyConstructible F, class Proj = identity>
requires Writable<O, indirect_result_of_t<F&(projected<I, Proj>)>>
tagged_pair<tag::in(I), tag::out(O)>
transform(I first, S last, O result, F op, Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O, CopyConstructible F,
class Proj = identity>
requires Writable<O, indirect_result_of_t<F&(
projected<iterator_t<R>, Proj>)>>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
transform(Rng&& rng, O result, F op, Proj proj = Proj{});
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, CopyConstructible F, class Proj1 = identity,
class Proj2 = identity>
requires Writable<O, indirect_result_of_t<F&(projected<I1, Proj1>,
projected<I2, Proj2>)>>
tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
transform(I1 first1, S1 last1, I2 first2, S2 last2, O result,
F binary_op, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
CopyConstructible F, class Proj1 = identity, class Proj2 = identity>
requires Writable<O, indirect_result_of_t<F&(
projected<iterator_t<Rng1>, Proj1>, projected<iterator_t<Rng2>, Proj2>)>>
tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
tag::in2(safe_iterator_t<Rng2>),
tag::out(O)>
transform(Rng1&& rng1, Rng2&& rng2, O result,
F binary_op, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputIterator I, Sentinel<I> S, class T1, class T2, class Proj = identity>
requires Writable<I, const T2&> &&
IndirectRelation<equal_to<>, projected<I, Proj>, const T1*>
I
replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = Proj{});
template <InputRange Rng, class T1, class T2, class Proj = identity>
requires Writable<iterator_t<Rng>, const T2&> &&
IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T1*>
safe_iterator_t<Rng>
replace(Rng&& rng, const T1& old_value, const T2& new_value, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires Writable<I, const T&>
I
replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = Proj{});
template <InputRange Rng, class T, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires Writable<iterator_t<Rng>, const T&>
safe_iterator_t<Rng>
replace_if(Rng&& rng, Pred pred, const T& new_value, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class T1, class T2, OutputIterator<const T2&> O,
class Proj = identity>
requires IndirectlyCopyable<I, O> &&
IndirectRelation<equal_to<>, projected<I, Proj>, const T1*>
tagged_pair<tag::in(I), tag::out(O)>
replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value,
Proj proj = Proj{});
template <InputRange Rng, class T1, class T2, OutputIterator<const T2&> O,
class Proj = identity>
requires IndirectlyCopyable<iterator_t<Rng>, O> &&
IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T1*>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
replace_copy(Rng&& rng, O result, const T1& old_value, const T2& new_value,
Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class T, OutputIterator<const T&> O,
class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
Proj proj = Proj{});
template <InputRange Rng, class T, OutputIterator<const T&> O, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
replace_copy_if(Rng&& rng, O result, Pred pred, const T& new_value,
Proj proj = Proj{});
template <class T, OutputIterator<const T&> O, Sentinel<O> S>
O fill(O first, S last, const T& value);
template <class T, OutputRange<const T&> Rng>
safe_iterator_t<Rng>
fill(Rng&& rng, const T& value);
template <class T, OutputIterator<const T&> O>
O fill_n(O first, difference_type_t<O> n, const T& value);
template <Iterator O, Sentinel<O> S, CopyConstructible F>
requires Invocable<F&> && Writable<O, result_of_t<F&()>>
O generate(O first, S last, F gen);
template <class Rng, CopyConstructible F>
requires Invocable<F&> && OutputRange<Rng, result_of_t<F&()>>
safe_iterator_t<Rng>
generate(Rng&& rng, F gen);
template <Iterator O, CopyConstructible F>
requires Invocable<F&> && Writable<O, result_of_t<F&()>>
O generate_n(O first, difference_type_t<O> n, F gen);
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity>
requires Permutable<I> &&
IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
I remove(I first, S last, const T& value, Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity>
requires Permutable<iterator_t<Rng>> &&
IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
safe_iterator_t<Rng>
remove(Rng&& rng, const T& value, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires Permutable<I>
I remove_if(I first, S last, Pred pred, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires Permutable<iterator_t<Rng>>
safe_iterator_t<Rng>
remove_if(Rng&& rng, Pred pred, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class T,
class Proj = identity>
requires IndirectlyCopyable<I, O> &&
IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
tagged_pair<tag::in(I), tag::out(O)>
remove_copy(I first, S last, O result, const T& value, Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O, class T, class Proj = identity>
requires IndirectlyCopyable<iterator_t<Rng>, O> &&
IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
remove_copy(Rng&& rng, O result, const T& value, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
remove_copy_if(I first, S last, O result, Pred pred, Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
remove_copy_if(Rng&& rng, O result, Pred pred, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectRelation<projected<I, Proj>> R = equal_to<>>
requires Permutable<I>
I unique(I first, S last, R comp = R{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectRelation<projected<iterator_t<Rng>, Proj>> R = equal_to<>>
requires Permutable<iterator_t<Rng>>
safe_iterator_t<Rng>
unique(Rng&& rng, R comp = R{}, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
class Proj = identity, IndirectRelation<projected<I, Proj>> R = equal_to<>>
requires IndirectlyCopyable<I, O> &&
(ForwardIterator<I> ||
(InputIterator<O> && Same<value_type_t<I>, value_type_t<O>>) ||
IndirectlyCopyableStorable<I, O>)
tagged_pair<tag::in(I), tag::out(O)>
unique_copy(I first, S last, O result, R comp = R{}, Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
IndirectRelation<projected<iterator_t<Rng>, Proj>> R = equal_to<>>
requires IndirectlyCopyable<iterator_t<Rng>, O> &&
(ForwardIterator<iterator_t<Rng>> ||
(InputIterator<O> && Same<value_type_t<iterator_t<Rng>>, value_type_t<O>>) ||
IndirectlyCopyableStorable<iterator_t<Rng>, O>)
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
unique_copy(Rng&& rng, O result, R comp = R{}, Proj proj = Proj{});
template <BidirectionalIterator I, Sentinel<I> S>
requires Permutable<I>
I reverse(I first, S last);
template <BidirectionalRange Rng>
requires Permutable<iterator_t<Rng>>
safe_iterator_t<Rng>
reverse(Rng&& rng);
template <BidirectionalIterator I, Sentinel<I> S, WeaklyIncrementable O>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)> reverse_copy(I first, S last, O result);
template <BidirectionalRange Rng, WeaklyIncrementable O>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
reverse_copy(Rng&& rng, O result);
template <ForwardIterator I, Sentinel<I> S>
requires Permutable<I>
tagged_pair<tag::begin(I), tag::end(I)>
rotate(I first, I middle, S last);
template <ForwardRange Rng>
requires Permutable<iterator_t<Rng>>
tagged_pair<tag::begin(safe_iterator_t<Rng>),
tag::end(safe_iterator_t<Rng>)>
rotate(Rng&& rng, iterator_t<Rng> middle);
template <ForwardIterator I, Sentinel<I> S, WeaklyIncrementable O>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
rotate_copy(I first, I middle, S last, O result);
template <ForwardRange Rng, WeaklyIncrementable O>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
rotate_copy(Rng&& rng, iterator_t<Rng> middle, O result);
// [alg.random.shuffle], shuffle:
template <RandomAccessIterator I, Sentinel<I> S, class Gen>
requires Permutable<I> &&
UniformRandomNumberGenerator<remove_reference_t<Gen>> &&
ConvertibleTo<result_of_t<Gen&()>, difference_type_t<I>>
I shuffle(I first, S last, Gen&& g);
template <RandomAccessRange Rng, class Gen>
requires Permutable<I> &&
UniformRandomNumberGenerator<remove_reference_t<Gen>> &&
ConvertibleTo<result_of_t<Gen&()>, difference_type_t<I>>
safe_iterator_t<Rng>
shuffle(Rng&& rng, Gen&& g);
// [alg.partitions], partitions:
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
bool is_partitioned(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
bool
is_partitioned(Rng&& rng, Pred pred, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires Permutable<I>
I partition(I first, S last, Pred pred, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires Permutable<iterator_t<Rng>>
safe_iterator_t<Rng>
partition(Rng&& rng, Pred pred, Proj proj = Proj{});
template <BidirectionalIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires Permutable<I>
I stable_partition(I first, S last, Pred pred, Proj proj = Proj{});
template <BidirectionalRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires Permutable<iterator_t<Rng>>
safe_iterator_t<Rng>
stable_partition(Rng&& rng, Pred pred, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O1, WeaklyIncrementable O2,
class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires IndirectlyCopyable<I, O1> && IndirectlyCopyable<I, O2>
tagged_tuple<tag::in(I), tag::out1(O1), tag::out2(O2)>
partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred,
Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O1, WeaklyIncrementable O2,
class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires IndirectlyCopyable<iterator_t<Rng>, O1> &&
IndirectlyCopyable<iterator_t<Rng>, O2>
tagged_tuple<tag::in(safe_iterator_t<Rng>), tag::out1(O1), tag::out2(O2)>
partition_copy(Rng&& rng, O1 out_true, O2 out_false, Pred pred, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
I partition_point(I first, S last, Pred pred, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
safe_iterator_t<Rng>
partition_point(Rng&& rng, Pred pred, Proj proj = Proj{});
// [alg.sorting], sorting and related operations:
// [alg.sort], sorting:
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
sort(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I stable_sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
stable_sort(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I partial_sort(I first, I middle, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
partial_sort(Rng&& rng, iterator_t<Rng> middle, Comp comp = Comp{},
Proj proj = Proj{});
template <InputIterator I1, Sentinel<I1> S1, RandomAccessIterator I2, Sentinel<I2> S2,
class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires IndirectlyCopyable<I1, I2> && Sortable<I2, Comp, Proj2> &&
IndirectStrictWeakOrder<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
I2
partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, RandomAccessRange Rng2, class Comp = less<>,
class Proj1 = identity, class Proj2 = identity>
requires IndirectlyCopyable<iterator_t<Rng1>, iterator_t<Rng2>> &&
Sortable<iterator_t<Rng2>, Comp, Proj2> &&
IndirectStrictWeakOrder<Comp, projected<iterator_t<Rng1>, Proj1>,
projected<iterator_t<Rng2>, Proj2>>
safe_iterator_t<Rng2>
partial_sort_copy(Rng1&& rng, Rng2&& result_rng, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
bool is_sorted(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
bool
is_sorted(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
I is_sorted_until(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
is_sorted_until(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I nth_element(I first, I nth, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
nth_element(Rng&& rng, iterator_t<Rng> nth, Comp comp = Comp{}, Proj proj = Proj{});
// [alg.binary.search], binary search:
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
I
lower_bound(I first, S last, const T& value, Comp comp = Comp{},
Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
lower_bound(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
I
upper_bound(I first, S last, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
upper_bound(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
tagged_pair<tag::begin(I), tag::end(I)>
equal_range(I first, S last, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
tagged_pair<tag::begin(safe_iterator_t<Rng>),
tag::end(safe_iterator_t<Rng>)>
equal_range(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
bool
binary_search(I first, S last, const T& value, Comp comp = Comp{},
Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
bool
binary_search(Rng&& rng, const T& value, Comp comp = Comp{},
Proj proj = Proj{});
// [alg.merge], merge:
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity,
class Proj2 = identity>
requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O, class Comp = less<>,
class Proj1 = identity, class Proj2 = identity>
requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
tag::in2(safe_iterator_t<Rng2>),
tag::out(O)>
merge(Rng1&& rng1, Rng2&& rng2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I
inplace_merge(I first, I middle, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <BidirectionalRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
inplace_merge(Rng&& rng, iterator_t<Rng> middle, Comp comp = Comp{},
Proj proj = Proj{});
// [alg.set.operations], set operations:
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
class Proj1 = identity, class Proj2 = identity,
IndirectStrictWeakOrder<projected<I1, Proj1>, projected<I2, Proj2>> Comp = less<>>
bool
includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, class Proj1 = identity,
class Proj2 = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng1>, Proj1>,
projected<iterator_t<Rng2>, Proj2>> Comp = less<>>
bool
includes(Rng1&& rng1, Rng2&& rng2, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
tag::in2(safe_iterator_t<Rng2>),
tag::out(O)>
set_union(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
O
set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
O
set_intersection(Rng1&& rng1, Rng2&& rng2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
tagged_pair<tag::in1(I1), tag::out(O)>
set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::out(O)>
set_difference(Rng1&& rng1, Rng2&& rng2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{},
Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
tag::in2(safe_iterator_t<Rng2>),
tag::out(O)>
set_symmetric_difference(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
// [alg.heap.operations], heap operations:
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I push_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
push_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I pop_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
pop_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I make_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
make_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I sort_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
sort_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
bool is_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
bool
is_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
I is_heap_until(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
is_heap_until(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
// [alg.min.max], minimum and maximum:
template <class T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr const T& min(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});
template <Copyable T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr T min(initializer_list<T> t, Comp comp = Comp{}, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
requires Copyable<value_type_t<iterator_t<Rng>>>
value_type_t<iterator_t<Rng>>
min(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <class T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr const T& max(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});
template <Copyable T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr T max(initializer_list<T> t, Comp comp = Comp{}, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
requires Copyable<value_type_t<iterator_t<Rng>>>
value_type_t<iterator_t<Rng>>
max(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <class T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr tagged_pair<tag::min(const T&), tag::max(const T&)>
minmax(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});
template <Copyable T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr tagged_pair<tag::min(T), tag::max(T)>
minmax(initializer_list<T> t, Comp comp = Comp{}, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
requires Copyable<value_type_t<iterator_t<Rng>>>
tagged_pair<tag::min(value_type_t<iterator_t<Rng>>),
tag::max(value_type_t<iterator_t<Rng>>)>
minmax(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
I min_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
min_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
I max_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
max_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
tagged_pair<tag::min(I), tag::max(I)>
minmax_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
tagged_pair<tag::min(safe_iterator_t<Rng>),
tag::max(safe_iterator_t<Rng>)>
minmax_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
class Proj1 = identity, class Proj2 = identity,
IndirectStrictWeakOrder<projected<I1, Proj1>, projected<I2, Proj2>> Comp = less<>>
bool
lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, class Proj1 = identity,
class Proj2 = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng1>, Proj1>,
projected<iterator_t<Rng2>, Proj2>> Comp = less<>>
bool
lexicographical_compare(Rng1&& rng1, Rng2&& rng2, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
// [alg.permutation.generators], permutations:
template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
bool next_permutation(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <BidirectionalRange Rng, class Comp = less<>,
class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
bool
next_permutation(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
bool prev_permutation(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <BidirectionalRange Rng, class Comp = less<>,
class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
bool
prev_permutation(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
}}}}
All of the algorithms are separated from the particular implementations of data structures and are parameterized by iterator types. Because of this, they can work with program-defined data structures, as long as these data structures have iterator types satisfying the assumptions on the algorithms.
For purposes of determining the existence of data races, algorithms shall not modify objects referenced through an iterator argument unless the specification requires such modification.
Both in-place and copying versions are provided for certain algorithms.4 When such a version is provided for algorithm it is called algorithm_copy. Algorithms that take predicates end with the suffix _if (which follows the suffix _copy).
[ Note: Unless otherwise specified, algorithms that take function objects as arguments are permitted to copy those function objects freely. Programmers for whom object identity is important should consider using a wrapper class that points to a noncopied implementation object such as reference_wrapper<T> ( ISO/IEC 14882:2014 §[refwrap]), or some equivalent solution. — end note ]
In the description of the algorithms operators + and - are used for some of the iterator categories for which they do not have to be defined. In these cases the semantics of a+n is the same as that of
X tmp = a; advance(tmp, n); return tmp;
and that of b-a is the same as of
return distance(a, b);
In the description of algorithm return values, sentinel values are sometimes returned where an iterator is expected. In these cases, the semantics are as if the sentinel is converted into an iterator as follows:
I tmp = first; while(tmp != last) ++tmp; return tmp;
Overloads of algorithms that take Range arguments ([ranges.range]) behave as if they are implemented by calling begin and end on the Range and dispatching to the overload that takes separate iterator and sentinel arguments.
The number and order of template parameters for algorithm declarations is unspecified, except where explicitly stated otherwise.
The decision whether to include a copying version was usually based on complexity considerations. When the cost of doing the operation dominates the cost of copy, the copying version is not included. For example, sort_copy is not included because the cost of sorting is much more significant, and users might as well do copy followed by sort.
11.3 Non-modifying sequence operations [alg.nonmodifying]
11.3.1 All of [alg.all_of]
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
bool all_of(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
bool all_of(Rng&& rng, Pred pred, Proj proj = Proj{});
Returns: true if [first,last) is empty or if invoke(pred, invoke(proj, *i)) is true for every iterator i in the range [first,last), and false otherwise.
Complexity: At most last - first applications of the predicate and last - first applications of the projection.
11.3.2 Any of [alg.any_of]
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
bool any_of(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
bool any_of(Rng&& rng, Pred pred, Proj proj = Proj{});
Returns: false if [first,last) is empty or if there is no iterator i in the range [first,last) such that invoke(pred, invoke(proj, *i)) is true, and true otherwise.
Complexity: At most last - first applications of the predicate and last - first applications of the projection.
11.3.3 None of [alg.none_of]
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
bool none_of(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
bool none_of(Rng&& rng, Pred pred, Proj proj = Proj{});
Returns: true if [first,last) is empty or if invoke(pred, invoke(proj, *i)) is false for every iterator i in the range [first,last), and false otherwise.
Complexity: At most last - first applications of the predicate and last - first applications of the projection.
11.3.4 For each [alg.foreach]
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryInvocable<projected<I, Proj>> Fun>
tagged_pair<tag::in(I), tag::fun(Fun)>
for_each(I first, S last, Fun f, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryInvocable<projected<iterator_t<Rng>, Proj>> Fun>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::fun(Fun)>
for_each(Rng&& rng, Fun f, Proj proj = Proj{});
Effects: Calls invoke(f, invoke(proj, *i)) for every iterator i in the range [first,last), starting from first and proceeding to last - 1. [ Note: If the result of invoke(proj, *i) is a mutable reference, f may apply nonconstant functions. — end note ]
Returns: {last, std::move(f)}.
Complexity: Applies f and proj exactly last - first times.
Remarks: If f returns a result, the result is ignored.
[ Note: The requirements of this algorithm are more strict than those specified in ISO/IEC 14882:2014 §[alg.foreach]. This algorithm requires Fun to satisfy CopyConstructible, whereas the algorithm in the C++ Standard requires only MoveConstructible. — end note ]
11.3.5 Find [alg.find]
template <InputIterator I, Sentinel<I> S, class T, class Proj = identity>
requires IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
I find(I first, S last, const T& value, Proj proj = Proj{});
template <InputRange Rng, class T, class Proj = identity>
requires IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
safe_iterator_t<Rng>
find(Rng&& rng, const T& value, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
I find_if(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
safe_iterator_t<Rng>
find_if(Rng&& rng, Pred pred, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
I find_if_not(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
safe_iterator_t<Rng>
find_if_not(Rng&& rng, Pred pred, Proj proj = Proj{});
Returns: The first iterator i in the range [first,last) for which the following corresponding conditions hold: invoke(proj, *i) == value, invoke(pred, invoke(proj, *i)) != false, invoke(pred, invoke(proj, *i)) == false. Returns last if no such iterator is found.
Complexity: At most last - first applications of the corresponding predicate and projection.
11.3.6 Find end [alg.find.end]
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
Sentinel<I2> S2, class Proj = identity,
IndirectRelation<I2, projected<I1, Proj>> Pred = equal_to<>>
I1
find_end(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = Pred{}, Proj proj = Proj{});
template <ForwardRange Rng1, ForwardRange Rng2,
class Proj = identity,
IndirectRelation<iterator_t<Rng2>,
projected<iterator_t<Rng>, Proj>> Pred = equal_to<>>
safe_iterator_t<Rng1>
find_end(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{}, Proj proj = Proj{});
Effects: Finds a subsequence of equal values in a sequence.
Returns: The last iterator i in the range [first1,last1 - (last2 - first2)) such that for every non-negative integer n < (last2 - first2), the following condition holds: invoke(pred, invoke(proj, *(i + n)), *(first2 + n)) != false. Returns last1 if [first2,last2) is empty or if no such iterator is found.
Complexity: At most (last2 - first2) * (last1 - first1 - (last2 - first2) + 1) applications of the corresponding predicate and projection.
11.3.7 Find first of [alg.find.first.of]
template <InputIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2,
class Proj1 = identity, class Proj2 = identity,
IndirectRelation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = equal_to<>>
I1
find_first_of(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, ForwardRange Rng2, class Proj1 = identity,
class Proj2 = identity,
IndirectRelation<projected<iterator_t<Rng1>, Proj1>,
projected<iterator_t<Rng2>, Proj2>> Pred = equal_to<>>
safe_iterator_t<Rng1>
find_first_of(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Effects: Finds an element that matches one of a set of values.
Returns: The first iterator i in the range [first1,last1) such that for some iterator j in the range [first2,last2) the following condition holds: invoke(pred, invoke(proj1, *i), invoke(proj2, *j)) != false. Returns last1 if [first2,last2) is empty or if no such iterator is found.
Complexity: At most (last1-first1) * (last2-first2) applications of the corresponding predicate and the two projections.
11.3.8 Adjacent find [alg.adjacent.find]
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectRelation<projected<I, Proj>> Pred = equal_to<>>
I
adjacent_find(I first, S last, Pred pred = Pred{},
Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectRelation<projected<iterator_t<Rng>, Proj>> Pred = equal_to<>>
safe_iterator_t<Rng>
adjacent_find(Rng&& rng, Pred pred = Pred{}, Proj proj = Proj{});
Returns: The first iterator i such that both i and i + 1 are in the range [first,last) for which the following corresponding condition holds: invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1))) != false. Returns last if no such iterator is found.
Complexity: For a nonempty range, exactly min((i - first) + 1, (last - first) - 1) applications of the corresponding predicate, where i is adjacent_find's return value, and no more than twice as many applications of the projection.
11.3.9 Count [alg.count]
template <InputIterator I, Sentinel<I> S, class T, class Proj = identity>
requires IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
difference_type_t<I>
count(I first, S last, const T& value, Proj proj = Proj{});
template <InputRange Rng, class T, class Proj = identity>
requires IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
difference_type_t<iterator_t<Rng>>
count(Rng&& rng, const T& value, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
difference_type_t<I>
count_if(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
difference_type_t<iterator_t<Rng>>
count_if(Rng&& rng, Pred pred, Proj proj = Proj{});
Effects: Returns the number of iterators i in the range [first,last) for which the following corresponding conditions hold: invoke(proj, *i) == value, invoke(pred, invoke(proj, *i)) != false.
Complexity: Exactly last - first applications of the corresponding predicate and projection.
11.3.10 Mismatch [mismatch]
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
class Proj1 = identity, class Proj2 = identity,
IndirectRelation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = equal_to<>>
tagged_pair<tag::in1(I1), tag::in2(I2)>
mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2,
class Proj1 = identity, class Proj2 = identity,
IndirectRelation<projected<iterator_t<Rng1>, Proj1>,
projected<iterator_t<Rng2>, Proj2>> Pred = equal_to<>>
tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::in2(safe_iterator_t<Rng2>)>
mismatch(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Returns: A pair of iterators i and j such that j == first2 + (i - first1) and i is the first iterator in the range [first1,last1) for which the following corresponding conditions hold:
j is in the range [first2, last2).
*i != *(first2 + (i - first1))
!invoke(pred, invoke(proj1, *i), invoke(proj2, *(first2 + (i - first1))))
Returns the pair first1 + min(last1 - first1, last2 - first2) and first2 + min(last1 - first1, last2 - first2) if such an iterator i is not found.
Complexity: At most last1 - first1 applications of the corresponding predicate and both projections.
11.3.11 Equal [alg.equal]
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
bool equal(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, class Pred = equal_to<>,
class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
bool equal(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Returns: If last1 - first1 != last2 - first2, return false. Otherwise return true if for every iterator i in the range [first1,last1) the following condition holds: invoke(pred, invoke(proj1, *i), invoke(proj2, *(first2 + (i - first1)))). Otherwise, returns false.
Complexity: No applications of the corresponding predicate and projections if:
SizedSentinel<S1, I1> is satisfied, and
SizedSentinel<S2, I2> is satisfied, and
last1 - first1 != last2 - first2.
Otherwise, at most min(last1 - first1, last2 - first2) applications of the corresponding predicate and projections.
11.3.12 Is permutation [alg.is_permutation]
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
Sentinel<I2> S2, class Pred = equal_to<>, class Proj1 = identity,
class Proj2 = identity>
requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
bool is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
bool is_permutation(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Returns: If last1 - first1 != last2 - first2, return false. Otherwise return true if there exists a permutation of the elements in the range [first2,first2 + (last1 - first1)), beginning with I2 begin, such that equal(first1, last1, begin, pred, proj1, proj2) returns true ; otherwise, returns false.
Complexity: No applications of the corresponding predicate and projections if:
SizedSentinel<S1, I1> is satisfied, and
SizedSentinel<S2, I2> is satisfied, and
last1 - first1 != last2 - first2.
Otherwise, exactly last1 - first1 applications of the corresponding predicate and projections if equal(first1, last1, first2, last2, pred, proj1, proj2) would return true; otherwise, at worst Ο(N2), where N has the value last1 - first1.
11.3.13 Search [alg.search]
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
Sentinel<I2> S2, class Pred = equal_to<>,
class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
I1
search(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
safe_iterator_t<Rng1>
search(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Effects: Finds a subsequence of equal values in a sequence.
Returns: The first iterator i in the range [first1,last1 - (last2-first2)) such that for every non-negative integer n less than last2 - first2 the following condition holds:
invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))) != false.
Returns first1 if [first2,last2) is empty, otherwise returns last1 if no such iterator is found.
Complexity: At most (last1 - first1) * (last2 - first2) applications of the corresponding predicate and projections.
template <ForwardIterator I, Sentinel<I> S, class T,
class Pred = equal_to<>, class Proj = identity>
requires IndirectlyComparable<I, const T*, Pred, Proj>
I
search_n(I first, S last, difference_type_t<I> count,
const T& value, Pred pred = Pred{},
Proj proj = Proj{});
template <ForwardRange Rng, class T, class Pred = equal_to<>,
class Proj = identity>
requires IndirectlyComparable<iterator_t<Rng>, const T*, Pred, Proj>
safe_iterator_t<Rng>
search_n(Rng&& rng, difference_type_t<iterator_t<Rng>> count,
const T& value, Pred pred = Pred{}, Proj proj = Proj{});
Effects: Finds a subsequence of equal values in a sequence.
Returns: The first iterator i in the range [first,last-count) such that for every non-negative integer n less than count the following condition holds: invoke(pred, invoke(proj, *(i + n)), value) != false. Returns last if no such iterator is found.
Complexity: At most last - first applications of the corresponding predicate and projection.
11.4 Mutating sequence operations [alg.modifying.operations]
11.4.1 Copy [alg.copy]
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
copy(I first, S last, O result);
template <InputRange Rng, WeaklyIncrementable O>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
copy(Rng&& rng, O result);
Effects: Copies elements in the range [first,last) into the range [result,result + (last - first)) starting from first and proceeding to last. For each non-negative integer n < (last - first), performs *(result + n) = *(first + n).
Returns: {last, result + (last - first)}.
Requires: result shall not be in the range [first,last).
Complexity: Exactly last - first assignments.
template <InputIterator I, WeaklyIncrementable O>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
copy_n(I first, difference_type_t<I> n, O result);
Effects: For each non-negative integer i < n, performs *(result + i) = *(first + i).
Returns: {first + n, result + n}.
Complexity: Exactly n assignments.
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
copy_if(I first, S last, O result, Pred pred, Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
copy_if(Rng&& rng, O result, Pred pred, Proj proj = Proj{});
Let N be the number of iterators i in the range [first,last) for which the condition invoke(pred, invoke(proj, *i)) holds.
Requires: The ranges [first,last) and [result,result + N) shall not overlap.
Effects: Copies all of the elements referred to by the iterator i in the range [first,last) for which invoke(pred, invoke(proj, *i)) is true.
Returns: {last, result + N}.
Complexity: Exactly last - first applications of the corresponding predicate and projection.
Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).
template <BidirectionalIterator I1, Sentinel<I1> S1, BidirectionalIterator I2>
requires IndirectlyCopyable<I1, I2>
tagged_pair<tag::in(I1), tag::out(I2)>
copy_backward(I1 first, S1 last, I2 result);
template <BidirectionalRange Rng, BidirectionalIterator I>
requires IndirectlyCopyable<iterator_t<Rng>, I>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(I)>
copy_backward(Rng&& rng, I result);
Effects: Copies elements in the range [first,last) into the range [result - (last-first),result) starting from last - 1 and proceeding to first.5 For each positive integer n <= (last - first), performs *(result - n) = *(last - n).
Requires: result shall not be in the range (first,last].
Returns: {last, result - (last - first)}.
Complexity: Exactly last - first assignments.
copy_backward should be used instead of copy when last is in the range [result - (last - first),result).
11.4.2 Move [alg.move]
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O>
requires IndirectlyMovable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
move(I first, S last, O result);
template <InputRange Rng, WeaklyIncrementable O>
requires IndirectlyMovable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
move(Rng&& rng, O result);
Effects: Moves elements in the range [first,last) into the range [result,result + (last - first)) starting from first and proceeding to last. For each non-negative integer n < (last-first), performs *(result + n) = ranges::iter_move(first + n).
Returns: {last, result + (last - first)}.
Requires: result shall not be in the range [first,last).
Complexity: Exactly last - first move assignments.
template <BidirectionalIterator I1, Sentinel<I1> S1, BidirectionalIterator I2>
requires IndirectlyMovable<I1, I2>
tagged_pair<tag::in(I1), tag::out(I2)>
move_backward(I1 first, S1 last, I2 result);
template <BidirectionalRange Rng, BidirectionalIterator I>
requires IndirectlyMovable<iterator_t<Rng>, I>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(I)>
move_backward(Rng&& rng, I result);
Effects: Moves elements in the range [first,last) into the range [result - (last-first),result) starting from last - 1 and proceeding to first.6 For each positive integer n <= (last - first), performs *(result - n) = ranges::iter_move(last - n).
Requires: result shall not be in the range (first,last].
Returns: {last, result - (last - first)}.
Complexity: Exactly last - first assignments.
move_backward should be used instead of move when last is in the range [result - (last - first),result).
11.4.3 swap [alg.swap]
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2>
requires IndirectlySwappable<I1, I2>
tagged_pair<tag::in1(I1), tag::in2(I2)>
swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2);
template <ForwardRange Rng1, ForwardRange Rng2>
requires IndirectlySwappable<iterator_t<Rng1>, iterator_t<Rng2>>
tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::in2(safe_iterator_t<Rng2>)>
swap_ranges(Rng1&& rng1, Rng2&& rng2);
Effects:
For each non-negative integer n < min(last1 - first1, last2 - first2)
performs:
ranges::iter_swap(first1 + n, first2 + n).
Requires: The two ranges [first1,last1) and [first2,last2) shall not overlap. *(first1 + n) shall be swappable with ([concepts.lib.corelang.swappable]) *(first2 + n).
Returns: {first1 + n, first2 + n}, where n is min(last1 - first1, last2 - first2).
Complexity: Exactly min(last1 - first1, last2 - first2) swaps.
11.4.4 Transform [alg.transform]
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
CopyConstructible F, class Proj = identity>
requires Writable<O, indirect_result_of_t<F&(projected<I, Proj>)>>
tagged_pair<tag::in(I), tag::out(O)>
transform(I first, S last, O result, F op, Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O, CopyConstructible F,
class Proj = identity>
requires Writable<O, indirect_result_of_t<F&(
projected<iterator_t<R>, Proj>)>>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
transform(Rng&& rng, O result, F op, Proj proj = Proj{});
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, CopyConstructible F, class Proj1 = identity,
class Proj2 = identity>
requires Writable<O, indirect_result_of_t<F&(projected<I1, Proj1>,
projected<I2, Proj2>)>>
tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
transform(I1 first1, S1 last1, I2 first2, S2 last2, O result,
F binary_op, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
CopyConstructible F, class Proj1 = identity, class Proj2 = identity>
requires Writable<O, indirect_result_of_t<F&(
projected<iterator_t<Rng1>, Proj1>, projected<iterator_t<Rng2>, Proj2>)>>
tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
tag::in2(safe_iterator_t<Rng2>),
tag::out(O)>
transform(Rng1&& rng1, Rng2&& rng2, O result,
F binary_op, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Let N be (last1 - first1) for unary transforms, or min(last1 - first1, last2 - first2) for binary transforms.
Effects: Assigns through every iterator i in the range [result,result + N) a new corresponding value equal to invoke(op, invoke(proj, *(first1 + (i - result)))) or invoke(binary_op, invoke(proj1, *(first1 + (i - result))), invoke(proj2, *(first2 + (i - result)))).
Requires: op and binary_op shall not invalidate iterators or subranges, or modify elements in the ranges [first1,first1 + N], [first2,first2 + N], and [result,result + N].7
Returns: {first1 + N, result + N} or make_tagged_tuple<tag::in1, tag::in2, tag::out>(first1 + N, first2 + N, result + N).
Complexity: Exactly N applications of op or binary_op and the corresponding projection(s).
Remarks: result may be equal to first1 in case of unary transform, or to first1 or first2 in case of binary transform.
The use of fully closed ranges is intentional.
11.4.5 Replace [alg.replace]
template <InputIterator I, Sentinel<I> S, class T1, class T2, class Proj = identity>
requires Writable<I, const T2&> &&
IndirectRelation<equal_to<>, projected<I, Proj>, const T1*>
I
replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = Proj{});
template <InputRange Rng, class T1, class T2, class Proj = identity>
requires Writable<iterator_t<Rng>, const T2&> &&
IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T1*>
safe_iterator_t<Rng>
replace(Rng&& rng, const T1& old_value, const T2& new_value, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires Writable<I, const T&>
I
replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = Proj{});
template <InputRange Rng, class T, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires Writable<iterator_t<Rng>, const T&>
safe_iterator_t<Rng>
replace_if(Rng&& rng, Pred pred, const T& new_value, Proj proj = Proj{});
Effects: Assigns new_value through each iterator i in the range [first,last) when the following corresponding conditions hold: invoke(proj, *i) == old_value, invoke(pred, invoke(proj, *i)) != false.
Returns: last.
Complexity: Exactly last - first applications of the corresponding predicate and projection.
template <InputIterator I, Sentinel<I> S, class T1, class T2, OutputIterator<const T2&> O,
class Proj = identity>
requires IndirectlyCopyable<I, O> &&
IndirectRelation<equal_to<>, projected<I, Proj>, const T1*>
tagged_pair<tag::in(I), tag::out(O)>
replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value,
Proj proj = Proj{});
template <InputRange Rng, class T1, class T2, OutputIterator<const T2&> O,
class Proj = identity>
requires IndirectlyCopyable<iterator_t<Rng>, O> &&
IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T1*>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
replace_copy(Rng&& rng, O result, const T1& old_value, const T2& new_value,
Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, class T, OutputIterator<const T&> O,
class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
Proj proj = Proj{});
template <InputRange Rng, class T, OutputIterator<const T&> O, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
replace_copy_if(Rng&& rng, O result, Pred pred, const T& new_value,
Proj proj = Proj{});
Requires: The ranges [first,last) and [result,result + (last - first)) shall not overlap.
Effects: Assigns to every iterator i in the range [result,result + (last - first)) either new_value or *(first + (i - result)) depending on whether the following corresponding conditions hold:
invoke(proj, *(first + (i - result))) == old_value invoke(pred, invoke(proj, *(first + (i - result)))) != false
Returns: {last, result + (last - first)}.
Complexity: Exactly last - first applications of the corresponding predicate and projection.
11.4.6 Fill [alg.fill]
template <class T, OutputIterator<const T&> O, Sentinel<O> S>
O fill(O first, S last, const T& value);
template <class T, OutputRange<const T&> Rng>
safe_iterator_t<Rng>
fill(Rng&& rng, const T& value);
template <class T, OutputIterator<const T&> O>
O fill_n(O first, difference_type_t<O> n, const T& value);
Effects: fill assigns value through all the iterators in the range [first,last). fill_n assigns value through all the iterators in the counted range [first,n) if n is positive, otherwise it does nothing.
Returns: last, where last is first + max(n, 0) for fill_n.
Complexity: Exactly last - first assignments.
11.4.7 Generate [alg.generate]
template <Iterator O, Sentinel<O> S, CopyConstructible F>
requires Invocable<F&> && Writable<O, result_of_t<F&()>>
O generate(O first, S last, F gen);
template <class Rng, CopyConstructible F>
requires Invocable<F&> && OutputRange<Rng, result_of_t<F&()>>
safe_iterator_t<Rng>
generate(Rng&& rng, F gen);
template <Iterator O, CopyConstructible F>
requires Invocable<F&> && Writable<O, result_of_t<F&()>>
O generate_n(O first, difference_type_t<O> n, F gen);
Effects: The generate algorithms invoke the function object gen and assign the return value of gen through all the iterators in the range [first,last). The generate_n algorithm invokes the function object gen and assigns the return value of gen through all the iterators in the counted range [first,n) if n is positive, otherwise it does nothing.
Returns: last, where last is first + max(n, 0) for generate_n.
Complexity: Exactly last - first evaluations of invoke(gen) and assignments.
11.4.8 Remove [alg.remove]
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity>
requires Permutable<I> &&
IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
I remove(I first, S last, const T& value, Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity>
requires Permutable<iterator_t<Rng>> &&
IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
safe_iterator_t<Rng>
remove(Rng&& rng, const T& value, Proj proj = Proj{});
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires Permutable<I>
I remove_if(I first, S last, Pred pred, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires Permutable<iterator_t<Rng>>
safe_iterator_t<Rng>
remove_if(Rng&& rng, Pred pred, Proj proj = Proj{});
Effects: Eliminates all the elements referred to by iterator i in the range [first,last) for which the following corresponding conditions hold: invoke(proj, *i) == value, invoke(pred, invoke(proj, *i)) != false.
Returns: The end of the resulting range.
Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).
Complexity: Exactly last - first applications of the corresponding predicate and projection.
Note: each element in the range [ret,last), where ret is the returned value, has a valid but unspecified state, because the algorithms can eliminate elements by moving from elements that were originally in that range.
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class T,
class Proj = identity>
requires IndirectlyCopyable<I, O> &&
IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
tagged_pair<tag::in(I), tag::out(O)>
remove_copy(I first, S last, O result, const T& value, Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O, class T, class Proj = identity>
requires IndirectlyCopyable<iterator_t<Rng>, O> &&
IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
remove_copy(Rng&& rng, O result, const T& value, Proj proj = Proj{});
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
remove_copy_if(I first, S last, O result, Pred pred, Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
remove_copy_if(Rng&& rng, O result, Pred pred, Proj proj = Proj{});
Requires: The ranges [first,last) and [result,result + (last - first)) shall not overlap.
Effects: Copies all the elements referred to by the iterator i in the range [first,last) for which the following corresponding conditions do not hold: invoke(proj, *i) == value, invoke(pred, invoke(proj, *i)) != false.
Returns: A pair consisting of last and the end of the resulting range.
Complexity: Exactly last - first applications of the corresponding predicate and projection.
Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).
11.4.9 Unique [alg.unique]
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectRelation<projected<I, Proj>> R = equal_to<>>
requires Permutable<I>
I unique(I first, S last, R comp = R{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectRelation<projected<iterator_t<Rng>, Proj>> R = equal_to<>>
requires Permutable<iterator_t<Rng>>
safe_iterator_t<Rng>
unique(Rng&& rng, R comp = R{}, Proj proj = Proj{});
Effects: For a nonempty range, eliminates all but the first element from every consecutive group of equivalent elements referred to by the iterator i in the range [first + 1,last) for which the following conditions hold: invoke(proj, *(i - 1)) == invoke(proj, *i) or invoke(pred, invoke(proj, *(i - 1)), invoke(proj, *i)) != false.
Returns: The end of the resulting range.
Complexity: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding predicate and no more than twice as many applications of the projection.
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
class Proj = identity, IndirectRelation<projected<I, Proj>> R = equal_to<>>
requires IndirectlyCopyable<I, O> &&
(ForwardIterator<I> ||
(InputIterator<O> && Same<value_type_t<I>, value_type_t<O>>) ||
IndirectlyCopyableStorable<I, O>)
tagged_pair<tag::in(I), tag::out(O)>
unique_copy(I first, S last, O result, R comp = R{}, Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
IndirectRelation<projected<iterator_t<Rng>, Proj>> R = equal_to<>>
requires IndirectlyCopyable<iterator_t<Rng>, O> &&
(ForwardIterator<iterator_t<Rng>> ||
(InputIterator<O> && Same<value_type_t<iterator_t<Rng>>, value_type_t<O>>) ||
IndirectlyCopyableStorable<iterator_t<Rng>, O>)
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
unique_copy(Rng&& rng, O result, R comp = R{}, Proj proj = Proj{});
Requires: The ranges [first,last) and [result,result+(last-first)) shall not overlap.
Effects: Copies only the first element from every consecutive group of equal elements referred to by the iterator i in the range [first,last) for which the following corresponding conditions hold:
invoke(proj, *i) == invoke(proj, *(i - 1))
or
invoke(pred, invoke(proj, *i), invoke(proj, *(i - 1))) != false.
Returns: A pair consisting of last and the end of the resulting range.
Complexity: For nonempty ranges, exactly last - first - 1 applications of the corresponding predicate and no more than twice as many applications of the projection.
11.4.10 Reverse [alg.reverse]
template <BidirectionalIterator I, Sentinel<I> S>
requires Permutable<I>
I reverse(I first, S last);
template <BidirectionalRange Rng>
requires Permutable<iterator_t<Rng>>
safe_iterator_t<Rng>
reverse(Rng&& rng);
Effects: For each non-negative integer i < (last - first)/2, applies iter_swap to all pairs of iterators first + i, (last - i) - 1.
Returns: last.
Complexity: Exactly (last - first)/2 swaps.
template <BidirectionalIterator I, Sentinel<I> S, WeaklyIncrementable O>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)> reverse_copy(I first, S last, O result);
template <BidirectionalRange Rng, WeaklyIncrementable O>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
reverse_copy(Rng&& rng, O result);
Effects: Copies the range [first,last) to the range [result,result+(last-first)) such that for every non-negative integer i < (last - first) the following assignment takes place: *(result + (last - first) - 1 - i) = *(first + i).
Requires: The ranges [first,last) and [result,result+(last-first)) shall not overlap.
Returns: {last, result + (last - first)}.
Complexity: Exactly last - first assignments.
11.4.11 Rotate [alg.rotate]
template <ForwardIterator I, Sentinel<I> S>
requires Permutable<I>
tagged_pair<tag::begin(I), tag::end(I)> rotate(I first, I middle, S last);
template <ForwardRange Rng>
requires Permutable<iterator_t<Rng>>
tagged_pair<tag::begin(safe_iterator_t<Rng>), tag::end(safe_iterator_t<Rng>)>
rotate(Rng&& rng, iterator_t<Rng> middle);
Effects: For each non-negative integer i < (last - first), places the element from the position first + i into position first + (i + (last - middle)) % (last - first).
Returns: {first + (last - middle), last}.
Remarks: This is a left rotate.
Requires: [first,middle) and [middle,last) shall be valid ranges.
Complexity: At most last - first swaps.
template <ForwardIterator I, Sentinel<I> S, WeaklyIncrementable O>
requires IndirectlyCopyable<I, O>
tagged_pair<tag::in(I), tag::out(O)>
rotate_copy(I first, I middle, S last, O result);
template <ForwardRange Rng, WeaklyIncrementable O>
requires IndirectlyCopyable<iterator_t<Rng>, O>
tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
rotate_copy(Rng&& rng, iterator_t<Rng> middle, O result);
Effects: Copies the range [first,last) to the range [result,result + (last - first)) such that for each non-negative integer i < (last - first) the following assignment takes place: *(result + i) = *(first + (i + (middle - first)) % (last - first)).
Returns: {last, result + (last - first)}.
Requires: The ranges [first,last) and [result,result + (last - first)) shall not overlap.
Complexity: Exactly last - first assignments.
11.4.12 Shuffle [alg.random.shuffle]
template <RandomAccessIterator I, Sentinel<I> S, class Gen>
requires Permutable<I> &&
UniformRandomNumberGenerator<remove_reference_t<Gen>> &&
ConvertibleTo<result_of_t<Gen&()>, difference_type_t<I>>
I shuffle(I first, S last, Gen&& g);
template <RandomAccessRange Rng, class Gen>
requires Permutable<I> &&
UniformRandomNumberGenerator<remove_reference_t<Gen>> &&
ConvertibleTo<result_of_t<Gen&()>, difference_type_t<I>>
safe_iterator_t<Rng>
shuffle(Rng&& rng, Gen&& g);
Effects: Permutes the elements in the range [first,last) such that each possible permutation of those elements has equal probability of appearance.
Complexity: Exactly (last - first) - 1 swaps.
Returns: last
Remarks: To the extent that the implementation of this function makes use of random numbers, the object g shall serve as the implementation's source of randomness.
11.4.13 Partitions [alg.partitions]
template <InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
bool is_partitioned(I first, S last, Pred pred, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
bool
is_partitioned(Rng&& rng, Pred pred, Proj proj = Proj{});
Returns: true if [first,last) is empty or if [first,last) is partitioned by pred and proj, i.e. if all iterators i for which invoke(pred, invoke(proj, *i)) != false come before those that do not, for every i in [first,last).
Complexity: Linear. At most last - first applications of pred and proj.
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires Permutable<I>
I partition(I first, S last, Pred pred, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires Permutable<iterator_t<Rng>>
safe_iterator_t<Rng>
partition(Rng&& rng, Pred pred, Proj proj = Proj{});
Effects: Permutes the elements in the range [first,last) such that there exists an iterator i such that for every iterator j in the range [first,i) invoke(pred, invoke(proj, *j)) != false, and for every iterator k in the range [i,last), invoke(pred, invoke(proj, *k)) == false.
Returns: An iterator i such that for every iterator j in the range [first,i) invoke(pred, invoke(proj, *j)) != false, and for every iterator k in the range [i,last), invoke(pred, invoke(proj, *k)) == false.
Complexity: If I meets the requirements for a BidirectionalIterator, at most (last - first) / 2 swaps; otherwise at most last - first swaps. Exactly last - first applications of the predicate and projection.
template <BidirectionalIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires Permutable<I>
I stable_partition(I first, S last, Pred pred, Proj proj = Proj{});
template <BidirectionalRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires Permutable<iterator_t<Rng>>
safe_iterator_t<Rng>
stable_partition(Rng&& rng, Pred pred, Proj proj = Proj{});
Effects: Permutes the elements in the range [first,last) such that there exists an iterator i such that for every iterator j in the range [first,i) invoke(pred, invoke(proj, *j)) != false, and for every iterator k in the range [i,last), invoke(pred, invoke(proj, *k)) == false.
Returns: An iterator i such that for every iterator j in the range [first,i), invoke(pred, invoke(proj, *j)) != false, and for every iterator k in the range [i,last), invoke(pred, invoke(proj, *k)) == false. The relative order of the elements in both groups is preserved.
Complexity: At most (last - first) * log(last - first) swaps, but only linear number of swaps if there is enough extra memory. Exactly last - first applications of the predicate and projection.
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O1, WeaklyIncrementable O2,
class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
requires IndirectlyCopyable<I, O1> && IndirectlyCopyable<I, O2>
tagged_tuple<tag::in(I), tag::out1(O1), tag::out2(O2)>
partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred,
Proj proj = Proj{});
template <InputRange Rng, WeaklyIncrementable O1, WeaklyIncrementable O2,
class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
requires IndirectlyCopyable<iterator_t<Rng>, O1> &&
IndirectlyCopyable<iterator_t<Rng>, O2>
tagged_tuple<tag::in(safe_iterator_t<Rng>), tag::out1(O1), tag::out2(O2)>
partition_copy(Rng&& rng, O1 out_true, O2 out_false, Pred pred, Proj proj = Proj{});
Requires: The input range shall not overlap with either of the output ranges.
Effects: For each iterator i in [first,last), copies *i to the output range beginning with out_true if invoke(pred, invoke(proj, *i)) is true, or to the output range beginning with out_false otherwise.
Returns: A tuple p such that get<0>(p) is last, get<1>(p) is the end of the output range beginning at out_true, and get<2>(p) is the end of the output range beginning at out_false.
Complexity: Exactly last - first applications of pred and proj.
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
I partition_point(I first, S last, Pred pred, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
safe_iterator_t<Rng>
partition_point(Rng&& rng, Pred pred, Proj proj = Proj{});
Requires: [first,last) shall be partitioned by pred and proj, i.e. there shall be an iterator mid such that all_of(first, mid, pred, proj) and none_of(mid, last, pred, proj) are both true.
Returns: An iterator mid such that all_of(first, mid, pred, proj) and none_of(mid, last, pred, proj) are both true.
Complexity: Ο(log(last - first)) applications of pred and proj.
11.5 Sorting and related operations [alg.sorting]
All the operations in [alg.sorting] take an optional binary callable predicate of type Comp that defaults to less<>.
Comp is a callable object ( ISO/IEC 14882:2014 §[func.require]). The return value of the invoke operation applied to an object of type Comp, when contextually converted to bool (Clause ISO/IEC 14882:2014 §[conv]), yields true if the first argument of the call is less than the second, and false otherwise. Comp comp is used throughout for algorithms assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.
A sequence is sorted with respect to a comparator and projection comp and proj if for every iterator i pointing to the sequence and every non-negative integer n such that i + n is a valid iterator pointing to an element of the sequence, invoke(comp, invoke(proj, *(i + n)), invoke(proj, *i)) == false.
A sequence [start,finish) is partitioned with respect to an expression f(e) if there exists an integer n such that for all 0 <= i < distance(start, finish), f(*(start + i)) is true if and only if i < n.
In the descriptions of the functions that deal with ordering relationships we frequently use a notion of equivalence to describe concepts such as stability. The equivalence to which we refer is not necessarily an operator==, but an equivalence relation induced by the strict weak ordering. That is, two elements a and b are considered equivalent if and only if !(a < b) && !(b < a).
11.5.1 Sorting [alg.sort]
11.5.1.1 sort [sort]
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
sort(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Sorts the elements in the range [first,last).
Returns: last.
Complexity: Ο(Nlog(N)) (where N == last - first) comparisons, and twice as many applications of the projection.
11.5.1.2 stable_sort [stable.sort]
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I stable_sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
stable_sort(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Sorts the elements in the range [first,last).
Returns: last.
Complexity: Let N == last - first. If enough extra memory is available, N log(N) comparisons. Otherwise, at most N log2(N) comparisons. In either case, twice as many applications of the projection as the number of comparisons.
Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).
11.5.1.3 partial_sort [partial.sort]
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I partial_sort(I first, I middle, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
partial_sort(Rng&& rng, iterator_t<Rng> middle, Comp comp = Comp{},
Proj proj = Proj{});
Returns: last.
Complexity: It takes approximately (last - first) * log(middle - first) comparisons, and exactly twice as many applications of the projection.
11.5.1.4 partial_sort_copy [partial.sort.copy]
template <InputIterator I1, Sentinel<I1> S1, RandomAccessIterator I2, Sentinel<I2> S2,
class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires IndirectlyCopyable<I1, I2> && Sortable<I2, Comp, Proj2> &&
IndirectStrictWeakOrder<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
I2
partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, RandomAccessRange Rng2, class Comp = less<>,
class Proj1 = identity, class Proj2 = identity>
requires IndirectlyCopyable<iterator_t<Rng1>, iterator_t<Rng2>> &&
Sortable<iterator_t<Rng2>, Comp, Proj2> &&
IndirectStrictWeakOrder<Comp, projected<iterator_t<Rng1>, Proj1>,
projected<iterator_t<Rng2>, Proj2>>
safe_iterator_t<Rng2>
partial_sort_copy(Rng1&& rng, Rng2&& result_rng, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Effects: Places the first min(last - first, result_last - result_first) sorted elements into the range [result_first,result_first + min(last - first, result_last - result_first)).
Returns: The smaller of: result_last or result_first + (last - first).
Complexity: Approximately
(last - first) * log(min(last - first, result_last - result_first))
comparisons, and exactly twice as many applications of the projection.
11.5.1.5 is_sorted [is.sorted]
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
bool is_sorted(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
bool
is_sorted(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Returns: is_sorted_until(first, last, comp, proj) == last
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
I is_sorted_until(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
is_sorted_until(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Returns: If distance(first, last) < 2, returns last. Otherwise, returns the last iterator i in [first,last] for which the range [first,i) is sorted.
Complexity: Linear.
11.5.2 Nth element [alg.nth.element]
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I nth_element(I first, I nth, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
nth_element(Rng&& rng, iterator_t<Rng> nth, Comp comp = Comp{}, Proj proj = Proj{});
After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted, unless nth == last. Also for every iterator i in the range [first,nth) and every iterator j in the range [nth,last) it holds that: invoke(comp, invoke(proj, *j), invoke(proj, *i)) == false.
Returns: last.
Complexity: Linear on average.
11.5.3 Binary search [alg.binary.search]
All of the algorithms in this section are versions of binary search and assume that the sequence being searched is partitioned with respect to an expression formed by binding the search key to an argument of the comparison function and projection. They work on non-random access iterators minimizing the number of comparisons, which will be logarithmic for all types of iterators. They are especially appropriate for random access iterators, because these algorithms do a logarithmic number of steps through the data structure. For non-random access iterators they execute a linear number of steps.
11.5.3.1 lower_bound [lower.bound]
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
I
lower_bound(I first, S last, const T& value, Comp comp = Comp{},
Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
lower_bound(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
Requires: The elements e of [first,last) shall be partitioned with respect to the expression invoke(comp, invoke(proj, e), value).
Returns: The furthermost iterator i in the range [first,last] such that for every iterator j in the range [first,i) the following corresponding condition holds: invoke(comp, invoke(proj, *j), value) != false.
Complexity: At most log2(last - first) + Ο(1) applications of the comparison function and projection.
11.5.3.2 upper_bound [upper.bound]
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
I
upper_bound(I first, S last, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
upper_bound(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
Requires: The elements e of [first,last) shall be partitioned with respect to the expression !invoke(comp, value, invoke(proj, e)).
Returns: The furthermost iterator i in the range [first,last] such that for every iterator j in the range [first,i) the following corresponding condition holds: invoke(comp, value, invoke(proj, *j)) == false.
Complexity: At most log2(last - first) + Ο(1) applications of the comparison function and projection.
11.5.3.3 equal_range [equal.range]
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
tagged_pair<tag::begin(I), tag::end(I)>
equal_range(I first, S last, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
tagged_pair<tag::begin(safe_iterator_t<Rng>),
tag::end(safe_iterator_t<Rng>)>
equal_range(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
Requires:
The elements
e
of
[first,last)
shall be partitioned with respect to the expressions
invoke(comp, invoke(proj, e), value)
and
!invoke(comp, value, invoke(proj, e)).
Also, for all elements
e
of
[first, last),
invoke(comp, invoke(proj, e), value)
shall imply
!invoke(comp, value, invoke(proj, e)).
Returns:
Complexity: At most 2 * log2(last - first) + Ο(1) applications of the comparison function and projection.
11.5.3.4 binary_search [binary.search]
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
bool
binary_search(I first, S last, const T& value, Comp comp = Comp{},
Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
bool
binary_search(Rng&& rng, const T& value, Comp comp = Comp{},
Proj proj = Proj{});
Requires: The elements e of [first,last) are partitioned with respect to the expressions invoke(comp, invoke(proj, e), value) and !invoke(comp, value, invoke(proj, e)). Also, for all elements e of [first, last), invoke(comp, invoke(proj, e), value) shall imply !invoke(comp, value, invoke(proj, e)).
Returns: true if there is an iterator i in the range [first,last) that satisfies the corresponding conditions: invoke(comp, invoke(proj, *i), value) == false && invoke(comp, value, invoke(proj, *i)) == false.
Complexity: At most log2(last - first) + Ο(1) applications of the comparison function and projection.
11.5.4 Merge [alg.merge]
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity,
class Proj2 = identity>
requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O, class Comp = less<>,
class Proj1 = identity, class Proj2 = identity>
requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
tag::in2(safe_iterator_t<Rng2>),
tag::out(O)>
merge(Rng1&& rng1, Rng2&& rng2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Effects: Copies all the elements of the two ranges [first1,last1) and [first2,last2) into the range [result,result_last), where result_last is result + (last1 - first1) + (last2 - first2). If an element a precedes b in an input range, a is copied into the output range before b. If e1 is an element of [first1,last1) and e2 of [first2,last2), e2 is copied into the output range before e1 if and only if bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1))) is true.
Requires: The ranges [first1,last1) and [first2,last2) shall be sorted with respect to comp, proj1, and proj2. The resulting range shall not overlap with either of the original ranges.
Returns: make_tagged_tuple<tag::in1, tag::in2, tag::out>(last1, last2, result_last).
Complexity: At most (last1 - first1) + (last2 - first2) - 1 applications of the comparison function and each projection.
Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).
template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I
inplace_merge(I first, I middle, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <BidirectionalRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
inplace_merge(Rng&& rng, iterator_t<Rng> middle, Comp comp = Comp{},
Proj proj = Proj{});
Effects: Merges two sorted consecutive ranges [first,middle) and [middle,last), putting the result of the merge into the range [first,last). The resulting range will be in non-decreasing order; that is, for every iterator i in [first,last) other than first, the condition invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1))) will be false.
Requires: The ranges [first,middle) and [middle,last) shall be sorted with respect to comp and proj.
Returns: last
Complexity: When enough additional memory is available, (last - first) - 1 applications of the comparison function and projection. If no additional memory is available, an algorithm with complexity N log(N) (where N is equal to last - first) may be used.
Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).
11.5.5 Set operations on sorted structures [alg.set.operations]
This section defines all the basic set operations on sorted structures. They also work with multisets ( ISO/IEC 14882:2014 §[multiset]) containing multiple copies of equivalent elements. The semantics of the set operations are generalized to multisets in a standard way by defining set_union() to contain the maximum number of occurrences of every element, set_intersection() to contain the minimum, and so on.
11.5.5.1 includes [includes]
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
class Proj1 = identity, class Proj2 = identity,
IndirectStrictWeakOrder<projected<I1, Proj1>, projected<I2, Proj2>> Comp = less<>>
bool
includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, class Proj1 = identity,
class Proj2 = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng1>, Proj1>,
projected<iterator_t<Rng2>, Proj2>> Comp = less<>>
bool
includes(Rng1&& rng1, Rng2&& rng2, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Returns: true if [first2,last2) is empty or if every element in the range [first2,last2) is contained in the range [first1,last1). Returns false otherwise.
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 applications of the comparison function and projections.
11.5.5.2 set_union [set.union]
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
tag::in2(safe_iterator_t<Rng2>),
tag::out(O)>
set_union(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Effects: Constructs a sorted union of the elements from the two ranges; that is, the set of elements that are present in one or both of the ranges.
Requires: The resulting range shall not overlap with either of the original ranges.
Returns:
make_tagged_tuple<tag::in1, tag::in2, tag::out>(last1, last2, result + n),
where n is
the number of elements in the constructed range.
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 applications of the comparison function and projections.
Remarks: If [first1,last1) contains m elements that are equivalent to each other and [first2,last2) contains n elements that are equivalent to them, then all m elements from the first range shall be copied to the output range, in order, and then max(n - m, 0) elements from the second range shall be copied to the output range, in order.
11.5.5.3 set_intersection [set.intersection]
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
O
set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
O
set_intersection(Rng1&& rng1, Rng2&& rng2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Effects: Constructs a sorted intersection of the elements from the two ranges; that is, the set of elements that are present in both of the ranges.
Requires: The resulting range shall not overlap with either of the original ranges.
Returns: The end of the constructed range.
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 applications of the comparison function and projections.
Remarks: If [first1,last1) contains m elements that are equivalent to each other and [first2,last2) contains n elements that are equivalent to them, the first min(m, n) elements shall be copied from the first range to the output range, in order.
11.5.5.4 set_difference [set.difference]
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
tagged_pair<tag::in1(I1), tag::out(O)>
set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::out(O)>
set_difference(Rng1&& rng1, Rng2&& rng2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Effects: Copies the elements of the range [first1,last1) which are not present in the range [first2,last2) to the range beginning at result. The elements in the constructed range are sorted.
Requires: The resulting range shall not overlap with either of the original ranges.
Returns: {last1, result + n}, where n is the number of elements in the constructed range.
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 applications of the comparison function and projections.
Remarks: If [first1,last1) contains m elements that are equivalent to each other and [first2,last2) contains n elements that are equivalent to them, the last max(m - n, 0) elements from [first1,last1) shall be copied to the output range.
11.5.5.5 set_symmetric_difference [set.symmetric.difference]
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{},
Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
tag::in2(safe_iterator_t<Rng2>),
tag::out(O)>
set_symmetric_difference(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Effects: Copies the elements of the range [first1,last1) that are not present in the range [first2,last2), and the elements of the range [first2,last2) that are not present in the range [first1,last1) to the range beginning at result. The elements in the constructed range are sorted.
Requires: The resulting range shall not overlap with either of the original ranges.
Returns:
make_tagged_tuple<tag::in1, tag::in2, tag::out>(last1, last2, result + n),
where n is
the number of elements in the constructed range.
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 applications of the comparison function and projections.
Remarks: If [first1,last1) contains m elements that are equivalent to each other and [first2,last2) contains n elements that are equivalent to them, then |m - n| of those elements shall be copied to the output range: the last m - n of these elements from [first1,last1) if m > n, and the last n - m of these elements from [first2,last2) if m < n.
11.5.6 Heap operations [alg.heap.operations]
A heap is a particular organization of elements in a range between two random access iterators [a,b). Its two key properties are:
There is no element greater than *a in the range and
*a may be removed by pop_heap(), or a new element added by push_heap(), in Ο(log(N)) time.
These properties make heaps useful as priority queues.
make_heap() converts a range into a heap and sort_heap() turns a heap into a sorted sequence.
11.5.6.1 push_heap [push.heap]
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I push_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
push_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Places the value in the location last - 1 into the resulting heap [first,last).
Requires: The range [first,last - 1) shall be a valid heap.
Returns: last
Complexity: At most log(last - first) applications of the comparison function and projection.
11.5.6.2 pop_heap [pop.heap]
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I pop_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
pop_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Requires: The range [first,last) shall be a valid non-empty heap.
Effects: Swaps the value in the location first with the value in the location last - 1 and makes [first,last - 1) into a heap.
Returns: last
Complexity: At most 2 * log(last - first) applications of the comparison function and projection.
11.5.6.3 make_heap [make.heap]
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I make_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
make_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Constructs a heap out of the range [first,last).
Returns: last
Complexity: At most 3 * (last - first) applications of the comparison function and projection.
11.5.6.4 sort_heap [sort.heap]
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I sort_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
sort_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Sorts elements in the heap [first,last).
Requires: The range [first,last) shall be a valid heap.
Returns: last
Complexity: At most N log(N) comparisons (where N == last - first), and exactly twice as many applications of the projection.
11.5.6.5 is_heap [is.heap]
template <RandomAccessIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
bool is_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
bool
is_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Returns: is_heap_until(first, last, comp, proj) == last
template <RandomAccessIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
I is_heap_until(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
is_heap_until(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Returns: If distance(first, last) < 2, returns last. Otherwise, returns the last iterator i in [first,last] for which the range [first,i) is a heap.
Complexity: Linear.
11.5.7 Minimum and maximum [alg.min.max]
template <class T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr const T& min(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});
Returns: The smaller value.
Remarks: Returns the first argument when the arguments are equivalent.
template <Copyable T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr T min(initializer_list<T> rng, Comp comp = Comp{}, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
requires Copyable<value_type_t<iterator_t<Rng>>>
value_type_t<iterator_t<Rng>>
min(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Requires: distance(rng) > 0.
Returns: The smallest value in the initializer_list or range.
Remarks: Returns a copy of the leftmost argument when several arguments are equivalent to the smallest.
template <class T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr const T& max(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});
Returns: The larger value.
Remarks: Returns the first argument when the arguments are equivalent.
template <Copyable T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr T max(initializer_list<T> rng, Comp comp = Comp{}, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
requires Copyable<value_type_t<iterator_t<Rng>>>
value_type_t<iterator_t<Rng>>
max(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Requires: distance(rng) > 0.
Returns: The largest value in the initializer_list or range.
Remarks: Returns a copy of the leftmost argument when several arguments are equivalent to the largest.
template <class T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr tagged_pair<tag::min(const T&), tag::max(const T&)>
minmax(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});
Returns: {b, a} if b is smaller than a, and {a, b} otherwise.
Remarks: Returns {a, b} when the arguments are equivalent.
Complexity: Exactly one comparison and exactly two applications of the projection.
template <Copyable T, class Proj = identity,
IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
constexpr tagged_pair<tag::min(T), tag::max(T)>
minmax(initializer_list<T> rng, Comp comp = Comp{}, Proj proj = Proj{});
template <InputRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj> Comp = less<>>
requires Copyable<value_type_t<iterator_t<Rng>>>
tagged_pair<tag::min(value_type_t<iterator_t<Rng>>),
tag::max(value_type_t<iterator_t<Rng>>)>
minmax(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Requires: distance(rng) > 0.
Returns: {x, y}, where x has the smallest and y has the largest value in the initializer_list or range.
Remarks: x is a copy of the leftmost argument when several arguments are equivalent to the smallest. y is a copy of the rightmost argument when several arguments are equivalent to the largest.
Complexity: At most (3/2) * distance(rng) applications of the corresponding predicate, and at most twice as many applications of the projection.
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
I min_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
min_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Returns:
The first iterator
i
in the range
[first,last)
such that for every iterator
j
in the range
[first,last)
the following corresponding condition holds:
invoke(comp, invoke(proj, *j), invoke(proj, *i)) == false.
Returns
last
if
first == last.
Complexity: Exactly max((last - first) - 1, 0) applications of the comparison function and exactly twice as many applications of the projection.
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
I max_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
max_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Returns:
The first iterator
i
in the range
[first,last)
such that for every iterator
j
in the range
[first,last)
the following corresponding condition holds:
invoke(comp, invoke(proj, *i), invoke(proj, *j)) == false.
Returns
last
if
first == last.
Complexity: Exactly max((last - first) - 1, 0) applications of the comparison function and exactly twice as many applications of the projection.
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
tagged_pair<tag::min(I), tag::max(I)>
minmax_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
tagged_pair<tag::min(safe_iterator_t<Rng>),
tag::max(safe_iterator_t<Rng>)>
minmax_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Returns: {first, first} if [first,last) is empty, otherwise {m, M}, where m is the first iterator in [first,last) such that no iterator in the range refers to a smaller element, and where M is the last iterator in [first,last) such that no iterator in the range refers to a larger element.
Complexity:
At most
applications of the comparison function and
at most twice as many applications of the projection,
where N is distance(first, last).
11.5.8 Lexicographical comparison [alg.lex.comparison]
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
class Proj1 = identity, class Proj2 = identity,
IndirectStrictWeakOrder<projected<I1, Proj1>, projected<I2, Proj2>> Comp = less<>>
bool
lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, class Proj1 = identity,
class Proj2 = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng1>, Proj1>,
projected<iterator_t<Rng2>, Proj2>> Comp = less<>>
bool
lexicographical_compare(Rng1&& rng1, Rng2&& rng2, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Returns: true if the sequence of elements defined by the range [first1,last1) is lexicographically less than the sequence of elements defined by the range [first2,last2) and false otherwise.
Complexity: At most 2*min((last1 - first1), (last2 - first2)) applications of the corresponding comparison and projections.
Remarks: If two sequences have the same number of elements and their corresponding elements are equivalent, then neither sequence is lexicographically less than the other. If one sequence is a prefix of the other, then the shorter sequence is lexicographically less than the longer sequence. Otherwise, the lexicographical comparison of the sequences yields the same result as the comparison of the first corresponding pair of elements that are not equivalent.
for ( ; first1 != last1 && first2 != last2 ; ++first1, (void) ++first2) {
if (invoke(comp, invoke(proj1, *first1), invoke(proj2, *first2))) return true;
if (invoke(comp, invoke(proj2, *first2), invoke(proj1, *first1))) return false;
}
return first1 == last1 && first2 != last2;
Remarks: An empty sequence is lexicographically less than any non-empty sequence, but not less than any empty sequence.
11.5.9 Permutation generators [alg.permutation.generators]
template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
bool next_permutation(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <BidirectionalRange Rng, class Comp = less<>,
class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
bool
next_permutation(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Takes a sequence defined by the range [first,last) and transforms it into the next permutation. The next permutation is found by assuming that the set of all permutations is lexicographically sorted with respect to comp and proj. If such a permutation exists, it returns true. Otherwise, it transforms the sequence into the smallest permutation, that is, the ascendingly sorted one, and returns false.
Complexity: At most (last - first)/2 swaps.
template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
bool prev_permutation(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <BidirectionalRange Rng, class Comp = less<>,
class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
bool
prev_permutation(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Takes a sequence defined by the range [first,last) and transforms it into the previous permutation. The previous permutation is found by assuming that the set of all permutations is lexicographically sorted with respect to comp and proj.
Returns: true if such a permutation exists. Otherwise, it transforms the sequence into the largest permutation, that is, the descendingly sorted one, and returns false.
Complexity: At most (last - first)/2 swaps.