From Jason Turner

[algorithms.requirements]

C++20 → C++23 10.5 KB 120 lines
Current Draft | LaTeX Source
Archived: C++20 | C++23
Markdown: C++20 | C++23
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpsmei1p_d/{from.md → to.md} +63 -53
tmp/tmpsmei1p_d/{from.md → to.md} RENAMED
@@ -37,94 +37,98 @@ 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
 
@@ -156,21 +160,27 @@ and if \[`b`, `a`) denotes a range, the same as those of
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
 
 
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 *Effects* element specifies that a value pointed to
43
+ by any iterator passed as an argument is modified, then the type of
44
+ that argument shall meet the requirements of a mutable iterator
45
+ [[iterator.requirements]].
46
  - If an algorithm’s template parameter is named `InputIterator`,
47
  `InputIterator1`, or `InputIterator2`, the template argument shall
48
  meet the *Cpp17InputIterator* requirements [[input.iterators]].
49
  - If an algorithm’s template parameter is named `OutputIterator`,
50
  `OutputIterator1`, or `OutputIterator2`, the template argument shall
51
  meet the *Cpp17OutputIterator* requirements [[output.iterators]].
52
  - If an algorithm’s template parameter is named `ForwardIterator`,
53
+ `ForwardIterator1`, `ForwardIterator2`, or `NoThrowForwardIterator`,
54
+ the template argument shall meet the *Cpp17ForwardIterator*
55
+ requirements [[forward.iterators]] if it is required to be a mutable
56
+ iterator, or model `forward_iterator` [[iterator.concept.forward]]
57
+ otherwise.
58
  - If an algorithm’s template parameter is named
59
+ `NoThrowForwardIterator`, the template argument is also required to
60
+ have the property that no exceptions are thrown from increment,
61
+ assignment, or comparison of, or indirection through, valid iterators.
 
 
62
  - If an algorithm’s template parameter is named `BidirectionalIterator`,
63
  `BidirectionalIterator1`, or `BidirectionalIterator2`, the template
64
  argument shall meet the *Cpp17BidirectionalIterator* requirements
65
+ [[bidirectional.iterators]] if it is required to be a mutable
66
+ iterator, or model `bidirectional_iterator` [[iterator.concept.bidir]]
67
+ otherwise.
68
  - If an algorithm’s template parameter is named `RandomAccessIterator`,
69
  `RandomAccessIterator1`, or `RandomAccessIterator2`, the template
70
  argument shall meet the *Cpp17RandomAccessIterator* requirements
71
+ [[random.access.iterators]] if it is required to be a mutable
72
+ iterator, or model `random_access_iterator`
73
+ [[iterator.concept.random.access]] otherwise.
74
 
75
+ [*Note 1*: These requirements do not affect iterator arguments that are
76
+ constrained, for which iterator category and mutability requirements are
77
+ expressed explicitly. — *end note*]
 
78
 
79
+ Both in-place and copying versions are provided for certain
80
+ algorithms.[^1]
 
 
 
81
 
82
+ When such a version is provided for *algorithm* it is called
 
83
  *algorithm`_copy`*. Algorithms that take predicates end with the suffix
84
  `_if` (which follows the suffix `_copy`).
85
 
86
  When not otherwise constrained, the `Predicate` parameter is used
87
  whenever an algorithm expects a function object [[function.objects]]
88
  that, when applied to the result of dereferencing the corresponding
89
+ iterator, returns a value testable as `true`. If an algorithm takes
90
+ `Predicate pred` as its argument and `first` as its iterator argument
91
+ with value type `T`, the expression `pred(*first)` shall be well-formed
92
+ and the type `decltype(pred(*first))` shall model `boolean-testable`
93
+ [[concept.booleantestable]]. The function object `pred` shall not apply
94
+ any non-constant function through its argument. Given a glvalue `u` of
95
+ type (possibly const) `T` that designates the same object as `*first`,
96
+ `pred(u)` shall be a valid expression that is equal to `pred(*first)`.
97
 
98
  When not otherwise constrained, the `BinaryPredicate` parameter is used
99
+ whenever an algorithm expects a function object that, when applied to
100
+ the result of dereferencing two corresponding iterators or to
101
+ dereferencing an iterator and type `T` when `T` is part of the
102
+ signature, returns a value testable as `true`. If an algorithm takes
103
  `BinaryPredicate binary_pred` as its argument and `first1` and `first2`
104
+ as its iterator arguments with respective value types `T1` and `T2`, the
105
+ expression `binary_pred(*first1, *first2)` shall be well-formed and the
106
+ type `decltype(binary_pred(*first1, *first2))` shall model
107
+ `boolean-testable`. Unless otherwise specified, `BinaryPredicate` always
108
+ takes the first iterator’s `value_type` as its first argument, that is,
109
+ in those cases when `T value` is part of the signature, the expression
110
+ `binary_pred(*first1, value)` shall be well-formed and the type
111
+ `decltype(binary_pred(*first1, value))` shall model `boolean-testable`.
112
+ `binary_pred` shall not apply any non-constant function through any of
113
+ its arguments. Given a glvalue `u` of type (possibly const) `T1` that
114
+ designates the same object as `*first1`, and a glvalue `v` of type
115
+ (possibly const) `T2` that designates the same object as `*first2`,
116
+ `binary_pred(u, *first2)`, `binary_pred(*first1, v)`, and
117
  `binary_pred(u, v)` shall each be a valid expression that is equal to
118
  `binary_pred(*first1, *first2)`, and `binary_pred(u, value)` shall be a
119
  valid expression that is equal to `binary_pred(*first1, value)`.
120
 
121
  The parameters `UnaryOperation`, `BinaryOperation`, `BinaryOperation1`,
122
  and `BinaryOperation2` are used whenever an algorithm expects a function
123
  object [[function.objects]].
124
 
125
  [*Note 2*: Unless otherwise specified, algorithms that take function
126
+ objects as arguments can copy those function objects freely. If object
127
+ identity is important, a wrapper class that points to a non-copied
128
+ implementation object such as `reference_wrapper<T>` [[refwrap]], or
129
+ some equivalent solution, can be used. — *end note*]
 
130
 
131
  When the description of an algorithm gives an expression such as
132
  `*first == value` for a condition, the expression shall evaluate to
133
  either `true` or `false` in boolean contexts.
134
 
 
160
  iter_difference_t<decltype(b)> n = 0;
161
  for (auto tmp = b; tmp != a; ++tmp) --n;
162
  return n;
163
  ```
164
 
165
+ In the description of the algorithms, given an iterator `a` whose
166
+ difference type is `D`, and an expression `n` of integer-like type other
167
+ than cv `D`, the semantics of `a + n` and `a - n` are, respectively,
168
+ those of `a + D(n)` and `a - D(n)`.
169
+
170
  In the description of algorithm return values, a sentinel value `s`
171
  denoting the end of a range \[`i`, `s`) is sometimes returned where an
172
  iterator is expected. In these cases, the semantics are as if the
173
  sentinel is converted into an iterator using `ranges::next(i, s)`.
174
 
175
  Overloads of algorithms that take `range` arguments [[range.range]]
176
  behave as if they are implemented by calling `ranges::begin` and
177
  `ranges::end` on the `range`(s) and dispatching to the overload in
178
  namespace `ranges` that takes separate iterator and sentinel arguments.
179
 
180
+ The well-formedness and behavior of a call to an algorithm with an
181
+ explicitly-specified template argument list is unspecified, except where
182
+ explicitly stated otherwise.
183
 
184
+ [*Note 3*: Consequently, an implementation can declare an algorithm
185
+ with different template parameters than those presented. — *end note*]
186