[alg.modifying.operations] - C++14 → C++17

Files changed (1) hide show

tmp/tmplzs9879w/{from.md → to.md} +308 -187

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

@@ -6,25 +6,47 @@
 template<class InputIterator, class OutputIterator>
   OutputIterator copy(InputIterator first, InputIterator last,
                       OutputIterator result);
 ```
 *Effects:* Copies elements in the range \[`first`, `last`) into the
 range \[`result`, `result + (last - first)`) starting from `first` and
 proceeding to `last`. For each non-negative integer
 `n < (last - first)`, performs `*(result + n) = *(first + n)`.
 *Returns:* `result + (last - first)`.
-*Requires:* `result` shall not be in the range \[`first`, `last`).
 *Complexity:* Exactly `last - first` assignments.
 ``` cpp
 template<class InputIterator, class Size, class OutputIterator>
   OutputIterator copy_n(InputIterator first, Size n,
                         OutputIterator result);
 ```
 *Effects:* For each non-negative integer i < n, performs
 `*(result + i) = *(first + i)`.
@@ -34,15 +56,24 @@ template<class InputIterator, class Size, class OutputIterator>
 ``` cpp
 template<class InputIterator, class OutputIterator, class Predicate>
   OutputIterator copy_if(InputIterator first, InputIterator last,
                          OutputIterator result, Predicate pred);
 ```
 *Requires:* The ranges \[`first`, `last`) and \[`result`,
 `result + (last - first)`) shall not overlap.
 *Effects:* Copies all of the elements referred to by the iterator `i` in
 the range \[`first`, `last`) for which `pred(*i)` is `true`.
 *Returns:* The end of the resulting range.
@@ -57,135 +88,182 @@ template<class BidirectionalIterator1, class BidirectionalIterator2>
     copy_backward(BidirectionalIterator1 first,
                   BidirectionalIterator1 last,
                   BidirectionalIterator2 result);
 ```
 *Effects:* Copies elements in the range \[`first`, `last`) into the
 range \[`result - (last-first)`, `result`) starting from `last - 1` and
 proceeding to `first`.[^2] For each positive integer
 `n <= (last - first)`, performs `*(result - n) = *(last - n)`.
-*Requires:* `result` shall not be in the range (`first`, `last`).
 *Returns:* `result - (last - first)`.
 *Complexity:* Exactly `last - first` assignments.
 ### Move <a id="alg.move">[[alg.move]]</a>
 ``` cpp
 template<class InputIterator, class OutputIterator>
-  OutputIterator move(InputIterator first, InputIterator last,
-                      OutputIterator result);
 ```
 *Effects:* Moves elements in the range \[`first`, `last`) into the range
 \[`result`, `result + (last - first)`) starting from first and
 proceeding to last. For each non-negative integer `n < (last-first)`,
 performs `*(result + n)` `= std::move(*(first + n))`.
 *Returns:* `result + (last - first)`.
-*Requires:* `result` shall not be in the range \[`first`, `last`).
 *Complexity:* Exactly `last - first` move assignments.
 ``` cpp
 template<class BidirectionalIterator1, class BidirectionalIterator2>
   BidirectionalIterator2
     move_backward(BidirectionalIterator1 first,
                   BidirectionalIterator1 last,
                   BidirectionalIterator2 result);
 ```
 *Effects:* Moves elements in the range \[`first`, `last`) into the range
 \[`result - (last-first)`, `result`) starting from `last - 1` and
 proceeding to first.[^3] For each positive integer
 `n <= (last - first)`, performs
 `*(result - n) = std::move(*(last - n))`.
-*Requires:* `result` shall not be in the range (`first`, `last`).
 *Returns:* `result - (last - first)`.
 *Complexity:* Exactly `last - first` assignments.
-### swap <a id="alg.swap">[[alg.swap]]</a>
 ``` cpp
 template<class ForwardIterator1, class ForwardIterator2>
   ForwardIterator2
     swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
                 ForwardIterator2 first2);
 ```
-*Effects:* For each non-negative integer `n < (last1 - first1)`
-performs: `swap(*(first1 + n), *(first2 + n))`.
 *Requires:* The two ranges \[`first1`, `last1`) and \[`first2`,
 `first2 + (last1 - first1)`) shall not overlap. `*(first1 + n)` shall be
 swappable with ([[swappable.requirements]]) `*(first2 + n)`.
 *Returns:* `first2 + (last1 - first1)`.
 *Complexity:* Exactly `last1 - first1` swaps.
 ``` cpp
 template<class ForwardIterator1, class ForwardIterator2>
   void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
 ```
-*Effects:* `swap(*a, *b)`.
 *Requires:* `a` and `b` shall be dereferenceable. `*a` shall be
 swappable with ([[swappable.requirements]]) `*b`.
 ### Transform <a id="alg.transform">[[alg.transform]]</a>
 ``` cpp
 template<class InputIterator, class OutputIterator,
          class UnaryOperation>
   OutputIterator
     transform(InputIterator first, InputIterator last,
               OutputIterator result, UnaryOperation op);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class BinaryOperation>
   OutputIterator
     transform(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, OutputIterator result,
               BinaryOperation binary_op);
 ```
 *Effects:* Assigns through every iterator `i` in the range \[`result`,
 `result + (last1 - first1)`) a new corresponding value equal to
-`op(*(first1 + (i - result))` or
 `binary_op(*(first1 + (i - result)), *(first2 + (i - result)))`.
-*Requires:* `op` and `binary_op` shall not invalidate iterators or
-subranges, or modify elements in the ranges \[`first1`, `last1`\],
-\[`first2`, `first2 + (last1 - first1)`\], and \[`result`,
-`result + (last1 - first1)`\].[^4]
 *Returns:* `result + (last1 - first1)`.
 *Complexity:* Exactly `last1 - first1` applications of `op` or
-`binary_op`.
 *Remarks:* `result` may be equal to `first` in case of unary transform,
 or to `first1` or `first2` in case of binary transform.
 ### Replace <a id="alg.replace">[[alg.replace]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
   void replace(ForwardIterator first, ForwardIterator last,
                const T& old_value, const T& new_value);
 template<class ForwardIterator, class Predicate, class T>
   void replace_if(ForwardIterator first, ForwardIterator last,
                   Predicate pred, const T& new_value);
 ```
 *Requires:* The expression `*first = new_value` shall be valid.
 *Effects:* Substitutes elements referred by the iterator `i` in the
@@ -199,21 +277,35 @@ predicate.
 template<class InputIterator, class OutputIterator, class T>
   OutputIterator
     replace_copy(InputIterator first, InputIterator last,
                  OutputIterator result,
                  const T& old_value, const T& new_value);
 template<class InputIterator, class OutputIterator, class Predicate, class T>
   OutputIterator
     replace_copy_if(InputIterator first, InputIterator last,
                     OutputIterator result,
                     Predicate pred, const T& new_value);
 ```
 *Requires:* The results of the expressions `*first` and `new_value`
-shall be writable to the `result` output iterator. The ranges \[`first`,
-`last`) and \[`result`, `result + (last - first)`) shall not overlap.
 *Effects:* Assigns to every iterator `i` in the range \[`result`,
 `result + (last - first)`) either `new_value` or
 `*(first + (i - result))` depending on whether the following
 corresponding conditions hold:
@@ -231,23 +323,30 @@ predicate.
 ### Fill <a id="alg.fill">[[alg.fill]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
   void fill(ForwardIterator first, ForwardIterator last, const T& value);
 template<class OutputIterator, class Size, class T>
   OutputIterator fill_n(OutputIterator first, Size n, const T& value);
 ```
-*Requires:* The expression `value` shall be writable to the output
-iterator. The type `Size` shall be convertible to an integral
 type ([[conv.integral]], [[class.conv]]).
-*Effects:* The first algorithm assigns `value` through all the iterators
-in the range \[`first`, `last`). The second algorithm assigns `value`
-through all the iterators in the range \[`first`, `first + n`) if `n` is
-positive, otherwise it does nothing.
 *Returns:* `fill_n` returns `first + n` for non-negative values of `n`
 and `first` for negative values.
 *Complexity:* Exactly `last - first`, `n`, or 0 assignments,
@@ -257,25 +356,32 @@ respectively.
 ``` cpp
 template<class ForwardIterator, class Generator>
   void generate(ForwardIterator first, ForwardIterator last,
                 Generator gen);
 template<class OutputIterator, class Size, class Generator>
   OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
 ```
-*Effects:* The first algorithm invokes the function object `gen` and
-assigns the return value of `gen` through all the iterators in the range
-\[`first`, `last`). The second algorithm invokes the function object
-`gen` and assigns the return value of `gen` through all the iterators in
-the range \[`first`, `first + n`) if `n` is positive, otherwise it does
-nothing.
 *Requires:* `gen` takes no arguments, `Size` shall be convertible to an
 integral type ([[conv.integral]], [[class.conv]]).
 *Returns:* `generate_n` returns `first + n` for non-negative values of
 `n` and `first` for negative values.
 *Complexity:* Exactly `last - first`, `n`, or 0 invocations of `gen` and
 assignments, respectively.
@@ -284,18 +390,26 @@ assignments, respectively.
 ``` cpp
 template<class ForwardIterator, class T>
   ForwardIterator remove(ForwardIterator first, ForwardIterator last,
                          const T& value);
 template<class ForwardIterator, class Predicate>
   ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
                             Predicate pred);
 ```
 *Requires:* The type of `*first` shall satisfy the `MoveAssignable`
-requirements (Table  [[moveassignable]]).
 *Effects:* Eliminates all the elements referred to by iterator `i` in
 the range \[`first`, `last`) for which the following corresponding
 conditions hold: `*i == value, pred(*i) != false`.
@@ -304,31 +418,46 @@ conditions hold: `*i == value, pred(*i) != false`.
 *Remarks:* Stable ([[algorithm.stable]]).
 *Complexity:* Exactly `last - first` applications of the corresponding
 predicate.
-*Note:* each element in the range \[`ret`, `last`), where `ret` is the
-returned value, has a valid but unspecified state, because the
 algorithms can eliminate elements by moving from elements that were
-originally in that range.
 ``` cpp
 template<class InputIterator, class OutputIterator, class T>
   OutputIterator
     remove_copy(InputIterator first, InputIterator last,
                 OutputIterator result, const T& value);
 template<class InputIterator, class OutputIterator, class Predicate>
   OutputIterator
     remove_copy_if(InputIterator first, InputIterator last,
                    OutputIterator result, Predicate pred);
 ```
 *Requires:* The ranges \[`first`, `last`) and \[`result`,
 `result + (last - first)`) shall not overlap. The expression
 `*result = *first` shall be valid.
 *Effects:* Copies all the elements referred to by the iterator `i` in
 the range \[`first`, `last`) for which the following corresponding
 conditions do not hold: `*i == value, pred(*i) != false`.
 *Returns:* The end of the resulting range.
@@ -341,51 +470,78 @@ predicate.
 ### Unique <a id="alg.unique">[[alg.unique]]</a>
 ``` cpp
 template<class ForwardIterator>
   ForwardIterator unique(ForwardIterator first, ForwardIterator last);
 template<class ForwardIterator, class BinaryPredicate>
   ForwardIterator unique(ForwardIterator first, ForwardIterator last,
                          BinaryPredicate pred);
 ```
 *Effects:* For a nonempty range, eliminates all but the first element
 from every consecutive group of equivalent elements referred to by the
 iterator `i` in the range \[`first + 1`, `last`) for which the following
 conditions hold: `*(i - 1) == *i` or `pred(*(i - 1), *i) != false`.
-*Requires:* The comparison function shall be an equivalence relation.
-The type of `*first` shall satisfy the `MoveAssignable` requirements
-(Table  [[moveassignable]]).
 *Returns:* The end of the resulting range.
 *Complexity:* For nonempty ranges, exactly `(last - first) - 1`
 applications of the corresponding predicate.
 ``` cpp
 template<class InputIterator, class OutputIterator>
   OutputIterator
     unique_copy(InputIterator first, InputIterator last,
                 OutputIterator result);
 template<class InputIterator, class OutputIterator,
          class BinaryPredicate>
   OutputIterator
     unique_copy(InputIterator first, InputIterator last,
                 OutputIterator result, BinaryPredicate pred);
 ```
-*Requires:* The comparison function shall be an equivalence relation.
-The ranges \[`first`, `last`) and \[`result`, `result+(last-first)`)
-shall not overlap. The expression `*result = *first` shall be valid. If
-neither `InputIterator` nor `OutputIterator` meets the requirements of
-forward iterator then the value type of `InputIterator` shall be
-`CopyConstructible` (Table  [[copyconstructible]]) and `CopyAssignable`
-(Table  [[copyassignable]]). Otherwise `CopyConstructible` is not
-required.
 *Effects:* Copies only the first element from every consecutive group of
 equal elements referred to by the iterator `i` in the range \[`first`,
 `last`) for which the following corresponding conditions hold:
 `*i == *(i - 1)` or `pred(*i, *(i - 1)) != false`.
@@ -398,206 +554,171 @@ applications of the corresponding predicate.
 ### Reverse <a id="alg.reverse">[[alg.reverse]]</a>
 ``` cpp
 template<class BidirectionalIterator>
   void reverse(BidirectionalIterator first, BidirectionalIterator last);
 ```
-*Effects:* For each non-negative integer `i < (last - first)/2`, applies
-`iter_swap` to all pairs of iterators `first + i, (last - i) - 1`.
 *Requires:* `*first` shall be swappable ([[swappable.requirements]]).
 *Complexity:* Exactly `(last - first)/2` swaps.
 ``` cpp
 template<class BidirectionalIterator, class OutputIterator>
   OutputIterator
-    reverse_copy(BidirectionalIterator first,
- BidirectionalIterator last, OutputIterator result);
 ```
 *Effects:* Copies the range \[`first`, `last`) to the range \[`result`,
 `result + (last - first)`) such that for every non-negative integer
 `i < (last - first)` the following assignment takes place:
 `*(result + (last - first) - 1 - i) = *(first + i)`.
-*Requires:* The ranges \[`first`, `last`) and \[`result`,
-`result+(last-first)`) shall not overlap.
 *Returns:* `result + (last - first)`.
 *Complexity:* Exactly `last - first` assignments.
 ### Rotate <a id="alg.rotate">[[alg.rotate]]</a>
 ``` cpp
 template<class ForwardIterator>
-  ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
- ForwardIterator last);
 ```
 *Effects:* For each non-negative integer `i < (last - first)`, places
 the element from the position `first + i` into position
 `first + (i + (last - middle)) % (last - first)`.
 *Returns:* `first + (last - middle)`.
 *Remarks:* This is a left rotate.
-*Requires:* \[`first`, `middle`) and \[`middle`, `last`) shall be valid
-ranges. `ForwardIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[moveconstructible]]) and the requirements of `MoveAssignable`
-(Table  [[moveassignable]]).
 *Complexity:* At most `last - first` swaps.
 ``` cpp
 template<class ForwardIterator, class OutputIterator>
   OutputIterator
-    rotate_copy(ForwardIterator first, ForwardIterator middle,
- ForwardIterator last, OutputIterator result);
 ```
 *Effects:* Copies the range \[`first`, `last`) to the range \[`result`,
 `result + (last - first)`) such that for each non-negative integer
 `i < (last - first)` the following assignment takes place:
 `*(result + i) = *(first + (i + (middle - first)) % (last - first))`.
 *Returns:* `result + (last - first)`.
-*Requires:* The ranges \[`first`, `last`) and \[`result`,
-`result + (last - first)`) shall not overlap.
 *Complexity:* Exactly `last - first` assignments.
 ### Shuffle <a id="alg.random.shuffle">[[alg.random.shuffle]]</a>
 ``` cpp
-template<class RandomAccessIterator, class UniformRandomNumberGenerator>
   void shuffle(RandomAccessIterator first,
                RandomAccessIterator last,
-                      UniformRandomNumberGenerator&& g);
 ```
 *Effects:* Permutes the elements in the range \[`first`, `last`) such
 that each possible permutation of those elements has equal probability
 of appearance.
-*Requires:* `RandomAccessIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type
-`UniformRandomNumberGenerator` shall meet the requirements of a uniform
-random number generator ([[rand.req.urng]]) type whose return type is
-convertible to `iterator_traits<RandomAccessIterator>::difference_type`.
 *Complexity:* Exactly `(last - first) - 1` swaps.
 *Remarks:* To the extent that the implementation of this function makes
 use of random numbers, the object `g` shall serve as the
 implementation’s source of randomness.
-### Partitions <a id="alg.partitions">[[alg.partitions]]</a>
-``` cpp
-template <class InputIterator, class Predicate>
-  bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
-```
-*Requires:* `InputIterator`’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);
-```
-*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`.
-*Requires:* `ForwardIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]).
-*Complexity:* If ForwardIterator meets the requirements for a
-BidirectionalIterator, at most `(last - first) / 2` swaps are done;
-otherwise at most `last - first` swaps are done. Exactly `last - first`
-applications of the predicate are done.
-``` cpp
-template<class BidirectionalIterator, class Predicate>
-  BidirectionalIterator
-    stable_partition(BidirectionalIterator first,
-                     BidirectionalIterator last, Predicate pred);
-```
-*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.
-*Requires:* `BidirectionalIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[moveconstructible]]) and of `MoveAssignable`
-(Table  [[moveassignable]]).
-*Complexity:* At most `(last - first) * log(last - first)` swaps, but
-only linear number of swaps if there is enough extra memory. Exactly
-`last - first` applications of the predicate.
-``` 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);
-```
-*Requires:* `InputIterator`’s value type shall be `CopyAssignable`, and
-shall be writable to the `out_true` and `out_false` `OutputIterator`s,
-and shall be convertible to `Predicate`’s argument type. 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`.

 template<class InputIterator, class OutputIterator>
   OutputIterator copy(InputIterator first, InputIterator last,
                       OutputIterator result);
 ```
+*Requires:* `result` shall not be in the range \[`first`, `last`).
 *Effects:* Copies elements in the range \[`first`, `last`) into the
 range \[`result`, `result + (last - first)`) starting from `first` and
 proceeding to `last`. For each non-negative integer
 `n < (last - first)`, performs `*(result + n) = *(first + n)`.
 *Returns:* `result + (last - first)`.
+*Complexity:* Exactly `last - first` assignments.
+``` cpp
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
+  ForwardIterator2 copy(ExecutionPolicy&& policy,
+                        ForwardIterator1 first, ForwardIterator1 last,
+                        ForwardIterator2 result);
+```
+*Requires:* The ranges \[`first`, `last`) and \[`result`,
+`result + (last - first)`) shall not overlap.
+*Effects:* Copies elements in the range \[`first`, `last`) into the
+range \[`result`, `result + (last - first)`). For each non-negative
+integer `n < (last - first)`, performs `*(result + n) = *(first + n)`.
+*Returns:* `result + (last - first)`.
 *Complexity:* Exactly `last - first` assignments.
 ``` cpp
 template<class InputIterator, class Size, class OutputIterator>
   OutputIterator copy_n(InputIterator first, Size n,
                         OutputIterator result);
+template<class ExecutionPolicy, class ForwardIterator1, class Size, class ForwardIterator2>
+  ForwardIterator2 copy_n(ExecutionPolicy&& exec,
+                          ForwardIterator1 first, Size n,
+                          ForwardIterator2 result);
 ```
 *Effects:* For each non-negative integer i < n, performs
 `*(result + i) = *(first + i)`.
 ``` cpp
 template<class InputIterator, class OutputIterator, class Predicate>
   OutputIterator copy_if(InputIterator first, InputIterator last,
                          OutputIterator result, Predicate pred);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Predicate>
+  ForwardIterator2 copy_if(ExecutionPolicy&& exec,
+                           ForwardIterator1 first, ForwardIterator1 last,
+                           ForwardIterator2 result, Predicate pred);
 ```
 *Requires:* The ranges \[`first`, `last`) and \[`result`,
 `result + (last - first)`) shall not overlap.
+[*Note 1*: For the overload with an `ExecutionPolicy`, there may be a
+performance cost if `iterator_traits<ForwardIterator1>::value_type` is
+not `MoveConstructible`
+(Table  [[tab:moveconstructible]]). — *end note*]
 *Effects:* Copies all of the elements referred to by the iterator `i` in
 the range \[`first`, `last`) for which `pred(*i)` is `true`.
 *Returns:* The end of the resulting range.
     copy_backward(BidirectionalIterator1 first,
                   BidirectionalIterator1 last,
                   BidirectionalIterator2 result);
 ```
+*Requires:* `result` shall not be in the range (`first`, `last`).
 *Effects:* Copies elements in the range \[`first`, `last`) into the
 range \[`result - (last-first)`, `result`) starting from `last - 1` and
 proceeding to `first`.[^2] For each positive integer
 `n <= (last - first)`, performs `*(result - n) = *(last - n)`.
 *Returns:* `result - (last - first)`.
 *Complexity:* Exactly `last - first` assignments.
 ### Move <a id="alg.move">[[alg.move]]</a>
 ``` cpp
 template<class InputIterator, class OutputIterator>
+  OutputIterator move(InputIterator first, InputIterator last, OutputIterator result);
 ```
+*Requires:* `result` shall not be in the range \[`first`, `last`).
 *Effects:* Moves elements in the range \[`first`, `last`) into the range
 \[`result`, `result + (last - first)`) starting from first and
 proceeding to last. For each non-negative integer `n < (last-first)`,
 performs `*(result + n)` `= std::move(*(first + n))`.
 *Returns:* `result + (last - first)`.
 *Complexity:* Exactly `last - first` move assignments.
+``` cpp
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
+  ForwardIterator2 move(ExecutionPolicy&& policy,
+                        ForwardIterator1 first, ForwardIterator1 last,
+                        ForwardIterator2 result);
+```
+*Requires:* The ranges \[`first`, `last`) and \[`result`,
+`result + (last - first)`) shall not overlap.
+*Effects:* Moves elements in the range \[`first`, `last`) into the range
+\[`result`, `result + (last - first)`). For each non-negative integer
+`n < (last - first)`, performs
+`*(result + n) = std::move(*(first + n))`.
+*Returns:* `result + (last - first)`.
+*Complexity:* Exactly `last - first` assignments.
 ``` cpp
 template<class BidirectionalIterator1, class BidirectionalIterator2>
   BidirectionalIterator2
     move_backward(BidirectionalIterator1 first,
                   BidirectionalIterator1 last,
                   BidirectionalIterator2 result);
 ```
+*Requires:* `result` shall not be in the range (`first`, `last`).
 *Effects:* Moves elements in the range \[`first`, `last`) into the range
 \[`result - (last-first)`, `result`) starting from `last - 1` and
 proceeding to first.[^3] For each positive integer
 `n <= (last - first)`, performs
 `*(result - n) = std::move(*(last - n))`.
 *Returns:* `result - (last - first)`.
 *Complexity:* Exactly `last - first` assignments.
+### Swap <a id="alg.swap">[[alg.swap]]</a>
 ``` cpp
 template<class ForwardIterator1, class ForwardIterator2>
   ForwardIterator2
     swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
                 ForwardIterator2 first2);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
+  ForwardIterator2
+    swap_ranges(ExecutionPolicy&& exec,
+                ForwardIterator1 first1, ForwardIterator1 last1,
+                ForwardIterator2 first2);
 ```
 *Requires:* The two ranges \[`first1`, `last1`) and \[`first2`,
 `first2 + (last1 - first1)`) shall not overlap. `*(first1 + n)` shall be
 swappable with ([[swappable.requirements]]) `*(first2 + n)`.
+*Effects:* For each non-negative integer `n < (last1 - first1)`
+performs: `swap(*(first1 + n), *(first2 + n))`.
 *Returns:* `first2 + (last1 - first1)`.
 *Complexity:* Exactly `last1 - first1` swaps.
 ``` cpp
 template<class ForwardIterator1, class ForwardIterator2>
   void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
 ```
 *Requires:* `a` and `b` shall be dereferenceable. `*a` shall be
 swappable with ([[swappable.requirements]]) `*b`.
+*Effects:* As if by `swap(*a, *b)`.
 ### Transform <a id="alg.transform">[[alg.transform]]</a>
 ``` cpp
 template<class InputIterator, class OutputIterator,
          class UnaryOperation>
   OutputIterator
     transform(InputIterator first, InputIterator last,
               OutputIterator result, UnaryOperation op);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class UnaryOperation>
+  ForwardIterator2
+    transform(ExecutionPolicy&& exec,
+              ForwardIterator1 first, ForwardIterator1 last,
+              ForwardIterator2 result, UnaryOperation op);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class BinaryOperation>
   OutputIterator
     transform(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, OutputIterator result,
               BinaryOperation binary_op);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class ForwardIterator, class BinaryOperation>
+  ForwardIterator
+    transform(ExecutionPolicy&& exec,
+              ForwardIterator1 first1, ForwardIterator1 last1,
+              ForwardIterator2 first2, ForwardIterator result,
+              BinaryOperation binary_op);
 ```
+*Requires:* `op` and `binary_op` shall not invalidate iterators or
+subranges, or modify elements in the ranges
+- \[`first1`, `last1`\],
+- \[`first2`, `first2 + (last1 - first1)`\], and
+- \[`result`, `result + (last1 - first1)`\].[^4]
 *Effects:* Assigns through every iterator `i` in the range \[`result`,
 `result + (last1 - first1)`) a new corresponding value equal to
+`op(*(first1 + (i - result)))` or
 `binary_op(*(first1 + (i - result)), *(first2 + (i - result)))`.
 *Returns:* `result + (last1 - first1)`.
 *Complexity:* Exactly `last1 - first1` applications of `op` or
+`binary_op`. This requirement also applies to the overload with an
+`ExecutionPolicy` .
 *Remarks:* `result` may be equal to `first` in case of unary transform,
 or to `first1` or `first2` in case of binary transform.
 ### Replace <a id="alg.replace">[[alg.replace]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
   void replace(ForwardIterator first, ForwardIterator last,
                const T& old_value, const T& new_value);
+template<class ExecutionPolicy, class ForwardIterator, class T>
+  void replace(ExecutionPolicy&& exec,
+               ForwardIterator first, ForwardIterator last,
+               const T& old_value, const T& new_value);
 template<class ForwardIterator, class Predicate, class T>
   void replace_if(ForwardIterator first, ForwardIterator last,
                   Predicate pred, const T& new_value);
+template<class ExecutionPolicy, class ForwardIterator, class Predicate, class T>
+  void replace_if(ExecutionPolicy&& exec,
+                  ForwardIterator first, ForwardIterator last,
+                  Predicate pred, const T& new_value);
 ```
 *Requires:* The expression `*first = new_value` shall be valid.
 *Effects:* Substitutes elements referred by the iterator `i` in the
 template<class InputIterator, class OutputIterator, class T>
   OutputIterator
     replace_copy(InputIterator first, InputIterator last,
                  OutputIterator result,
                  const T& old_value, const T& new_value);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T>
+  ForwardIterator2
+    replace_copy(ExecutionPolicy&& exec,
+                 ForwardIterator1 first, ForwardIterator1 last,
+                 ForwardIterator2 result,
+                 const T& old_value, const T& new_value);
 template<class InputIterator, class OutputIterator, class Predicate, class T>
   OutputIterator
     replace_copy_if(InputIterator first, InputIterator last,
                     OutputIterator result,
                     Predicate pred, const T& new_value);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class Predicate, class T>
+  ForwardIterator2
+    replace_copy_if(ExecutionPolicy&& exec,
+                    ForwardIterator1 first, ForwardIterator1 last,
+                    ForwardIterator2 result,
+                    Predicate pred, const T& new_value);
 ```
 *Requires:* The results of the expressions `*first` and `new_value`
+shall be writable ([[iterator.requirements.general]]) to the `result`
+output iterator. The ranges \[`first`, `last`) and \[`result`,
+`result + (last - first)`) shall not overlap.
 *Effects:* Assigns to every iterator `i` in the range \[`result`,
 `result + (last - first)`) either `new_value` or
 `*(first + (i - result))` depending on whether the following
 corresponding conditions hold:
 ### Fill <a id="alg.fill">[[alg.fill]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
   void fill(ForwardIterator first, ForwardIterator last, const T& value);
+template<class ExecutionPolicy, class ForwardIterator, class T>
+  void fill(ExecutionPolicy&& exec,
+            ForwardIterator first, ForwardIterator last, const T& value);
 template<class OutputIterator, class Size, class T>
   OutputIterator fill_n(OutputIterator first, Size n, const T& value);
+template<class ExecutionPolicy, class ForwardIterator, class Size, class T>
+  ForwardIterator fill_n(ExecutionPolicy&& exec,
+                         ForwardIterator first, Size n, const T& value);
 ```
+*Requires:* The expression `value` shall be
+writable ([[iterator.requirements.general]]) to the output iterator.
+The type `Size` shall be convertible to an integral
 type ([[conv.integral]], [[class.conv]]).
+*Effects:* The `fill` algorithms assign `value` through all the
+iterators in the range \[`first`, `last`). The `fill_n` algorithms
+assign `value` through all the iterators in the range \[`first`,
+`first + n`) if `n` is positive, otherwise they do nothing.
 *Returns:* `fill_n` returns `first + n` for non-negative values of `n`
 and `first` for negative values.
 *Complexity:* Exactly `last - first`, `n`, or 0 assignments,
 ``` cpp
 template<class ForwardIterator, class Generator>
   void generate(ForwardIterator first, ForwardIterator last,
                 Generator gen);
+template<class ExecutionPolicy, class ForwardIterator, class Generator>
+  void generate(ExecutionPolicy&& exec,
+                ForwardIterator first, ForwardIterator last,
+                Generator gen);
 template<class OutputIterator, class Size, class Generator>
   OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
+template<class ExecutionPolicy, class ForwardIterator, class Size, class Generator>
+  ForwardIterator generate_n(ExecutionPolicy&& exec,
+                             ForwardIterator first, Size n, Generator gen);
 ```
 *Requires:* `gen` takes no arguments, `Size` shall be convertible to an
 integral type ([[conv.integral]], [[class.conv]]).
+*Effects:* The `generate` algorithms invoke the function object `gen`
+and assign the return value of `gen` through all the iterators in the
+range \[`first`, `last`). The `generate_n` algorithms invoke the
+function object `gen` and assign the return value of `gen` through all
+the iterators in the range \[`first`, `first + n`) if `n` is positive,
+otherwise they do nothing.
 *Returns:* `generate_n` returns `first + n` for non-negative values of
 `n` and `first` for negative values.
 *Complexity:* Exactly `last - first`, `n`, or 0 invocations of `gen` and
 assignments, respectively.
 ``` cpp
 template<class ForwardIterator, class T>
   ForwardIterator remove(ForwardIterator first, ForwardIterator last,
                          const T& value);
+template<class ExecutionPolicy, class ForwardIterator, class T>
+  ForwardIterator remove(ExecutionPolicy&& exec,
+                         ForwardIterator first, ForwardIterator last,
+                         const T& value);
 template<class ForwardIterator, class Predicate>
   ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
                             Predicate pred);
+template<class ExecutionPolicy, class ForwardIterator, class Predicate>
+  ForwardIterator remove_if(ExecutionPolicy&& exec,
+                            ForwardIterator first, ForwardIterator last,
+                            Predicate pred);
 ```
 *Requires:* The type of `*first` shall satisfy the `MoveAssignable`
+requirements (Table  [[tab:moveassignable]]).
 *Effects:* Eliminates all the elements referred to by iterator `i` in
 the range \[`first`, `last`) for which the following corresponding
 conditions hold: `*i == value, pred(*i) != false`.
 *Remarks:* Stable ([[algorithm.stable]]).
 *Complexity:* Exactly `last - first` applications of the corresponding
 predicate.
+[*Note 1*: Each element in the range \[`ret`, `last`), where `ret` is
+the returned value, has a valid but unspecified state, because the
 algorithms can eliminate elements by moving from elements that were
+originally in that range. — *end note*]
 ``` cpp
 template<class InputIterator, class OutputIterator, class T>
   OutputIterator
     remove_copy(InputIterator first, InputIterator last,
                 OutputIterator result, const T& value);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T>
+  ForwardIterator2
+    remove_copy(ExecutionPolicy&& exec,
+                ForwardIterator1 first, ForwardIterator1 last,
+                ForwardIterator2 result, const T& value);
 template<class InputIterator, class OutputIterator, class Predicate>
   OutputIterator
     remove_copy_if(InputIterator first, InputIterator last,
                    OutputIterator result, Predicate pred);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Predicate>
+  ForwardIterator2
+    remove_copy_if(ExecutionPolicy&& exec,
+                   ForwardIterator1 first, ForwardIterator1 last,
+                   ForwardIterator2 result, Predicate pred);
 ```
 *Requires:* The ranges \[`first`, `last`) and \[`result`,
 `result + (last - first)`) shall not overlap. The expression
 `*result = *first` shall be valid.
+[*Note 2*: For the overloads with an `ExecutionPolicy`, there may be a
+performance cost if `iterator_traits<ForwardIterator1>::value_type` is
+not `MoveConstructible`
+(Table  [[tab:moveconstructible]]). — *end note*]
 *Effects:* Copies all the elements referred to by the iterator `i` in
 the range \[`first`, `last`) for which the following corresponding
 conditions do not hold: `*i == value, pred(*i) != false`.
 *Returns:* The end of the resulting range.
 ### Unique <a id="alg.unique">[[alg.unique]]</a>
 ``` cpp
 template<class ForwardIterator>
   ForwardIterator unique(ForwardIterator first, ForwardIterator last);
+template<class ExecutionPolicy, class ForwardIterator>
+  ForwardIterator unique(ExecutionPolicy&& exec,
+                         ForwardIterator first, ForwardIterator last);
 template<class ForwardIterator, class BinaryPredicate>
   ForwardIterator unique(ForwardIterator first, ForwardIterator last,
                          BinaryPredicate pred);
+template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate>
+  ForwardIterator unique(ExecutionPolicy&& exec,
+                         ForwardIterator first, ForwardIterator last,
+                         BinaryPredicate pred);
 ```
+*Requires:* The comparison function shall be an equivalence relation.
+The type of `*first` shall satisfy the `MoveAssignable` requirements
+(Table  [[tab:moveassignable]]).
 *Effects:* For a nonempty range, eliminates all but the first element
 from every consecutive group of equivalent elements referred to by the
 iterator `i` in the range \[`first + 1`, `last`) for which the following
 conditions hold: `*(i - 1) == *i` or `pred(*(i - 1), *i) != false`.
 *Returns:* The end of the resulting range.
 *Complexity:* For nonempty ranges, exactly `(last - first) - 1`
 applications of the corresponding predicate.
 ``` cpp
 template<class InputIterator, class OutputIterator>
   OutputIterator
     unique_copy(InputIterator first, InputIterator last,
                 OutputIterator result);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
+  ForwardIterator2
+    unique_copy(ExecutionPolicy&& exec,
+                ForwardIterator1 first, ForwardIterator1 last,
+                ForwardIterator2 result);
 template<class InputIterator, class OutputIterator,
          class BinaryPredicate>
   OutputIterator
     unique_copy(InputIterator first, InputIterator last,
                 OutputIterator result, BinaryPredicate pred);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class BinaryPredicate>
+  ForwardIterator2
+    unique_copy(ExecutionPolicy&& exec,
+                ForwardIterator1 first, ForwardIterator1 last,
+                ForwardIterator2 result, BinaryPredicate pred);
 ```
+*Requires:*
+- The comparison function shall be an equivalence relation.
+- The ranges \[`first`, `last`) and \[`result`, `result+(last-first)`)
+ shall not overlap.
+- The expression `*result = *first` shall be valid.
+- For the overloads with no `ExecutionPolicy`, let `T` be the value type
+  of `InputIterator`. If `InputIterator` meets the forward iterator
+  requirements, then there are no additional requirements for `T`.
+  Otherwise, if `OutputIterator` meets the forward iterator requirements
+  and its value type is the same as `T`, then `T` shall be
+  `CopyAssignable` (Table  [[tab:copyassignable]]). Otherwise, `T` shall
+  be both `CopyConstructible` (Table  [[tab:copyconstructible]]) and
+  `CopyAssignable`. \[*Note 1*: For the overloads with an
+  `ExecutionPolicy`, there may be a performance cost if the value type
+  of `ForwardIterator1` is not both `CopyConstructible` and
+  `CopyAssignable`. — *end note*]
 *Effects:* Copies only the first element from every consecutive group of
 equal elements referred to by the iterator `i` in the range \[`first`,
 `last`) for which the following corresponding conditions hold:
 `*i == *(i - 1)` or `pred(*i, *(i - 1)) != false`.
 ### Reverse <a id="alg.reverse">[[alg.reverse]]</a>
 ``` cpp
 template<class BidirectionalIterator>
   void reverse(BidirectionalIterator first, BidirectionalIterator last);
+template<class ExecutionPolicy, class BidirectionalIterator>
+  void reverse(ExecutionPolicy&& exec,
+               BidirectionalIterator first, BidirectionalIterator last);
 ```
 *Requires:* `*first` shall be swappable ([[swappable.requirements]]).
+*Effects:* For each non-negative integer `i < (last - first) / 2`,
+applies `iter_swap` to all pairs of iterators
+`first + i, (last - i) - 1`.
+*Requires:* `BidirectionalIterator` shall satisfy the requirements of
+`ValueSwappable` ([[swappable.requirements]]).
 *Complexity:* Exactly `(last - first)/2` swaps.
 ``` cpp
 template<class BidirectionalIterator, class OutputIterator>
   OutputIterator
+    reverse_copy(BidirectionalIterator first, BidirectionalIterator last,
+                 OutputIterator result);
+template<class ExecutionPolicy, class BidirectionalIterator, class ForwardIterator>
+  ForwardIterator
+    reverse_copy(ExecutionPolicy&& exec,
+                 BidirectionalIterator first, BidirectionalIterator last,
+                 ForwardIterator result);
 ```
+*Requires:* The ranges \[`first`, `last`) and \[`result`,
+`result + (last - first)`) shall not overlap.
 *Effects:* Copies the range \[`first`, `last`) to the range \[`result`,
 `result + (last - first)`) such that for every non-negative integer
 `i < (last - first)` the following assignment takes place:
 `*(result + (last - first) - 1 - i) = *(first + i)`.
 *Returns:* `result + (last - first)`.
 *Complexity:* Exactly `last - first` assignments.
 ### Rotate <a id="alg.rotate">[[alg.rotate]]</a>
 ``` cpp
 template<class ForwardIterator>
+  ForwardIterator
+    rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
+template<class ExecutionPolicy, class ForwardIterator>
+  ForwardIterator
+    rotate(ExecutionPolicy&& exec,
+           ForwardIterator first, ForwardIterator middle, ForwardIterator last);
 ```
+*Requires:* \[`first`, `middle`) and \[`middle`, `last`) shall be valid
+ranges. `ForwardIterator` shall satisfy the requirements of
+`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
+shall satisfy the requirements of `MoveConstructible`
+(Table  [[tab:moveconstructible]]) and the requirements of
+`MoveAssignable` (Table  [[tab:moveassignable]]).
 *Effects:* For each non-negative integer `i < (last - first)`, places
 the element from the position `first + i` into position
 `first + (i + (last - middle)) % (last - first)`.
 *Returns:* `first + (last - middle)`.
 *Remarks:* This is a left rotate.
 *Complexity:* At most `last - first` swaps.
 ``` cpp
 template<class ForwardIterator, class OutputIterator>
   OutputIterator
+    rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last,
+                OutputIterator result);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
+  ForwardIterator2
+    rotate_copy(ExecutionPolicy&& exec,
+                ForwardIterator1 first, ForwardIterator1 middle, ForwardIterator1 last,
+                ForwardIterator2 result);
 ```
+*Requires:* The ranges \[`first`, `last`) and \[`result`,
+`result + (last - first)`) shall not overlap.
 *Effects:* Copies the range \[`first`, `last`) to the range \[`result`,
 `result + (last - first)`) such that for each non-negative integer
 `i < (last - first)` the following assignment takes place:
 `*(result + i) = *(first + (i + (middle - first)) % (last - first))`.
 *Returns:* `result + (last - first)`.
 *Complexity:* Exactly `last - first` assignments.
+### Sample <a id="alg.random.sample">[[alg.random.sample]]</a>
+``` cpp
+template<class PopulationIterator, class SampleIterator,
+         class Distance, class UniformRandomBitGenerator>
+  SampleIterator sample(PopulationIterator first, PopulationIterator last,
+                        SampleIterator out, Distance n,
+                        UniformRandomBitGenerator&& g);
+```
+*Requires:*
+- `PopulationIterator` shall satisfy the requirements of an input
+  iterator ([[input.iterators]]).
+- `SampleIterator` shall satisfy the requirements of an output
+  iterator ([[output.iterators]]).
+- `SampleIterator` shall satisfy the additional requirements of a random
+  access iterator ([[random.access.iterators]]) unless
+  `PopulationIterator` satisfies the additional requirements of a
+  forward iterator ([[forward.iterators]]).
+- `PopulationIterator`’s value type shall be
+  writable ([[iterator.requirements.general]]) to `out`.
+- `Distance` shall be an integer type.
+- `remove_reference_t<UniformRandomBitGenerator>` shall meet the
+  requirements of a uniform random bit generator type
+  ([[rand.req.urng]]) whose return type is convertible to `Distance`.
+- `out` shall not be in the range \[`first`, `last`).
+*Effects:* Copies `min(last - first, n)` elements (the *sample*) from
+\[`first`, `last`) (the *population*) to `out` such that each possible
+sample has equal probability of appearance.
+[*Note 1*: Algorithms that obtain such effects include *selection
+sampling* and *reservoir sampling*. — *end note*]
+*Returns:* The end of the resulting sample range.
+*Complexity:* 𝑂(`last - first`).
+*Remarks:*
+- Stable if and only if `PopulationIterator` satisfies the requirements
+  of a forward iterator.
+- To the extent that the implementation of this function makes use of
+  random numbers, the object `g` shall serve as the implementation’s
+  source of randomness.
 ### Shuffle <a id="alg.random.shuffle">[[alg.random.shuffle]]</a>
 ``` cpp
+template<class RandomAccessIterator, class UniformRandomBitGenerator>
   void shuffle(RandomAccessIterator first,
                RandomAccessIterator last,
+               UniformRandomBitGenerator&& g);
 ```
+*Requires:* `RandomAccessIterator` shall satisfy the requirements of
+`ValueSwappable` ([[swappable.requirements]]). The type
+`remove_reference_t<UniformRandomBitGenerator>` shall meet the
+requirements of a uniform random bit generator ([[rand.req.urng]]) type
+whose return type is convertible to
+`iterator_traits<RandomAccessIterator>::difference_type`.
 *Effects:* Permutes the elements in the range \[`first`, `last`) such
 that each possible permutation of those elements has equal probability
 of appearance.
 *Complexity:* Exactly `(last - first) - 1` swaps.
 *Remarks:* To the extent that the implementation of this function makes
 use of random numbers, the object `g` shall serve as the
 implementation’s source of randomness.

Diff to HTML by rtfpessoa