From Jason Turner

[alg.remove]

C++23 → Trunk 10.9 KB 122 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpzoztnrdj/{from.md → to.md} +95 -21
tmp/tmpzoztnrdj/{from.md → to.md} RENAMED
@@ -1,12 +1,13 @@
1
  ### Remove <a id="alg.remove">[[alg.remove]]</a>
2
 
3
  ``` cpp
4
- template<class ForwardIterator, class T>
5
  constexpr ForwardIterator remove(ForwardIterator first, ForwardIterator last,
6
  const T& value);
7
- template<class ExecutionPolicy, class ForwardIterator, class T>
 
8
  ForwardIterator remove(ExecutionPolicy&& exec,
9
  ForwardIterator first, ForwardIterator last,
10
  const T& value);
11
 
12
  template<class ForwardIterator, class Predicate>
@@ -15,26 +16,52 @@ template<class ForwardIterator, class Predicate>
15
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
16
  ForwardIterator remove_if(ExecutionPolicy&& exec,
17
  ForwardIterator first, ForwardIterator last,
18
  Predicate pred);
19
 
20
- template<permutable I, sentinel_for<I> S, class T, class Proj = identity>
 
21
  requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
22
  constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {});
23
- template<forward_range R, class T, class Proj = identity>
 
24
  requires permutable<iterator_t<R>> &&
25
  indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
26
  constexpr borrowed_subrange_t<R>
27
  ranges::remove(R&& r, const T& value, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
28
  template<permutable I, sentinel_for<I> S, class Proj = identity,
29
  indirect_unary_predicate<projected<I, Proj>> Pred>
30
  constexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {});
31
  template<forward_range R, class Proj = identity,
32
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
33
  requires permutable<iterator_t<R>>
34
  constexpr borrowed_subrange_t<R>
35
  ranges::remove_if(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
36
  ```
37
 
38
  Let E be
39
 
40
  - `bool(*i == value)` for `remove`;
@@ -63,16 +90,17 @@ predicate and any projection.
63
  the returned value, has a valid but unspecified state, because the
64
  algorithms can eliminate elements by moving from elements that were
65
  originally in that range. — *end note*]
66
 
67
  ``` cpp
68
- template<class InputIterator, class OutputIterator, class T>
 
69
  constexpr OutputIterator
70
  remove_copy(InputIterator first, InputIterator last,
71
  OutputIterator result, const T& value);
72
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
73
- class T>
74
  ForwardIterator2
75
  remove_copy(ExecutionPolicy&& exec,
76
  ForwardIterator1 first, ForwardIterator1 last,
77
  ForwardIterator2 result, const T& value);
78
 
@@ -85,62 +113,108 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
85
  ForwardIterator2
86
  remove_copy_if(ExecutionPolicy&& exec,
87
  ForwardIterator1 first, ForwardIterator1 last,
88
  ForwardIterator2 result, Predicate pred);
89
 
90
- template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class T,
91
- class Proj = identity>
92
  requires indirectly_copyable<I, O> &&
93
  indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
94
  constexpr ranges::remove_copy_result<I, O>
95
  ranges::remove_copy(I first, S last, O result, const T& value, Proj proj = {});
96
- template<input_range R, weakly_incrementable O, class T, class Proj = identity>
 
97
  requires indirectly_copyable<iterator_t<R>, O> &&
98
  indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
99
  constexpr ranges::remove_copy_result<borrowed_iterator_t<R>, O>
100
  ranges::remove_copy(R&& r, O result, const T& value, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
101
  template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
102
  class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
103
  requires indirectly_copyable<I, O>
104
  constexpr ranges::remove_copy_if_result<I, O>
105
  ranges::remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {});
106
  template<input_range R, weakly_incrementable O, class Proj = identity,
107
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
108
  requires indirectly_copyable<iterator_t<R>, O>
109
  constexpr ranges::remove_copy_if_result<borrowed_iterator_t<R>, O>
110
  ranges::remove_copy_if(R&& r, O result, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
111
  ```
112
 
113
- Let E be
114
 
115
  - `bool(*i == value)` for `remove_copy`;
116
  - `bool(pred(*i))` for `remove_copy_if`;
117
  - `bool(invoke(proj, *i) == value)` for `ranges::remove_copy`;
118
  - `bool(invoke(pred, invoke(proj, *i)))` for `ranges::remove_copy_if`.
119
 
120
- Let N be the number of elements in \[`first`, `last`) for which E is
121
- `false`.
 
 
 
 
 
122
 
123
  *Mandates:* `*first` is writable [[iterator.requirements.general]] to
124
  `result`.
125
 
126
  *Preconditions:* The ranges \[`first`, `last`) and \[`result`,
127
- `result + (last - first)`) do not overlap.
128
 
129
- [*Note 2*: For the overloads with an `ExecutionPolicy`, there might be
130
- a performance cost if `iterator_traits<ForwardIterator1>::value_type`
131
- does not meet the *Cpp17MoveConstructible*
132
- ([[cpp17.moveconstructible]]) requirements. — *end note*]
 
 
 
133
 
134
- *Effects:* Copies all the elements referred to by the iterator `i` in
135
- the range \[`first`, `last`) for which E is `false`.
 
136
 
137
  *Returns:*
138
 
139
  - `result + `N, for the algorithms in namespace `std`.
140
- - `{last, result + `N`}`, for the algorithms in namespace `ranges`.
 
 
 
 
 
141
 
142
- *Complexity:* Exactly `last - first` applications of the corresponding
143
  predicate and any projection.
144
 
145
  *Remarks:* Stable [[algorithm.stable]].
146
 
 
1
  ### Remove <a id="alg.remove">[[alg.remove]]</a>
2
 
3
  ``` cpp
4
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
5
  constexpr ForwardIterator remove(ForwardIterator first, ForwardIterator last,
6
  const T& value);
7
+ template<class ExecutionPolicy, class ForwardIterator,
8
+ class T = iterator_traits<ForwardIterator>::value_type>
9
  ForwardIterator remove(ExecutionPolicy&& exec,
10
  ForwardIterator first, ForwardIterator last,
11
  const T& value);
12
 
13
  template<class ForwardIterator, class Predicate>
 
16
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
17
  ForwardIterator remove_if(ExecutionPolicy&& exec,
18
  ForwardIterator first, ForwardIterator last,
19
  Predicate pred);
20
 
21
+ template<permutable I, sentinel_for<I> S, class Proj = identity,
22
+ class T = projected_value_t<I, Proj>>
23
  requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
24
  constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {});
25
+ template<forward_range R, class Proj = identity,
26
+ class T = projected_value_t<iterator_t<R>, Proj>>
27
  requires permutable<iterator_t<R>> &&
28
  indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
29
  constexpr borrowed_subrange_t<R>
30
  ranges::remove(R&& r, const T& value, Proj proj = {});
31
+
32
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
33
+ class Proj = identity, class T = projected_value_t<I, Proj>>
34
+ requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
35
+ subrange<I>
36
+ ranges::remove(Ep&& exec, I first, S last, const T& value, Proj proj = {});
37
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
38
+ class T = projected_value_t<iterator_t<R>, Proj>>
39
+ requires permutable<iterator_t<R>> &&
40
+ indirect_binary_predicate<ranges::equal_to,
41
+ projected<iterator_t<R>, Proj>, const T*>
42
+ borrowed_subrange_t<R>
43
+ ranges::remove(Ep&& exec, R&& r, const T& value, Proj proj = {});
44
+
45
  template<permutable I, sentinel_for<I> S, class Proj = identity,
46
  indirect_unary_predicate<projected<I, Proj>> Pred>
47
  constexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {});
48
  template<forward_range R, class Proj = identity,
49
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
50
  requires permutable<iterator_t<R>>
51
  constexpr borrowed_subrange_t<R>
52
  ranges::remove_if(R&& r, Pred pred, Proj proj = {});
53
+
54
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
55
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
56
+ subrange<I>
57
+ ranges::remove_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
58
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
59
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
60
+ requires permutable<iterator_t<R>>
61
+ borrowed_subrange_t<R>
62
+ ranges::remove_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
63
  ```
64
 
65
  Let E be
66
 
67
  - `bool(*i == value)` for `remove`;
 
90
  the returned value, has a valid but unspecified state, because the
91
  algorithms can eliminate elements by moving from elements that were
92
  originally in that range. — *end note*]
93
 
94
  ``` cpp
95
+ template<class InputIterator, class OutputIterator,
96
+ class T = iterator_traits<InputIterator>::value_type>
97
  constexpr OutputIterator
98
  remove_copy(InputIterator first, InputIterator last,
99
  OutputIterator result, const T& value);
100
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
101
+ class T = iterator_traits<ForwardIterator1>::value_type>
102
  ForwardIterator2
103
  remove_copy(ExecutionPolicy&& exec,
104
  ForwardIterator1 first, ForwardIterator1 last,
105
  ForwardIterator2 result, const T& value);
106
 
 
113
  ForwardIterator2
114
  remove_copy_if(ExecutionPolicy&& exec,
115
  ForwardIterator1 first, ForwardIterator1 last,
116
  ForwardIterator2 result, Predicate pred);
117
 
118
+ template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
119
+ class Proj = identity, class T = projected_value_t<I, Proj>>
120
  requires indirectly_copyable<I, O> &&
121
  indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
122
  constexpr ranges::remove_copy_result<I, O>
123
  ranges::remove_copy(I first, S last, O result, const T& value, Proj proj = {});
124
+ template<input_range R, weakly_incrementable O, class Proj = identity,
125
+ class T = projected_value_t<iterator_t<R>, Proj>>
126
  requires indirectly_copyable<iterator_t<R>, O> &&
127
  indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
128
  constexpr ranges::remove_copy_result<borrowed_iterator_t<R>, O>
129
  ranges::remove_copy(R&& r, O result, const T& value, Proj proj = {});
130
+
131
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
132
+ random_access_iterator O, sized_sentinel_for<O> OutS,
133
+ class Proj = identity, class T = projected_value_t<I, Proj>>
134
+ requires indirectly_copyable<I, O> &&
135
+ indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
136
+ ranges::remove_copy_result<I, O>
137
+ ranges::remove_copy(Ep&& exec, I first, S last, O result, OutS result_last,
138
+ const T& value, Proj proj = {});
139
+ template<execution-policy Ep, sized-random-access-range R, sized-random-access-range OutR,
140
+ class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
141
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>> &&
142
+ indirect_binary_predicate<ranges::equal_to,
143
+ projected<iterator_t<R>, Proj>, const T*>
144
+ ranges::remove_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
145
+ ranges::remove_copy(Ep&& exec, R&& r, OutR&& result_r, const T& value, Proj proj = {});
146
+
147
  template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
148
  class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
149
  requires indirectly_copyable<I, O>
150
  constexpr ranges::remove_copy_if_result<I, O>
151
  ranges::remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {});
152
  template<input_range R, weakly_incrementable O, class Proj = identity,
153
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
154
  requires indirectly_copyable<iterator_t<R>, O>
155
  constexpr ranges::remove_copy_if_result<borrowed_iterator_t<R>, O>
156
  ranges::remove_copy_if(R&& r, O result, Pred pred, Proj proj = {});
157
+
158
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
159
+ random_access_iterator O, sized_sentinel_for<O> OutS,
160
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
161
+ requires indirectly_copyable<I, O>
162
+ ranges::remove_copy_if_result<I, O>
163
+ ranges::remove_copy_if(Ep&& exec, I first, S last, O result, OutS result_last,
164
+ Pred pred, Proj proj = {});
165
+ template<execution-policy Ep, sized-random-access-range R, sized-random-access-range OutR,
166
+ class Proj = identity,
167
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
168
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
169
+ ranges::remove_copy_if_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
170
+ ranges::remove_copy_if(Ep&& exec, R&& r, OutR&& result_r, Pred pred, Proj proj = {});
171
  ```
172
 
173
+ Let E(`i`) be
174
 
175
  - `bool(*i == value)` for `remove_copy`;
176
  - `bool(pred(*i))` for `remove_copy_if`;
177
  - `bool(invoke(proj, *i) == value)` for `ranges::remove_copy`;
178
  - `bool(invoke(pred, invoke(proj, *i)))` for `ranges::remove_copy_if`.
179
 
180
+ Let:
181
+
182
+ - M be the number of iterators `i` in \[`first`, `last`) for which
183
+ E(`i`) is `false`;
184
+ - `result_last` be `result + `M for the overloads with no parameter
185
+ `result_last` or `result_r`;
186
+ - N be min(M, `result_last - result`).
187
 
188
  *Mandates:* `*first` is writable [[iterator.requirements.general]] to
189
  `result`.
190
 
191
  *Preconditions:* The ranges \[`first`, `last`) and \[`result`,
192
+ `result + `N) do not overlap.
193
 
194
+ [*Note 2*: For the parallel algorithm overloads in namespace `std`,
195
+ there can be a performance cost if
196
+ `iterator_traits<ForwardIterator1>::value_type` does not meet the
197
+ *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) requirements.
198
+ For the parallel algorithm overloads in namespace `ranges`, there can be
199
+ a performance cost if `iter_value_t<I>` does not model
200
+ `move_constructible`. — *end note*]
201
 
202
+ *Effects:* Copies the first N elements referred to by the iterator `i`
203
+ in the range \[`first`, `last`) for which E(`i`) is `false` into the
204
+ range \[`result`, `result + `N).
205
 
206
  *Returns:*
207
 
208
  - `result + `N, for the algorithms in namespace `std`.
209
+ - `{last, result + `N`}`, for the algorithms in namespace `ranges`, if N
210
+ is equal to M.
211
+ - Otherwise, `{j, result_last}`, for the algorithms in namespace
212
+ `ranges`, where `j` is the iterator in \[`first`, `last`) for which
213
+ E(`j`) is `false` and there are exactly N iterators `i` in \[`first`,
214
+ `j`) for which E(`i`) is `false`.
215
 
216
+ *Complexity:* At most `last - first` applications of the corresponding
217
  predicate and any projection.
218
 
219
  *Remarks:* Stable [[algorithm.stable]].
220