From Jason Turner

[algorithms.requirements]

C++17 → C++20 11.4 KB 178 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp0q1o3r5v/{from.md → to.md} +126 -49
tmp/tmp0q1o3r5v/{from.md → to.md} RENAMED
@@ -4,96 +4,173 @@ 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
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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
+ The entities defined in the `std::ranges` namespace in this Clause are
10
+ not found by argument-dependent name lookup [[basic.lookup.argdep]].
11
+ When found by unqualified [[basic.lookup.unqual]] name lookup for the
12
+ *postfix-expression* in a function call [[expr.call]], they inhibit
13
+ argument-dependent name lookup.
14
+
15
+ [*Example 1*:
16
+
17
+ ``` cpp
18
+ void foo() {
19
+ using namespace std::ranges;
20
+ std::vector<int> vec{1,2,3};
21
+ find(begin(vec), end(vec), 2); // #1
22
+ }
23
+ ```
24
+
25
+ The function call expression at `#1` invokes `std::ranges::find`, not
26
+ `std::find`, despite that (a) the iterator type returned from
27
+ `begin(vec)` and `end(vec)` may be associated with namespace `std` and
28
+ (b) `std::find` is more specialized [[temp.func.order]] than
29
+ `std::ranges::find` since the former requires its first two parameters
30
+ to have the same type.
31
+
32
+ — *end example*]
33
+
34
  For purposes of determining the existence of data races, algorithms
35
  shall not modify objects referenced through an iterator argument unless
36
  the specification requires such modification.
37
 
38
+ Throughout this Clause, where the template parameters are not
39
+ constrained, the names of template parameters are used to express type
40
+ requirements.
41
 
42
  - If an algorithm’s template parameter is named `InputIterator`,
43
  `InputIterator1`, or `InputIterator2`, the template argument shall
44
+ meet the *Cpp17InputIterator* requirements [[input.iterators]].
45
  - If an algorithm’s template parameter is named `OutputIterator`,
46
  `OutputIterator1`, or `OutputIterator2`, the template argument shall
47
+ meet the *Cpp17OutputIterator* requirements [[output.iterators]].
 
48
  - If an algorithm’s template parameter is named `ForwardIterator`,
49
  `ForwardIterator1`, or `ForwardIterator2`, the template argument shall
50
+ meet the *Cpp17ForwardIterator* requirements [[forward.iterators]].
51
+ - If an algorithm’s template parameter is named
52
+ `NoThrowForwardIterator`, the template argument shall meet the
53
+ *Cpp17ForwardIterator* requirements [[forward.iterators]], and is
54
+ required to have the property that no exceptions are thrown from
55
+ increment, assignment, or comparison of, or indirection through, valid
56
+ iterators.
57
  - If an algorithm’s template parameter is named `BidirectionalIterator`,
58
  `BidirectionalIterator1`, or `BidirectionalIterator2`, the template
59
+ argument shall meet the *Cpp17BidirectionalIterator* requirements
60
+ [[bidirectional.iterators]].
61
  - If an algorithm’s template parameter is named `RandomAccessIterator`,
62
  `RandomAccessIterator1`, or `RandomAccessIterator2`, the template
63
+ argument shall meet the *Cpp17RandomAccessIterator* requirements
64
+ [[random.access.iterators]].
65
 
66
+ If an algorithm’s *Effects:* element specifies that a value pointed to
67
+ by any iterator passed as an argument is modified, then that algorithm
68
+ has an additional type requirement: The type of that argument shall meet
69
+ the requirements of a mutable iterator [[iterator.requirements]].
70
 
71
  [*Note 1*: This requirement does not affect arguments that are named
72
  `OutputIterator`, `OutputIterator1`, or `OutputIterator2`, because
73
+ output iterators must always be mutable, nor does it affect arguments
74
+ that are constrained, for which mutability requirements are expressed
75
+ explicitly. — *end note*]
76
 
77
+ Both in-place and copying versions are provided for certain algorithms.
78
+ [^1] When such a version is provided for *algorithm* it is called
79
+ *algorithm`_copy`*. Algorithms that take predicates end with the suffix
80
+ `_if` (which follows the suffix `_copy`).
81
 
82
+ When not otherwise constrained, the `Predicate` parameter is used
83
+ whenever an algorithm expects a function object [[function.objects]]
84
+ that, when applied to the result of dereferencing the corresponding
85
+ iterator, returns a value testable as `true`. In other words, if an
86
+ algorithm takes `Predicate pred` as its argument and `first` as its
87
+ iterator argument with value type `T`, it should work correctly in the
88
+ construct `pred(*first)` contextually converted to `bool` [[conv]]. The
89
+ function object `pred` shall not apply any non-constant function through
90
+ the dereferenced iterator. Given a glvalue `u` of type (possibly
91
+ `const`) `T` that designates the same object as `*first`, `pred(u)`
92
+ shall be a valid expression that is equal to `pred(*first)`.
93
 
94
+ When not otherwise constrained, the `BinaryPredicate` parameter is used
95
+ whenever an algorithm expects a function object that when applied to the
96
+ result of dereferencing two corresponding iterators or to dereferencing
97
+ an iterator and type `T` when `T` is part of the signature returns a
98
+ value testable as `true`. In other words, if an algorithm takes
99
+ `BinaryPredicate binary_pred` as its argument and `first1` and `first2`
100
+ as its iterator arguments with respective value types `T1` and `T2`, it
101
+ should work correctly in the construct `binary_pred(*first1, *first2)`
102
+ contextually converted to `bool` [[conv]]. Unless otherwise specified,
103
+ `BinaryPredicate` always takes the first iterator’s `value_type` as its
104
+ first argument, that is, in those cases when `T value` is part of the
105
+ signature, it should work correctly in the construct
106
+ `binary_pred(*first1, value)` contextually converted to `bool` [[conv]].
107
+ `binary_pred` shall not apply any non-constant function through the
108
+ dereferenced iterators. Given a glvalue `u` of type (possibly `const`)
109
+ `T1` that designates the same object as `*first1`, and a glvalue `v` of
110
+ type (possibly `const`) `T2` that designates the same object as
111
+ `*first2`, `binary_pred(u, *first2)`, `binary_pred(*first1, v)`, and
112
+ `binary_pred(u, v)` shall each be a valid expression that is equal to
113
+ `binary_pred(*first1, *first2)`, and `binary_pred(u, value)` shall be a
114
+ valid expression that is equal to `binary_pred(*first1, value)`.
115
+
116
+ The parameters `UnaryOperation`, `BinaryOperation`, `BinaryOperation1`,
117
+ and `BinaryOperation2` are used whenever an algorithm expects a function
118
+ object [[function.objects]].
119
 
120
  [*Note 2*: Unless otherwise specified, algorithms that take function
121
  objects as arguments are permitted to copy those function objects
122
  freely. Programmers for whom object identity is important should
123
  consider using a wrapper class that points to a noncopied implementation
124
+ object such as `reference_wrapper<T>` [[refwrap]], or some equivalent
125
  solution. — *end note*]
126
 
127
  When the description of an algorithm gives an expression such as
128
  `*first == value` for a condition, the expression shall evaluate to
129
  either `true` or `false` in boolean contexts.
130
 
131
+ In the description of the algorithms, operator `+` is used for some of
132
+ the iterator categories for which it does not have to be defined. In
133
+ these cases the semantics of `a + n` are the same as those of
134
 
135
  ``` cpp
136
+ auto tmp = a;
137
+ for (; n < 0; ++n) --tmp;
138
+ for (; n > 0; --n) ++tmp;
139
  return tmp;
140
  ```
141
 
142
+ Similarly, operator `-` is used for some combinations of iterators and
143
+ sentinel types for which it does not have to be defined. If \[`a`, `b`)
144
+ denotes a range, the semantics of `b - a` in these cases are the same as
145
+ those of
146
 
147
  ``` cpp
148
+ iter_difference_t<decltype(a)> n = 0;
149
+ for (auto tmp = a; tmp != b; ++tmp) ++n;
150
+ return n;
151
  ```
152
 
153
+ and if \[`b`, `a`) denotes a range, the same as those of
154
+
155
+ ``` cpp
156
+ iter_difference_t<decltype(b)> n = 0;
157
+ for (auto tmp = b; tmp != a; ++tmp) --n;
158
+ return n;
159
+ ```
160
+
161
+ In the description of algorithm return values, a sentinel value `s`
162
+ denoting the end of a range \[`i`, `s`) is sometimes returned where an
163
+ iterator is expected. In these cases, the semantics are as if the
164
+ sentinel is converted into an iterator using `ranges::next(i, s)`.
165
+
166
+ Overloads of algorithms that take `range` arguments [[range.range]]
167
+ behave as if they are implemented by calling `ranges::begin` and
168
+ `ranges::end` on the `range`(s) and dispatching to the overload in
169
+ namespace `ranges` that takes separate iterator and sentinel arguments.
170
+
171
+ The number and order of deducible template parameters for algorithm
172
+ declarations are unspecified, except where explicitly stated otherwise.
173
+
174
+ [*Note 3*: Consequently, the algorithms may not be called with
175
+ explicitly-specified template argument lists. — *end note*]
176
+