The operations in [alg.sorting] defined directly in namespace std have two versions: one that takes a function object of type Compare and one that uses an operator<.

The return value of the function call operation applied to an object of type Compare, when converted to bool, yields true if the first argument of the call is less than the second, and false otherwise.

Compare comp is used throughout for algorithms assuming an ordering relation.

For all algorithms that take Compare, there is a version that uses operator< instead.

That is, comp(*i, *j) != false defaults to *i < *j != false.

For algorithms other than those described in [alg.binary.search], comp shall induce a strict weak ordering on the values.

The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering.

A sequence is sorted with respect to a comp and proj for 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, bool(invoke(comp, invoke(proj, *(i + n)), invoke(proj, *i))) is false.

A sequence is sorted with respect to a comparator comp for a comparator comp if it is sorted with respect to comp and identity{} (the identity projection).

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 < (finish - start), 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).

template<class RandomAccessIterator> constexpr void sort(RandomAccessIterator first, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator> void sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> constexpr void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> void sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> constexpr I ranges::sort(I first, S last, Comp comp = {}, Proj proj = {}); template<random_access_range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> constexpr borrowed_iterator_t<R> ranges::sort(R&& r, Comp comp = {}, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> I ranges::sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> borrowed_iterator_t<R> ranges::sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});

Let comp be less{} and proj be identity{} for the overloads with no parameters by those names.

Effects: Sorts the elements in the range [first, last) with respect to comp and proj.

Returns: last for the overloads in namespace ranges.

Complexity: Let N be last - first.

comparisons and projections.

template<class RandomAccessIterator> constexpr void stable_sort(RandomAccessIterator first, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator> void stable_sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> constexpr void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> void stable_sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> constexpr I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {}); template<random_access_range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> constexpr borrowed_iterator_t<R> ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> I ranges::stable_sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> borrowed_iterator_t<R> ranges::stable_sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});

Let comp be less{} and proj be identity{} for the overloads with no parameters by those names.

Effects: Sorts the elements in the range [first, last) with respect to comp and proj.

Returns: last for the overloads in namespace ranges.

Complexity: Let N be last - first.

If enough extra memory is available, comparisons.

Otherwise, at most comparisons.

In either case, twice as many projections as the number of comparisons.

template<class RandomAccessIterator> constexpr void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator> void partial_sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> constexpr void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> void partial_sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> constexpr I ranges::partial_sort(I first, I middle, S last, Comp comp = {}, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> I ranges::partial_sort(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {});

Let comp be less{} and proj be identity{} for the overloads with no parameters by those names.

Preconditions: [first, middle) and [middle, last) are valid ranges.

Effects: Places the first middle - first elements from the range [first, last) as sorted with respect to comp and proj into the range [first, middle).

The rest of the elements in the range [middle, last) are placed in an unspecified order.

Returns: last for the overload in namespace ranges.

Complexity: Approximately (last - first) * log(middle - first) comparisons, and twice as many projections.

template<random_access_range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> constexpr borrowed_iterator_t<R> ranges::partial_sort(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});

Effects: Equivalent to: return ranges::partial_sort(ranges::begin(r), middle, ranges::end(r), comp, proj);

template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> borrowed_iterator_t<R> ranges::partial_sort(Ep&& exec, R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});

Effects: Equivalent to: return ranges::partial_sort(std::forward<Ep>(exec), ranges::begin(r), middle, ranges::begin(r) + ranges::distance(r), comp, proj);

template<class InputIterator, class RandomAccessIterator> constexpr RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template<class InputIterator, class RandomAccessIterator, class Compare> constexpr RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); template<input_iterator I1, sentinel_for<I1> S1, random_access_iterator I2, sentinel_for<I2> S2, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> && indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>> constexpr ranges::partial_sort_copy_result<I1, I2> ranges::partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_range R1, random_access_range R2, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> && sortable<iterator_t<R2>, Comp, Proj2> && indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>> constexpr ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>> ranges::partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2, sized_sentinel_for<I2> S2, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> && indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>> ranges::partial_sort_copy_result<I1, I2> ranges::partial_sort_copy(Ep&& exec, I1 first, S1 last, I2 result_first, S2 result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> && sortable<iterator_t<R2>, Comp, Proj2> && indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>> ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>> ranges::partial_sort_copy(Ep&& exec, R1&& r, R2&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});

Let N be min(last - first,  result_last - result_first).

Let comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names.

For iterators a1 and b1 in [first, last), and iterators x2 and y2 in [result_first, result_last), after evaluating the assignment *y2 = *b1, let E be the value of bool(invoke(comp, invoke(proj1, *a1), invoke(proj2, *y2))).

Effects: Places the first N elements as sorted with respect to comp and proj2 into the range [result_first, result_first + N).

Returns:

• result_first + N for the overloads in namespace std.

• {last, result_first + N} for the overloads in namespace ranges.

Complexity: Approximately (last - first) * log N comparisons, and twice as many projections.

template<class ForwardIterator> constexpr bool is_sorted(ForwardIterator first, ForwardIterator last);

Effects: Equivalent to: return is_sorted_until(first, last) == last;

template<class ExecutionPolicy, class ForwardIterator> bool is_sorted(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last);

Effects: Equivalent to: return is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last) == last;

template<class ForwardIterator, class Compare> constexpr bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);

Effects: Equivalent to: return is_sorted_until(first, last, comp) == last;

template<class ExecutionPolicy, class ForwardIterator, class Compare> bool is_sorted(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Compare comp);

Effects: Equivalent to: return is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last;

template<forward_iterator I, sentinel_for<I> S, class Proj = identity, indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> constexpr bool ranges::is_sorted(I first, S last, Comp comp = {}, Proj proj = {}); template<forward_range R, class Proj = identity, indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr bool ranges::is_sorted(R&& r, Comp comp = {}, Proj proj = {});

Effects: Equivalent to: return ranges​::​is_sorted_until(first, last, comp, proj) == last;

template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity, indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> bool ranges::is_sorted(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<execution-policy Ep, sized-random-access-range R, class Proj = identity, indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> bool ranges::is_sorted(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});

Effects: Equivalent to: return ranges::is_sorted_until(std::forward<Ep>(exec), first, last, comp, proj) == last;

template<class ForwardIterator> constexpr ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator is_sorted_until(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class Compare> constexpr ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); template<class ExecutionPolicy, class ForwardIterator, class Compare> ForwardIterator is_sorted_until(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Compare comp); template<forward_iterator I, sentinel_for<I> S, class Proj = identity, indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> constexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {}); template<forward_range R, class Proj = identity, indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr borrowed_iterator_t<R> ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity, indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> I ranges::is_sorted_until(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<execution-policy Ep, sized-random-access-range R, class Proj = identity, indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> borrowed_iterator_t<R> ranges::is_sorted_until(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});

Let comp be less{} and proj be identity{} for the overloads with no parameters by those names.

Returns: The last iterator i in [first, last] for which the range [first, i) is sorted with respect to comp and proj.

template<class RandomAccessIterator> constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator> void nth_element(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> void nth_element(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> constexpr I ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> I ranges::nth_element(Ep&& exec, I first, I nth, S last, Comp comp = {}, Proj proj = {});

Let comp be less{} and proj be identity{} for the overloads with no parameters by those names.

Preconditions: [first, nth) and [nth, last) are valid ranges.

Effects: 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 with respect to comp and proj, 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: bool(invoke(comp, invoke(proj, *j), invoke(proj, *i))) is false.

Returns: last for the overload in namespace ranges.

Complexity: For the non-parallel algorithm overloads, linear on average.

For the parallel algorithm overloads, applications of the predicate, and swaps, where .

template<random_access_range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> constexpr borrowed_iterator_t<R> ranges::nth_element(R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {});

Effects: Equivalent to: return ranges::nth_element(ranges::begin(r), nth, ranges::end(r), comp, proj);

template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> borrowed_iterator_t<R> ranges::nth_element(Ep&& exec, R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {});

Effects: Equivalent to: return ranges::nth_element(std::forward<Ep>(exec), ranges::begin(r), nth, ranges::begin(r) + ranges::distance(r), comp, proj);

All of the algorithms in [alg.binary.search] 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.

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.

template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type> constexpr ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type, class Compare> constexpr ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); template<forward_iterator I, sentinel_for<I> S, class Proj = identity, class T = projected_value_t<I, Proj>, indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less> constexpr I ranges::lower_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); template<forward_range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>, indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr borrowed_iterator_t<R> ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});

Let comp be less{} and proj be identity{} for overloads with no parameters by those names.

Preconditions: The elements e of [first, last) are partitioned with respect to the expression

bool(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), bool(invoke(comp, invoke(proj, *j), value)) is true.

Complexity: At most comparisons and projections.

template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type> constexpr ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type, class Compare> constexpr ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); template<forward_iterator I, sentinel_for<I> S, class Proj = identity, class T = projected_value_t<I, Proj>, indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less> constexpr I ranges::upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); template<forward_range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>, indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr borrowed_iterator_t<R> ranges::upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});

Let comp be less{} and proj be identity{} for overloads with no parameters by those names.

Preconditions: The elements e of [first, last) are partitioned with respect to the expression

!bool(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), !bool(invoke(comp, value, invoke(proj, *j))) is true.

Complexity: At most comparisons and projections.

template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type> constexpr pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type, class Compare> constexpr pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); template<forward_iterator I, sentinel_for<I> S, class Proj = identity, class T = projected_value_t<I, Proj>, indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less> constexpr subrange<I> ranges::equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); template<forward_range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>, indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr borrowed_subrange_t<R> ranges::equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});

Let comp be less{} and proj be identity{} for overloads with no parameters by those names.

Preconditions: The elements e of [first, last) are partitioned with respect to the expressions bool(invoke(comp, invoke(proj, e), value)) and !bool(invoke(comp, value, invoke(proj, e))).

Also, for all elements e of [first, last), bool(comp(e, value)) implies !bool(comp(​value, e)) for the overloads in namespace std.

Returns:

• For the overloads in namespace std: {lower_bound(first, last, value, comp), upper_bound(first, last, value, comp)}
• For the overloads in namespace ranges: {ranges::lower_bound(first, last, value, comp, proj), ranges::upper_bound(first, last, value, comp, proj)}

Complexity: At most comparisons and projections.

template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type> constexpr bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type, class Compare> constexpr bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); template<forward_iterator I, sentinel_for<I> S, class Proj = identity, class T = projected_value_t<I, Proj>, indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less> constexpr bool ranges::binary_search(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); template<forward_range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>, indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr bool ranges::binary_search(R&& r, const T& value, Comp comp = {}, Proj proj = {});

Let comp be less{} and proj be identity{} for overloads with no parameters by those names.

Preconditions: The elements e of [first, last) are partitioned with respect to the expressions bool(invoke(comp, invoke(proj, e), value)) and !bool(invoke(comp, value, invoke(proj, e))).

Also, for all elements e of [first, last), bool(comp(e, value)) implies !bool(comp(​value, e)) for the overloads in namespace std.

Returns: true if and only if for some iterator i in the range [first, last), !bool(invoke(comp, invoke(proj, *i), value)) && !bool(invoke(comp, value, invoke(proj, *i))) is true.

Complexity: At most comparisons and projections.

template<class InputIterator, class Predicate> constexpr bool is_partitioned(InputIterator first, InputIterator last, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class Predicate> bool is_partitioned(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred); template<input_iterator I, sentinel_for<I> S, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {}); template<input_range R, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> bool ranges::is_partitioned(Ep&& exec, I first, S last, Pred pred, Proj proj = {}); template<execution-policy Ep, sized-random-access-range R, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> bool ranges::is_partitioned(Ep&& exec, R&& r, Pred pred, Proj proj = {});

Let proj be identity{} for the overloads with no parameter named proj.

Returns: true if and only if the elements e of [first, last) are partitioned with respect to the expression bool(invoke(pred, invoke(proj, e))).

Complexity: Linear.

At most last - first applications of pred and proj.

template<class ForwardIterator, class Predicate> constexpr ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class Predicate> ForwardIterator partition(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred); template<permutable I, sentinel_for<I> S, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> constexpr subrange<I> ranges::partition(I first, S last, Pred pred, Proj proj = {}); template<forward_range R, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> requires permutable<iterator_t<R>> constexpr borrowed_subrange_t<R> ranges::partition(R&& r, Pred pred, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> requires permutable<I> subrange<I> ranges::partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {}); template<execution-policy Ep, sized-random-access-range R, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> requires permutable<iterator_t<R>> borrowed_subrange_t<R> ranges::partition(Ep&& exec, R&& r, Pred pred, Proj proj = {});

Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x))).

Effects: Places all the elements e in [first, last) that satisfy E(e) before all the elements that do not.

Returns: Let i be an iterator such that E(*j) is true for every iterator j in [first, i) and false for every iterator j in [i, last).

Complexity: Let :

• For the non-parallel algorithm overloads, exactly N applications of the predicate and projection.

  At most swaps if the type of first meets the Cpp17BidirectionalIterator requirements for the overloads in namespace std or models bidirectional_iterator for the overloads in namespace ranges, and at most N swaps otherwise.

• For the parallel algorithm overloads, swaps and applications of the predicate.

template<class BidirectionalIterator, class Predicate> BidirectionalIterator constexpr stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred); template<class ExecutionPolicy, class BidirectionalIterator, class Predicate> BidirectionalIterator stable_partition(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator last, Predicate pred); template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> requires permutable<I> constexpr subrange<I> ranges::stable_partition(I first, S last, Pred pred, Proj proj = {}); template<bidirectional_range R, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> requires permutable<iterator_t<R>> constexpr borrowed_subrange_t<R> ranges::stable_partition(R&& r, Pred pred, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> requires permutable<I> subrange<I> ranges::stable_partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {}); template<execution-policy Ep, sized-random-access-range R, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> requires permutable<iterator_t<R>> borrowed_subrange_t<R> ranges::stable_partition(Ep&& exec, R&& r, Pred pred, Proj proj = {});

Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x))).

Effects: Places all the elements e in [first, last) that satisfy E(e) before all the elements that do not.

The relative order of the elements in both groups is preserved.

Returns: Let i be an iterator such that for every iterator j in [first, i), E(*j) is true, and for every iterator j in the range [i, last), E(*j) is false.

Complexity: Let N = last - first:

• For the non-parallel algorithm overloads, at most swaps, but only swaps if there is enough extra memory.

  Exactly N applications of the predicate and projection.

• For the parallel algorithm overloads, swaps and applications of the predicate.

template<class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate> constexpr pair<OutputIterator1, OutputIterator2> partition_copy(InputIterator first, InputIterator last, OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class ForwardIterator1, class ForwardIterator2, class Predicate> pair<ForwardIterator1, ForwardIterator2> partition_copy(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, ForwardIterator1 out_true, ForwardIterator2 out_false, Predicate pred); template<input_iterator I, sentinel_for<I> S, weakly_incrementable O1, weakly_incrementable O2, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2> constexpr ranges::partition_copy_result<I, O1, O2> ranges::partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred, Proj proj = {}); template<input_range R, weakly_incrementable O1, weakly_incrementable O2, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> requires indirectly_copyable<iterator_t<R>, O1> && indirectly_copyable<iterator_t<R>, O2> constexpr ranges::partition_copy_result<borrowed_iterator_t<R>, O1, O2> ranges::partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, random_access_iterator O1, sized_sentinel_for<O1> OutS1, random_access_iterator O2, sized_sentinel_for<O2> OutS2, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2> ranges::partition_copy_result<I, O1, O2> ranges::partition_copy(Ep&& exec, I first, S last, O1 out_true, OutS1 last_true, O2 out_false, OutS2 last_false, Pred pred, Proj proj = {}); template<execution-policy Ep, sized-random-access-range R, sized-random-access-range OutR1, sized-random-access-range OutR2, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> requires indirectly_copyable<iterator_t<R>, iterator_t<OutR1>> && indirectly_copyable<iterator_t<R>, iterator_t<OutR2>> ranges::partition_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR1>, borrowed_iterator_t<OutR2>> ranges::partition_copy(Ep&& exec, R&& r, OutR1&& out_true_r, OutR2&& out_false_r, Pred pred, Proj proj = {});

Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x))).

For the overloads with no parameters last_true, last_false, out_true_r, or out_false_r, let

• M be the number of iterators i in [first, last) for which E(*i) is true, and K be last - first - M;
• last_true be out_true + M, and last_false be out_false + K.

For the overloads with parameters last_true, last_false, out_true_r, or out_false_r, let M be last_true - out_true and K be last_false - out_false.

Let:

• i1 be the iterator in [first, last) for which E(*i1) is true and there are exactly M iterators j in [first, i1) for which E(*j) is true, or last if no such iterator exists;
• i2 be the iterator in [first, last) for which E(*i2) is false and there are exactly K iterators j in [first, i2) for which E(*j) is false, or last if no such iterator exists;
• N be min(i1 - first,  i2 - first).

Effects: For each iterator i in [first, first + N), copies *i to the output range [out_true, last_true) if E(*i) is true, or to the output range [out_false, last_false) otherwise.

Returns: Let Q be the number of elements copied into the output range [out_true, last_true), and V be the number of elements copied into the output range [out_false, last_false).

Complexity: At most last - first applications of pred and proj.

template<class ForwardIterator, class Predicate> constexpr ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); template<forward_iterator I, sentinel_for<I> S, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> constexpr I ranges::partition_point(I first, S last, Pred pred, Proj proj = {}); template<forward_range R, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> constexpr borrowed_iterator_t<R> ranges::partition_point(R&& r, Pred pred, Proj proj = {});

Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x))).

Preconditions: The elements e of [first, last) are partitioned with respect to E(e).

Returns: An iterator mid such that E(*i) is true for all iterators i in [first, mid), and false for all iterators i in [mid, last).

Complexity: applications of pred and proj.

template<class InputIterator1, class InputIterator2, class OutputIterator> constexpr OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator merge(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> constexpr OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator merge(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::merge_result<I1, I2, O> ranges::merge(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O> ranges::merge(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2, sized_sentinel_for<I2> S2, random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> ranges::merge_result<I1, I2, O> ranges::merge(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result, OutS result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2, sized-random-access-range OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2> ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>> ranges::merge(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});

Let:

• N be:
  • (last1 - first1) + (last2 - first2) for the overloads with no parameter result_last or result_r;
  • min((last1 - first1) + (last2 - first2),  result_last - result) for the overloads with parameters result_last or result_r;
• comp be less{}, proj1 be identity{}, and proj2 be identity{}, for the overloads with no parameters by those names;
• E be bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)));
• K be the smallest integer in [0, last1 - first1) such that for the element e1 in the position first1 + K there are at least elements e2 in [first2, last2) for which E holds, and be equal to last1 - first1 if no such integer exists.

  [Note 1:

  first1 + K points to the position past the last element to be copied.

  — end note]

Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.

The resulting range does not overlap with either of the original ranges.

Effects: Copies the first K elements of the range [first1, last1) and the first elements of the range [first2, last2) into the range [result, result + N).

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 E is true.

Returns:

• result + N for the overloads in namespace std.

• {first1 + K, first2 + N - K, result + N} for the overloads in namespace ranges.

Complexity:

• For the non-parallel algorithm overloads, at most comparisons and applications of each projection.

• For the parallel algorithm overloads, comparisons and applications of each projection.

template<class BidirectionalIterator> constexpr void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); template<class ExecutionPolicy, class BidirectionalIterator> void inplace_merge(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); template<class BidirectionalIterator, class Compare> constexpr void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); template<class ExecutionPolicy, class BidirectionalIterator, class Compare> void inplace_merge(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> constexpr I ranges::inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> I ranges::inplace_merge(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {});

Let comp be less{} and proj be identity{} for the overloads with no parameters by those names.

Preconditions: [first, middle) and [middle, last) are valid ranges sorted with respect to comp and 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 is sorted with respect to comp and proj.

Returns: last for the overload in namespace ranges.

In either case, twice as many projections as comparisons.

template<bidirectional_range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> constexpr borrowed_iterator_t<R> ranges::inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});

Effects: Equivalent to: return ranges::inplace_merge(ranges::begin(r), middle, ranges::end(r), comp, proj);

template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> borrowed_iterator_t<R> ranges::inplace_merge(Ep&& exec, R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});

Effects: Equivalent to: return ranges::inplace_merge(std::forward<Ep>(exec), ranges::begin(r), middle, ranges::begin(r) + ranges::distance(r), comp, proj);

Subclause [alg.set.operations] defines all the basic set operations on sorted structures.

They also work with multisets ([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.

template<class InputIterator1, class InputIterator2> constexpr bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> bool includes(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class InputIterator1, class InputIterator2, class Compare> constexpr bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare> bool includes(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, Compare comp); template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity, indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp = ranges::less> constexpr bool ranges::includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_range R1, input_range R2, class Proj1 = identity, class Proj2 = identity, indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>> Comp = ranges::less> constexpr bool ranges::includes(R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2, sized_sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity, indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp = ranges::less> bool ranges::includes(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2, class Proj1 = identity, class Proj2 = identity, indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>> Comp = ranges::less> bool ranges::includes(Ep&& exec, R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});

Let comp be less{}, proj1 be identity{}, and proj2 be identity{}, for the overloads with no parameters by those names.

Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.

Returns: true if and only if [first2, last2) is a subsequence of [first1, last1).

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.

template<class InputIterator1, class InputIterator2, class OutputIterator> constexpr OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_union(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> constexpr OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_union(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::set_union_result<I1, I2, O> ranges::set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O> ranges::set_union(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2, sized_sentinel_for<I2> S2, random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> ranges::set_union_result<I1, I2, O> ranges::set_union(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result, OutS result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2, sized-random-access-range OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2> ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>> ranges::set_union(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});

Let:

• comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names;
• M be the number of elements in the sorted union (see below);
• result_last be result + M for the overloads with no parameter result_last or result_r;
• N be min(M,  result_last - result).

Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.

The resulting range does not overlap with either of the original ranges.

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.

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 are included in the union, in order, and then the final elements from the second range are included in the union, in order.

If, of those elements, k elements from the first range are copied to the output range, then the first elements from the second range are considered skipped.

Copies the first N elements of the sorted union to the range [result, result + N).

Returns:

• result_last for the overloads in namespace std.

• {last1, last2, result + N} for the overloads in namespace ranges, if N is equal to M.

• Otherwise, {first1 + A, first2 + B, result_last} for the overloads in namespace ranges, where A and B are the numbers of copied or skipped elements in [first1, last1) and [first2, last2), respectively.

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.

template<class InputIterator1, class InputIterator2, class OutputIterator> constexpr OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_intersection(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> constexpr OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_intersection(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::set_intersection_result<I1, I2, O> ranges::set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O> ranges::set_intersection(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2, sized_sentinel_for<I2> S2, random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> ranges::set_intersection_result<I1, I2, O> ranges::set_intersection(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result, OutS result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2, sized-random-access-range OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2> ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>> ranges::set_intersection(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});

Let:

• comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names;
• M be the number of elements in the sorted intersection (see below);
• result_last be result + M for the overloads with no parameter result_last or result_r;
• N be min(M,  result_last - result).

Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.

The resulting range does not overlap with either of the original ranges.

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.

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 elements from the first range are included in the sorted intersection.

If, of those elements, k elements from the first range are copied to the output range, then the first k elements from the second range are considered skipped.

If , a non-copied element is also considered skipped if it compares less than the element of the sorted intersection.

Copies the first N elements of the sorted intersection to the range [result, result + N).

Returns:

• result_last for the overloads in namespace std.

• {last1, last2, result + N} for the overloads in namespace ranges, if N is equal to M.

• Otherwise, {first1 + A, first2 + B, result_last} for the overloads in namespace ranges, where A and B are the numbers of copied or skipped elements in [first1, last1) and [first2, last2), respectively.

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.

template<class InputIterator1, class InputIterator2, class OutputIterator> constexpr OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> constexpr OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::set_difference_result<I1, O> ranges::set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::set_difference_result<borrowed_iterator_t<R1>, O> ranges::set_difference(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2, sized_sentinel_for<I2> S2, random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> ranges::set_difference_result<I1, O> ranges::set_difference(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result, OutS result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2, sized-random-access-range OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2> ranges::set_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<OutR>> ranges::set_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});

Let:

• comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names;
• M be the number of elements in the sorted difference (see below);
• result_last be result + M for the overloads with no parameter result_last or result_r;
• N be min(M,  result_last - result).

Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.

The resulting range does not overlap with either of the original ranges.

Effects: Constructs a sorted difference between the elements from the two ranges; that is, the set of elements that are present in the range [first1, last1) but not [first2, last2).

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 elements from [first1, last1) are included in the sorted difference, in order.

Copies the first N elements of the sorted difference to the range [result, result + N).

Returns:

• result_last for the overloads in namespace std.

• {last1, result + N} for the overloads in namespace ranges, if N is equal to M.

• Otherwise, {j1, result_last} for the overloads in namespace ranges, where the iterator j1 points to the position of the element in [first1, last1) corresponding to the element of the sorted difference.

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.

template<class InputIterator1, class InputIterator2, class OutputIterator> constexpr OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_symmetric_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> constexpr OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_symmetric_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::set_symmetric_difference_result<I1, I2, O> ranges::set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O> ranges::set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2, sized_sentinel_for<I2> S2, random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> ranges::set_symmetric_difference_result<I1, I2, O> ranges::set_symmetric_difference(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result, OutS result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2, sized-random-access-range OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2> ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>> ranges::set_symmetric_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});

Let:

• comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names;
• M be the number of elements in the sorted symmetric difference (see below);
• result_last be result + M for the overloads with no parameter result_last or result_r;
• N be min(M,  result_last - result).

Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.

The resulting range does not overlap with either of the original ranges.

Effects: Constructs a sorted symmetric difference of the elements from the two ranges; that is, the set of elements that are present in exactly one of [first1, last1) and [first2, last2).

If [first1, last1) contains m elements that are equivalent to each other and [first2, last2) contains n elements that are equivalent to them, then of those elements are included in the symmetric difference: the last of these elements from [first1, last1), in order, if , and the last of these elements from [first2, last2), in order, if .

If , a non-copied element is considered skipped if it compares less than or equivalent to the element of the sorted symmetric difference, unless it is from the same range as that element and does not precede it.

Copies the first N elements of the sorted symmetric difference to the range [result, result + N).

Returns:

• result_last for the overloads in namespace std.

• {last1, last2, result + N} for the overloads in namespace ranges, if N is equal to .

• Otherwise, {first1 + A, first2 + B, result_last} for the overloads in namespace ranges, where A and B are the numbers of copied or skipped elements in [first1, last1) and [first2, last2), respectively.

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.

A random access range [a, b) is a heap with respect to comp and proj for a comparator and projection comp and proj if its elements are organized such that:

• With N = b - a, for all i, , bool(invoke(comp, invoke(proj, a[]), invoke(​proj, a[i]))) is false.

• *a may be removed by pop_heap, or a new element added by push_heap, in 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.

template<class RandomAccessIterator> constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> constexpr I ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {}); template<random_access_range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> constexpr borrowed_iterator_t<R> ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {});

Let comp be less{} and proj be identity{} for the overloads with no parameters by those names.

Preconditions: The range [first, last - 1) is a valid heap with respect to comp and proj.

Effects: Places the value in the location last - 1 into the resulting heap [first, last).