[alg.sorting] # 26 Algorithms library [[algorithms]](./#algorithms) ## 26.8 Sorting and related operations [alg.sorting] ### [26.8.1](#general) General [[alg.sorting.general]](alg.sorting.general) [1](#general-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8666) 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<[.](#general-1.sentence-1) [2](#general-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8672) Compare is a function object type ([[function.objects]](function.objects "22.10 Function objects")) that meets the requirements for a template parameter named BinaryPredicate ([[algorithms.requirements]](algorithms.requirements "26.2 Algorithms requirements"))[.](#general-2.sentence-1) 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, andfalse otherwise[.](#general-2.sentence-2) Compare comp is used throughout for algorithms assuming an ordering relation[.](#general-2.sentence-3) [3](#general-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8685) For all algorithms that take Compare, there is a version that uses operator< instead[.](#general-3.sentence-1) That is, comp(*i, *j) != false defaults to *i < *j != false[.](#general-3.sentence-2) For algorithms other than those described in [[alg.binary.search]](#alg.binary.search "26.8.4 Binary search"),comp shall induce a strict weak ordering on the values[.](#general-3.sentence-3) [4](#general-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8692) The term [*strict*](#def:strict) refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term [*weak*](#def:weak) to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering[.](#general-4.sentence-1) If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations: - [(4.1)](#general-4.1) comp(a, b) && comp(b, c) implies comp(a, c) - [(4.2)](#general-4.2) equiv(a, b) && equiv(b, c) implies equiv(a, c) [*Note [1](#general-note-1)*: Under these conditions, it can be shown that - [(4.3)](#general-4.3) equiv is an equivalence relation, - [(4.4)](#general-4.4) comp induces a well-defined relation on the equivalence classes determined by equiv, and - [(4.5)](#general-4.5) the induced relation is a strict total ordering[.](#general-4.sentence-2) — *end note*] [5](#general-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8718) A sequence is [*sorted with respect to a comp and proj*](#def: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[.](#general-5.sentence-1) [6](#general-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8731) A sequence is [*sorted with respect to a comparator comp*](#def:sorted_with_respect_to_a_comparator_comp) for a comparator comp if it is sorted with respect tocomp and identity{} (the identity projection)[.](#general-6.sentence-1) [7](#general-7) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8738) A sequence [start, finish) is[*partitioned with respect to an expression*](#def: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[.](#general-7.sentence-1) [8](#general-8) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8745) In the descriptions of the functions that deal with ordering relationships we frequently use a notion of equivalence to describe concepts such as stability[.](#general-8.sentence-1) The equivalence to which we refer is not necessarily an operator==, but an equivalence relation induced by the strict weak ordering[.](#general-8.sentence-2) That is, two elements a and b are considered equivalent if and only if !(a < b) && !(b < a)[.](#general-8.sentence-3) ### [26.8.2](#alg.sort) Sorting [[alg.sort]](alg.sort) #### [26.8.2.1](#sort) sort [[sort]](sort) [🔗](#lib:sort) `template constexpr void sort(RandomAccessIterator first, RandomAccessIterator last); template void sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last); template constexpr void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template void sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") constexpr I ranges::sort(I first, S last, Comp comp = {}, Proj proj = {}); template<[random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> constexpr borrowed_iterator_t ranges::sort(R&& r, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") I ranges::sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> borrowed_iterator_t ranges::sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [1](#sort-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8795) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#sort-1.sentence-1) [2](#sort-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8800) *Preconditions*: For the overloads in namespace std,RandomAccessIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")) and the type of *first meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and[*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements")) requirements[.](#sort-2.sentence-1) [3](#sort-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8809) *Effects*: Sorts the elements in the range [first, last) with respect to comp and proj[.](#sort-3.sentence-1) [4](#sort-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8814) *Returns*: last for the overloads in namespace ranges[.](#sort-4.sentence-1) [5](#sort-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8818) *Complexity*: Let N be last - first[.](#sort-5.sentence-1) O(NlogN) comparisons and projections[.](#sort-5.sentence-2) #### [26.8.2.2](#stable.sort) stable_sort [[stable.sort]](stable.sort) [🔗](#lib:stable_sort) `template constexpr void stable_sort(RandomAccessIterator first, RandomAccessIterator last); template void stable_sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last); template constexpr void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template void stable_sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") constexpr I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {}); template<[random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> constexpr borrowed_iterator_t ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") I ranges::stable_sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> borrowed_iterator_t ranges::stable_sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [1](#stable.sort-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8863) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#stable.sort-1.sentence-1) [2](#stable.sort-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8868) *Preconditions*: For the overloads in namespace std,RandomAccessIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")) and the type of *first meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and[*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements")) requirements[.](#stable.sort-2.sentence-1) [3](#stable.sort-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8877) *Effects*: Sorts the elements in the range [first, last) with respect to comp and proj[.](#stable.sort-3.sentence-1) [4](#stable.sort-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8882) *Returns*: last for the overloads in namespace ranges[.](#stable.sort-4.sentence-1) [5](#stable.sort-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8886) *Complexity*: Let N be last - first[.](#stable.sort-5.sentence-1) If enough extra memory is available, Nlog(N) comparisons[.](#stable.sort-5.sentence-2) Otherwise, at most Nlog2(N) comparisons[.](#stable.sort-5.sentence-3) In either case, twice as many projections as the number of comparisons[.](#stable.sort-5.sentence-4) [6](#stable.sort-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8893) *Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#stable.sort-6.sentence-1) #### [26.8.2.3](#partial.sort) partial_sort [[partial.sort]](partial.sort) [🔗](#lib:partial_sort) `template constexpr void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template void partial_sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template constexpr void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); template void partial_sort(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); template<[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") constexpr I ranges::partial_sort(I first, I middle, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") I ranges::partial_sort(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {}); ` [1](#partial.sort-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8936) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#partial.sort-1.sentence-1) [2](#partial.sort-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8941) *Preconditions*: [first, middle) and [middle, last) are valid ranges[.](#partial.sort-2.sentence-1) For the overloads in namespace std,RandomAccessIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")) and the type of *first meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and[*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements")) requirements[.](#partial.sort-2.sentence-2) [3](#partial.sort-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8951) *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)[.](#partial.sort-3.sentence-1) The rest of the elements in the range [middle, last) are placed in an unspecified order[.](#partial.sort-3.sentence-2) [4](#partial.sort-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8961) *Returns*: last for the overload in namespace ranges[.](#partial.sort-4.sentence-1) [5](#partial.sort-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8965) *Complexity*: Approximately (last - first) * log(middle - first) comparisons, and twice as many projections[.](#partial.sort-5.sentence-1) [🔗](#partial.sort-itemdecl:2) `template<[random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> constexpr borrowed_iterator_t ranges::partial_sort(R&& r, iterator_t middle, Comp comp = {}, Proj proj = {}); ` [6](#partial.sort-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8979) *Effects*: Equivalent to:return ranges::partial_sort(ranges::begin(r), middle, ranges::end(r), comp, proj); [🔗](#partial.sort-itemdecl:3) `template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> borrowed_iterator_t ranges::partial_sort(Ep&& exec, R&& r, iterator_t middle, Comp comp = {}, Proj proj = {}); ` [7](#partial.sort-7) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8997) *Effects*: Equivalent to:return ranges::partial_sort(std::forward(exec), ranges::begin(r), middle, ranges::end(r), comp, proj); #### [26.8.2.4](#partial.sort.copy) partial_sort_copy [[partial.sort.copy]](partial.sort.copy) [🔗](#lib:partial_sort_copy) `template constexpr RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template RandomAccessIterator partial_sort_copy(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template constexpr RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); template RandomAccessIterator partial_sort_copy(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I1, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S1, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I2, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S2, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]") && [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") && [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), projected> constexpr ranges::partial_sort_copy_result ranges::partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R1, [random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R2, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), iterator_t> && [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj2> && [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj1>, projected, Proj2>> constexpr ranges::partial_sort_copy_result, borrowed_iterator_t> ranges::partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I1, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S1, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I2, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S2, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]") && [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") && [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), projected> ranges::partial_sort_copy_result 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](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R1, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R2, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), iterator_t> && [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj2> && [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj1>, projected, Proj2>> ranges::partial_sort_copy_result, borrowed_iterator_t> ranges::partial_sort_copy(Ep&& exec, R1&& r, R2&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); ` [1](#partial.sort.copy-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9076) Let N be min(last - first, result_last - result_first)[.](#partial.sort.copy-1.sentence-1) Let comp be less{}, andproj1 and proj2 be identity{} for the overloads with no parameters by those names[.](#partial.sort.copy-1.sentence-2) [2](#partial.sort.copy-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9082) *Mandates*: For the overloads in namespace std, the expression *first is writable ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General")) to result_first[.](#partial.sort.copy-2.sentence-1) [3](#partial.sort.copy-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9088) *Preconditions*: For the overloads in namespace std,RandomAccessIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")), the type of *result_first meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and[*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements")) requirements[.](#partial.sort.copy-3.sentence-1) [4](#partial.sort.copy-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9097) 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 ofbool(invoke(comp, invoke(proj1, *a1), invoke(proj2, *y2))). Then, after evaluating the assignment *x2 = *a1, E is equal tobool(invoke(comp, invoke(proj2, *x2), invoke(proj2, *y2))). [*Note [1](#partial.sort.copy-note-1)*: Writing a value from the input range into the output range does not affect how it is ordered by comp and proj1 or proj2[.](#partial.sort.copy-4.sentence-2) — *end note*] [5](#partial.sort.copy-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9113) *Effects*: Places the first N elements as sorted with respect to comp and proj2 into the range [result_first, result_first + N)[.](#partial.sort.copy-5.sentence-1) [6](#partial.sort.copy-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9119) *Returns*: - [(6.1)](#partial.sort.copy-6.1) result_first + N for the overloads in namespace std[.](#partial.sort.copy-6.1.sentence-1) - [(6.2)](#partial.sort.copy-6.2) {last, result_first + N} for the overloads in namespace ranges[.](#partial.sort.copy-6.2.sentence-1) [7](#partial.sort.copy-7) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9129) *Complexity*: Approximately (last - first) * log N comparisons, and twice as many projections[.](#partial.sort.copy-7.sentence-1) #### [26.8.2.5](#is.sorted) is_sorted [[is.sorted]](is.sorted) [🔗](#lib:is_sorted) `template constexpr bool is_sorted(ForwardIterator first, ForwardIterator last); ` [1](#is.sorted-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9144) *Effects*: Equivalent to: return is_sorted_until(first, last) == last; [🔗](#lib:is_sorted_) `template bool is_sorted(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last); ` [2](#is.sorted-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9157) *Effects*: Equivalent to:return is_sorted_until(std::forward(exec), first, last) == last; [🔗](#lib:is_sorted__) `template constexpr bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp); ` [3](#is.sorted-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9173) *Effects*: Equivalent to: return is_sorted_until(first, last, comp) == last; [🔗](#lib:is_sorted___) `template bool is_sorted(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Compare comp); ` [4](#is.sorted-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9188) *Effects*: Equivalent to:return is_sorted_until(std::forward(exec), first, last, comp) == last; [🔗](#lib:is_sorted____) `template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr bool ranges::is_sorted(I first, S last, Comp comp = {}, Proj proj = {}); template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> constexpr bool ranges::is_sorted(R&& r, Comp comp = {}, Proj proj = {}); ` [5](#is.sorted-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9207) *Effects*: Equivalent to:return ranges​::​is_sorted_until(first, last, comp, proj) == last; [🔗](#is.sorted-itemdecl:6) `template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> bool ranges::is_sorted(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> bool ranges::is_sorted(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [6](#is.sorted-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9224) *Effects*: Equivalent to:return ranges::is_sorted_until(std::forward(exec), first, last, comp, proj) == last; [🔗](#lib:is_sorted_until) `template constexpr ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last); template ForwardIterator is_sorted_until(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last); template constexpr ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); template ForwardIterator is_sorted_until(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Compare comp); template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {}); template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> constexpr borrowed_iterator_t ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> I ranges::is_sorted_until(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> borrowed_iterator_t ranges::is_sorted_until(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [7](#is.sorted-7) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9272) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#is.sorted-7.sentence-1) [8](#is.sorted-8) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9277) *Returns*: The last iterator i in [first, last] for which the range [first, i) is sorted with respect to comp and proj[.](#is.sorted-8.sentence-1) [9](#is.sorted-9) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9283) *Complexity*: Linear[.](#is.sorted-9.sentence-1) ### [26.8.3](#alg.nth.element) Nth element [[alg.nth.element]](alg.nth.element) [🔗](#lib:nth_element) `template constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template void nth_element(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); template void nth_element(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); template<[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") constexpr I ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") I ranges::nth_element(Ep&& exec, I first, I nth, S last, Comp comp = {}, Proj proj = {}); ` [1](#alg.nth.element-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9320) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#alg.nth.element-1.sentence-1) [2](#alg.nth.element-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9325) *Preconditions*: [first, nth) and [nth, last) are valid ranges[.](#alg.nth.element-2.sentence-1) For the overloads in namespace std,RandomAccessIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")), and the type of *first meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and[*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements")) requirements[.](#alg.nth.element-2.sentence-2) [3](#alg.nth.element-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9335) *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[.](#alg.nth.element-3.sentence-1) 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[.](#alg.nth.element-3.sentence-2) [4](#alg.nth.element-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9346) *Returns*: last for the overload in namespace ranges[.](#alg.nth.element-4.sentence-1) [5](#alg.nth.element-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9350) *Complexity*: For the non-parallel algorithm overloads, linear on average[.](#alg.nth.element-5.sentence-1) For the parallel algorithm overloads, O(N) applications of the predicate, and O(NlogN) swaps, where N=last - first[.](#alg.nth.element-5.sentence-2) [🔗](#alg.nth.element-itemdecl:2) `template<[random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> constexpr borrowed_iterator_t ranges::nth_element(R&& r, iterator_t nth, Comp comp = {}, Proj proj = {}); ` [6](#alg.nth.element-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9365) *Effects*: Equivalent to:return ranges::nth_element(ranges::begin(r), nth, ranges::end(r), comp, proj); [🔗](#alg.nth.element-itemdecl:3) `template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> borrowed_iterator_t ranges::nth_element(Ep&& exec, R&& r, iterator_t nth, Comp comp = {}, Proj proj = {}); ` [7](#alg.nth.element-7) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9382) *Effects*: Equivalent to:return ranges::nth_element(std::forward(exec), ranges::begin(r), nth, ranges::end(r), comp, proj); ### [26.8.4](#alg.binary.search) Binary search [[alg.binary.search]](alg.binary.search) #### [26.8.4.1](#alg.binary.search.general) General [[alg.binary.search.general]](alg.binary.search.general) [1](#alg.binary.search.general-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9395) All of the algorithms in [[alg.binary.search]](#alg.binary.search "26.8.4 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[.](#alg.binary.search.general-1.sentence-1) They work on non-random access iterators minimizing the number of comparisons, which will be logarithmic for all types of iterators[.](#alg.binary.search.general-1.sentence-2) They are especially appropriate for random access iterators, because these algorithms do a logarithmic number of steps through the data structure[.](#alg.binary.search.general-1.sentence-3) For non-random access iterators they execute a linear number of steps[.](#alg.binary.search.general-1.sentence-4) #### [26.8.4.2](#lower.bound) lower_bound [[lower.bound]](lower.bound) [🔗](#lib:lower_bound) `template::value_type> constexpr ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value); template::value_type, class Compare> constexpr ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, class T = projected_value_t, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr I ranges::lower_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, class T = projected_value_t, Proj>, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> constexpr borrowed_iterator_t ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); ` [1](#lower.bound-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9436) Let comp be less{} andproj be identity{} for overloads with no parameters by those names[.](#lower.bound-1.sentence-1) [2](#lower.bound-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9441) *Preconditions*: The elements e of [first, last) are partitioned with respect to the expression bool(invoke(comp, invoke(proj, e), value))[.](#lower.bound-2.sentence-2) [3](#lower.bound-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9447) *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[.](#lower.bound-3.sentence-1) [4](#lower.bound-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9453) *Complexity*: At most log2(last - first)+O(1) comparisons and projections[.](#lower.bound-4.sentence-1) #### [26.8.4.3](#upper.bound) upper_bound [[upper.bound]](upper.bound) [🔗](#lib:upper_bound) `template::value_type> constexpr ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value); template::value_type, class Compare> constexpr ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, class T = projected_value_t, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr I ranges::upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, class T = projected_value_t, Proj>, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> constexpr borrowed_iterator_t ranges::upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); ` [1](#upper.bound-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9486) Let comp be less{} andproj be identity{} for overloads with no parameters by those names[.](#upper.bound-1.sentence-1) [2](#upper.bound-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9491) *Preconditions*: The elements e of [first, last) are partitioned with respect to the expression !bool(invoke(comp, value, invoke(proj, e)))[.](#upper.bound-2.sentence-2) [3](#upper.bound-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9497) *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[.](#upper.bound-3.sentence-1) [4](#upper.bound-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9503) *Complexity*: At most log2(last - first)+O(1) comparisons and projections[.](#upper.bound-4.sentence-1) #### [26.8.4.4](#equal.range) equal_range [[equal.range]](equal.range) [🔗](#lib:equal_range) `template::value_type> constexpr pair equal_range(ForwardIterator first, ForwardIterator last, const T& value); template::value_type, class Compare> constexpr pair equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, class T = projected_value_t, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr subrange ranges::equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, class T = projected_value_t, Proj>, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> constexpr borrowed_subrange_t ranges::equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {}); ` [1](#equal.range-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9538) Let comp be less{} andproj be identity{} for overloads with no parameters by those names[.](#equal.range-1.sentence-1) [2](#equal.range-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9543) *Preconditions*: The elements e of [first, last) are partitioned with respect to the expressionsbool(invoke(comp, invoke(proj, e), value)) and!bool(invoke(comp, value, invoke(proj, e)))[.](#equal.range-2.sentence-1) Also, for all elements e of [first, last),bool(comp(e, value)) implies !bool(comp(​value, e)) for the overloads in namespace std[.](#equal.range-2.sentence-2) [3](#equal.range-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9553) *Returns*: - [(3.1)](#equal.range-3.1) For the overloads in namespace std:{lower_bound(first, last, value, comp), upper_bound(first, last, value, comp)} - [(3.2)](#equal.range-3.2) For the overloads in namespace ranges:{ranges::lower_bound(first, last, value, comp, proj), ranges::upper_bound(first, last, value, comp, proj)} [4](#equal.range-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9570) *Complexity*: At most2∗log2(last - first)+O(1) comparisons and projections[.](#equal.range-4.sentence-1) #### [26.8.4.5](#binary.search) binary_search [[binary.search]](binary.search) [🔗](#lib:binary_search) `template::value_type> constexpr bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); template::value_type, class Compare> constexpr bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, class T = projected_value_t, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr bool ranges::binary_search(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, class T = projected_value_t, Proj>, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> constexpr bool ranges::binary_search(R&& r, const T& value, Comp comp = {}, Proj proj = {}); ` [1](#binary.search-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9605) Let comp be less{} andproj be identity{} for overloads with no parameters by those names[.](#binary.search-1.sentence-1) [2](#binary.search-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9610) *Preconditions*: The elements e of [first, last) are partitioned with respect to the expressionsbool(invoke(comp, invoke(proj, e), value)) and!bool(invoke(comp, value, invoke(proj, e)))[.](#binary.search-2.sentence-1) Also, for all elements e of [first, last),bool(comp(e, value)) implies !bool(comp(​value, e)) for the overloads in namespace std[.](#binary.search-2.sentence-2) [3](#binary.search-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9620) *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[.](#binary.search-3.sentence-1) [4](#binary.search-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9628) *Complexity*: At most log2(last - first)+O(1) comparisons and projections[.](#binary.search-4.sentence-1) ### [26.8.5](#alg.partitions) Partitions [[alg.partitions]](alg.partitions) [🔗](#lib:is_partitioned) `template constexpr bool is_partitioned(InputIterator first, InputIterator last, Predicate pred); template bool is_partitioned(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred); template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Pred> constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Pred> constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Pred> bool ranges::is_partitioned(Ep&& exec, I first, S last, Pred pred, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Pred> bool ranges::is_partitioned(Ep&& exec, R&& r, Pred pred, Proj proj = {}); ` [1](#alg.partitions-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9659) Let proj be identity{} for the overloads with no parameter named proj[.](#alg.partitions-1.sentence-1) [2](#alg.partitions-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9663) *Returns*: true if and only if the elements e of [first, last) are partitioned with respect to the expressionbool(invoke(pred, invoke(proj, e)))[.](#alg.partitions-2.sentence-1) [3](#alg.partitions-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9669) *Complexity*: Linear[.](#alg.partitions-3.sentence-1) At most last - first applications of pred and proj[.](#alg.partitions-3.sentence-2) [🔗](#lib:partition) `template constexpr ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred); template ForwardIterator partition(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred); template<[permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Pred> constexpr subrange ranges::partition(I first, S last, Pred pred, Proj proj = {}); template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Pred> requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")> constexpr borrowed_subrange_t ranges::partition(R&& r, Pred pred, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Pred> subrange ranges::partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Pred> requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")> borrowed_subrange_t ranges::partition(Ep&& exec, R&& r, Pred pred, Proj proj = {}); ` [4](#alg.partitions-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9704) Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x)))[.](#alg.partitions-4.sentence-1) [5](#alg.partitions-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9709) *Preconditions*: For the overloads in namespace std,ForwardIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements"))[.](#alg.partitions-5.sentence-1) [6](#alg.partitions-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9715) *Effects*: Places all the elements e in [first, last) that satisfy E(e) before all the elements that do not[.](#alg.partitions-6.sentence-1) [7](#alg.partitions-7) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9720) *Returns*: Let i be an iterator such that E(*j) istrue for every iterator j in [first, i) andfalse for every iterator j in [i, last)[.](#alg.partitions-7.sentence-1) Returns: - [(7.1)](#alg.partitions-7.1) i for the overloads in namespace std[.](#alg.partitions-7.1.sentence-1) - [(7.2)](#alg.partitions-7.2) {i, last} for the overloads in namespace ranges[.](#alg.partitions-7.2.sentence-1) [8](#alg.partitions-8) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9732) *Complexity*: Let N=last - first: - [(8.1)](#alg.partitions-8.1) For the non-parallel algorithm overloads, exactly N applications of the predicate and projection[.](#alg.partitions-8.1.sentence-1) At most N/2 swaps if the type of first meets the [*Cpp17BidirectionalIterator*](bidirectional.iterators#:Cpp17BidirectionalIterator "24.3.5.6 Bidirectional iterators [bidirectional.iterators]") requirements for the overloads in namespace std or models [bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") for the overloads in namespace ranges, and at most N swaps otherwise[.](#alg.partitions-8.1.sentence-2) - [(8.2)](#alg.partitions-8.2) For the parallel algorithm overloads, O(NlogN) swaps and O(N) applications of the predicate[.](#alg.partitions-8.2.sentence-1) [🔗](#lib:stable_partition) `template BidirectionalIterator constexpr stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred); template BidirectionalIterator stable_partition(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator last, Predicate pred); template<[bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Pred> requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]") constexpr subrange ranges::stable_partition(I first, S last, Pred pred, Proj proj = {}); template<[bidirectional_range](range.refinements#concept:bidirectional_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Pred> requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")> constexpr borrowed_subrange_t ranges::stable_partition(R&& r, Pred pred, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Pred> requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]") subrange ranges::stable_partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Pred> requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")> borrowed_subrange_t ranges::stable_partition(Ep&& exec, R&& r, Pred pred, Proj proj = {}); ` [9](#alg.partitions-9) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9784) Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x)))[.](#alg.partitions-9.sentence-1) [10](#alg.partitions-10) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9789) *Preconditions*: For the overloads in namespace std,BidirectionalIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")) and the type of *first meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and[*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements")) requirements[.](#alg.partitions-10.sentence-1) [11](#alg.partitions-11) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9798) *Effects*: Places all the elements e in [first, last) that satisfy E(e) before all the elements that do not[.](#alg.partitions-11.sentence-1) The relative order of the elements in both groups is preserved[.](#alg.partitions-11.sentence-2) [12](#alg.partitions-12) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9804) *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[.](#alg.partitions-12.sentence-1) Returns: - [(12.1)](#alg.partitions-12.1) i for the overloads in namespace std[.](#alg.partitions-12.1.sentence-1) - [(12.2)](#alg.partitions-12.2) {i, last} for the overloads in namespace ranges[.](#alg.partitions-12.2.sentence-1) [13](#alg.partitions-13) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9817) *Complexity*: Let N = last - first: - [(13.1)](#alg.partitions-13.1) For the non-parallel algorithm overloads, at most Nlog2N swaps, but only O(N) swaps if there is enough extra memory[.](#alg.partitions-13.1.sentence-1) Exactly N applications of the predicate and projection[.](#alg.partitions-13.1.sentence-2) - [(13.2)](#alg.partitions-13.2) For the parallel algorithm overloads, O(NlogN) swaps and O(N) applications of the predicate[.](#alg.partitions-13.2.sentence-1) [🔗](#lib:partition_copy) `template constexpr pair partition_copy(InputIterator first, InputIterator last, OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred); template pair partition_copy(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, ForwardIterator1 out_true, ForwardIterator2 out_false, Predicate pred); template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O1, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O2, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Pred> requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]") && [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]") constexpr ranges::partition_copy_result ranges::partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred, Proj proj = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O1, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O2, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Pred> requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), O1> && [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), O2> constexpr ranges::partition_copy_result, O1, O2> ranges::partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") O1, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") OutS1, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") O2, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") OutS2, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Pred> requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]") && [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]") ranges::partition_copy_result 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](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR1, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR2, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Pred> requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), iterator_t> && [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), iterator_t> ranges::partition_copy_result, borrowed_iterator_t, borrowed_iterator_t> ranges::partition_copy(Ep&& exec, R&& r, OutR1&& out_true_r, OutR2&& out_false_r, Pred pred, Proj proj = {}); ` [14](#alg.partitions-14) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9880) Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x)))[.](#alg.partitions-14.sentence-1) [15](#alg.partitions-15) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9885) For the overloads with no parameterslast_true, last_false, out_true_r, or out_false_r, let - [(15.1)](#alg.partitions-15.1) M be the number of iterators i in [first, last) for which E(*i) is true, and K be last - first - M; - [(15.2)](#alg.partitions-15.2) last_true be out_true + M, and last_false be out_false + K[.](#alg.partitions-15.sentence-1) [16](#alg.partitions-16) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9899) For the overloads with parameterslast_true, last_false, out_true_r, or out_false_r, let M be last_true - out_true and K be last_false - out_false[.](#alg.partitions-16.sentence-1) [17](#alg.partitions-17) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9905) Let: - [(17.1)](#alg.partitions-17.1) 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; - [(17.2)](#alg.partitions-17.2) 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; - [(17.3)](#alg.partitions-17.3) N be min(i1 - first, i2 - first)[.](#alg.partitions-17.sentence-1) [18](#alg.partitions-18) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9924) *Mandates*: For the overloads in namespace std, the expression *first is writable ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General")) to out_true and out_false[.](#alg.partitions-18.sentence-1) [19](#alg.partitions-19) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9931) *Preconditions*: The input range and output ranges do not overlap[.](#alg.partitions-19.sentence-1) [*Note [1](#alg.partitions-note-1)*: For the parallel algorithm overload in namespace std, there can be a performance cost if first's value type does not meet the *Cpp17CopyConstructible* requirements[.](#alg.partitions-19.sentence-2) For the parallel algorithm overloads in namespace ranges, there can be a performance cost if first's value type does not model [copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]")[.](#alg.partitions-19.sentence-3) — *end note*] [20](#alg.partitions-20) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9944) *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[.](#alg.partitions-20.sentence-1) [21](#alg.partitions-21) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9951) *Returns*: Let o1 be the iterator past the last copied element in the output range [out_true, last_true), and o2 be the iterator past the last copied element in the output range [out_false, last_false)[.](#alg.partitions-21.sentence-1) Returns: - [(21.1)](#alg.partitions-21.1) {o1, o2} for the overloads in namespace std[.](#alg.partitions-21.1.sentence-1) - [(21.2)](#alg.partitions-21.2) {first + N, o1, o2} for the overloads in namespace ranges[.](#alg.partitions-21.2.sentence-1) [22](#alg.partitions-22) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9963) *Complexity*: At most last - first applications of pred and proj[.](#alg.partitions-22.sentence-1) [🔗](#lib:partition_point) `template constexpr ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Pred> constexpr I ranges::partition_point(I first, S last, Pred pred, Proj proj = {}); template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Pred> constexpr borrowed_iterator_t ranges::partition_point(R&& r, Pred pred, Proj proj = {}); ` [23](#alg.partitions-23) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9984) Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x)))[.](#alg.partitions-23.sentence-1) [24](#alg.partitions-24) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9989) *Preconditions*: The elements e of [first, last) are partitioned with respect to E(e)[.](#alg.partitions-24.sentence-1) [25](#alg.partitions-25) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9994) *Returns*: An iterator mid such that E(*i) is true for all iterators i in [first, mid), andfalse for all iterators i in [mid, last)[.](#alg.partitions-25.sentence-1) [26](#alg.partitions-26) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10001) *Complexity*: O(log(last - first)) applications of pred and proj[.](#alg.partitions-26.sentence-1) ### [26.8.6](#alg.merge) Merge [[alg.merge]](alg.merge) [🔗](#lib:merge) `template constexpr OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template ForwardIterator merge(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template constexpr OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template ForwardIterator merge(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I1, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S1, [input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I2, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S2, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") constexpr ranges::merge_result ranges::merge(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R1, [input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R2, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]"), iterator_t, O, Comp, Proj1, Proj2> constexpr ranges::merge_result, borrowed_iterator_t, O> ranges::merge(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I1, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S1, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I2, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S2, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") O, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") ranges::merge_result 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](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R1, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R2, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]"), iterator_t, iterator_t, Comp, Proj1, Proj2> ranges::merge_result, borrowed_iterator_t, borrowed_iterator_t> ranges::merge(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); ` [1](#alg.merge-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10071) Let: - [(1.1)](#alg.merge-1.1) N be: * [(1.1.1)](#alg.merge-1.1.1) (last1 - first1) + (last2 - first2) for the overloads with no parameter result_last or result_r; * [(1.1.2)](#alg.merge-1.1.2) min((last1 - first1) + (last2 - first2), result_last - result) for the overloads with parameters result_last or result_r; - [(1.2)](#alg.merge-1.2) comp be less{}, proj1 be identity{}, and proj2 be identity{}, for the overloads with no parameters by those names; - [(1.3)](#alg.merge-1.3) E(e1, e1) be bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1))); - [(1.4)](#alg.merge-1.4) K be the smallest integer in [0, last1 - first1) such that for the element e1 in the position first1 + K there are at least N−K elements e2 in [first2, last2) for which E(e1, e1) holds, and be equal to last1 - first1 if no such integer exists[.](#alg.merge-1.sentence-1) [*Note [1](#alg.merge-note-1)*: first1 + K points to the position past the last element to be copied[.](#alg.merge-1.4.sentence-2) — *end note*] [2](#alg.merge-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10103) *Preconditions*: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively[.](#alg.merge-2.sentence-1) The resulting range does not overlap with either of the original ranges[.](#alg.merge-2.sentence-2) [3](#alg.merge-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10110) *Effects*: Copies the first K elements of the range [first1, last1) and the first N−K elements of the range [first2, last2) into the range [result, result + N)[.](#alg.merge-3.sentence-1) If an element a precedes b in an input range,a is copied into the output range before b[.](#alg.merge-3.sentence-2) If e1 is an element of [first1, last1) ande2 of [first2, last2),e2 is copied into the output range before e1 if and only if E(e1, e1) is true[.](#alg.merge-3.sentence-3) [4](#alg.merge-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10122) *Returns*: - [(4.1)](#alg.merge-4.1) result + N for the overloads in namespace std[.](#alg.merge-4.1.sentence-1) - [(4.2)](#alg.merge-4.2) {first1 + K, first2 + N - K, result + N} for the overloads in namespace ranges[.](#alg.merge-4.2.sentence-1) [5](#alg.merge-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10133) *Complexity*: - [(5.1)](#alg.merge-5.1) For the non-parallel algorithm overloads, at most N−1 comparisons and applications of each projection[.](#alg.merge-5.1.sentence-1) - [(5.2)](#alg.merge-5.2) For the parallel algorithm overloads, O(N) comparisons and applications of each projection[.](#alg.merge-5.2.sentence-1) [6](#alg.merge-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10144) *Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#alg.merge-6.sentence-1) [🔗](#lib:inplace_merge) `template constexpr void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); template void inplace_merge(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); template constexpr void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); template void inplace_merge(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); template<[bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") constexpr I ranges::inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") I ranges::inplace_merge(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {}); ` [7](#alg.merge-7) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10182) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#alg.merge-7.sentence-1) [8](#alg.merge-8) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10187) *Preconditions*: [first, middle) and [middle, last) are valid ranges sorted with respect to comp and proj[.](#alg.merge-8.sentence-1) For the overloads in namespace std,BidirectionalIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")) and the type of *first meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and[*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements")) requirements[.](#alg.merge-8.sentence-2) [9](#alg.merge-9) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10198) *Effects*: Merges two sorted consecutive ranges [first, middle) and [middle, last), putting the result of the merge into the range [first, last)[.](#alg.merge-9.sentence-1) The resulting range is sorted with respect to comp and proj[.](#alg.merge-9.sentence-2) [10](#alg.merge-10) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10205) *Returns*: last for the overload in namespace ranges[.](#alg.merge-10.sentence-1) [11](#alg.merge-11) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10209) *Complexity*: Let N=last - first: - [(11.1)](#alg.merge-11.1) For the non-parallel algorithm overloads, and if enough additional memory is available, at most N−1 comparisons[.](#alg.merge-11.1.sentence-1) - [(11.2)](#alg.merge-11.2) Otherwise, O(NlogN) comparisons[.](#alg.merge-11.2.sentence-1) In either case, twice as many projections as comparisons[.](#alg.merge-11.sentence-2) [12](#alg.merge-12) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10221) *Remarks*: [Stable](algorithm.stable "16.4.6.8 Requirements for stable algorithms [algorithm.stable]")[.](#alg.merge-12.sentence-1) [🔗](#alg.merge-itemdecl:3) `template<[bidirectional_range](range.refinements#concept:bidirectional_range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> constexpr borrowed_iterator_t ranges::inplace_merge(R&& r, iterator_t middle, Comp comp = {}, Proj proj = {}); ` [13](#alg.merge-13) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10234) *Effects*: Equivalent to:return ranges::inplace_merge(ranges::begin(r), middle, ranges::end(r), comp, proj); [🔗](#alg.merge-itemdecl:4) `template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> borrowed_iterator_t ranges::inplace_merge(Ep&& exec, R&& r, iterator_t middle, Comp comp = {}, Proj proj = {}); ` [14](#alg.merge-14) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10252) *Effects*: Equivalent to:return ranges::inplace_merge(std::forward(exec), ranges::begin(r), middle, ranges::end(r), comp, proj); ### [26.8.7](#alg.set.operations) Set operations on sorted structures [[alg.set.operations]](alg.set.operations) #### [26.8.7.1](#alg.set.operations.general) General [[alg.set.operations.general]](alg.set.operations.general) [1](#alg.set.operations.general-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10265) Subclause [[alg.set.operations]](#alg.set.operations "26.8.7 Set operations on sorted structures") defines all the basic set operations on sorted structures[.](#alg.set.operations.general-1.sentence-1) They also work with multisets ([[multiset]](multiset "23.4.7 Class template multiset")) containing multiple copies of equivalent elements[.](#alg.set.operations.general-1.sentence-2) 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[.](#alg.set.operations.general-1.sentence-3) #### [26.8.7.2](#includes) includes [[includes]](includes) [🔗](#lib:includes) `template constexpr bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template bool includes(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template constexpr bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); template bool includes(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, Compare comp); template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I1, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S1, [input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I2, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S2, class Proj1 = identity, class Proj2 = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), projected> Comp = ranges::less> constexpr bool ranges::includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R1, [input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R2, class Proj1 = identity, class Proj2 = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj1>, projected, Proj2>> Comp = ranges::less> constexpr bool ranges::includes(R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I1, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S1, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I2, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S2, class Proj1 = identity, class Proj2 = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), projected> 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](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R1, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R2, class Proj1 = identity, class Proj2 = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj1>, projected, Proj2>> Comp = ranges::less> bool ranges::includes(Ep&& exec, R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); ` [1](#includes-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10325) Let comp be less{},proj1 be identity{}, andproj2 be identity{}, for the overloads with no parameters by those names[.](#includes-1.sentence-1) [2](#includes-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10331) *Preconditions*: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively[.](#includes-2.sentence-1) [3](#includes-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10336) *Returns*: true if and only if [first2, last2) is a subsequence of [first1, last1)[.](#includes-3.sentence-1) [*Note [1](#includes-note-1)*: A sequence S is a subsequence of another sequence T if S can be obtained from T by removing some, all, or none of T's elements and keeping the remaining elements in the same order[.](#includes-3.sentence-2) — *end note*] [4](#includes-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10346) *Complexity*: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection[.](#includes-4.sentence-1) #### [26.8.7.3](#set.union) set_union [[set.union]](set.union) [🔗](#lib:set_union) `template constexpr OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template ForwardIterator set_union(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template constexpr OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template ForwardIterator set_union(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I1, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S1, [input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I2, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S2, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") constexpr ranges::set_union_result ranges::set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R1, [input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R2, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]"), iterator_t, O, Comp, Proj1, Proj2> constexpr ranges::set_union_result, borrowed_iterator_t, O> ranges::set_union(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I1, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S1, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I2, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S2, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") O, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") ranges::set_union_result 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](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R1, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R2, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]"), iterator_t, iterator_t, Comp, Proj1, Proj2> ranges::set_union_result, borrowed_iterator_t, borrowed_iterator_t> ranges::set_union(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); ` [1](#set.union-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10416) Let: - [(1.1)](#set.union-1.1) comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names; - [(1.2)](#set.union-1.2) M be last1 - first1 plus the number of elements in [first2, last2) that are not present in [first1, last1); - [(1.3)](#set.union-1.3) result_last be result + M for the overloads with no parameter result_last or result_r; - [(1.4)](#set.union-1.4) N be min(M, result_last - result)[.](#set.union-1.sentence-1) [2](#set.union-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10433) *Preconditions*: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively[.](#set.union-2.sentence-1) The resulting range does not overlap with either of the original ranges[.](#set.union-2.sentence-2) [3](#set.union-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10439) *Effects*: Constructs a sorted union of N elements from the two ranges; that is, the set of elements that are present in one or both of the ranges[.](#set.union-3.sentence-1) [4](#set.union-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10444) *Returns*: - [(4.1)](#set.union-4.1) result_last for the overloads in namespace std[.](#set.union-4.1.sentence-1) - [(4.2)](#set.union-4.2) {last1, last2, result + N} for the overloads in namespace ranges, if N is equal to M[.](#set.union-4.2.sentence-1) - [(4.3)](#set.union-4.3) Otherwise, {j1, j2, result_last} for the overloads in namespace ranges, where the iterators j1 and j2 point to positions past the last copied or skipped elements in [first1, last1) and [first2, last2), respectively[.](#set.union-4.3.sentence-1) [5](#set.union-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10462) *Complexity*: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection[.](#set.union-5.sentence-1) [6](#set.union-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10467) *Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#set.union-6.sentence-1) 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 copied to the output range, in order, and then the final max(n−m,0) elements from the second range are copied to the output range, in order[.](#set.union-6.sentence-2) #### [26.8.7.4](#set.intersection) set_intersection [[set.intersection]](set.intersection) [🔗](#lib:set_intersection) `template constexpr OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template ForwardIterator set_intersection(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template constexpr OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template ForwardIterator set_intersection(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I1, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S1, [input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I2, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S2, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") constexpr ranges::set_intersection_result ranges::set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R1, [input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R2, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]"), iterator_t, O, Comp, Proj1, Proj2> constexpr ranges::set_intersection_result, borrowed_iterator_t, O> ranges::set_intersection(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I1, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S1, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I2, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S2, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") O, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") ranges::set_intersection_result 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](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R1, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R2, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]"), iterator_t, iterator_t, Comp, Proj1, Proj2> ranges::set_intersection_result, borrowed_iterator_t, borrowed_iterator_t> ranges::set_intersection(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); ` [1](#set.intersection-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10546) Let: - [(1.1)](#set.intersection-1.1) comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names; - [(1.2)](#set.intersection-1.2) M be the number of elements in [first1, last1) that are present in [first2, last2); - [(1.3)](#set.intersection-1.3) result_last be result + M for the overloads with no parameter result_last or result_r; - [(1.4)](#set.intersection-1.4) N be min(M, result_last - result)[.](#set.intersection-1.sentence-1) [2](#set.intersection-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10563) *Preconditions*: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively[.](#set.intersection-2.sentence-1) The resulting range does not overlap with either of the original ranges[.](#set.intersection-2.sentence-2) [3](#set.intersection-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10569) *Effects*: Constructs a sorted intersection of N elements from the two ranges; that is, the set of elements that are present in both of the ranges[.](#set.intersection-3.sentence-1) [4](#set.intersection-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10574) *Returns*: - [(4.1)](#set.intersection-4.1) result_last for the overloads in namespace std[.](#set.intersection-4.1.sentence-1) - [(4.2)](#set.intersection-4.2) {last1, last2, result + N} for the overloads in namespace ranges, if N is equal to M[.](#set.intersection-4.2.sentence-1) - [(4.3)](#set.intersection-4.3) Otherwise, {j1, j2, result_last} for the overloads in namespace ranges, where the iterators j1 and j2 point to positions past the last copied or skipped elements in [first1, last1) and [first2, last2), respectively[.](#set.intersection-4.3.sentence-1) [5](#set.intersection-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10592) *Complexity*: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection[.](#set.intersection-5.sentence-1) [6](#set.intersection-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10597) *Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#set.intersection-6.sentence-1) 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 are copied from the first range to the output range, in order[.](#set.intersection-6.sentence-2) #### [26.8.7.5](#set.difference) set_difference [[set.difference]](set.difference) [🔗](#lib:set_difference) `template constexpr OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template ForwardIterator set_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template constexpr OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template ForwardIterator set_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I1, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S1, [input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I2, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S2, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") constexpr ranges::set_difference_result ranges::set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R1, [input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R2, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]"), iterator_t, O, Comp, Proj1, Proj2> constexpr ranges::set_difference_result, O> ranges::set_difference(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I1, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S1, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I2, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S2, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") O, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") ranges::set_difference_result 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](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R1, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R2, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]"), iterator_t, iterator_t, Comp, Proj1, Proj2> ranges::set_difference_result, borrowed_iterator_t> ranges::set_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); ` [1](#set.difference-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10673) Let: - [(1.1)](#set.difference-1.1) comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names; - [(1.2)](#set.difference-1.2) M be the number of elements in [first1, last1) that are not present in [first2, last2); - [(1.3)](#set.difference-1.3) result_last be result + M for the overloads with no parameter result_last or result_r; - [(1.4)](#set.difference-1.4) N be min(M, result_last - result)[.](#set.difference-1.sentence-1) [2](#set.difference-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10690) *Preconditions*: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively[.](#set.difference-2.sentence-1) The resulting range does not overlap with either of the original ranges[.](#set.difference-2.sentence-2) [3](#set.difference-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10696) *Effects*: Copies N elements of the range [first1, last1) which are not present in the range [first2, last2) to the range [result, result + N)[.](#set.difference-3.sentence-1) The elements in the constructed range are sorted[.](#set.difference-3.sentence-2) [4](#set.difference-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10703) *Returns*: - [(4.1)](#set.difference-4.1) result_last for the overloads in namespace std[.](#set.difference-4.1.sentence-1) - [(4.2)](#set.difference-4.2) {last1, result + N} for the overloads in namespace ranges, if N is equal to M[.](#set.difference-4.2.sentence-1) - [(4.3)](#set.difference-4.3) Otherwise, {j1, result_last} for the overloads in namespace ranges, where the iterator j1 points to positions past the last copied or skipped elements in [first1, last1) and [first2, last2), respectively[.](#set.difference-4.3.sentence-1) [5](#set.difference-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10721) *Complexity*: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection[.](#set.difference-5.sentence-1) [6](#set.difference-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10726) *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) are copied to the output range, in order[.](#set.difference-6.sentence-1) #### [26.8.7.6](#set.symmetric.difference) set_symmetric_difference [[set.symmetric.difference]](set.symmetric.difference) [🔗](#lib:set_symmetric_difference) `template constexpr OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template ForwardIterator set_symmetric_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template constexpr OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template ForwardIterator set_symmetric_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I1, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S1, [input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I2, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S2, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") constexpr ranges::set_symmetric_difference_result ranges::set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R1, [input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R2, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]"), iterator_t, O, Comp, Proj1, Proj2> constexpr ranges::set_symmetric_difference_result, borrowed_iterator_t, O> ranges::set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I1, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S1, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I2, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S2, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") O, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") ranges::set_symmetric_difference_result 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](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R1, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R2, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires [mergeable](alg.req.mergeable#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]"), iterator_t, iterator_t, Comp, Proj1, Proj2> ranges::set_symmetric_difference_result, borrowed_iterator_t, borrowed_iterator_t> ranges::set_symmetric_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); ` [1](#set.symmetric.difference-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10804) Let: - [(1.1)](#set.symmetric.difference-1.1) comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names; - [(1.2)](#set.symmetric.difference-1.2) K be the number of elements in [first1, last1) that are not present in [first2, last2)[.](#set.symmetric.difference-1.2.sentence-1) - [(1.3)](#set.symmetric.difference-1.3) M be the number of elements in [first2, last2) that are not present in [first1, last1)[.](#set.symmetric.difference-1.3.sentence-1) - [(1.4)](#set.symmetric.difference-1.4) result_last be result + M + K for the overloads with no parameter result_last or result_r; - [(1.5)](#set.symmetric.difference-1.5) N be min(K+M, result_last - result)[.](#set.symmetric.difference-1.5.sentence-1) [2](#set.symmetric.difference-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10822) *Preconditions*: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively[.](#set.symmetric.difference-2.sentence-1) The resulting range does not overlap with either of the original ranges[.](#set.symmetric.difference-2.sentence-2) [3](#set.symmetric.difference-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10828) *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 [result, result + N)[.](#set.symmetric.difference-3.sentence-1) The elements in the constructed range are sorted[.](#set.symmetric.difference-3.sentence-2) [4](#set.symmetric.difference-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10837) *Returns*: - [(4.1)](#set.symmetric.difference-4.1) result_last for the overloads in namespace std[.](#set.symmetric.difference-4.1.sentence-1) - [(4.2)](#set.symmetric.difference-4.2) {last1, last2, result + N} for the overloads in namespace ranges, if N is equal to M+K[.](#set.symmetric.difference-4.2.sentence-1) - [(4.3)](#set.symmetric.difference-4.3) Otherwise, {j1, j2, result_last} for the overloads in namespace ranges, where the iterators j1 and j2 point to positions past the last copied or skipped elements in [first1, last1) and [first2, last2), respectively[.](#set.symmetric.difference-4.3.sentence-1) [5](#set.symmetric.difference-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10855) *Complexity*: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection[.](#set.symmetric.difference-5.sentence-1) [6](#set.symmetric.difference-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10860) *Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#set.symmetric.difference-6.sentence-1) 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 constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last); template constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") constexpr I ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {}); template<[random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> constexpr borrowed_iterator_t ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {}); ` [1](#push.heap-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10924) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#push.heap-1.sentence-1) [2](#push.heap-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10929) *Preconditions*: The range [first, last - 1) is a valid heap with respect to comp and proj[.](#push.heap-2.sentence-1) For the overloads in namespace std,RandomAccessIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")) and the type of *first meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and the [*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements"))[.](#push.heap-2.sentence-2) [3](#push.heap-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10940) *Effects*: Places the value in the location last - 1 into the resulting heap [first, last)[.](#push.heap-3.sentence-1) [4](#push.heap-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10945) *Returns*: last for the overloads in namespace ranges[.](#push.heap-4.sentence-1) [5](#push.heap-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10949) *Complexity*: At most log(last - first) comparisons and twice as many projections[.](#push.heap-5.sentence-1) #### [26.8.8.3](#pop.heap) pop_heap [[pop.heap]](pop.heap) [🔗](#lib:pop_heap) `template constexpr void pop_heap(RandomAccessIterator first, RandomAccessIterator last); template constexpr void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") constexpr I ranges::pop_heap(I first, S last, Comp comp = {}, Proj proj = {}); template<[random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> constexpr borrowed_iterator_t ranges::pop_heap(R&& r, Comp comp = {}, Proj proj = {}); ` [1](#pop.heap-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10977) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#pop.heap-1.sentence-1) [2](#pop.heap-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10982) *Preconditions*: The range [first, last) is a valid non-empty heap with respect to comp and proj[.](#pop.heap-2.sentence-1) For the overloads in namespace std,RandomAccessIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")) and the type of *first meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and[*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements")) requirements[.](#pop.heap-2.sentence-2) [3](#pop.heap-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L10993) *Effects*: Swaps the value in the location first with the value in the locationlast - 1 and makes [first, last - 1) into a heap with respect to comp and proj[.](#pop.heap-3.sentence-1) [4](#pop.heap-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11002) *Returns*: last for the overloads in namespace ranges[.](#pop.heap-4.sentence-1) [5](#pop.heap-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11006) *Complexity*: At most 2log(last - first) comparisons and twice as many projections[.](#pop.heap-5.sentence-1) #### [26.8.8.4](#make.heap) make_heap [[make.heap]](make.heap) [🔗](#lib:make_heap) `template constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last); template constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") constexpr I ranges::make_heap(I first, S last, Comp comp = {}, Proj proj = {}); template<[random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> constexpr borrowed_iterator_t ranges::make_heap(R&& r, Comp comp = {}, Proj proj = {}); ` [1](#make.heap-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11035) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#make.heap-1.sentence-1) [2](#make.heap-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11040) *Preconditions*: For the overloads in namespace std,RandomAccessIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")) and the type of *first meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and[*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements")) requirements[.](#make.heap-2.sentence-1) [3](#make.heap-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11049) *Effects*: Constructs a heap with respect to comp and proj out of the range [first, last)[.](#make.heap-3.sentence-1) [4](#make.heap-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11054) *Returns*: last for the overloads in namespace ranges[.](#make.heap-4.sentence-1) [5](#make.heap-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11058) *Complexity*: At most 3(last - first) comparisons and twice as many projections[.](#make.heap-5.sentence-1) #### [26.8.8.5](#sort.heap) sort_heap [[sort.heap]](sort.heap) [🔗](#lib:sort_heap) `template constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") constexpr I ranges::sort_heap(I first, S last, Comp comp = {}, Proj proj = {}); template<[random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> constexpr borrowed_iterator_t ranges::sort_heap(R&& r, Comp comp = {}, Proj proj = {}); ` [1](#sort.heap-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11086) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#sort.heap-1.sentence-1) [2](#sort.heap-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11091) *Preconditions*: The range [first, last) is a valid heap with respect to comp and proj[.](#sort.heap-2.sentence-1) For the overloads in namespace std,RandomAccessIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")) and the type of *first meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and[*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements")) requirements[.](#sort.heap-2.sentence-2) [3](#sort.heap-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11102) *Effects*: Sorts elements in the heap [first, last) with respect to comp and proj[.](#sort.heap-3.sentence-1) [4](#sort.heap-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11107) *Returns*: last for the overloads in namespace ranges[.](#sort.heap-4.sentence-1) [5](#sort.heap-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11111) *Complexity*: At most 2NlogN comparisons, where N=last - first, and twice as many projections[.](#sort.heap-5.sentence-1) #### [26.8.8.6](#is.heap) is_heap [[is.heap]](is.heap) [🔗](#lib:is_heap) `template constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last); ` [1](#is.heap-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11126) *Effects*: Equivalent to: return is_heap_until(first, last) == last; [🔗](#lib:is_heap_) `template bool is_heap(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last); ` [2](#is.heap-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11139) *Effects*: Equivalent to:return is_heap_until(std::forward(exec), first, last) == last; [🔗](#lib:is_heap__) `template constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); ` [3](#is.heap-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11155) *Effects*: Equivalent to: return is_heap_until(first, last, comp) == last; [🔗](#lib:is_heap___) `template bool is_heap(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last, Compare comp); ` [4](#is.heap-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11169) *Effects*: Equivalent to:return is_heap_until(std::forward(exec), first, last, comp) == last; [🔗](#lib:is_heap____) `template<[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr bool ranges::is_heap(I first, S last, Comp comp = {}, Proj proj = {}); template<[random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> constexpr bool ranges::is_heap(R&& r, Comp comp = {}, Proj proj = {}); ` [5](#is.heap-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11188) *Effects*: Equivalent to:return ranges​::​is_heap_until(first, last, comp, proj) == last; [🔗](#is.heap-itemdecl:6) `template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> bool ranges::is_heap(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> bool ranges::is_heap(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [6](#is.heap-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11205) *Effects*: Equivalent to:return ranges::is_heap_until(std::forward(exec), first, last, comp, proj) == last; [🔗](#lib:is_heap_until) `template constexpr RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last); template RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last); template constexpr RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr I ranges::is_heap_until(I first, S last, Comp comp = {}, Proj proj = {}); template<[random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> constexpr borrowed_iterator_t ranges::is_heap_until(R&& r, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> I ranges::is_heap_until(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> borrowed_iterator_t ranges::is_heap_until(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [7](#is.heap-7) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11252) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#is.heap-7.sentence-1) [8](#is.heap-8) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11257) *Returns*: The last iterator i in [first, last] for which the range [first, i) is a heap with respect to comp and proj[.](#is.heap-8.sentence-1) [9](#is.heap-9) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11263) *Complexity*: Linear[.](#is.heap-9.sentence-1) ### [26.8.9](#alg.min.max) Minimum and maximum [[alg.min.max]](alg.min.max) [🔗](#lib:min) `template constexpr const T& min(const T& a, const T& b); template constexpr const T& min(const T& a, const T& b, Compare comp); template> Comp = ranges::less> constexpr const T& ranges::min(const T& a, const T& b, Comp comp = {}, Proj proj = {}); ` [1](#alg.min.max-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11284) *Preconditions*: For the first form, T meets the[*Cpp17LessThanComparable*](utility.arg.requirements#:Cpp17LessThanComparable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements (Table [29](utility.arg.requirements#tab:cpp17.lessthancomparable "Table 29: Cpp17LessThanComparable requirements"))[.](#alg.min.max-1.sentence-1) [2](#alg.min.max-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11289) *Returns*: The smaller value[.](#alg.min.max-2.sentence-1) Returns the first argument when the arguments are equivalent[.](#alg.min.max-2.sentence-2) [3](#alg.min.max-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11294) *Complexity*: Exactly one comparison and two applications of the projection, if any[.](#alg.min.max-3.sentence-1) [4](#alg.min.max-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11298) *Remarks*: An invocation may explicitly specify an argument for the template parameter T of the overloads in namespace std[.](#alg.min.max-4.sentence-1) [🔗](#lib:min_) `template constexpr T min(initializer_list r); template constexpr T min(initializer_list r, Compare comp); template<[copyable](concepts.object#concept:copyable "18.6 Object concepts [concepts.object]") T, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr T ranges::min(initializer_list r, Comp comp = {}, Proj proj = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> requires [indirectly_copyable_storable](alg.req.ind.copy#concept:indirectly_copyable_storable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), range_value_t*> constexpr range_value_t ranges::min(R&& r, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> requires [indirectly_copyable_storable](alg.req.ind.copy#concept:indirectly_copyable_storable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), range_value_t*> range_value_t ranges::min(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [5](#alg.min.max-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11328) *Preconditions*: ranges​::​distance(r) > 0[.](#alg.min.max-5.sentence-1) For the overloads in namespace std,T meets the [*Cpp17CopyConstructible*](utility.arg.requirements#:Cpp17CopyConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements[.](#alg.min.max-5.sentence-2) For the first form, T meets the [*Cpp17LessThanComparable*](utility.arg.requirements#:Cpp17LessThanComparable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements (Table [29](utility.arg.requirements#tab:cpp17.lessthancomparable "Table 29: Cpp17LessThanComparable requirements"))[.](#alg.min.max-5.sentence-3) [6](#alg.min.max-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11336) *Returns*: The smallest value in the input range[.](#alg.min.max-6.sentence-1) Returns a copy of the leftmost element when several elements are equivalent to the smallest[.](#alg.min.max-6.sentence-2) [7](#alg.min.max-7) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11342) *Complexity*: Exactly ranges​::​distance(r) - 1 comparisons and twice as many applications of the projection, if any[.](#alg.min.max-7.sentence-1) [8](#alg.min.max-8) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11347) *Remarks*: An invocation may explicitly specify an argument for the template parameter T of the overloads in namespace std[.](#alg.min.max-8.sentence-1) [🔗](#lib:max) `template constexpr const T& max(const T& a, const T& b); template constexpr const T& max(const T& a, const T& b, Compare comp); template> Comp = ranges::less> constexpr const T& ranges::max(const T& a, const T& b, Comp comp = {}, Proj proj = {}); ` [9](#alg.min.max-9) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11367) *Preconditions*: For the first form, T meets the[*Cpp17LessThanComparable*](utility.arg.requirements#:Cpp17LessThanComparable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements (Table [29](utility.arg.requirements#tab:cpp17.lessthancomparable "Table 29: Cpp17LessThanComparable requirements"))[.](#alg.min.max-9.sentence-1) [10](#alg.min.max-10) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11372) *Returns*: The larger value[.](#alg.min.max-10.sentence-1) Returns the first argument when the arguments are equivalent[.](#alg.min.max-10.sentence-2) [11](#alg.min.max-11) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11377) *Complexity*: Exactly one comparison and two applications of the projection, if any[.](#alg.min.max-11.sentence-1) [12](#alg.min.max-12) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11381) *Remarks*: An invocation may explicitly specify an argument for the template parameter T of the overloads in namespace std[.](#alg.min.max-12.sentence-1) [🔗](#lib:max_) `template constexpr T max(initializer_list r); template constexpr T max(initializer_list r, Compare comp); template<[copyable](concepts.object#concept:copyable "18.6 Object concepts [concepts.object]") T, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr T ranges::max(initializer_list r, Comp comp = {}, Proj proj = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> requires [indirectly_copyable_storable](alg.req.ind.copy#concept:indirectly_copyable_storable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), range_value_t*> constexpr range_value_t ranges::max(R&& r, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> requires [indirectly_copyable_storable](alg.req.ind.copy#concept:indirectly_copyable_storable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), range_value_t*> range_value_t ranges::max(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [13](#alg.min.max-13) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11411) *Preconditions*: ranges​::​distance(r) > 0[.](#alg.min.max-13.sentence-1) For the overloads in namespace std,T meets the [*Cpp17CopyConstructible*](utility.arg.requirements#:Cpp17CopyConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements[.](#alg.min.max-13.sentence-2) For the first form, T meets the [*Cpp17LessThanComparable*](utility.arg.requirements#:Cpp17LessThanComparable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements (Table [29](utility.arg.requirements#tab:cpp17.lessthancomparable "Table 29: Cpp17LessThanComparable requirements"))[.](#alg.min.max-13.sentence-3) [14](#alg.min.max-14) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11419) *Returns*: The largest value in the input range[.](#alg.min.max-14.sentence-1) Returns a copy of the leftmost element when several elements are equivalent to the largest[.](#alg.min.max-14.sentence-2) [15](#alg.min.max-15) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11425) *Complexity*: Exactly ranges​::​distance(r) - 1 comparisons and twice as many applications of the projection, if any[.](#alg.min.max-15.sentence-1) [16](#alg.min.max-16) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11430) *Remarks*: An invocation may explicitly specify an argument for the template parameter T of the overloads in namespace std[.](#alg.min.max-16.sentence-1) [🔗](#lib:minmax) `template constexpr pair minmax(const T& a, const T& b); template constexpr pair minmax(const T& a, const T& b, Compare comp); template> Comp = ranges::less> constexpr ranges::minmax_result ranges::minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {}); ` [17](#alg.min.max-17) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11452) *Preconditions*: For the first form, T meets the[*Cpp17LessThanComparable*](utility.arg.requirements#:Cpp17LessThanComparable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements (Table [29](utility.arg.requirements#tab:cpp17.lessthancomparable "Table 29: Cpp17LessThanComparable requirements"))[.](#alg.min.max-17.sentence-1) [18](#alg.min.max-18) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11457) *Returns*: {b, a} if b is smaller than a, and{a, b} otherwise[.](#alg.min.max-18.sentence-1) [19](#alg.min.max-19) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11462) *Complexity*: Exactly one comparison and two applications of the projection, if any[.](#alg.min.max-19.sentence-1) [20](#alg.min.max-20) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11466) *Remarks*: An invocation may explicitly specify an argument for the template parameter T of the overloads in namespace std[.](#alg.min.max-20.sentence-1) [🔗](#lib:minmax_) `template constexpr pair minmax(initializer_list t); template constexpr pair minmax(initializer_list t, Compare comp); template<[copyable](concepts.object#concept:copyable "18.6 Object concepts [concepts.object]") T, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr ranges::minmax_result ranges::minmax(initializer_list r, Comp comp = {}, Proj proj = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> requires [indirectly_copyable_storable](alg.req.ind.copy#concept:indirectly_copyable_storable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), range_value_t*> constexpr ranges::minmax_result> ranges::minmax(R&& r, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> requires [indirectly_copyable_storable](alg.req.ind.copy#concept:indirectly_copyable_storable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), range_value_t*> ranges::minmax_result> ranges::minmax(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [21](#alg.min.max-21) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11497) *Preconditions*: ranges​::​distance(r) > 0[.](#alg.min.max-21.sentence-1) For the overloads in namespace std,T meets the [*Cpp17CopyConstructible*](utility.arg.requirements#:Cpp17CopyConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements[.](#alg.min.max-21.sentence-2) For the first form, type T meets the [*Cpp17LessThanComparable*](utility.arg.requirements#:Cpp17LessThanComparable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements (Table [29](utility.arg.requirements#tab:cpp17.lessthancomparable "Table 29: Cpp17LessThanComparable requirements"))[.](#alg.min.max-21.sentence-3) [22](#alg.min.max-22) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11505) *Returns*: Let X be the return type[.](#alg.min.max-22.sentence-1) Returns X{x, y}, where x is a copy of the leftmost element with the smallest value andy a copy of the rightmost element with the largest value in the input range[.](#alg.min.max-22.sentence-2) [23](#alg.min.max-23) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11513) *Complexity*: At most (3/2)ranges::distance(r) applications of the corresponding predicate and twice as many applications of the projection, if any[.](#alg.min.max-23.sentence-1) [24](#alg.min.max-24) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11519) *Remarks*: An invocation may explicitly specify an argument for the template parameter T of the overloads in namespace std[.](#alg.min.max-24.sentence-1) [🔗](#lib:min_element) `template constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last); template ForwardIterator min_element(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last); template constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp); template ForwardIterator min_element(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Compare comp); template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr I ranges::min_element(I first, S last, Comp comp = {}, Proj proj = {}); template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> constexpr borrowed_iterator_t ranges::min_element(R&& r, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> I ranges::min_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> borrowed_iterator_t ranges::min_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [25](#alg.min.max-25) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11562) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#alg.min.max-25.sentence-1) [26](#alg.min.max-26) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11567) *Returns*: The first iterator i in the range [first, last) such that for every iterator j in the range [first, last),bool(invoke(comp, invoke(proj, *j), invoke(proj, *i))) is false[.](#alg.min.max-26.sentence-1) Returns last if first == last[.](#alg.min.max-26.sentence-2) [27](#alg.min.max-27) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11577) *Complexity*: Exactly max(last - first - 1,0) comparisons and twice as many projections[.](#alg.min.max-27.sentence-1) [🔗](#lib:max_element) `template constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last); template ForwardIterator max_element(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last); template constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp); template ForwardIterator max_element(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Compare comp); template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr I ranges::max_element(I first, S last, Comp comp = {}, Proj proj = {}); template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> constexpr borrowed_iterator_t ranges::max_element(R&& r, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> I ranges::max_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> borrowed_iterator_t ranges::max_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [28](#alg.min.max-28) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11619) Let comp be less{} and proj be identity{} for the overloads with no parameters by those names[.](#alg.min.max-28.sentence-1) [29](#alg.min.max-29) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11624) *Returns*: The first iterator i in the range [first, last) such that for every iterator j in the range [first, last),bool(invoke(comp, invoke(proj, *i), invoke(proj, *j))) is false[.](#alg.min.max-29.sentence-1) Returns last if first == last[.](#alg.min.max-29.sentence-2) [30](#alg.min.max-30) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11634) *Complexity*: Exactly max(last - first - 1,0) comparisons and twice as many projections[.](#alg.min.max-30.sentence-1) [🔗](#lib:minmax_element) `template constexpr pair minmax_element(ForwardIterator first, ForwardIterator last); template pair minmax_element(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last); template constexpr pair minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); template pair minmax_element(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Compare comp); template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> constexpr ranges::minmax_element_result ranges::minmax_element(I first, S last, Comp comp = {}, Proj proj = {}); template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> constexpr ranges::minmax_element_result> ranges::minmax_element(R&& r, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")> Comp = ranges::less> ranges::minmax_element_result ranges::minmax_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj>> Comp = ranges::less> ranges::minmax_element_result> ranges::minmax_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {}); ` [31](#alg.min.max-31) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11680) *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[204](#footnote-204 "This behavior intentionally differs from max_­element.") in [first, last) such that no iterator in the range refers to a larger element[.](#alg.min.max-31.sentence-1) [32](#alg.min.max-32) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11692) *Complexity*: Let N be last - first[.](#alg.min.max-32.sentence-1) At most max(⌊32(N−1)⌋,0) comparisons and twice as many applications of the projection, if any[.](#alg.min.max-32.sentence-2) [204)](#footnote-204)[204)](#footnoteref-204) This behavior intentionally differs from max_element[.](#footnote-204.sentence-1) ### [26.8.10](#alg.clamp) Bounded value [[alg.clamp]](alg.clamp) [🔗](#lib:clamp) `template constexpr const T& clamp(const T& v, const T& lo, const T& hi); template constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); template> Comp = ranges::less> constexpr const T& ranges::clamp(const T& v, const T& lo, const T& hi, Comp comp = {}, Proj proj = {}); ` [1](#alg.clamp-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11714) Let comp be less{} for the overloads with no parameter comp, and let proj be identity{} for the overloads with no parameter proj[.](#alg.clamp-1.sentence-1) [2](#alg.clamp-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11720) *Preconditions*: bool(invoke(comp, invoke(proj, hi), invoke(proj, lo))) is false[.](#alg.clamp-2.sentence-1) For the first form, type T meets the [*Cpp17LessThanComparable*](utility.arg.requirements#:Cpp17LessThanComparable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements (Table [29](utility.arg.requirements#tab:cpp17.lessthancomparable "Table 29: Cpp17LessThanComparable requirements"))[.](#alg.clamp-2.sentence-2) [3](#alg.clamp-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11727) *Returns*: lo if bool(invoke(comp, invoke(proj, v), invoke(proj, lo))) is true,hi if bool(​invoke(comp, invoke(proj, hi), invoke(proj, v))) is true, otherwise v[.](#alg.clamp-3.sentence-1) [4](#alg.clamp-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11733) [*Note [1](#alg.clamp-note-1)*: If NaN is avoided, T can be a floating-point type[.](#alg.clamp-4.sentence-1) — *end note*] [5](#alg.clamp-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11738) *Complexity*: At most two comparisons and three applications of the projection[.](#alg.clamp-5.sentence-1) ### [26.8.11](#alg.lex.comparison) Lexicographical comparison [[alg.lex.comparison]](alg.lex.comparison) [🔗](#lib:lexicographical_compare) `template constexpr bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template bool lexicographical_compare(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template constexpr bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); template bool lexicographical_compare(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, Compare comp); template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I1, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S1, [input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I2, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S2, class Proj1 = identity, class Proj2 = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), projected> Comp = ranges::less> constexpr bool ranges::lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R1, [input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R2, class Proj1 = identity, class Proj2 = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj1>, projected, Proj2>> Comp = ranges::less> constexpr bool ranges::lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I1, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S1, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I2, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") S2, class Proj1 = identity, class Proj2 = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), projected> Comp = ranges::less> bool ranges::lexicographical_compare(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R1, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R2, class Proj1 = identity, class Proj2 = identity, [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]"), Proj1>, projected, Proj2>> Comp = ranges::less> bool ranges::lexicographical_compare(Ep&& exec, R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); ` [1](#alg.lex.comparison-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11801) *Returns*: true if and only 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)[.](#alg.lex.comparison-1.sentence-1) [2](#alg.lex.comparison-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11808) *Complexity*: At most 2 min(last1 - first1, last2 - first2) applications of the corresponding comparison and each projection, if any[.](#alg.lex.comparison-2.sentence-1) [3](#alg.lex.comparison-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11813) *Remarks*: If two sequences have the same number of elements and their corresponding elements (if any) are equivalent, then neither sequence is lexicographically less than the other[.](#alg.lex.comparison-3.sentence-1) If one sequence is a proper prefix of the other, then the shorter sequence is lexicographically less than the longer sequence[.](#alg.lex.comparison-3.sentence-2) 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[.](#alg.lex.comparison-3.sentence-3) [4](#alg.lex.comparison-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11824) [*Example [1](#alg.lex.comparison-example-1)*: ranges​::​lexicographical_compare(I1, S1, I2, S2, Comp, Proj1, Proj2) can be implemented as: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; — *end example*] [5](#alg.lex.comparison-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11837) [*Note [1](#alg.lex.comparison-note-1)*: An empty sequence is lexicographically less than any non-empty sequence, but not less than any empty sequence[.](#alg.lex.comparison-5.sentence-1) — *end note*] ### [26.8.12](#alg.three.way) Three-way comparison algorithms [[alg.three.way]](alg.three.way) [🔗](#lib:lexicographical_compare_three_way) `template constexpr auto lexicographical_compare_three_way(InputIterator1 b1, InputIterator1 e1, InputIterator2 b2, InputIterator2 e2, Cmp comp) -> decltype(comp(*b1, *b2)); ` [1](#alg.three.way-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11857) Let N be min(e1 - b1, e2 - b2)[.](#alg.three.way-1.sentence-1) Let E(n) be comp(*(b1 + n), *(b2 + n))[.](#alg.three.way-1.sentence-2) [2](#alg.three.way-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11861) *Mandates*: decltype(comp(*b1, *b2)) is a comparison category type[.](#alg.three.way-2.sentence-1) [3](#alg.three.way-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11865) *Returns*: E(i), where i is the smallest integer in [0, N) such that E(i) != 0 is true, or(e1 - b1) <=> (e2 - b2) if no such integer exists[.](#alg.three.way-3.sentence-1) [4](#alg.three.way-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11871) *Complexity*: At most N applications of comp[.](#alg.three.way-4.sentence-1) [🔗](#lib:lexicographical_compare_three_way_) `template constexpr auto lexicographical_compare_three_way(InputIterator1 b1, InputIterator1 e1, InputIterator2 b2, InputIterator2 e2); ` [5](#alg.three.way-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11885) *Effects*: Equivalent to:return lexicographical_compare_three_way(b1, e1, b2, e2, compare_three_way()); ### [26.8.13](#alg.permutation.generators) Permutation generators [[alg.permutation.generators]](alg.permutation.generators) [🔗](#lib:next_permutation) `template constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); template constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); template<[bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") constexpr ranges::next_permutation_result ranges::next_permutation(I first, S last, Comp comp = {}, Proj proj = {}); template<[bidirectional_range](range.refinements#concept:bidirectional_range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> constexpr ranges::next_permutation_result> ranges::next_permutation(R&& r, Comp comp = {}, Proj proj = {}); ` [1](#alg.permutation.generators-1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11918) Let comp be less{} and proj be identity{} for overloads with no parameters by those names[.](#alg.permutation.generators-1.sentence-1) [2](#alg.permutation.generators-2) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11923) *Preconditions*: For the overloads in namespace std,BidirectionalIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements"))[.](#alg.permutation.generators-2.sentence-1) [3](#alg.permutation.generators-3) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11929) *Effects*: Takes a sequence defined by the range [first, last) and transforms it into the next permutation[.](#alg.permutation.generators-3.sentence-1) The next permutation is found by assuming that the set of all permutations is lexicographically sorted with respect to comp and proj[.](#alg.permutation.generators-3.sentence-2) If no such permutation exists, transforms the sequence into the first permutation; that is, the ascendingly-sorted one[.](#alg.permutation.generators-3.sentence-3) [4](#alg.permutation.generators-4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11939) *Returns*: Let B be true if a next permutation was found and otherwise false[.](#alg.permutation.generators-4.sentence-1) Returns: - [(4.1)](#alg.permutation.generators-4.1) B for the overloads in namespace std[.](#alg.permutation.generators-4.1.sentence-1) - [(4.2)](#alg.permutation.generators-4.2) { last, B } for the overloads in namespace ranges[.](#alg.permutation.generators-4.2.sentence-1) [5](#alg.permutation.generators-5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11949) *Complexity*: At most (last - first) / 2 swaps[.](#alg.permutation.generators-5.sentence-1) [🔗](#lib:prev_permutation) `template constexpr bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last); template constexpr bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); template<[bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") S, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") constexpr ranges::prev_permutation_result ranges::prev_permutation(I first, S last, Comp comp = {}, Proj proj = {}); template<[bidirectional_range](range.refinements#concept:bidirectional_range "25.4.6 Other range refinements [range.refinements]") R, class Comp = ranges::less, class Proj = identity> requires [sortable](alg.req.sortable#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]"), Comp, Proj> constexpr ranges::prev_permutation_result> ranges::prev_permutation(R&& r, Comp comp = {}, Proj proj = {}); ` [6](#alg.permutation.generators-6) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11977) Let comp be less{} and proj be identity{} for overloads with no parameters by those names[.](#alg.permutation.generators-6.sentence-1) [7](#alg.permutation.generators-7) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11982) *Preconditions*: For the overloads in namespace std,BidirectionalIterator meets the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements"))[.](#alg.permutation.generators-7.sentence-1) [8](#alg.permutation.generators-8) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11988) *Effects*: Takes a sequence defined by the range [first, last) and transforms it into the previous permutation[.](#alg.permutation.generators-8.sentence-1) The previous permutation is found by assuming that the set of all permutations is lexicographically sorted with respect to comp and proj[.](#alg.permutation.generators-8.sentence-2) If no such permutation exists, transforms the sequence into the last permutation; that is, the descendingly-sorted one[.](#alg.permutation.generators-8.sentence-3) [9](#alg.permutation.generators-9) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L11998) *Returns*: Let B be true if a previous permutation was found and otherwise false[.](#alg.permutation.generators-9.sentence-1) Returns: - [(9.1)](#alg.permutation.generators-9.1) B for the overloads in namespace std[.](#alg.permutation.generators-9.1.sentence-1) - [(9.2)](#alg.permutation.generators-9.2) { last, B } for the overloads in namespace ranges[.](#alg.permutation.generators-9.2.sentence-1) [10](#alg.permutation.generators-10) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12008) *Complexity*: At most (last - first) / 2 swaps[.](#alg.permutation.generators-10.sentence-1)