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

Files changed (1) hide show

tmp/tmp76zluuda/{from.md → to.md} +1194 -452

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

@@ -1,19 +1,18 @@
 ## Sorting and related operations <a id="alg.sorting">[[alg.sorting]]</a>
-All the operations in  [[alg.sorting]] 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]]). The return value of
-the function call operation applied to an object of type `Compare`, when
-contextually converted to `bool` (Clause  [[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. It is assumed that `comp` will not apply any
-non-constant function through the dereferenced iterator.
 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
@@ -31,21 +30,27 @@ for a partial ordering. If we define `equiv(a, b)` as
 [*Note 1*:
 Under these conditions, it can be shown that
-- `equiv` is an equivalence relation
 - `comp` induces a well-defined relation on the equivalence classes
-  determined by `equiv`
-- The induced relation is a strict total ordering.
 — *end note*]
-A sequence is *sorted with respect to a comparator* `comp` 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, `comp(*(i + n), *i) == false`.
 A sequence \[`start`, `finish`) is *partitioned with respect to an
 expression* `f(e)` if there exists an integer `n` such that for all
 `0 <= i < (finish - start)`, `f(*(start + i))` is `true` if and only if
 `i < n`.
@@ -61,33 +66,50 @@ equivalent if and only if `!(a < b) && !(b < a)`.
 #### `sort` <a id="sort">[[sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
-  void sort(RandomAccessIterator first, RandomAccessIterator last);
 template<class ExecutionPolicy, class RandomAccessIterator>
   void sort(ExecutionPolicy&& exec,
             RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
-  void sort(RandomAccessIterator first, RandomAccessIterator last,
                       Compare comp);
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
   void sort(ExecutionPolicy&& exec,
             RandomAccessIterator first, RandomAccessIterator last,
             Compare comp);
 ```
-*Requires:* `RandomAccessIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
-(Table  [[tab:moveassignable]]).
-*Effects:* Sorts the elements in the range \[`first`, `last`).
-*Complexity:* 𝑂(N log N) comparisons, where N = `last - first`.
 #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
@@ -101,70 +123,112 @@ template<class RandomAccessIterator, class Compare>
                    Compare comp);
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
   void stable_sort(ExecutionPolicy&& exec,
                    RandomAccessIterator first, RandomAccessIterator last,
                    Compare comp);
 ```
-*Requires:* `RandomAccessIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
-(Table  [[tab:moveassignable]]).
-*Effects:* Sorts the elements in the range \[`first`, `last`).
-*Complexity:* At most N log²(N) comparisons, where N = `last - first`,
-but only N log N comparisons if there is enough extra memory.
-*Remarks:* Stable ([[algorithm.stable]]).
 #### `partial_sort` <a id="partial.sort">[[partial.sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
-  void partial_sort(RandomAccessIterator first,
                               RandomAccessIterator middle,
                               RandomAccessIterator last);
 template<class ExecutionPolicy, class RandomAccessIterator>
   void partial_sort(ExecutionPolicy&& exec,
                     RandomAccessIterator first,
                     RandomAccessIterator middle,
                     RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
-  void partial_sort(RandomAccessIterator first,
                               RandomAccessIterator middle,
                               RandomAccessIterator last,
                               Compare comp);
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
   void partial_sort(ExecutionPolicy&& exec,
                     RandomAccessIterator first,
                     RandomAccessIterator middle,
                     RandomAccessIterator last,
                     Compare comp);
 ```
-*Requires:* `RandomAccessIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
-(Table  [[tab:moveassignable]]).
-*Effects:* Places the first `middle - first` sorted elements from the
-range \[`first`, `last`) into the range \[`first`, `middle`). The rest
-of the elements in the range \[`middle`, `last`) are placed in an
-unspecified order.
 *Complexity:* Approximately `(last - first) * log(middle - first)`
-comparisons.
 #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
 ``` cpp
 template<class InputIterator, class RandomAccessIterator>
-  RandomAccessIterator
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last);
 template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
   RandomAccessIterator
@@ -173,11 +237,11 @@ template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterato
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last);
 template<class InputIterator, class RandomAccessIterator,
          class Compare>
-  RandomAccessIterator
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last,
                       Compare comp);
 template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
@@ -186,398 +250,611 @@ template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterato
     partial_sort_copy(ExecutionPolicy&& exec,
                       ForwardIterator first, ForwardIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last,
                       Compare comp);
 ```
-*Requires:* `RandomAccessIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of
-`*result_first` shall satisfy the requirements of `MoveConstructible`
-(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
-(Table  [[tab:moveassignable]]).
-*Effects:* Places the first
-`min(last - first, result_last - result_first)` sorted elements into the
-range \[`result_first`,
-`result_first + min(last - first, result_last - result_first)`).
-*Returns:* The smaller of: `result_last` or
-`result_first + (last - first)`.
-*Complexity:* Approximately
-`(last - first) * log(min(last - first, result_last - result_first))`
-comparisons.
 #### `is_sorted` <a id="is.sorted">[[is.sorted]]</a>
 ``` cpp
 template<class ForwardIterator>
-  bool is_sorted(ForwardIterator first, ForwardIterator last);
 ```
-*Returns:* `is_sorted_until(first, last) == last`
 ``` cpp
 template<class ExecutionPolicy, class ForwardIterator>
   bool is_sorted(ExecutionPolicy&& exec,
                  ForwardIterator first, ForwardIterator last);
 ```
-*Returns:*
-`is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last) == last`
 ``` cpp
 template<class ForwardIterator, class Compare>
-  bool is_sorted(ForwardIterator first, ForwardIterator last,
                            Compare comp);
 ```
-*Returns:* `is_sorted_until(first, last, comp) == last`
 ``` cpp
 template<class ExecutionPolicy, class ForwardIterator, class Compare>
   bool is_sorted(ExecutionPolicy&& exec,
                  ForwardIterator first, ForwardIterator last,
                  Compare comp);
 ```
-*Returns:*
 ``` cpp
-is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last
 ```
 ``` cpp
 template<class ForwardIterator>
- ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
 template<class ExecutionPolicy, class ForwardIterator>
-  ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
                     ForwardIterator first, ForwardIterator last);
 template<class ForwardIterator, class Compare>
- ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
                     Compare comp);
 template<class ExecutionPolicy, class ForwardIterator, class Compare>
-  ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
                     ForwardIterator first, ForwardIterator last,
                     Compare comp);
 ```
-*Returns:* If `(last - first) < 2`, returns `last`. Otherwise, returns
-the last iterator `i` in \[`first`, `last`\] for which the range
-\[`first`, `i`) is sorted.
 *Complexity:* Linear.
 ### Nth element <a id="alg.nth.element">[[alg.nth.element]]</a>
 ``` cpp
 template<class RandomAccessIterator>
-  void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                              RandomAccessIterator last);
 template<class ExecutionPolicy, class RandomAccessIterator>
   void nth_element(ExecutionPolicy&& exec,
                    RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
-  void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                              RandomAccessIterator last,  Compare comp);
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
   void nth_element(ExecutionPolicy&& exec,
                    RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last, Compare comp);
 ```
-*Requires:* `RandomAccessIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
-(Table  [[tab:moveassignable]]).
 *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, unless `nth == last`. Also for every iterator `i` in the
-range \[`first`, `nth`) and every iterator `j` in the range \[`nth`,
-`last`) it holds that: `!(*j < *i)` or `comp(*j, *i) == false`.
 *Complexity:* For the overloads with no `ExecutionPolicy`, linear on
 average. For the overloads with an `ExecutionPolicy`, 𝑂(N) applications
 of the predicate, and 𝑂(N log N) swaps, where N = `last - first`.
 ### Binary search <a id="alg.binary.search">[[alg.binary.search]]</a>
-All of the algorithms in this section are versions of binary search and
-assume that the sequence being searched is partitioned with respect to
-an expression formed by binding the search key to an argument of the
-implied or explicit 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>
-  ForwardIterator
     lower_bound(ForwardIterator first, ForwardIterator last,
                 const T& value);
 template<class ForwardIterator, class T, class Compare>
-  ForwardIterator
     lower_bound(ForwardIterator first, ForwardIterator last,
                 const T& value, Compare comp);
 ```
-*Requires:* The elements `e` of \[`first`, `last`) shall be partitioned
-with respect to the expression `e < value` or `comp(e, value)`.
 *Returns:* The furthermost iterator `i` in the range \[`first`, `last`\]
-such that for every iterator `j` in the range \[`first`, `i`) the
-following corresponding conditions hold: `*j < value` or
-`comp(*j, value) != false`.
-*Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
 #### `upper_bound` <a id="upper.bound">[[upper.bound]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
-  ForwardIterator
     upper_bound(ForwardIterator first, ForwardIterator last,
                 const T& value);
 template<class ForwardIterator, class T, class Compare>
-  ForwardIterator
     upper_bound(ForwardIterator first, ForwardIterator last,
                 const T& value, Compare comp);
 ```
-*Requires:* The elements `e` of \[`first`, `last`) shall be partitioned
-with respect to the expression `!(value < e)` or `!comp(value, e)`.
 *Returns:* The furthermost iterator `i` in the range \[`first`, `last`\]
-such that for every iterator `j` in the range \[`first`, `i`) the
-following corresponding conditions hold: `!(value < *j)` or
-`comp(value, *j) == false`.
-*Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
 #### `equal_range` <a id="equal.range">[[equal.range]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
-  pair<ForwardIterator, ForwardIterator>
     equal_range(ForwardIterator first,
                 ForwardIterator last, const T& value);
 template<class ForwardIterator, class T, class Compare>
-  pair<ForwardIterator, ForwardIterator>
     equal_range(ForwardIterator first,
                 ForwardIterator last, const T& value,
                 Compare comp);
 ```
-*Requires:* The elements `e` of \[`first`, `last`) shall be partitioned
-with respect to the expressions `e < value` and `!(value < e)` or
-`comp(e, value)` and `!comp(value, e)`. Also, for all elements `e` of
-`[first, last)`, `e < value` shall imply `!(value < e)` or
-`comp(e, value)` shall imply `!comp(value, e)`.
 *Returns:*
   ``` cpp
-make_pair(lower_bound(first, last, value),
- upper_bound(first, last, value))
   ```
-or
   ``` cpp
-make_pair(lower_bound(first, last, value, comp),
- upper_bound(first, last, value, comp))
   ```
-*Complexity:* At most 2 * log₂(`last - first`) + 𝑂(1) comparisons.
 #### `binary_search` <a id="binary.search">[[binary.search]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
- bool binary_search(ForwardIterator first, ForwardIterator last,
                   const T& value);
 template<class ForwardIterator, class T, class Compare>
- bool binary_search(ForwardIterator first, ForwardIterator last,
                   const T& value, Compare comp);
 ```
-*Requires:* The elements `e` of \[`first`, `last`) are partitioned with
-respect to the expressions `e < value` and `!(value < e)` or
-`comp(e, value)` and `!comp(value, e)`. Also, for all elements `e` of
-`[first, last)`, `e < value` implies `!(value < e)` or `comp(e, value)`
-implies `!comp(value, e)`.
-*Returns:* `true` if there is an iterator `i` in the range \[`first`,
-`last`) that satisfies the corresponding conditions:
-`!(*i < value) && !(value < *i)` or
-`comp(*i, value) == false && comp(value, *i) == false`.
-*Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
 ### Partitions <a id="alg.partitions">[[alg.partitions]]</a>
 ``` cpp
 template<class InputIterator, class Predicate>
-  bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
 template<class ExecutionPolicy, class ForwardIterator, class Predicate>
   bool is_partitioned(ExecutionPolicy&& exec,
                       ForwardIterator first, ForwardIterator last, Predicate pred);
 ```
-*Requires:* For the overload with no `ExecutionPolicy`,
-`InputIterator`’s value type shall be convertible to `Predicate`’s
-argument type. For the overload with an `ExecutionPolicy`,
-`ForwardIterator`’s value type shall be convertible to `Predicate`’s
-argument type.
-*Returns:* `true` if \[`first`, `last`) is empty or if \[`first`,
-`last`) is partitioned by `pred`, i.e. if all elements that satisfy
-`pred` appear before those that do not.
-*Complexity:* Linear. At most `last - first` applications of `pred`.
 ``` cpp
 template<class ForwardIterator, class Predicate>
-  ForwardIterator
     partition(ForwardIterator first, ForwardIterator last, Predicate pred);
 template<class ExecutionPolicy, class ForwardIterator, class Predicate>
   ForwardIterator
     partition(ExecutionPolicy&& exec,
               ForwardIterator first, ForwardIterator last, Predicate pred);
 ```
-*Requires:* `ForwardIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]).
-*Effects:* Places all the elements in the range \[`first`, `last`) that
-satisfy `pred` before all the elements that do not satisfy it.
-*Returns:* An iterator `i` such that for every iterator `j` in the range
-\[`first`, `i`) `pred(*j) != false`, and for every iterator `k` in the
-range \[`i`, `last`), `pred(*k) == false`.
 *Complexity:* Let N = `last - first`:
 - For the overload with no `ExecutionPolicy`, exactly N applications of
-  the predicate. At most N / 2 swaps if `ForwardIterator` meets the
-  `BidirectionalIterator` requirements and at most N swaps otherwise.
 - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
   applications of the predicate.
 ``` cpp
 template<class BidirectionalIterator, class Predicate>
   BidirectionalIterator
-    stable_partition(BidirectionalIterator first, BidirectionalIterator last,
-                     Predicate pred);
 template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
   BidirectionalIterator
     stable_partition(ExecutionPolicy&& exec,
-                     BidirectionalIterator first, BidirectionalIterator last,
-                     Predicate pred);
 ```
-*Requires:* `BidirectionalIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
-(Table  [[tab:moveassignable]]).
-*Effects:* Places all the elements in the range \[`first`, `last`) that
-satisfy `pred` before all the elements that do not satisfy it.
-*Returns:* An iterator `i` such that for every iterator `j` in the range
-\[`first`, `i`), `pred(*j) != false`, and for every iterator `k` in the
-range \[`i`, `last`), `pred(*k) == false`. The relative order of the
-elements in both groups is preserved.
 *Complexity:* Let N = `last - first`:
-- For the overload 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.
 - 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>
-  pair<OutputIterator1, OutputIterator2>
     partition_copy(InputIterator first, InputIterator last,
-                   OutputIterator1 out_true, OutputIterator2 out_false,
-                   Predicate pred);
 template<class ExecutionPolicy, class ForwardIterator, class ForwardIterator1,
          class ForwardIterator2, class Predicate>
   pair<ForwardIterator1, ForwardIterator2>
     partition_copy(ExecutionPolicy&& exec,
                    ForwardIterator first, ForwardIterator last,
-                   ForwardIterator1 out_true, ForwardIterator2 out_false,
-                   Predicate pred);
 ```
-*Requires:*
-- For the overload with no `ExecutionPolicy`, `InputIterator`’s value
-  type shall be `CopyAssignable` (Table  [[tab:copyassignable]]), and
-  shall be writable ([[iterator.requirements.general]]) to the
-  `out_true` and `out_false` `OutputIterator`s, and shall be convertible
-  to `Predicate`’s argument type.
-- For the overload with an `ExecutionPolicy`, `ForwardIterator`’s value
-  type shall be `CopyAssignable`, and shall be writable to the
-  `out_true` and `out_false` `ForwardIterator`s, and shall be
-  convertible to `Predicate`’s argument type. \[*Note 1*: There may be a
-  performance cost if `ForwardIterator`’s value type is not
-  `CopyConstructible`. — *end note*]
-- For both overloads, the input range shall not overlap with either of
-  the output ranges.
 *Effects:* For each iterator `i` in \[`first`, `last`), copies `*i` to
-the output range beginning with `out_true` if `pred(*i)` is `true`, or
-to the output range beginning with `out_false` otherwise.
-*Returns:* A pair `p` such that `p.first` is the end of the output range
-beginning at `out_true` and `p.second` is the end of the output range
-beginning at `out_false`.
-*Complexity:* Exactly `last - first` applications of `pred`.
 ``` cpp
 template<class ForwardIterator, class Predicate>
- ForwardIterator partition_point(ForwardIterator first,
- ForwardIterator last,
-                                  Predicate pred);
 ```
-*Requires:* `ForwardIterator`’s value type shall be convertible to
-`Predicate`’s argument type. \[`first`, `last`) shall be partitioned by
-`pred`, i.e. all elements that satisfy `pred` shall appear before those
-that do not.
-*Returns:* An iterator `mid` such that `all_of(first, mid, pred)` and
-`none_of(mid, last, pred)` are both `true`.
-*Complexity:* 𝑂(log(`last - first`)) applications of `pred`.
 ### Merge <a id="alg.merge">[[alg.merge]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
-  OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator>
@@ -587,43 +864,67 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
           ForwardIterator2 first2, ForwardIterator2 last2,
           ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
-  OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     merge(ExecutionPolicy&& exec,
           ForwardIterator1 first1, ForwardIterator1 last1,
           ForwardIterator2 first2, ForwardIterator2 last2,
           ForwardIterator result, Compare comp);
 ```
-*Requires:* The ranges \[`first1`, `last1`) and \[`first2`, `last2`)
-shall be sorted with respect to `operator<` or `comp`. The resulting
-range shall not overlap with either of the original ranges.
-*Effects:*  Copies all the elements of the two ranges \[`first1`,
 `last1`) and \[`first2`, `last2`) into the range \[`result`,
-`result_last`), where `result_last` is
-`result + (last1 - first1) + (last2 - first2)`, such that the resulting
-range satisfies `is_sorted(result, result_last)` or
-`is_sorted(result, result_last, comp)`, respectively.
-*Returns:* `result + (last1 - first1) + (last2 - first2)`.
-*Complexity:* Let N = `(last1 - first1) + (last2 - first2)`:
-- For the overloads with no `ExecutionPolicy`, at most N - 1
-  comparisons.
 - For the overloads with an `ExecutionPolicy`, 𝑂(N) comparisons.
-*Remarks:* Stable ([[algorithm.stable]]).
 ``` cpp
 template<class BidirectionalIterator>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
@@ -641,81 +942,124 @@ template<class BidirectionalIterator, class Compare>
 template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
   void inplace_merge(ExecutionPolicy&& exec,
                      BidirectionalIterator first,
                      BidirectionalIterator middle,
                      BidirectionalIterator last, Compare comp);
 ```
-*Requires:* The ranges \[`first`, `middle`) and \[`middle`, `last`)
-shall be sorted with respect to `operator<` or `comp`.
-`BidirectionalIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
-(Table  [[tab:moveassignable]]).
 *Effects:* Merges two sorted consecutive ranges \[`first`, `middle`) and
 \[`middle`, `last`), putting the result of the merge into the range
-\[`first`, `last`). The resulting range will be in non-decreasing order;
-that is, for every iterator `i` in \[`first`, `last`) other than
-`first`, the condition `*i < *(i - 1)` or, respectively,
-`comp(*i, *(i - 1))` will be `false`.
 *Complexity:* Let N = `last - first`:
-- For the overloads with no `ExecutionPolicy`, if enough additional
   memory is available, exactly N - 1 comparisons.
-- For the overloads with no `ExecutionPolicy` if no additional memory is
-  available, 𝑂(N log N) comparisons.
-- For the overloads with an `ExecutionPolicy`, 𝑂(N log N) comparisons.
-*Remarks:* Stable ([[algorithm.stable]]).
 ### Set operations on sorted structures <a id="alg.set.operations">[[alg.set.operations]]</a>
-This section 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>
-  bool includes(InputIterator1 first1, InputIterator1 last1,
                           InputIterator2 first2, InputIterator2 last2);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
   bool includes(ExecutionPolicy&& exec,
                 ForwardIterator1 first1, ForwardIterator1 last1,
                 ForwardIterator2 first2, ForwardIterator2 last2);
 template<class InputIterator1, class InputIterator2, class Compare>
-  bool includes(InputIterator1 first1, InputIterator1 last1,
                           InputIterator2 first2, InputIterator2 last2,
                           Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
   bool includes(ExecutionPolicy&& exec,
                 ForwardIterator1 first1, ForwardIterator1 last1,
                 ForwardIterator2 first2, ForwardIterator2 last2,
                 Compare comp);
 ```
-*Returns:* `true` if \[`first2`, `last2`) is empty or if every element
-in the range \[`first2`, `last2`) is contained in the range \[`first1`,
-`last1`). Returns `false` otherwise.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
-comparisons.
 #### `set_union` <a id="set.union">[[set.union]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
-  OutputIterator
     set_union(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator>
@@ -725,48 +1069,71 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
               ForwardIterator2 first2, ForwardIterator2 last2,
               ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
-  OutputIterator
     set_union(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     set_union(ExecutionPolicy&& exec,
               ForwardIterator1 first1, ForwardIterator1 last1,
               ForwardIterator2 first2, ForwardIterator2 last2,
               ForwardIterator result, Compare comp);
 ```
-*Requires:* The resulting range shall not overlap with either of the
 original ranges.
 *Effects:* Constructs a sorted union of the elements from the two
 ranges; that is, the set of elements that are present in one or both of
 the ranges.
-*Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
-comparisons.
-*Remarks:* If \[`first1`, `last1`) contains m elements that are
-equivalent to each other and \[`first2`, `last2`) contains n elements
-that are equivalent to them, then all m elements from the first range
-shall be copied to the output range, in order, and then max(n - m, 0)
-elements from the second range shall be copied to the output range, in
-order.
 #### `set_intersection` <a id="set.intersection">[[set.intersection]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
-  OutputIterator
     set_intersection(InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator>
@@ -776,46 +1143,69 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
                      ForwardIterator2 first2, ForwardIterator2 last2,
                      ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
-  OutputIterator
     set_intersection(InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     set_intersection(ExecutionPolicy&& exec,
                      ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2, ForwardIterator2 last2,
                      ForwardIterator result, Compare comp);
 ```
-*Requires:* The resulting range shall not overlap with either of the
 original ranges.
 *Effects:* Constructs a sorted intersection of the elements from the two
 ranges; that is, the set of elements that are present in both of the
 ranges.
-*Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
-comparisons.
-*Remarks:* If \[`first1`, `last1`) contains m elements that are
-equivalent to each other and \[`first2`, `last2`) contains n elements
-that are equivalent to them, the first min(m, n) elements shall be
-copied from the first range to the output range, in order.
 #### `set_difference` <a id="set.difference">[[set.difference]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
-  OutputIterator
     set_difference(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2,
                    OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator>
@@ -825,46 +1215,69 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
                    ForwardIterator2 first2, ForwardIterator2 last2,
                    ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
-  OutputIterator
     set_difference(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2,
                    OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     set_difference(ExecutionPolicy&& exec,
                    ForwardIterator1 first1, ForwardIterator1 last1,
                    ForwardIterator2 first2, ForwardIterator2 last2,
                    ForwardIterator result, Compare comp);
 ```
-*Requires:* The resulting range shall not overlap with either of the
 original ranges.
 *Effects:* Copies the elements of the range \[`first1`, `last1`) which
 are not present in the range \[`first2`, `last2`) to the range beginning
 at `result`. The elements in the constructed range are sorted.
-*Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
-comparisons.
 *Remarks:* If \[`first1`, `last1`) contains m elements that are
 equivalent to each other and \[`first2`, `last2`) contains n elements
 that are equivalent to them, the last max(m - n, 0) elements from
-\[`first1`, `last1`) shall be copied to the output range.
 #### `set_symmetric_difference` <a id="set.symmetric.difference">[[set.symmetric.difference]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
-  OutputIterator
     set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator>
@@ -874,308 +1287,497 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
                              ForwardIterator2 first2, ForwardIterator2 last2,
                              ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
-  OutputIterator
     set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     set_symmetric_difference(ExecutionPolicy&& exec,
                              ForwardIterator1 first1, ForwardIterator1 last1,
                              ForwardIterator2 first2, ForwardIterator2 last2,
                              ForwardIterator result, Compare comp);
 ```
-*Requires:* The resulting range shall not overlap with either of the
 original ranges.
 *Effects:* Copies the elements of the range \[`first1`, `last1`) that
 are not present in the range \[`first2`, `last2`), and the elements of
 the range \[`first2`, `last2`) that are not present in the range
 \[`first1`, `last1`) to the range beginning at `result`. The elements in
 the constructed range are sorted.
-*Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
-comparisons.
-*Remarks:* If \[`first1`, `last1`) contains m elements that are
-equivalent to each other and \[`first2`, `last2`) contains n elements
-that are equivalent to them, then |m - n| of those elements shall be
-copied to the output range: the last m - n of these elements from
-\[`first1`, `last1`) if m > n, and the last n - m of these elements from
-\[`first2`, `last2`) if m < n.
 ### Heap operations <a id="alg.heap.operations">[[alg.heap.operations]]</a>
-A *heap* is a particular organization of elements in a range between two
-random access iterators \[`a`, `b`) such that:
 - With `N = b - a`, for all i, 0 < i < N,
-  `comp(a[\left \lfloor{\frac{i - 1}{2}}\right \rfloor], a[i])` is
-  `false`.
-- `*a` may be removed by `pop_heap()`, or a new element added by
-  `push_heap()`, in 𝑂(log N) time.
 These properties make heaps useful as priority queues.
-`make_heap()`
-converts a range into a heap and `sort_heap()` turns a heap into a
-sorted sequence.
 #### `push_heap` <a id="push.heap">[[push.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
-  void push_heap(RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
-  void push_heap(RandomAccessIterator first, RandomAccessIterator last,
                            Compare comp);
 ```
-*Requires:* The range \[`first`, `last - 1`) shall be a valid heap. The
-type of `*first` shall satisfy the `MoveConstructible` requirements
-(Table  [[tab:moveconstructible]]) and the `MoveAssignable` requirements
-(Table  [[tab:moveassignable]]).
 *Effects:* Places the value in the location `last - 1` into the
 resulting heap \[`first`, `last`).
-*Complexity:* At most log(`last - first`) comparisons.
 #### `pop_heap` <a id="pop.heap">[[pop.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
-  void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
-  void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                           Compare comp);
 ```
-*Requires:* The range \[`first`, `last`) shall be a valid non-empty
-heap. `RandomAccessIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
-(Table  [[tab:moveassignable]]).
 *Effects:* Swaps the value in the location `first` with the value in the
-location `last - 1` and makes \[`first`, `last - 1`) into a heap.
-*Complexity:* At most 2 log(`last - first`) comparisons.
 #### `make_heap` <a id="make.heap">[[make.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
-  void make_heap(RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
-  void make_heap(RandomAccessIterator first, RandomAccessIterator last,
                            Compare comp);
 ```
-*Requires:* The type of `*first` shall satisfy the `MoveConstructible`
-requirements (Table  [[tab:moveconstructible]]) and the `MoveAssignable`
-requirements (Table  [[tab:moveassignable]]).
-*Effects:* Constructs a heap out of the range \[`first`, `last`).
-*Complexity:* At most 3(`last - first`) comparisons.
 #### `sort_heap` <a id="sort.heap">[[sort.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
-  void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
-  void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
                            Compare comp);
 ```
-*Requires:* The range \[`first`, `last`) shall be a valid heap.
-`RandomAccessIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
-(Table  [[tab:moveassignable]]).
-*Effects:* Sorts elements in the heap \[`first`, `last`).
-*Complexity:* At most N log N comparisons, where N = `last - first`.
 #### `is_heap` <a id="is.heap">[[is.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
-  bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
 ```
-*Returns:* `is_heap_until(first, last) == last`
 ``` cpp
 template<class ExecutionPolicy, class RandomAccessIterator>
   bool is_heap(ExecutionPolicy&& exec,
                RandomAccessIterator first, RandomAccessIterator last);
 ```
-*Returns:*
-`is_heap_until(std::forward<ExecutionPolicy>(exec), first, last) == last`
 ``` cpp
 template<class RandomAccessIterator, class Compare>
-  bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 ```
-*Returns:* `is_heap_until(first, last, comp) == last`
 ``` cpp
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
   bool is_heap(ExecutionPolicy&& exec,
-               RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 ```
-*Returns:*
 ``` cpp
-is_heap_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last
 ```
 ``` cpp
 template<class RandomAccessIterator>
- RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
 template<class ExecutionPolicy, class RandomAccessIterator>
-  RandomAccessIterator is_heap_until(ExecutionPolicy&& exec,
                   RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
- RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp);
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
-  RandomAccessIterator is_heap_until(ExecutionPolicy&& exec,
                   RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp);
 ```
-*Returns:* If `(last - first) < 2`, returns `last`. Otherwise, returns
-the last iterator `i` in \[`first`, `last`\] for which the range
-\[`first`, `i`) is a heap.
 *Complexity:* Linear.
 ### Minimum and maximum <a id="alg.min.max">[[alg.min.max]]</a>
 ``` cpp
-template<class T> constexpr const T& min(const T& a, const T& b);
 template<class T, class Compare>
   constexpr const T& min(const T& a, const T& b, Compare comp);
 ```
-*Requires:* For the first form, type `T` shall be `LessThanComparable`
-(Table  [[tab:lessthancomparable]]).
 *Returns:* The smaller value.
 *Remarks:* Returns the first argument when the arguments are equivalent.
-*Complexity:* Exactly one comparison.
 ``` cpp
 template<class T>
-  constexpr T min(initializer_list<T> t);
 template<class T, class Compare>
-  constexpr T min(initializer_list<T> t, Compare comp);
 ```
-*Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
-first form, type `T` shall be `LessThanComparable`.
-*Returns:* The smallest value in the initializer_list.
-*Remarks:* Returns a copy of the leftmost argument when several
-arguments are equivalent to the smallest.
-*Complexity:* Exactly `t.size() - 1` comparisons.
 ``` 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);
 ```
-*Requires:* For the first form, type `T` shall be `LessThanComparable`
-(Table  [[tab:lessthancomparable]]).
 *Returns:* The larger value.
 *Remarks:* Returns the first argument when the arguments are equivalent.
-*Complexity:* Exactly one comparison.
 ``` cpp
 template<class T>
-  constexpr T max(initializer_list<T> t);
 template<class T, class Compare>
-  constexpr T max(initializer_list<T> t, Compare comp);
 ```
-*Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
-first form, type `T` shall be `LessThanComparable`.
-*Returns:* The largest value in the initializer_list.
-*Remarks:* Returns a copy of the leftmost argument when several
-arguments are equivalent to the largest.
-*Complexity:* Exactly `t.size() - 1` comparisons.
 ``` 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);
 ```
-*Requires:* For the first form, type `T` shall be `LessThanComparable`
-(Table  [[tab:lessthancomparable]]).
-*Returns:* `pair<const T&, const T&>(b, a)` if `b` is smaller than `a`,
-and `pair<const T&, const T&>(a, b)` otherwise.
-*Remarks:* Returns `pair<const T&, const T&>(a, b)` when the arguments
-are equivalent.
-*Complexity:* Exactly one comparison.
 ``` 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);
 ```
-*Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
-first form, type `T` shall be `LessThanComparable`.
-*Returns:* `pair<T, T>(x, y)`, where `x` has the smallest and `y` has
-the largest value in the initializer list.
-*Remarks:* `x` is a copy of the leftmost argument when several arguments
-are equivalent to the smallest. `y` is a copy of the rightmost argument
-when several arguments are equivalent to the largest.
-*Complexity:* At most (3/2)`t.size()` applications of the corresponding
-predicate.
 ``` cpp
 template<class ForwardIterator>
   constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
@@ -1188,19 +1790,34 @@ template<class ForwardIterator, class Compare>
                                         Compare comp);
 template<class ExecutionPolicy, class ForwardIterator, class Compare>
   ForwardIterator min_element(ExecutionPolicy&& exec,
                               ForwardIterator first, ForwardIterator last,
                               Compare comp);
 ```
 *Returns:* The first iterator `i` in the range \[`first`, `last`) such
-that for every iterator `j` in the range \[`first`, `last`) the
-following corresponding conditions hold: `!(*j < *i)` or
-`comp(*j, *i) == false`. Returns `last` if `first == last`.
-*Complexity:* Exactly max(`last - first - 1`, 0) applications of the
-corresponding comparisons.
 ``` cpp
 template<class ForwardIterator>
   constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
 template<class ExecutionPolicy, class ForwardIterator>
@@ -1212,19 +1829,34 @@ template<class ForwardIterator, class Compare>
                                         Compare comp);
 template<class ExecutionPolicy, class ForwardIterator, class Compare>
   ForwardIterator max_element(ExecutionPolicy&& exec,
                               ForwardIterator first, ForwardIterator last,
                               Compare comp);
 ```
 *Returns:* The first iterator `i` in the range \[`first`, `last`) such
-that for every iterator `j` in the range \[`first`, `last`) the
-following corresponding conditions hold: `!(*i < *j)` or
-`comp(*i, *j) == false`. Returns `last` if `first == last`.
-*Complexity:* Exactly max(`last - first - 1`, 0) applications of the
-corresponding comparisons.
 ``` cpp
 template<class ForwardIterator>
   constexpr pair<ForwardIterator, ForwardIterator>
     minmax_element(ForwardIterator first, ForwardIterator last);
@@ -1238,147 +1870,257 @@ template<class ForwardIterator, class Compare>
     minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator, class Compare>
   pair<ForwardIterator, ForwardIterator>
     minmax_element(ExecutionPolicy&& exec,
                    ForwardIterator first, ForwardIterator last, Compare comp);
 ```
-*Returns:* `make_pair(first, first)` if \[`first`, `last`) is empty,
-otherwise `make_pair(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:* At most
-$\max(\bigl\lfloor{\frac{3}{2}} (N-1)\bigr\rfloor, 0)$ applications of
-the corresponding predicate, where N is `last - first`.
 ### Bounded value <a id="alg.clamp">[[alg.clamp]]</a>
 ``` cpp
 template<class T>
   constexpr const T& clamp(const T& v, const T& lo, const T& hi);
 template<class T, class Compare>
   constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp);
 ```
-*Requires:* The value of `lo` shall be no greater than `hi`. For the
-first form, type `T` shall be `LessThanComparable`
-(Table  [[tab:lessthancomparable]]).
-*Returns:* `lo` if `v` is less than `lo`, `hi` if `hi` is less than `v`,
-otherwise `v`.
 [*Note 1*: If NaN is avoided, `T` can be a floating-point
 type. — *end note*]
-*Complexity:* At most two comparisons.
 ### Lexicographical comparison <a id="alg.lex.comparison">[[alg.lex.comparison]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2>
-  bool
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
   bool
     lexicographical_compare(ExecutionPolicy&& exec,
                             ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2);
 template<class InputIterator1, class InputIterator2, class Compare>
-  bool
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2,
                             Compare comp);
-template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
   bool
     lexicographical_compare(ExecutionPolicy&& exec,
                             ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2,
                             Compare comp);
 ```
-*Returns:* `true` if the sequence of elements defined by the range
-\[`first1`, `last1`) is lexicographically less than the sequence of
-elements defined by the range \[`first2`, `last2`) and `false`
-otherwise.
 *Complexity:* At most 2 min(`last1 - first1`,  `last2 - first2`)
-applications of the corresponding comparison.
 *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. If one sequence is a prefix of
-the other, then the shorter sequence is lexicographically less than the
-longer sequence. Otherwise, the lexicographical comparison of the
-sequences yields the same result as the comparison of the first
 corresponding pair of elements that are not equivalent.
 [*Example 1*:
-The following sample implementation satisfies these requirements:
 ``` cpp
 for ( ; first1 != last1 && first2 != last2 ; ++first1, (void) ++first2) {
-  if (*first1 < *first2) return true;
-  if (*first2 < *first1) return false;
 }
 return first1 == last1 && first2 != last2;
 ```
 — *end example*]
 [*Note 1*: An empty sequence is lexicographically less than any
 non-empty sequence, but not less than any empty sequence. — *end note*]
 ### Permutation generators <a id="alg.permutation.generators">[[alg.permutation.generators]]</a>
 ``` cpp
 template<class BidirectionalIterator>
-  bool next_permutation(BidirectionalIterator first,
                                   BidirectionalIterator last);
 template<class BidirectionalIterator, class Compare>
-  bool next_permutation(BidirectionalIterator first,
                                   BidirectionalIterator last, Compare comp);
 ```
-*Requires:* `BidirectionalIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]).
 *Effects:* Takes a sequence defined by the range \[`first`, `last`) and
 transforms it into the next permutation. The next permutation is found
 by assuming that the set of all permutations is lexicographically sorted
-with respect to `operator<` or `comp`.
-*Returns:* `true` if such a permutation exists. Otherwise, it transforms
-the sequence into the smallest permutation, that is, the ascendingly
-sorted one, and returns `false`.
 *Complexity:* At most `(last - first) / 2` swaps.
 ``` cpp
 template<class BidirectionalIterator>
-  bool prev_permutation(BidirectionalIterator first,
                                   BidirectionalIterator last);
 template<class BidirectionalIterator, class Compare>
-  bool prev_permutation(BidirectionalIterator first,
                                   BidirectionalIterator last, Compare comp);
 ```
-*Requires:* `BidirectionalIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]).
 *Effects:* Takes a sequence defined by the range \[`first`, `last`) and
 transforms it into the previous permutation. The previous permutation is
 found by assuming that the set of all permutations is lexicographically
-sorted with respect to `operator<` or `comp`.
-*Returns:* `true` if such a permutation exists. Otherwise, it transforms
-the sequence into the largest permutation, that is, the descendingly
-sorted one, and returns `false`.
 *Complexity:* At most `(last - first) / 2` swaps.

 ## 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
 [*Note 1*:
 Under these conditions, it can be shown that
+- `equiv` is an equivalence relation,
 - `comp` induces a well-defined relation on the equivalence classes
+  determined by `equiv`, and
+- the induced relation is a strict total ordering.
 — *end note*]
+A sequence is *sorted with respect to a `comp` and `proj`* for a
+comparator and projection `comp` and `proj` if for every iterator `i`
+pointing to the sequence and every non-negative integer `n` such that
+`i + n` is a valid iterator pointing to an element of the sequence,
+``` cpp
+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`.
 #### `sort` <a id="sort">[[sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
+ constexpr void sort(RandomAccessIterator first, RandomAccessIterator last);
 template<class ExecutionPolicy, class RandomAccessIterator>
   void sort(ExecutionPolicy&& exec,
             RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
+ constexpr void sort(RandomAccessIterator first, RandomAccessIterator last,
                       Compare comp);
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
   void sort(ExecutionPolicy&& exec,
             RandomAccessIterator first, RandomAccessIterator last,
             Compare comp);
+template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  constexpr I
+    ranges::sort(I first, S last, Comp comp = {}, Proj proj = {});
+template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  constexpr borrowed_iterator_t<R>
+    ranges::sort(R&& r, Comp comp = {}, Proj proj = {});
 ```
+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:* Sorts the elements in the range \[`first`, `last`) with
+respect to `comp` and `proj`.
+*Returns:* `last` for the overloads in namespace `ranges`.
+*Complexity:* Let N be `last - first`. 𝑂(N log N) comparisons and
+projections.
 #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
                    Compare comp);
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
   void stable_sort(ExecutionPolicy&& exec,
                    RandomAccessIterator first, RandomAccessIterator last,
                    Compare comp);
+template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {});
+template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  borrowed_iterator_t<R>
+    ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {});
 ```
+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:* Sorts the elements in the range \[`first`, `last`) with
+respect to `comp` and `proj`.
+*Returns:* `last` for the overloads in namespace `ranges`.
+*Complexity:* Let N be `last - first`. If enough extra memory is
+available, N log(N) comparisons. Otherwise, at most N log²(N)
+comparisons. In either case, twice as many projections as the number of
+comparisons.
+*Remarks:* Stable [[algorithm.stable]].
 #### `partial_sort` <a id="partial.sort">[[partial.sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
+ constexpr void partial_sort(RandomAccessIterator first,
                               RandomAccessIterator middle,
                               RandomAccessIterator last);
 template<class ExecutionPolicy, class RandomAccessIterator>
   void partial_sort(ExecutionPolicy&& exec,
                     RandomAccessIterator first,
                     RandomAccessIterator middle,
                     RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
+ constexpr void partial_sort(RandomAccessIterator first,
                               RandomAccessIterator middle,
                               RandomAccessIterator last,
                               Compare comp);
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
   void partial_sort(ExecutionPolicy&& exec,
                     RandomAccessIterator first,
                     RandomAccessIterator middle,
                     RandomAccessIterator last,
                     Compare comp);
+template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  constexpr I
+    ranges::partial_sort(I first, I middle, S last, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
+*Preconditions:* \[`first`, `middle`) and \[`middle`, `last`) are valid
+ranges. 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:* Places the first `middle - first` elements from the range
+\[`first`, `last`) as sorted with respect to `comp` and `proj` into the
+range \[`first`, `middle`). The rest of the elements in the range
+\[`middle`, `last`) are placed in an unspecified order.
+*Returns:* `last` for the overload in namespace `ranges`.
 *Complexity:* Approximately `(last - first) * log(middle - first)`
+comparisons, and twice as many projections.
+``` cpp
+template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  constexpr borrowed_iterator_t<R>
+    ranges::partial_sort(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
+```
+*Effects:* Equivalent to:
+``` cpp
+return ranges::partial_sort(ranges::begin(r), middle, ranges::end(r), comp, proj);
+```
 #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
 ``` cpp
 template<class InputIterator, class RandomAccessIterator>
+ constexpr RandomAccessIterator
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last);
 template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
   RandomAccessIterator
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last);
 template<class InputIterator, class RandomAccessIterator,
          class Compare>
+ constexpr RandomAccessIterator
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last,
                       Compare comp);
 template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
     partial_sort_copy(ExecutionPolicy&& exec,
                       ForwardIterator first, ForwardIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last,
                       Compare comp);
+template<input_iterator I1, sentinel_for<I1> S1, random_access_iterator I2, sentinel_for<I2> S2,
+         class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+  requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
+           indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
+  constexpr ranges::partial_sort_copy_result<I1, I2>
+    ranges::partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
+                              Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+template<input_range R1, random_access_range R2, class Comp = ranges::less,
+         class Proj1 = identity, class Proj2 = identity>
+  requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
+           sortable<iterator_t<R2>, Comp, Proj2> &&
+           indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
+                                      projected<iterator_t<R2>, Proj2>>
+  constexpr ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
+    ranges::partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
+                              Proj1 proj1 = {}, Proj2 proj2 = {});
 ```
+Let N be min(`last - first`,  `result_last - result_first`). Let `comp`
+be `less{}`, and `proj1` and `proj2` be `identity{}` for the overloads
+with no parameters by those names.
+*Mandates:* For the overloads in namespace `std`, the expression
+`*first` is writable [[iterator.requirements.general]] to
+`result_first`.
+*Preconditions:* For the overloads in namespace `std`,
+`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))).
+```
+Then, after evaluating the assignment `*x2 = *a1`, E is equal to
+``` cpp
+bool(invoke(comp, invoke(proj2, *x2), invoke(proj2, *y2))).
+```
+[*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`. — *end note*]
+*Effects:* Places the first N elements as sorted with respect to `comp`
+and `proj2` into the range \[`result_first`, `result_first + `N).
+*Returns:*
+- `result_first + `N for the overloads in namespace `std`.
+- `{last, result_first + `N`}` for the overloads in namespace `ranges`.
+*Complexity:* Approximately `(last - first) * log `N comparisons, and
+twice as many projections.
 #### `is_sorted` <a id="is.sorted">[[is.sorted]]</a>
 ``` cpp
 template<class ForwardIterator>
+ constexpr bool is_sorted(ForwardIterator first, ForwardIterator last);
 ```
+*Effects:* Equivalent to: `return is_sorted_until(first, last) == last;`
 ``` cpp
 template<class ExecutionPolicy, class ForwardIterator>
   bool is_sorted(ExecutionPolicy&& exec,
                  ForwardIterator first, ForwardIterator last);
 ```
+*Effects:* Equivalent to:
+``` cpp
+return is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last) == last;
+```
 ``` cpp
 template<class ForwardIterator, class Compare>
+ constexpr bool is_sorted(ForwardIterator first, ForwardIterator last,
                            Compare comp);
 ```
+*Effects:* Equivalent to:
+`return is_sorted_until(first, last, comp) == last;`
 ``` cpp
 template<class ExecutionPolicy, class ForwardIterator, class Compare>
   bool is_sorted(ExecutionPolicy&& exec,
                  ForwardIterator first, ForwardIterator last,
                  Compare comp);
 ```
+*Effects:* Equivalent to:
 ``` cpp
+return is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last;
 ```
+``` cpp
+template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
+         indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+  constexpr bool ranges::is_sorted(I first, S last, Comp comp = {}, Proj proj = {});
+template<forward_range R, class Proj = identity,
+         indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+  constexpr bool ranges::is_sorted(R&& r, Comp comp = {}, Proj proj = {});
+```
+*Effects:* Equivalent to:
+`return ranges::is_sorted_until(first, last, comp, proj) == last;`
 ``` cpp
 template<class ForwardIterator>
+ constexpr ForwardIterator
+    is_sorted_until(ForwardIterator first, ForwardIterator last);
 template<class ExecutionPolicy, class ForwardIterator>
+  ForwardIterator
+    is_sorted_until(ExecutionPolicy&& exec,
                     ForwardIterator first, ForwardIterator last);
 template<class ForwardIterator, class Compare>
+ constexpr ForwardIterator
+    is_sorted_until(ForwardIterator first, ForwardIterator last,
                     Compare comp);
 template<class ExecutionPolicy, class ForwardIterator, class Compare>
+  ForwardIterator
+    is_sorted_until(ExecutionPolicy&& exec,
                     ForwardIterator first, ForwardIterator last,
                     Compare comp);
+template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
+         indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+  constexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {});
+template<forward_range R, class Proj = identity,
+         indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+  constexpr borrowed_iterator_t<R>
+    ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
+*Returns:* The last iterator `i` in \[`first`, `last`\] for which the
+range \[`first`, `i`) is sorted with respect to `comp` and `proj`.
 *Complexity:* Linear.
 ### Nth element <a id="alg.nth.element">[[alg.nth.element]]</a>
 ``` cpp
 template<class RandomAccessIterator>
+ constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                              RandomAccessIterator last);
 template<class ExecutionPolicy, class RandomAccessIterator>
   void nth_element(ExecutionPolicy&& exec,
                    RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
+ constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                              RandomAccessIterator last,  Compare comp);
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
   void nth_element(ExecutionPolicy&& exec,
                    RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last, Compare comp);
+template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  constexpr I
+    ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
+*Preconditions:* \[`first`, `nth`) and \[`nth`, `last`) are valid
+ranges. 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:* After `nth_element` the element in the position pointed to by
 `nth` is the element that would be in that position if the whole range
+were sorted with respect to `comp` and `proj`, unless `nth == last`.
+Also for every iterator `i` in the range \[`first`, `nth`) and every
+iterator `j` in the range \[`nth`, `last`) it holds that:
+`bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is `false`.
+*Returns:* `last` for the overload in namespace `ranges`.
 *Complexity:* For the overloads with no `ExecutionPolicy`, linear on
 average. For the overloads with an `ExecutionPolicy`, 𝑂(N) applications
 of the predicate, and 𝑂(N log N) swaps, where N = `last - first`.
+``` cpp
+template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  constexpr borrowed_iterator_t<R>
+    ranges::nth_element(R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {});
+```
+*Effects:* Equivalent to:
+``` cpp
+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>
+ constexpr ForwardIterator
     lower_bound(ForwardIterator first, ForwardIterator last,
                 const T& value);
 template<class ForwardIterator, class T, class Compare>
+ constexpr ForwardIterator
     lower_bound(ForwardIterator first, ForwardIterator last,
                 const T& value, Compare comp);
+template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+         indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+  constexpr I ranges::lower_bound(I first, S last, const T& value, Comp comp = {},
+                                  Proj proj = {});
+template<forward_range R, class T, class Proj = identity,
+         indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+           ranges::less>
+  constexpr borrowed_iterator_t<R>
+    ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for overloads with no
+parameters by those names.
+*Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
+with respect to the expression
+`bool(invoke(comp, invoke(proj, e), value))`.
 *Returns:* The furthermost iterator `i` in the range \[`first`, `last`\]
+such that for every iterator `j` in the range \[`first`, `i`),
+`bool(invoke(comp, invoke(proj, *j), value))` is `true`.
+*Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons and
+projections.
 #### `upper_bound` <a id="upper.bound">[[upper.bound]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
+ constexpr ForwardIterator
     upper_bound(ForwardIterator first, ForwardIterator last,
                 const T& value);
 template<class ForwardIterator, class T, class Compare>
+ constexpr ForwardIterator
     upper_bound(ForwardIterator first, ForwardIterator last,
                 const T& value, Compare comp);
+template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+         indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+  constexpr I ranges::upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
+template<forward_range R, class T, class Proj = identity,
+         indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+           ranges::less>
+  constexpr borrowed_iterator_t<R>
+    ranges::upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for overloads with no
+parameters by those names.
+*Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
+with respect to the expression
+`!bool(invoke(comp, value, invoke(proj, e)))`.
 *Returns:* The furthermost iterator `i` in the range \[`first`, `last`\]
+such that for every iterator `j` in the range \[`first`, `i`),
+`!bool(invoke(comp, value, invoke(proj, *j)))` is `true`.
+*Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons and
+projections.
 #### `equal_range` <a id="equal.range">[[equal.range]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
+ constexpr pair<ForwardIterator, ForwardIterator>
     equal_range(ForwardIterator first,
                 ForwardIterator last, const T& value);
 template<class ForwardIterator, class T, class Compare>
+ constexpr pair<ForwardIterator, ForwardIterator>
     equal_range(ForwardIterator first,
                 ForwardIterator last, const T& value,
                 Compare comp);
+template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+         indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+  constexpr subrange<I>
+    ranges::equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
+template<forward_range R, class T, class Proj = identity,
+         indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+           ranges::less>
+  constexpr borrowed_subrange_t<R>
+    ranges::equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for overloads with no
+parameters by those names.
+*Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
+with respect to the expressions
+`bool(invoke(comp, invoke(proj, e), value))` and
+`!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
+`e` of `[first, last)`, `bool(comp(e, value))` implies
+`!bool(comp(value, e))` for the overloads in namespace `std`.
 *Returns:*
+- For the overloads in namespace `std`:
   ``` cpp
+  {lower_bound(first, last, value, comp),
+ upper_bound(first, last, value, comp)}
   ```
+- For the overloads in namespace `ranges`:
   ``` cpp
+  {ranges::lower_bound(first, last, value, comp, proj),
+   ranges::upper_bound(first, last, value, comp, proj)}
   ```
+*Complexity:* At most 2 * log₂(`last - first`) + 𝑂(1) comparisons and
+projections.
 #### `binary_search` <a id="binary.search">[[binary.search]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
+ constexpr bool
+    binary_search(ForwardIterator first, ForwardIterator last,
                   const T& value);
 template<class ForwardIterator, class T, class Compare>
+ constexpr bool
+    binary_search(ForwardIterator first, ForwardIterator last,
                   const T& value, Compare comp);
+template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+         indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+  constexpr bool ranges::binary_search(I first, S last, const T& value, Comp comp = {},
+                                       Proj proj = {});
+template<forward_range R, class T, class Proj = identity,
+         indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+           ranges::less>
+  constexpr bool ranges::binary_search(R&& r, const T& value, Comp comp = {},
+                                       Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for overloads with no
+parameters by those names.
+*Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
+with respect to the expressions
+`bool(invoke(comp, invoke(proj, e), value))` and
+`!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
+`e` of `[first, last)`, `bool(comp(e, value))` implies
+`!bool(comp(value, e))` for the overloads in namespace `std`.
+*Returns:* `true` if and only if for some iterator `i` in the range
+\[`first`, `last`),
+`!bool(invoke(comp, invoke(proj, *i), value)) && !bool(invoke(comp, value, invoke(proj, *i)))`
+is `true`.
+*Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons and
+projections.
 ### Partitions <a id="alg.partitions">[[alg.partitions]]</a>
 ``` cpp
 template<class InputIterator, class Predicate>
+ constexpr bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
 template<class ExecutionPolicy, class ForwardIterator, class Predicate>
   bool is_partitioned(ExecutionPolicy&& exec,
                       ForwardIterator first, ForwardIterator last, Predicate pred);
+template<input_iterator I, sentinel_for<I> S, class Proj = identity,
+         indirect_unary_predicate<projected<I, Proj>> Pred>
+  constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});
+template<input_range R, class Proj = identity,
+         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+  constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});
 ```
+Let `proj` be `identity{}` for the overloads with no parameter named
+`proj`.
+*Returns:* `true` if and only if the elements `e` of \[`first`, `last`)
+are partitioned with respect to the expression
+`bool(invoke(pred, invoke(proj, e)))`.
+*Complexity:* Linear. At most `last - first` applications of `pred` and
+`proj`.
 ``` cpp
 template<class ForwardIterator, class Predicate>
+ constexpr ForwardIterator
     partition(ForwardIterator first, ForwardIterator last, Predicate pred);
 template<class ExecutionPolicy, class ForwardIterator, class Predicate>
   ForwardIterator
     partition(ExecutionPolicy&& exec,
               ForwardIterator first, ForwardIterator last, Predicate pred);
+template<permutable I, sentinel_for<I> S, class Proj = identity,
+         indirect_unary_predicate<projected<I, Proj>> Pred>
+  constexpr subrange<I>
+    ranges::partition(I first, S last, Pred pred, Proj proj = {});
+template<forward_range R, class Proj = identity,
+         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+  requires permutable<iterator_t<R>>
+  constexpr borrowed_subrange_t<R>
+    ranges::partition(R&& r, Pred pred, Proj proj = {});
 ```
+Let `proj` be `identity{}` for the overloads with no parameter named
+`proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
+*Preconditions:* For the overloads in namespace `std`, `ForwardIterator`
+meets the *Cpp17ValueSwappable* requirements [[swappable.requirements]].
+*Effects:* Places all the elements `e` in \[`first`, `last`) that
+satisfy E(`e`) before all the elements that do not.
+*Returns:* Let `i` be an iterator such that E(`*j`) is `true` for every
+iterator `j` in \[`first`, `i`) and `false` for every iterator `j` in
+\[`i`, `last`). Returns:
+- `i` for the overloads in namespace `std`.
+- `{i, last}` for the overloads in namespace `ranges`.
 *Complexity:* Let N = `last - first`:
 - For the overload with no `ExecutionPolicy`, exactly N applications of
+  the predicate and projection. At most N / 2 swaps if the type of
+  `first` meets the *Cpp17BidirectionalIterator* requirements for the
+  overloads in namespace `std` or models `bidirectional_iterator` for
+  the overloads in namespace `ranges`, and at most N swaps otherwise.
 - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
   applications of the predicate.
 ``` cpp
 template<class BidirectionalIterator, class Predicate>
   BidirectionalIterator
+    stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
 template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
   BidirectionalIterator
     stable_partition(ExecutionPolicy&& exec,
+                     BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
+template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
+         indirect_unary_predicate<projected<I, Proj>> Pred>
+  requires permutable<I>
+  subrange<I> ranges::stable_partition(I first, S last, Pred pred, Proj proj = {});
+template<bidirectional_range R, class Proj = identity,
+         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+  requires permutable<iterator_t<R>>
+  borrowed_subrange_t<R> ranges::stable_partition(R&& r, Pred pred, Proj proj = {});
 ```
+Let `proj` be `identity{}` for the overloads with no parameter named
+`proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
+*Preconditions:* For the overloads in namespace `std`,
+`BidirectionalIterator` meets the *Cpp17ValueSwappable*
+requirements [[swappable.requirements]] and the type of `*first` meets
+the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
+*Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
+*Effects:* Places all the elements `e` in \[`first`, `last`) that
+satisfy E(`e`) before all the elements that do not. The relative order
+of the elements in both groups is preserved.
+*Returns:* Let `i` be an iterator such that for every iterator `j` in
+\[`first`, `i`), E(`*j`) is `true`, and for every iterator `j` in the
+range \[`i`, `last`), E(`*j`) is `false`. 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>
   pair<ForwardIterator1, ForwardIterator2>
     partition_copy(ExecutionPolicy&& exec,
                    ForwardIterator first, ForwardIterator last,
+                   ForwardIterator1 out_true, ForwardIterator2 out_false, Predicate pred);
+template<input_iterator I, sentinel_for<I> S, weakly_incrementable O1, weakly_incrementable O2,
+         class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
+  requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>
+  constexpr ranges::partition_copy_result<I, O1, O2>
+    ranges::partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred,
+                           Proj proj = {});
+template<input_range R, weakly_incrementable O1, weakly_incrementable O2,
+         class Proj = identity,
+         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+  requires indirectly_copyable<iterator_t<R>, O1> &&
+           indirectly_copyable<iterator_t<R>, O2>
+  constexpr ranges::partition_copy_result<borrowed_iterator_t<R>, O1, O2>
+    ranges::partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {});
 ```
+Let `proj` be `identity{}` for the overloads with no parameter named
+`proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
+*Mandates:* For the overloads in namespace `std`, the expression
+`*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
+the output range beginning with `out_false` otherwise.
+*Returns:* Let `o1` be the end of the output range beginning at
+`out_true`, and `o2` the end of the output range beginning at
+`out_false`. Returns
+- `{o1, o2}` for the overloads in namespace `std`.
+- `{last, o1, o2}` for the overloads in namespace `ranges`.
+*Complexity:* Exactly `last - first` applications of `pred` and `proj`.
 ``` cpp
 template<class ForwardIterator, class Predicate>
+ constexpr ForwardIterator
+    partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
+template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
+         indirect_unary_predicate<projected<I, Proj>> Pred>
+  constexpr I ranges::partition_point(I first, S last, Pred pred, Proj proj = {});
+template<forward_range R, class Proj = identity,
+         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+  constexpr borrowed_iterator_t<R>
+    ranges::partition_point(R&& r, Pred pred, Proj proj = {});
 ```
+Let `proj` be `identity{}` for the overloads with no parameter named
+`proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
+*Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
+with respect to E(`e`).
+*Returns:* An iterator `mid` such that E(`*i`) is `true` for all
+iterators `i` in \[`first`, `mid`), and `false` for all iterators `i` in
+\[`mid`, `last`).
+*Complexity:* 𝑂(log(`last - first`)) applications of `pred` and `proj`.
 ### Merge <a id="alg.merge">[[alg.merge]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
+ constexpr OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator>
           ForwardIterator2 first2, ForwardIterator2 last2,
           ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
+ constexpr OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     merge(ExecutionPolicy&& exec,
           ForwardIterator1 first1, ForwardIterator1 last1,
           ForwardIterator2 first2, ForwardIterator2 last2,
           ForwardIterator result, Compare comp);
+template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+         weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity,
+         class Proj2 = identity>
+  requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+  constexpr ranges::merge_result<I1, I2, O>
+    ranges::merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
+                  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less,
+         class Proj1 = identity, class Proj2 = identity>
+  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+  constexpr ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
+    ranges::merge(R1&& r1, R2&& r2, O result,
+                  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
 ```
+Let N be `(last1 - first1) + (last2 - first2)`. Let `comp` be `less{}`,
+`proj1` be `identity{}`, and `proj2` be `identity{}`, for the overloads
+with no parameters by those names.
+*Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
+`last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
+respectively. The resulting range does not overlap with either of the
+original ranges.
+*Effects:* Copies all the elements of the two ranges \[`first1`,
 `last1`) and \[`first2`, `last2`) into the range \[`result`,
+`result_last`), where `result_last` is `result + `N. If an element `a`
+precedes `b` in an input range, `a` is copied into the output range
+before `b`. If `e1` is an element of \[`first1`, `last1`) and `e2` of
+\[`first2`, `last2`), `e2` is copied into the output range before `e1`
+if and only if
+`bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))` is `true`.
+*Returns:*
+- `result_last` for the overloads in namespace `std`.
+- `{last1, last2, result_last}` for the overloads in namespace `ranges`.
+*Complexity:*
+- For the overloads with no `ExecutionPolicy`, at most N - 1 comparisons
+  and applications of each projection.
 - For the overloads with an `ExecutionPolicy`, 𝑂(N) comparisons.
+*Remarks:* Stable [[algorithm.stable]].
 ``` cpp
 template<class BidirectionalIterator>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
 template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
   void inplace_merge(ExecutionPolicy&& exec,
                      BidirectionalIterator first,
                      BidirectionalIterator middle,
                      BidirectionalIterator last, Compare comp);
+template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  I ranges::inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
+*Preconditions:* \[`first`, `middle`) and \[`middle`, `last`) are valid
+ranges sorted with respect to `comp` and `proj`. For the overloads in
+namespace `std`, `BidirectionalIterator` meets the *Cpp17ValueSwappable*
+requirements [[swappable.requirements]] and the type of `*first` meets
+the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
+*Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
 *Effects:* Merges two sorted consecutive ranges \[`first`, `middle`) and
 \[`middle`, `last`), putting the result of the merge into the range
+\[`first`, `last`). The resulting range is sorted with respect to `comp`
+and `proj`.
+*Returns:* `last` for the overload in namespace `ranges`.
 *Complexity:* Let N = `last - first`:
+- For the overloads with no `ExecutionPolicy`, and if enough additional
   memory is available, exactly N - 1 comparisons.
+- Otherwise, 𝑂(N log N) comparisons.
+In either case, twice as many projections as comparisons.
+*Remarks:* Stable [[algorithm.stable]].
+``` cpp
+template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  borrowed_iterator_t<R>
+    ranges::inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
+```
+*Effects:* Equivalent to:
+``` cpp
+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>
+ constexpr bool includes(InputIterator1 first1, InputIterator1 last1,
                           InputIterator2 first2, InputIterator2 last2);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
   bool includes(ExecutionPolicy&& exec,
                 ForwardIterator1 first1, ForwardIterator1 last1,
                 ForwardIterator2 first2, ForwardIterator2 last2);
 template<class InputIterator1, class InputIterator2, class Compare>
+ constexpr bool includes(InputIterator1 first1, InputIterator1 last1,
                           InputIterator2 first2, InputIterator2 last2,
                           Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
   bool includes(ExecutionPolicy&& exec,
                 ForwardIterator1 first1, ForwardIterator1 last1,
                 ForwardIterator2 first2, ForwardIterator2 last2,
                 Compare comp);
+template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+         class Proj1 = identity, class Proj2 = identity,
+         indirect_strict_weak_order<projected<I1, Proj1>,
+                                    projected<I2, Proj2>> Comp = ranges::less>
+  constexpr bool ranges::includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
+                                  Proj1 proj1 = {}, Proj2 proj2 = {});
+template<input_range R1, input_range R2, class Proj1 = identity,
+         class Proj2 = identity,
+         indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
+                                    projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
+  constexpr bool ranges::includes(R1&& r1, R2&& r2, Comp comp = {},
+                                  Proj1 proj1 = {}, Proj2 proj2 = {});
 ```
+Let `comp` be `less{}`, `proj1` be `identity{}`, and `proj2` be
+`identity{}`, for the overloads with no parameters by those names.
+*Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
+`last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
+respectively.
+*Returns:* `true` if and only if \[`first2`, `last2`) is a subsequence
+of \[`first1`, `last1`).
+[*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. — *end note*]
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
+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,
          class ForwardIterator>
               ForwardIterator2 first2, ForwardIterator2 last2,
               ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
+ constexpr OutputIterator
     set_union(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     set_union(ExecutionPolicy&& exec,
               ForwardIterator1 first1, ForwardIterator1 last1,
               ForwardIterator2 first2, ForwardIterator2 last2,
               ForwardIterator result, Compare comp);
+template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+         weakly_incrementable O, class Comp = ranges::less,
+         class Proj1 = identity, class Proj2 = identity>
+  requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+  constexpr ranges::set_union_result<I1, I2, O>
+    ranges::set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
+                      Proj1 proj1 = {}, Proj2 proj2 = {});
+template<input_range R1, input_range R2, weakly_incrementable O,
+         class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+  constexpr ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
+    ranges::set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
+                      Proj1 proj1 = {}, Proj2 proj2 = {});
 ```
+Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
+overloads with no parameters by those names.
+*Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
+`last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
+respectively. The resulting range does not overlap with either of the
 original ranges.
 *Effects:* Constructs a sorted union of the elements from the two
 ranges; that is, the set of elements that are present in one or both of
 the ranges.
+*Returns:* Let `result_last` be the end of the constructed range.
+Returns
+- `result_last` for the overloads in namespace `std`.
+- `{last1, last2, result_last}` for the overloads in namespace `ranges`.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
+comparisons and applications of each projection.
+*Remarks:* Stable [[algorithm.stable]]. 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_intersection` <a id="set.intersection">[[set.intersection]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
+ constexpr OutputIterator
     set_intersection(InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator>
                      ForwardIterator2 first2, ForwardIterator2 last2,
                      ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
+ constexpr OutputIterator
     set_intersection(InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     set_intersection(ExecutionPolicy&& exec,
                      ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2, ForwardIterator2 last2,
                      ForwardIterator result, Compare comp);
+template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+         weakly_incrementable O, class Comp = ranges::less,
+         class Proj1 = identity, class Proj2 = identity>
+  requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+  constexpr ranges::set_intersection_result<I1, I2, O>
+    ranges::set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
+                             Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+template<input_range R1, input_range R2, weakly_incrementable O,
+         class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+  constexpr ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
+    ranges::set_intersection(R1&& r1, R2&& r2, O result,
+                             Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
 ```
+Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
+overloads with no parameters by those names.
+*Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
+`last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
+respectively. The resulting range does not overlap with either of the
 original ranges.
 *Effects:* Constructs a sorted intersection of the elements from the two
 ranges; that is, the set of elements that are present in both of the
 ranges.
+*Returns:* Let `result_last` be the end of the constructed range.
+Returns
+- `result_last` for the overloads in namespace `std`.
+- `{last1, last2, result_last}` for the overloads in namespace `ranges`.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
+comparisons and applications of each projection.
+*Remarks:* Stable [[algorithm.stable]]. 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_difference` <a id="set.difference">[[set.difference]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
+ constexpr OutputIterator
     set_difference(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2,
                    OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator>
                    ForwardIterator2 first2, ForwardIterator2 last2,
                    ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
+ constexpr OutputIterator
     set_difference(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2,
                    OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     set_difference(ExecutionPolicy&& exec,
                    ForwardIterator1 first1, ForwardIterator1 last1,
                    ForwardIterator2 first2, ForwardIterator2 last2,
                    ForwardIterator result, Compare comp);
+template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+         weakly_incrementable O, class Comp = ranges::less,
+         class Proj1 = identity, class Proj2 = identity>
+  requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+  constexpr ranges::set_difference_result<I1, O>
+    ranges::set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
+                           Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+template<input_range R1, input_range R2, weakly_incrementable O,
+         class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+  constexpr ranges::set_difference_result<borrowed_iterator_t<R1>, O>
+    ranges::set_difference(R1&& r1, R2&& r2, O result,
+                           Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
 ```
+Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
+overloads with no parameters by those names.
+*Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
+`last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
+respectively. The resulting range does not overlap with either of the
 original ranges.
 *Effects:* Copies the elements of the range \[`first1`, `last1`) which
 are not present in the range \[`first2`, `last2`) to the range beginning
 at `result`. The elements in the constructed range are sorted.
+*Returns:* Let `result_last` be the end of the constructed range.
+Returns
+- `result_last` for the overloads in namespace `std`.
+- `{last1, result_last}` for the overloads in namespace `ranges`.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
+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,
          class OutputIterator>
+ constexpr OutputIterator
     set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator>
                              ForwardIterator2 first2, ForwardIterator2 last2,
                              ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
+ constexpr OutputIterator
     set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     set_symmetric_difference(ExecutionPolicy&& exec,
                              ForwardIterator1 first1, ForwardIterator1 last1,
                              ForwardIterator2 first2, ForwardIterator2 last2,
                              ForwardIterator result, Compare comp);
+template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+         weakly_incrementable O, class Comp = ranges::less,
+         class Proj1 = identity, class Proj2 = identity>
+  requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+  constexpr ranges::set_symmetric_difference_result<I1, I2, O>
+    ranges::set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
+                                     Comp comp = {}, Proj1 proj1 = {},
+                                     Proj2 proj2 = {});
+template<input_range R1, input_range R2, weakly_incrementable O,
+         class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+  constexpr ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>,
+                                                    borrowed_iterator_t<R2>, O>
+    ranges::set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
+                                     Proj1 proj1 = {}, Proj2 proj2 = {});
 ```
+Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
+overloads with no parameters by those names.
+*Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
+`last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
+respectively. The resulting range does not overlap with either of the
 original ranges.
 *Effects:* Copies the elements of the range \[`first1`, `last1`) that
 are not present in the range \[`first2`, `last2`), and the elements of
 the range \[`first2`, `last2`) that are not present in the range
 \[`first1`, `last1`) to the range beginning at `result`. The elements in
 the constructed range are sorted.
+*Returns:* Let `result_last` be the end of the constructed range.
+Returns
+- `result_last` for the overloads in namespace `std`.
+- `{last1, last2, result_last}` for the overloads in namespace `ranges`.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
+comparisons and applications of each projection.
+*Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
+m elements that are equivalent to each other and \[`first2`, `last2`)
+contains n elements that are equivalent to them, then |m - n| of those
+elements shall be copied to the output range: the last m - n of these
+elements from \[`first1`, `last1`) if m > n, and the last n - m of these
+elements from \[`first2`, `last2`) if m < n. 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,
+  `bool(invoke(comp, invoke(proj, a[\left \lfloor{\frac{i - 1}{2}}\right \rfloor]), invoke({}proj, a[i])))`
+ is `false`.
+- `*a` may be removed by `pop_heap`, or a new element added by
+  `push_heap`, in 𝑂(log N) time.
 These properties make heaps useful as priority queues.
+`make_heap` converts a range into a heap and `sort_heap` turns a heap
+into a sorted sequence.
 #### `push_heap` <a id="push.heap">[[push.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
+ constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
+ constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last,
                            Compare comp);
+template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  constexpr I
+    ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {});
+template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  constexpr borrowed_iterator_t<R>
+    ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
+*Preconditions:* The range \[`first`, `last - 1`) is a valid heap with
+respect to `comp` and `proj`. 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`.
+*Complexity:* At most log(`last - first`) comparisons and twice as many
+projections.
 #### `pop_heap` <a id="pop.heap">[[pop.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
+ constexpr void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
+ constexpr void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                           Compare comp);
+template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  constexpr I
+    ranges::pop_heap(I first, S last, Comp comp = {}, Proj proj = {});
+template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  constexpr borrowed_iterator_t<R>
+    ranges::pop_heap(R&& r, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
+*Preconditions:* The range \[`first`, `last`) is a valid non-empty 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* ([[cpp17.moveconstructible]]) and
+*Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
 *Effects:* Swaps the value in the location `first` with the value in the
+location `last - 1` and makes \[`first`, `last - 1`) into a heap with
+respect to `comp` and `proj`.
+*Returns:* `last` for the overloads in namespace `ranges`.
+*Complexity:* At most 2 log(`last - first`) comparisons and twice as
+many projections.
 #### `make_heap` <a id="make.heap">[[make.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
+ constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
+ constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last,
                            Compare comp);
+template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  constexpr I
+    ranges::make_heap(I first, S last, Comp comp = {}, Proj proj = {});
+template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  constexpr borrowed_iterator_t<R>
+    ranges::make_heap(R&& r, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
+*Preconditions:* 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`.
+*Complexity:* At most 3(`last - first`) comparisons and twice as many
+projections.
 #### `sort_heap` <a id="sort.heap">[[sort.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
+ constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
+ constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
                            Compare comp);
+template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  constexpr I
+    ranges::sort_heap(I first, S last, Comp comp = {}, Proj proj = {});
+template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  constexpr borrowed_iterator_t<R>
+    ranges::sort_heap(R&& r, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
+*Preconditions:* The range \[`first`, `last`) 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* ([[cpp17.moveconstructible]]) and
+*Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
+*Effects:* Sorts elements in the heap \[`first`, `last`) with respect to
+`comp` and `proj`.
+*Returns:* `last` for the overloads in namespace `ranges`.
+*Complexity:* At most 2N log N comparisons, where N = `last - first`,
+and twice as many projections.
 #### `is_heap` <a id="is.heap">[[is.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
+ constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
 ```
+*Effects:* Equivalent to: `return is_heap_until(first, last) == last;`
 ``` cpp
 template<class ExecutionPolicy, class RandomAccessIterator>
   bool is_heap(ExecutionPolicy&& exec,
                RandomAccessIterator first, RandomAccessIterator last);
 ```
+*Effects:* Equivalent to:
+``` cpp
+return is_heap_until(std::forward<ExecutionPolicy>(exec), first, last) == last;
+```
 ``` cpp
 template<class RandomAccessIterator, class Compare>
+ constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
+                         Compare comp);
 ```
+*Effects:* Equivalent to:
+`return is_heap_until(first, last, comp) == last;`
 ``` cpp
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
   bool is_heap(ExecutionPolicy&& exec,
+               RandomAccessIterator first, RandomAccessIterator last,
+               Compare comp);
 ```
+*Effects:* Equivalent to:
 ``` cpp
+return is_heap_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last;
 ```
+``` cpp
+template<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
+         indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+  constexpr bool ranges::is_heap(I first, S last, Comp comp = {}, Proj proj = {});
+template<random_access_range R, class Proj = identity,
+         indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+  constexpr bool ranges::is_heap(R&& r, Comp comp = {}, Proj proj = {});
+```
+*Effects:* Equivalent to:
+`return ranges::is_heap_until(first, last, comp, proj) == last;`
 ``` cpp
 template<class RandomAccessIterator>
+ constexpr RandomAccessIterator
+    is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
 template<class ExecutionPolicy, class RandomAccessIterator>
+  RandomAccessIterator
+    is_heap_until(ExecutionPolicy&& exec,
                   RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
+ constexpr RandomAccessIterator
+    is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp);
 template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
+  RandomAccessIterator
+    is_heap_until(ExecutionPolicy&& exec,
                   RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp);
+template<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
+         indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+  constexpr I ranges::is_heap_until(I first, S last, Comp comp = {}, Proj proj = {});
+template<random_access_range R, class Proj = identity,
+         indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+  constexpr borrowed_iterator_t<R>
+    ranges::is_heap_until(R&& r, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
+*Returns:* The last iterator `i` in \[`first`, `last`\] for which the
+range \[`first`, `i`) is a heap with respect to `comp` and `proj`.
 *Complexity:* Linear.
 ### Minimum and maximum <a id="alg.min.max">[[alg.min.max]]</a>
 ``` cpp
+template<class T>
+  constexpr const T& min(const T& a, const T& b);
 template<class T, class Compare>
   constexpr const T& min(const T& a, const T& b, Compare comp);
+template<class T, class Proj = identity,
+         indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
+  constexpr const T& ranges::min(const T& a, const T& b, Comp comp = {}, Proj proj = {});
 ```
+*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);
+template<copyable T, class Proj = identity,
+         indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
+  constexpr T ranges::min(initializer_list<T> r, Comp comp = {}, Proj proj = {});
+template<input_range R, class Proj = identity,
+         indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+  requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
+  constexpr range_value_t<R>
+    ranges::min(R&& r, Comp comp = {}, Proj proj = {});
 ```
+*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);
+template<class T, class Proj = identity,
+         indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
+  constexpr const T& ranges::max(const T& a, const T& b, Comp comp = {}, Proj proj = {});
 ```
+*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);
+template<copyable T, class Proj = identity,
+         indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
+  constexpr T ranges::max(initializer_list<T> r, Comp comp = {}, Proj proj = {});
+template<input_range R, class Proj = identity,
+         indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+  requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
+  constexpr range_value_t<R>
+    ranges::max(R&& r, Comp comp = {}, Proj proj = {});
 ```
+*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);
+template<class T, class Proj = identity,
+         indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
+  constexpr ranges::minmax_result<const T&>
+    ranges::minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {});
 ```
+*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);
+template<copyable T, class Proj = identity,
+         indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
+  constexpr ranges::minmax_result<T>
+    ranges::minmax(initializer_list<T> r, Comp comp = {}, Proj proj = {});
+template<input_range R, class Proj = identity,
+         indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+  requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
+  constexpr ranges::minmax_result<range_value_t<R>>
+    ranges::minmax(R&& r, Comp comp = {}, Proj proj = {});
 ```
+*Preconditions:* `ranges::distance(r) > 0`. For the overloads in
+namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
+For the first form, type `T` meets the *Cpp17LessThanComparable*
+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);
                                         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,
+         indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+  constexpr borrowed_iterator_t<R>
+    ranges::min_element(R&& r, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
 *Returns:* The first iterator `i` in the range \[`first`, `last`) such
+that for every iterator `j` in the range \[`first`, `last`),
+``` cpp
+bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))
+```
+is `false`. Returns `last` if `first == last`.
+*Complexity:* Exactly max(`last - first - 1`, 0) comparisons and twice
+as many projections.
 ``` cpp
 template<class ForwardIterator>
   constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
 template<class ExecutionPolicy, class ForwardIterator>
                                         Compare comp);
 template<class ExecutionPolicy, class ForwardIterator, class Compare>
   ForwardIterator max_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::max_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 borrowed_iterator_t<R>
+    ranges::max_element(R&& r, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
 *Returns:* The first iterator `i` in the range \[`first`, `last`) such
+that for every iterator `j` in the range \[`first`, `last`),
+``` cpp
+bool(invoke(comp, invoke(proj, *i), invoke(proj, *j)))
+```
+is `false`. Returns `last` if `first == last`.
+*Complexity:* Exactly max(`last - first - 1`, 0) comparisons and twice
+as many projections.
 ``` cpp
 template<class ForwardIterator>
   constexpr pair<ForwardIterator, ForwardIterator>
     minmax_element(ForwardIterator first, ForwardIterator last);
     minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator, class Compare>
   pair<ForwardIterator, ForwardIterator>
     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.
 ### Bounded value <a id="alg.clamp">[[alg.clamp]]</a>
 ``` cpp
 template<class T>
   constexpr const T& clamp(const T& v, const T& lo, const T& hi);
 template<class T, class Compare>
   constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp);
+template<class T, class Proj = identity,
+         indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
+  constexpr const T&
+    ranges::clamp(const T& v, const T& lo, const T& hi, Comp comp = {}, Proj proj = {});
 ```
+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
+projection.
 ### Lexicographical comparison <a id="alg.lex.comparison">[[alg.lex.comparison]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2>
+ constexpr bool
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
   bool
     lexicographical_compare(ExecutionPolicy&& exec,
                             ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2);
 template<class InputIterator1, class InputIterator2, class Compare>
+ constexpr bool
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2,
                             Compare comp);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class Compare>
   bool
     lexicographical_compare(ExecutionPolicy&& exec,
                             ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2,
                             Compare comp);
+template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+         class Proj1 = identity, class Proj2 = identity,
+         indirect_strict_weak_order<projected<I1, Proj1>,
+                                    projected<I2, Proj2>> Comp = ranges::less>
+  constexpr bool
+    ranges::lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
+                                    Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+template<input_range R1, input_range R2, class Proj1 = identity,
+         class Proj2 = identity,
+         indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
+                                    projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
+  constexpr bool
+    ranges::lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {},
+                                    Proj1 proj1 = {}, Proj2 proj2 = {});
 ```
+*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`).
 *Complexity:* At most 2 min(`last1 - first1`,  `last2 - first2`)
+applications of the corresponding comparison and each projection, if
+any.
 *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. If one sequence is a proper
+prefix of the other, then the shorter sequence is lexicographically less
+than the longer sequence. Otherwise, the lexicographical comparison of
+the sequences yields the same result as the comparison of the first
 corresponding pair of elements that are not equivalent.
 [*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;
 }
 return first1 == last1 && first2 != last2;
 ```
 — *end example*]
 [*Note 1*: An empty sequence is lexicographically less than any
 non-empty sequence, but not less than any empty sequence. — *end note*]
+### Three-way comparison algorithms <a id="alg.three.way">[[alg.three.way]]</a>
+``` cpp
+template<class InputIterator1, class InputIterator2, class Cmp>
+  constexpr auto
+    lexicographical_compare_three_way(InputIterator1 b1, InputIterator1 e1,
+                                      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,
+                                      InputIterator2 b2, InputIterator2 e2);
+```
+*Effects:* Equivalent to:
+``` cpp
+return lexicographical_compare_three_way(b1, e1, b2, e2, compare_three_way());
+```
 ### Permutation generators <a id="alg.permutation.generators">[[alg.permutation.generators]]</a>
 ``` cpp
 template<class BidirectionalIterator>
+ constexpr bool next_permutation(BidirectionalIterator first,
                                   BidirectionalIterator last);
 template<class BidirectionalIterator, class Compare>
+ constexpr bool next_permutation(BidirectionalIterator first,
                                   BidirectionalIterator last, Compare comp);
+template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  constexpr ranges::next_permutation_result<I>
+    ranges::next_permutation(I first, S last, Comp comp = {}, Proj proj = {});
+template<bidirectional_range R, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  constexpr ranges::next_permutation_result<borrowed_iterator_t<R>>
+    ranges::next_permutation(R&& r, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for overloads with no
+parameters by those names.
+*Preconditions:* For the overloads in namespace `std`,
+`BidirectionalIterator` meets the *Cpp17ValueSwappable*
+requirements [[swappable.requirements]].
 *Effects:* Takes a sequence defined by the range \[`first`, `last`) and
 transforms it into the next permutation. The next permutation is found
 by assuming that the set of all permutations is lexicographically sorted
+with respect to `comp` and `proj`. If no such permutation exists,
+transforms the sequence into the first permutation; that is, the
+ascendingly-sorted one.
+*Returns:* Let `B` be `true` if a next permutation was found and
+otherwise `false`. Returns:
+- `B` for the overloads in namespace `std`.
+- `{ last, B }` for the overloads in namespace `ranges`.
 *Complexity:* At most `(last - first) / 2` swaps.
 ``` cpp
 template<class BidirectionalIterator>
+ constexpr bool prev_permutation(BidirectionalIterator first,
                                   BidirectionalIterator last);
 template<class BidirectionalIterator, class Compare>
+ constexpr bool prev_permutation(BidirectionalIterator first,
                                   BidirectionalIterator last, Compare comp);
+template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  constexpr ranges::prev_permutation_result<I>
+    ranges::prev_permutation(I first, S last, Comp comp = {}, Proj proj = {});
+template<bidirectional_range R, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  constexpr ranges::prev_permutation_result<borrowed_iterator_t<R>>
+    ranges::prev_permutation(R&& r, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for overloads with no
+parameters by those names.
+*Preconditions:* For the overloads in namespace `std`,
+`BidirectionalIterator` meets the *Cpp17ValueSwappable*
+requirements [[swappable.requirements]].
 *Effects:* Takes a sequence defined by the range \[`first`, `last`) and
 transforms it into the previous permutation. The previous permutation is
 found by assuming that the set of all permutations is lexicographically
+sorted with respect to `comp` and `proj`. If no such permutation exists,
+transforms the sequence into the last permutation; that is, the
+descendingly-sorted one.
+*Returns:* Let `B` be `true` if a previous permutation was found and
+otherwise `false`. Returns:
+- `B` for the overloads in namespace `std`.
+- `{ last, B }` for the overloads in namespace `ranges`.
 *Complexity:* At most `(last - first) / 2` swaps.

Diff to HTML by rtfpessoa