tmp/tmp_7g662jq/{from.md → to.md}
RENAMED
|
@@ -0,0 +1,99 @@
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
+
## Algorithms requirements <a id="algorithms.requirements">[[algorithms.requirements]]</a>
|
| 2 |
+
|
| 3 |
+
All of the algorithms are separated from the particular implementations
|
| 4 |
+
of data structures and are parameterized by iterator types. Because of
|
| 5 |
+
this, they can work with program-defined data structures, as long as
|
| 6 |
+
these data structures have iterator types satisfying the assumptions on
|
| 7 |
+
the algorithms.
|
| 8 |
+
|
| 9 |
+
For purposes of determining the existence of data races, algorithms
|
| 10 |
+
shall not modify objects referenced through an iterator argument unless
|
| 11 |
+
the specification requires such modification.
|
| 12 |
+
|
| 13 |
+
Throughout this Clause, the names of template parameters are used to
|
| 14 |
+
express type requirements.
|
| 15 |
+
|
| 16 |
+
- If an algorithm’s template parameter is named `InputIterator`,
|
| 17 |
+
`InputIterator1`, or `InputIterator2`, the template argument shall
|
| 18 |
+
satisfy the requirements of an input iterator ([[input.iterators]]).
|
| 19 |
+
- If an algorithm’s template parameter is named `OutputIterator`,
|
| 20 |
+
`OutputIterator1`, or `OutputIterator2`, the template argument shall
|
| 21 |
+
satisfy the requirements of an output iterator (
|
| 22 |
+
[[output.iterators]]).
|
| 23 |
+
- If an algorithm’s template parameter is named `ForwardIterator`,
|
| 24 |
+
`ForwardIterator1`, or `ForwardIterator2`, the template argument shall
|
| 25 |
+
satisfy the requirements of a forward iterator (
|
| 26 |
+
[[forward.iterators]]).
|
| 27 |
+
- If an algorithm’s template parameter is named `BidirectionalIterator`,
|
| 28 |
+
`BidirectionalIterator1`, or `BidirectionalIterator2`, the template
|
| 29 |
+
argument shall satisfy the requirements of a bidirectional iterator (
|
| 30 |
+
[[bidirectional.iterators]]).
|
| 31 |
+
- If an algorithm’s template parameter is named `RandomAccessIterator`,
|
| 32 |
+
`RandomAccessIterator1`, or `RandomAccessIterator2`, the template
|
| 33 |
+
argument shall satisfy the requirements of a random-access iterator (
|
| 34 |
+
[[random.access.iterators]]).
|
| 35 |
+
|
| 36 |
+
If an algorithm’s *Effects:* section says that a value pointed to by any
|
| 37 |
+
iterator passed as an argument is modified, then that algorithm has an
|
| 38 |
+
additional type requirement: The type of that argument shall satisfy the
|
| 39 |
+
requirements of a mutable iterator ([[iterator.requirements]]).
|
| 40 |
+
|
| 41 |
+
[*Note 1*: This requirement does not affect arguments that are named
|
| 42 |
+
`OutputIterator`, `OutputIterator1`, or `OutputIterator2`, because
|
| 43 |
+
output iterators must always be mutable. — *end note*]
|
| 44 |
+
|
| 45 |
+
Both in-place and copying versions are provided for certain
|
| 46 |
+
algorithms.[^1] When such a version is provided for *algorithm* it is
|
| 47 |
+
called *algorithm`_copy`*. Algorithms that take predicates end with the
|
| 48 |
+
suffix `_if` (which follows the suffix `_copy`).
|
| 49 |
+
|
| 50 |
+
The `Predicate` parameter is used whenever an algorithm expects a
|
| 51 |
+
function object ([[function.objects]]) that, when applied to the result
|
| 52 |
+
of dereferencing the corresponding iterator, returns a value testable as
|
| 53 |
+
`true`. In other words, if an algorithm takes `Predicate pred` as its
|
| 54 |
+
argument and `first` as its iterator argument, it should work correctly
|
| 55 |
+
in the construct `pred(*first)` contextually converted to `bool`
|
| 56 |
+
(Clause [[conv]]). The function object `pred` shall not apply any
|
| 57 |
+
non-constant function through the dereferenced iterator.
|
| 58 |
+
|
| 59 |
+
The `BinaryPredicate` parameter is used whenever an algorithm expects a
|
| 60 |
+
function object that when applied to the result of dereferencing two
|
| 61 |
+
corresponding iterators or to dereferencing an iterator and type `T`
|
| 62 |
+
when `T` is part of the signature returns a value testable as `true`. In
|
| 63 |
+
other words, if an algorithm takes `BinaryPredicate binary_pred` as its
|
| 64 |
+
argument and `first1` and `first2` as its iterator arguments, it should
|
| 65 |
+
work correctly in the construct `binary_pred(*first1, *first2)`
|
| 66 |
+
contextually converted to `bool` (Clause [[conv]]). `BinaryPredicate`
|
| 67 |
+
always takes the first iterator’s `value_type` as its first argument,
|
| 68 |
+
that is, in those cases when `T value` is part of the signature, it
|
| 69 |
+
should work correctly in the construct `binary_pred(*first1, value)`
|
| 70 |
+
contextually converted to `bool` (Clause [[conv]]). `binary_pred` shall
|
| 71 |
+
not apply any non-constant function through the dereferenced iterators.
|
| 72 |
+
|
| 73 |
+
[*Note 2*: Unless otherwise specified, algorithms that take function
|
| 74 |
+
objects as arguments are permitted to copy those function objects
|
| 75 |
+
freely. Programmers for whom object identity is important should
|
| 76 |
+
consider using a wrapper class that points to a noncopied implementation
|
| 77 |
+
object such as `reference_wrapper<T>` ([[refwrap]]), or some equivalent
|
| 78 |
+
solution. — *end note*]
|
| 79 |
+
|
| 80 |
+
When the description of an algorithm gives an expression such as
|
| 81 |
+
`*first == value` for a condition, the expression shall evaluate to
|
| 82 |
+
either `true` or `false` in boolean contexts.
|
| 83 |
+
|
| 84 |
+
In the description of the algorithms operators `+` and `-` are used for
|
| 85 |
+
some of the iterator categories for which they do not have to be
|
| 86 |
+
defined. In these cases the semantics of `a+n` is the same as that of
|
| 87 |
+
|
| 88 |
+
``` cpp
|
| 89 |
+
X tmp = a;
|
| 90 |
+
advance(tmp, n);
|
| 91 |
+
return tmp;
|
| 92 |
+
```
|
| 93 |
+
|
| 94 |
+
and that of `b-a` is the same as of
|
| 95 |
+
|
| 96 |
+
``` cpp
|
| 97 |
+
return distance(a, b);
|
| 98 |
+
```
|
| 99 |
+
|