[alg.sorting] - C++20 → C++23

Files changed (1) hide show

tmp/tmpypxhy_tj/{from.md → to.md} +99 -89

tmp/tmpypxhy_tj/{from.md → to.md} RENAMED Viewed

@@ -1,18 +1,20 @@
 ## Sorting and related operations <a id="alg.sorting">[[alg.sorting]]</a>
 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<`.
 `Compare` is a function object type [[function.objects]] that meets the
 requirements for a template parameter named `BinaryPredicate`
 [[algorithms.requirements]]. The return value of the function call
-operation applied to an object of type `Compare`, when contextually
-converted to `bool` [[conv]], yields `true` if the first argument of the
-call is less than the second, and `false` otherwise. `Compare comp` is
-used throughout for algorithms assuming an ordering relation.
 For all algorithms that take `Compare`, there is a version that uses
 `operator<` instead. That is, `comp(*i, *j) != false` defaults to
 `*i < *j != false`. For algorithms other than those described in
 [[alg.binary.search]], `comp` shall induce a strict weak ordering on the
@@ -48,10 +50,14 @@ pointing to the sequence and every non-negative integer `n` such that
 bool(invoke(comp, invoke(proj, *(i + n)), invoke(proj, *i)))
 ```
 is `false`.
 A sequence \[`start`, `finish`) is *partitioned with respect to an
 expression* `f(e)` if there exists an integer `n` such that for all
 `0 <= i < (finish - start)`, `f(*(start + i))` is `true` if and only if
 `i < n`.
@@ -283,13 +289,13 @@ with no parameters by those names.
 `RandomAccessIterator` meets the *Cpp17ValueSwappable*
 requirements [[swappable.requirements]], the type of `*result_first`
 meets the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
 *Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
-*Preconditions:* For iterators `a1` and `b1` in \[`first`, `last`), and
-iterators `x2` and `y2` in \[`result_first`, `result_last`), after
-evaluating the assignment `*y2 = *b1`, let E be the value of
 ``` cpp
 bool(invoke(comp, invoke(proj1, *a1), invoke(proj2, *y2))).
 ```
@@ -467,19 +473,21 @@ template<random_access_range R, class Comp = ranges::less, class Proj = identity
 return ranges::nth_element(ranges::begin(r), nth, ranges::end(r), comp, proj);
 ```
 ### Binary search <a id="alg.binary.search">[[alg.binary.search]]</a>
-All of the algorithms in this subclause are versions of binary search
-and assume that the sequence being searched is partitioned with respect
-to an expression formed by binding the search key to an argument of the
-comparison function. They work on non-random access iterators minimizing
-the number of comparisons, which will be logarithmic for all types of
-iterators. They are especially appropriate for random access iterators,
-because these algorithms do a logarithmic number of steps through the
-data structure. For non-random access iterators they execute a linear
-number of steps.
 #### `lower_bound` <a id="lower.bound">[[lower.bound]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
@@ -759,19 +767,18 @@ range \[`i`, `last`), E(`*j`) is `false`. Returns:
 - `i` for the overloads in namespace `std`.
 - `{i, last}` for the overloads in namespace `ranges`.
 *Complexity:* Let N = `last - first`:
-- For the overloads with no `ExecutionPolicy`, at most N log N swaps,
   but only 𝑂(N) swaps if there is enough extra memory. Exactly N
   applications of the predicate and projection.
 - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
   applications of the predicate.
 ``` cpp
-template<class InputIterator, class OutputIterator1,
-         class OutputIterator2, class Predicate>
   constexpr pair<OutputIterator1, OutputIterator2>
     partition_copy(InputIterator first, InputIterator last,
                    OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred);
 template<class ExecutionPolicy, class ForwardIterator, class ForwardIterator1,
          class ForwardIterator2, class Predicate>
@@ -802,11 +809,11 @@ Let `proj` be `identity{}` for the overloads with no parameter named
 `*first` is writable [[iterator.requirements.general]] to `out_true` and
 `out_false`.
 *Preconditions:* The input range and output ranges do not overlap.
-[*Note 1*: For the overload with an `ExecutionPolicy`, there may be a
 performance cost if `first`’s value type does not meet the
 *Cpp17CopyConstructible* requirements. — *end note*]
 *Effects:* For each iterator `i` in \[`first`, `last`), copies `*i` to
 the output range beginning with `out_true` if E(`*i`) is `true`, or to
@@ -991,16 +998,18 @@ template<bidirectional_range R, class Comp = ranges::less, class Proj = identity
 return ranges::inplace_merge(ranges::begin(r), middle, ranges::end(r), comp, proj);
 ```
 ### Set operations on sorted structures <a id="alg.set.operations">[[alg.set.operations]]</a>
-This subclause defines all the basic set operations on sorted
-structures. They also work with `multiset`s [[multiset]] containing
-multiple copies of equivalent elements. The semantics of the set
-operations are generalized to `multiset`s 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.
 #### `includes` <a id="includes">[[includes]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2>
@@ -1053,12 +1062,11 @@ keeping the remaining elements in the same order. — *end note*]
 comparisons and applications of each projection.
 #### `set_union` <a id="set.union">[[set.union]]</a>
 ``` cpp
-template<class InputIterator1, class InputIterator2,
-         class OutputIterator>
   constexpr OutputIterator
     set_union(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
@@ -1067,12 +1075,11 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
     set_union(ExecutionPolicy&& exec,
               ForwardIterator1 first1, ForwardIterator1 last1,
               ForwardIterator2 first2, ForwardIterator2 last2,
               ForwardIterator result);
-template<class InputIterator1, class InputIterator2,
-         class OutputIterator, class Compare>
   constexpr OutputIterator
     set_union(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
@@ -1266,11 +1273,11 @@ Returns
 comparisons and applications of each projection.
 *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`) is copied to the output range, in order.
 #### `set_symmetric_difference` <a id="set.symmetric.difference">[[set.symmetric.difference]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
@@ -1349,10 +1356,12 @@ elements from \[`first1`, `last1`) if m > n, and the last n - m of these
 elements from \[`first2`, `last2`) if m < n. In either case, the
 elements are copied in order.
 ### Heap operations <a id="alg.heap.operations">[[alg.heap.operations]]</a>
 A random access range \[`a`, `b`) is a *heap with respect to `comp` and
 `proj`* for a comparator and projection `comp` and `proj` if its
 elements are organized such that:
 - With `N = b - a`, for all i, 0 < i < N,
@@ -1389,14 +1398,15 @@ template<random_access_range R, class Comp = ranges::less, class Proj = identity
 Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
 no parameters by those names.
 *Preconditions:* The range \[`first`, `last - 1`) is a valid heap with
-respect to `comp` and `proj`. For the overloads in namespace `std`, the
-type of `*first` meets the *Cpp17MoveConstructible* requirements
-([[cpp17.moveconstructible]]) and the *Cpp17MoveAssignable*
-requirements ([[cpp17.moveassignable]]).
 *Effects:* Places the value in the location `last - 1` into the
 resulting heap \[`first`, `last`).
 *Returns:* `last` for the overloads in namespace `ranges`.
@@ -1466,14 +1476,15 @@ template<random_access_range R, class Comp = ranges::less, class Proj = identity
 ```
 Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
 no parameters by those names.
-*Preconditions:* For the overloads in namespace `std`, the type of
-`*first` meets the *Cpp17MoveConstructible*
-([[cpp17.moveconstructible]]) and *Cpp17MoveAssignable*
-([[cpp17.moveassignable]]) requirements.
 *Effects:* Constructs a heap with respect to `comp` and `proj` out of
 the range \[`first`, `last`).
 *Returns:* `last` for the overloads in namespace `ranges`.
@@ -1625,19 +1636,19 @@ template<class T, class Proj = identity,
 ```
 *Preconditions:* For the first form, `T` meets the
 *Cpp17LessThanComparable* requirements ([[cpp17.lessthancomparable]]).
-*Returns:* The smaller value.
-*Remarks:* Returns the first argument when the arguments are equivalent.
-An invocation may explicitly specify an argument for the template
-parameter `T` of the overloads in namespace `std`.
 *Complexity:* Exactly one comparison and two applications of the
 projection, if any.
 ``` cpp
 template<class T>
   constexpr T min(initializer_list<T> r);
 template<class T, class Compare>
   constexpr T min(initializer_list<T> r, Compare comp);
@@ -1655,20 +1666,19 @@ template<input_range R, class Proj = identity,
 *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
 namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
 For the first form, `T` meets the *Cpp17LessThanComparable* requirements
 ([[cpp17.lessthancomparable]]).
-*Returns:* The smallest value in the input range.
-*Remarks:* Returns a copy of the leftmost element when several elements
-are equivalent to the smallest. An invocation may explicitly specify an
-argument for the template parameter `T` of the overloads in namespace
-`std`.
 *Complexity:* Exactly `ranges::distance(r) - 1` comparisons and twice as
 many applications of the projection, if any.
 ``` cpp
 template<class T>
   constexpr const T& max(const T& a, const T& b);
 template<class T, class Compare>
   constexpr const T& max(const T& a, const T& b, Compare comp);
@@ -1679,19 +1689,19 @@ template<class T, class Proj = identity,
 ```
 *Preconditions:* For the first form, `T` meets the
 *Cpp17LessThanComparable* requirements ([[cpp17.lessthancomparable]]).
-*Returns:* The larger value.
-*Remarks:* Returns the first argument when the arguments are equivalent.
-An invocation may explicitly specify an argument for the template
-parameter `T` of the overloads in namespace `std`.
 *Complexity:* Exactly one comparison and two applications of the
 projection, if any.
 ``` cpp
 template<class T>
   constexpr T max(initializer_list<T> r);
 template<class T, class Compare>
   constexpr T max(initializer_list<T> r, Compare comp);
@@ -1709,20 +1719,19 @@ template<input_range R, class Proj = identity,
 *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
 namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
 For the first form, `T` meets the *Cpp17LessThanComparable* requirements
 ([[cpp17.lessthancomparable]]).
-*Returns:* The largest value in the input range.
-*Remarks:* Returns a copy of the leftmost element when several elements
-are equivalent to the largest. An invocation may explicitly specify an
-argument for the template parameter `T` of the overloads in namespace
-`std`.
 *Complexity:* Exactly `ranges::distance(r) - 1` comparisons and twice as
 many applications of the projection, if any.
 ``` cpp
 template<class T>
   constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
 template<class T, class Compare>
   constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
@@ -1736,16 +1745,16 @@ template<class T, class Proj = identity,
 *Preconditions:* For the first form, `T` meets the
 *Cpp17LessThanComparable* requirements ([[cpp17.lessthancomparable]]).
 *Returns:* `{b, a}` if `b` is smaller than `a`, and `{a, b}` otherwise.
-*Remarks:* An invocation may explicitly specify an argument for the
-template parameter `T` of the overloads in namespace `std`.
 *Complexity:* Exactly one comparison and two applications of the
 projection, if any.
 ``` cpp
 template<class T>
   constexpr pair<T, T> minmax(initializer_list<T> t);
 template<class T, class Compare>
   constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
@@ -1768,17 +1777,17 @@ requirements ([[cpp17.lessthancomparable]]).
 *Returns:* Let `X` be the return type. Returns `X{x, y}`, where `x` is a
 copy of the leftmost element with the smallest value and `y` a copy of
 the rightmost element with the largest value in the input range.
-*Remarks:* An invocation may explicitly specify an argument for the
-template parameter `T` of the overloads in namespace `std`.
 *Complexity:* At most (3/2)`ranges::distance(r)` applications of the
 corresponding predicate and twice as many applications of the
 projection, if any.
 ``` cpp
 template<class ForwardIterator>
   constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
 template<class ExecutionPolicy, class ForwardIterator>
@@ -1788,12 +1797,11 @@ template<class ExecutionPolicy, class ForwardIterator>
 template<class ForwardIterator, class Compare>
   constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                                         Compare comp);
 template<class ExecutionPolicy, class ForwardIterator, class Compare>
   ForwardIterator min_element(ExecutionPolicy&& exec,
-                              ForwardIterator first, ForwardIterator last,
-                              Compare comp);
 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
          indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
   constexpr I ranges::min_element(I first, S last, Comp comp = {}, Proj proj = {});
 template<forward_range R, class Proj = identity,
@@ -1873,23 +1881,25 @@ template<class ExecutionPolicy, class ForwardIterator, class Compare>
     minmax_element(ExecutionPolicy&& exec,
                    ForwardIterator first, ForwardIterator last, Compare comp);
 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
          indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
-  constexpr ranges::minmax_result<I>
     ranges::minmax_element(I first, S last, Comp comp = {}, Proj proj = {});
 template<forward_range R, class Proj = identity,
          indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
-  constexpr ranges::minmax_result<borrowed_iterator_t<R>>
     ranges::minmax_element(R&& r, Comp comp = {}, Proj proj = {});
 ```
 *Returns:* `{first, first}` if \[`first`, `last`) is empty, otherwise
 `{m, M}`, where `m` is the first iterator in \[`first`, `last`) such
 that no iterator in the range refers to a smaller element, and where `M`
-is the last iterator[^5] in \[`first`, `last`) such that no iterator in
-the range refers to a larger element.
 *Complexity:* Let N be `last - first`. At most
 $\max(\bigl\lfloor{\frac{3}{2}} (N-1)\bigr\rfloor, 0)$ comparisons and
 twice as many applications of the projection, if any.
@@ -1907,16 +1917,19 @@ template<class T, class Proj = identity,
 ```
 Let `comp` be `less{}` for the overloads with no parameter `comp`, and
 let `proj` be `identity{}` for the overloads with no parameter `proj`.
-*Preconditions:* `bool(comp(proj(hi), proj(lo)))` is `false`. For the
-first form, type `T` meets the *Cpp17LessThanComparable* requirements
-([[cpp17.lessthancomparable]]).
-*Returns:* `lo` if `bool(comp(proj(v), proj(lo)))` is `true`, `hi` if
-`bool(comp(proj(hi), proj(v)))` is `true`, otherwise `v`.
 [*Note 1*: If NaN is avoided, `T` can be a floating-point
 type. — *end note*]
 *Complexity:* At most two comparisons and three applications of the
@@ -1981,11 +1994,11 @@ the sequences yields the same result as the comparison of the first
 corresponding pair of elements that are not equivalent.
 [*Example 1*:
 `ranges::lexicographical_compare(I1, S1, I2, S2, Comp, Proj1, Proj2)`
-could be implemented as:
 ``` cpp
 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;
@@ -2007,23 +2020,20 @@ template<class InputIterator1, class InputIterator2, class Cmp>
                                       InputIterator2 b2, InputIterator2 e2,
                                       Cmp comp)
       -> decltype(comp(*b1, *b2));
 ```
 *Mandates:* `decltype(comp(*b1, *b2))` is a comparison category type.
-*Effects:* Lexicographically compares two ranges and produces a result
-of the strongest applicable comparison category type. Equivalent to:
-``` cpp
-for ( ; b1 != e1 && b2 != e2; void(++b1), void(++b2) )
-  if (auto cmp = comp(*b1,*b2); cmp != 0)
-    return cmp;
-return b1 != e1 ? strong_ordering::greater :
-       b2 != e2 ? strong_ordering::less :
-                  strong_ordering::equal;
-```
 ``` cpp
 template<class InputIterator1, class InputIterator2>
   constexpr auto
     lexicographical_compare_three_way(InputIterator1 b1, InputIterator1 e1,

 ## Sorting and related operations <a id="alg.sorting">[[alg.sorting]]</a>
+### General <a id="alg.sorting.general">[[alg.sorting.general]]</a>
 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<`.
 `Compare` is a function object type [[function.objects]] that meets the
 requirements for a template parameter named `BinaryPredicate`
 [[algorithms.requirements]]. The return value of the function call
+operation applied to an object of type `Compare`, when converted to
+`bool`, yields `true` if the first argument of the call is less than the
+second, and `false` otherwise. `Compare comp` is used throughout for
+algorithms assuming an ordering relation.
 For all algorithms that take `Compare`, there is a version that uses
 `operator<` instead. That is, `comp(*i, *j) != false` defaults to
 `*i < *j != false`. For algorithms other than those described in
 [[alg.binary.search]], `comp` shall induce a strict weak ordering on the
 bool(invoke(comp, invoke(proj, *(i + n)), invoke(proj, *i)))
 ```
 is `false`.
+A sequence is *sorted with respect to a comparator `comp`* for a
+comparator `comp` if it is sorted with respect to `comp` and
+`identity{}` (the identity projection).
 A sequence \[`start`, `finish`) is *partitioned with respect to an
 expression* `f(e)` if there exists an integer `n` such that for all
 `0 <= i < (finish - start)`, `f(*(start + i))` is `true` if and only if
 `i < n`.
 `RandomAccessIterator` meets the *Cpp17ValueSwappable*
 requirements [[swappable.requirements]], the type of `*result_first`
 meets the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
 *Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
+For iterators `a1` and `b1` in \[`first`, `last`), and iterators `x2`
+and `y2` in \[`result_first`, `result_last`), after evaluating the
+assignment `*y2 = *b1`, let E be the value of
 ``` cpp
 bool(invoke(comp, invoke(proj1, *a1), invoke(proj2, *y2))).
 ```
 return ranges::nth_element(ranges::begin(r), nth, ranges::end(r), comp, proj);
 ```
 ### Binary search <a id="alg.binary.search">[[alg.binary.search]]</a>
+#### General <a id="alg.binary.search.general">[[alg.binary.search.general]]</a>
+All of the algorithms in [[alg.binary.search]] are versions of binary
+search and assume that the sequence being searched is partitioned with
+respect to an expression formed by binding the search key to an argument
+of the comparison function. They work on non-random access iterators
+minimizing the number of comparisons, which will be logarithmic for all
+types of iterators. They are especially appropriate for random access
+iterators, because these algorithms do a logarithmic number of steps
+through the data structure. For non-random access iterators they execute
+a linear number of steps.
 #### `lower_bound` <a id="lower.bound">[[lower.bound]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
 - `i` for the overloads in namespace `std`.
 - `{i, last}` for the overloads in namespace `ranges`.
 *Complexity:* Let N = `last - first`:
+- For the overloads with no `ExecutionPolicy`, at most N log₂ N swaps,
   but only 𝑂(N) swaps if there is enough extra memory. Exactly N
   applications of the predicate and projection.
 - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
   applications of the predicate.
 ``` cpp
+template<class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate>
   constexpr pair<OutputIterator1, OutputIterator2>
     partition_copy(InputIterator first, InputIterator last,
                    OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred);
 template<class ExecutionPolicy, class ForwardIterator, class ForwardIterator1,
          class ForwardIterator2, class Predicate>
 `*first` is writable [[iterator.requirements.general]] to `out_true` and
 `out_false`.
 *Preconditions:* The input range and output ranges do not overlap.
+[*Note 1*: For the overload with an `ExecutionPolicy`, there might be a
 performance cost if `first`’s value type does not meet the
 *Cpp17CopyConstructible* requirements. — *end note*]
 *Effects:* For each iterator `i` in \[`first`, `last`), copies `*i` to
 the output range beginning with `out_true` if E(`*i`) is `true`, or to
 return ranges::inplace_merge(ranges::begin(r), middle, ranges::end(r), comp, proj);
 ```
 ### Set operations on sorted structures <a id="alg.set.operations">[[alg.set.operations]]</a>
+#### General <a id="alg.set.operations.general">[[alg.set.operations.general]]</a>
+Subclause [[alg.set.operations]] defines all the basic set operations on
+sorted structures. They also work with `multiset`s [[multiset]]
+containing multiple copies of equivalent elements. The semantics of the
+set operations are generalized to `multiset`s 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.
 #### `includes` <a id="includes">[[includes]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2>
 comparisons and applications of each projection.
 #### `set_union` <a id="set.union">[[set.union]]</a>
 ``` cpp
+template<class InputIterator1, class InputIterator2, class OutputIterator>
   constexpr OutputIterator
     set_union(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
     set_union(ExecutionPolicy&& exec,
               ForwardIterator1 first1, ForwardIterator1 last1,
               ForwardIterator2 first2, ForwardIterator2 last2,
               ForwardIterator result);
+template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
   constexpr OutputIterator
     set_union(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
 comparisons and applications of each projection.
 *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_symmetric_difference` <a id="set.symmetric.difference">[[set.symmetric.difference]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
 elements from \[`first2`, `last2`) if m < n. In either case, the
 elements are copied in order.
 ### Heap operations <a id="alg.heap.operations">[[alg.heap.operations]]</a>
+#### General <a id="alg.heap.operations.general">[[alg.heap.operations.general]]</a>
 A random access range \[`a`, `b`) is a *heap with respect to `comp` and
 `proj`* for a comparator and projection `comp` and `proj` if its
 elements are organized such that:
 - With `N = b - a`, for all i, 0 < i < N,
 Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
 no parameters by those names.
 *Preconditions:* The range \[`first`, `last - 1`) is a valid heap with
+respect to `comp` and `proj`. For the overloads in namespace `std`,
+`RandomAccessIterator` meets the *Cpp17ValueSwappable*
+requirements [[swappable.requirements]] and the type of `*first` meets
+the *Cpp17MoveConstructible* requirements ([[cpp17.moveconstructible]])
+and the *Cpp17MoveAssignable* requirements ([[cpp17.moveassignable]]).
 *Effects:* Places the value in the location `last - 1` into the
 resulting heap \[`first`, `last`).
 *Returns:* `last` for the overloads in namespace `ranges`.
 ```
 Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
 no parameters by those names.
+*Preconditions:* For the overloads in namespace `std`,
+`RandomAccessIterator` meets the *Cpp17ValueSwappable*
+requirements [[swappable.requirements]] and the type of `*first` meets
+the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
+*Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
 *Effects:* Constructs a heap with respect to `comp` and `proj` out of
 the range \[`first`, `last`).
 *Returns:* `last` for the overloads in namespace `ranges`.
 ```
 *Preconditions:* For the first form, `T` meets the
 *Cpp17LessThanComparable* requirements ([[cpp17.lessthancomparable]]).
+*Returns:* The smaller value. Returns the first argument when the
+arguments are equivalent.
 *Complexity:* Exactly one comparison and two applications of the
 projection, if any.
+*Remarks:* An invocation may explicitly specify an argument for the
+template parameter `T` of the overloads in namespace `std`.
 ``` cpp
 template<class T>
   constexpr T min(initializer_list<T> r);
 template<class T, class Compare>
   constexpr T min(initializer_list<T> r, Compare comp);
 *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
 namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
 For the first form, `T` meets the *Cpp17LessThanComparable* requirements
 ([[cpp17.lessthancomparable]]).
+*Returns:* The smallest value in the input range. Returns a copy of the
+leftmost element when several elements are equivalent to the smallest.
 *Complexity:* Exactly `ranges::distance(r) - 1` comparisons and twice as
 many applications of the projection, if any.
+*Remarks:* An invocation may explicitly specify an argument for the
+template parameter `T` of the overloads in namespace `std`.
 ``` cpp
 template<class T>
   constexpr const T& max(const T& a, const T& b);
 template<class T, class Compare>
   constexpr const T& max(const T& a, const T& b, Compare comp);
 ```
 *Preconditions:* For the first form, `T` meets the
 *Cpp17LessThanComparable* requirements ([[cpp17.lessthancomparable]]).
+*Returns:* The larger value. Returns the first argument when the
+arguments are equivalent.
 *Complexity:* Exactly one comparison and two applications of the
 projection, if any.
+*Remarks:* An invocation may explicitly specify an argument for the
+template parameter `T` of the overloads in namespace `std`.
 ``` cpp
 template<class T>
   constexpr T max(initializer_list<T> r);
 template<class T, class Compare>
   constexpr T max(initializer_list<T> r, Compare comp);
 *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
 namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
 For the first form, `T` meets the *Cpp17LessThanComparable* requirements
 ([[cpp17.lessthancomparable]]).
+*Returns:* The largest value in the input range. Returns a copy of the
+leftmost element when several elements are equivalent to the largest.
 *Complexity:* Exactly `ranges::distance(r) - 1` comparisons and twice as
 many applications of the projection, if any.
+*Remarks:* An invocation may explicitly specify an argument for the
+template parameter `T` of the overloads in namespace `std`.
 ``` cpp
 template<class T>
   constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
 template<class T, class Compare>
   constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
 *Preconditions:* For the first form, `T` meets the
 *Cpp17LessThanComparable* requirements ([[cpp17.lessthancomparable]]).
 *Returns:* `{b, a}` if `b` is smaller than `a`, and `{a, b}` otherwise.
 *Complexity:* Exactly one comparison and two applications of the
 projection, if any.
+*Remarks:* An invocation may explicitly specify an argument for the
+template parameter `T` of the overloads in namespace `std`.
 ``` cpp
 template<class T>
   constexpr pair<T, T> minmax(initializer_list<T> t);
 template<class T, class Compare>
   constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
 *Returns:* Let `X` be the return type. Returns `X{x, y}`, where `x` is a
 copy of the leftmost element with the smallest value and `y` a copy of
 the rightmost element with the largest value in the input range.
 *Complexity:* At most (3/2)`ranges::distance(r)` applications of the
 corresponding predicate and twice as many applications of the
 projection, if any.
+*Remarks:* An invocation may explicitly specify an argument for the
+template parameter `T` of the overloads in namespace `std`.
 ``` cpp
 template<class ForwardIterator>
   constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
 template<class ExecutionPolicy, class ForwardIterator>
 template<class ForwardIterator, class Compare>
   constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                                         Compare comp);
 template<class ExecutionPolicy, class ForwardIterator, class Compare>
   ForwardIterator min_element(ExecutionPolicy&& exec,
+                              ForwardIterator first, ForwardIterator last, Compare comp);
 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
          indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
   constexpr I ranges::min_element(I first, S last, Comp comp = {}, Proj proj = {});
 template<forward_range R, class Proj = identity,
     minmax_element(ExecutionPolicy&& exec,
                    ForwardIterator first, ForwardIterator last, Compare comp);
 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
          indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+  constexpr ranges::minmax_element_result<I>
     ranges::minmax_element(I first, S last, Comp comp = {}, Proj proj = {});
 template<forward_range R, class Proj = identity,
          indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+  constexpr ranges::minmax_element_result<borrowed_iterator_t<R>>
     ranges::minmax_element(R&& r, Comp comp = {}, Proj proj = {});
 ```
 *Returns:* `{first, first}` if \[`first`, `last`) is empty, otherwise
 `{m, M}`, where `m` is the first iterator in \[`first`, `last`) such
 that no iterator in the range refers to a smaller element, and where `M`
+is the last iterator[^5]
+in \[`first`, `last`) such that no iterator in the range refers to a
+larger element.
 *Complexity:* Let N be `last - first`. At most
 $\max(\bigl\lfloor{\frac{3}{2}} (N-1)\bigr\rfloor, 0)$ comparisons and
 twice as many applications of the projection, if any.
 ```
 Let `comp` be `less{}` for the overloads with no parameter `comp`, and
 let `proj` be `identity{}` for the overloads with no parameter `proj`.
+*Preconditions:*
+`bool(invoke(comp, invoke(proj, hi), invoke(proj, lo)))` is `false`. For
+the first form, type `T` meets the *Cpp17LessThanComparable*
+requirements ([[cpp17.lessthancomparable]]).
+*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`.
 [*Note 1*: If NaN is avoided, `T` can be a floating-point
 type. — *end note*]
 *Complexity:* At most two comparisons and three applications of the
 corresponding pair of elements that are not equivalent.
 [*Example 1*:
 `ranges::lexicographical_compare(I1, S1, I2, S2, Comp, Proj1, Proj2)`
+can be implemented as:
 ``` cpp
 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;
                                       InputIterator2 b2, InputIterator2 e2,
                                       Cmp comp)
       -> decltype(comp(*b1, *b2));
 ```
+Let N be min(`e1 - b1`, `e2 - b2`). Let E(n) be
+`comp(*(b1 + `n`), *(b2 + `n`))`.
 *Mandates:* `decltype(comp(*b1, *b2))` is a comparison category type.
+*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.
+*Complexity:* At most N applications of `comp`.
 ``` cpp
 template<class InputIterator1, class InputIterator2>
   constexpr auto
     lexicographical_compare_three_way(InputIterator1 b1, InputIterator1 e1,

Diff to HTML by rtfpessoa