From Jason Turner

[alg.set.operations]

C++17 → C++20 19.9 KB 223 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/tmpnzjhuolm/{from.md → to.md} +167 -49
tmp/tmpnzjhuolm/{from.md → to.md} RENAMED
@@ -1,49 +1,72 @@
1
  ### Set operations on sorted structures <a id="alg.set.operations">[[alg.set.operations]]</a>
2
 
3
- This section defines all the basic set operations on sorted structures.
4
- They also work with `multiset`s ([[multiset]]) containing multiple
5
- copies of equivalent elements. The semantics of the set operations are
6
- generalized to `multiset`s in a standard way by defining `set_union()`
7
- to contain the maximum number of occurrences of every element,
8
- `set_intersection()` to contain the minimum, and so on.
9
 
10
  #### `includes` <a id="includes">[[includes]]</a>
11
 
12
  ``` cpp
13
  template<class InputIterator1, class InputIterator2>
14
- bool includes(InputIterator1 first1, InputIterator1 last1,
15
  InputIterator2 first2, InputIterator2 last2);
16
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
17
  bool includes(ExecutionPolicy&& exec,
18
  ForwardIterator1 first1, ForwardIterator1 last1,
19
  ForwardIterator2 first2, ForwardIterator2 last2);
20
 
21
  template<class InputIterator1, class InputIterator2, class Compare>
22
- bool includes(InputIterator1 first1, InputIterator1 last1,
23
  InputIterator2 first2, InputIterator2 last2,
24
  Compare comp);
25
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
26
  bool includes(ExecutionPolicy&& exec,
27
  ForwardIterator1 first1, ForwardIterator1 last1,
28
  ForwardIterator2 first2, ForwardIterator2 last2,
29
  Compare comp);
 
 
 
 
 
 
 
 
 
 
 
 
 
30
  ```
31
 
32
- *Returns:* `true` if \[`first2`, `last2`) is empty or if every element
33
- in the range \[`first2`, `last2`) is contained in the range \[`first1`,
34
- `last1`). Returns `false` otherwise.
 
 
 
 
 
 
 
 
 
 
35
 
36
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
37
- comparisons.
38
 
39
  #### `set_union` <a id="set.union">[[set.union]]</a>
40
 
41
  ``` cpp
42
  template<class InputIterator1, class InputIterator2,
43
  class OutputIterator>
44
- OutputIterator
45
  set_union(InputIterator1 first1, InputIterator1 last1,
46
  InputIterator2 first2, InputIterator2 last2,
47
  OutputIterator result);
48
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
49
  class ForwardIterator>
@@ -53,48 +76,71 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
53
  ForwardIterator2 first2, ForwardIterator2 last2,
54
  ForwardIterator result);
55
 
56
  template<class InputIterator1, class InputIterator2,
57
  class OutputIterator, class Compare>
58
- OutputIterator
59
  set_union(InputIterator1 first1, InputIterator1 last1,
60
  InputIterator2 first2, InputIterator2 last2,
61
  OutputIterator result, Compare comp);
62
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
63
  class ForwardIterator, class Compare>
64
  ForwardIterator
65
  set_union(ExecutionPolicy&& exec,
66
  ForwardIterator1 first1, ForwardIterator1 last1,
67
  ForwardIterator2 first2, ForwardIterator2 last2,
68
  ForwardIterator result, Compare comp);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
69
  ```
70
 
71
- *Requires:* The resulting range shall not overlap with either of the
 
 
 
 
 
72
  original ranges.
73
 
74
  *Effects:* Constructs a sorted union of the elements from the two
75
  ranges; that is, the set of elements that are present in one or both of
76
  the ranges.
77
 
78
- *Returns:* The end of the constructed range.
 
 
 
 
79
 
80
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
81
- comparisons.
82
 
83
- *Remarks:* If \[`first1`, `last1`) contains m elements that are
84
- equivalent to each other and \[`first2`, `last2`) contains n elements
85
- that are equivalent to them, then all m elements from the first range
86
- shall be copied to the output range, in order, and then max(n - m, 0)
87
- elements from the second range shall be copied to the output range, in
88
- order.
89
 
90
  #### `set_intersection` <a id="set.intersection">[[set.intersection]]</a>
91
 
92
  ``` cpp
93
  template<class InputIterator1, class InputIterator2,
94
  class OutputIterator>
95
- OutputIterator
96
  set_intersection(InputIterator1 first1, InputIterator1 last1,
97
  InputIterator2 first2, InputIterator2 last2,
98
  OutputIterator result);
99
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
100
  class ForwardIterator>
@@ -104,46 +150,69 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
104
  ForwardIterator2 first2, ForwardIterator2 last2,
105
  ForwardIterator result);
106
 
107
  template<class InputIterator1, class InputIterator2,
108
  class OutputIterator, class Compare>
109
- OutputIterator
110
  set_intersection(InputIterator1 first1, InputIterator1 last1,
111
  InputIterator2 first2, InputIterator2 last2,
112
  OutputIterator result, Compare comp);
113
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
114
  class ForwardIterator, class Compare>
115
  ForwardIterator
116
  set_intersection(ExecutionPolicy&& exec,
117
  ForwardIterator1 first1, ForwardIterator1 last1,
118
  ForwardIterator2 first2, ForwardIterator2 last2,
119
  ForwardIterator result, Compare comp);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
120
  ```
121
 
122
- *Requires:* The resulting range shall not overlap with either of the
 
 
 
 
 
123
  original ranges.
124
 
125
  *Effects:* Constructs a sorted intersection of the elements from the two
126
  ranges; that is, the set of elements that are present in both of the
127
  ranges.
128
 
129
- *Returns:* The end of the constructed range.
 
 
 
 
130
 
131
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
132
- comparisons.
133
 
134
- *Remarks:* If \[`first1`, `last1`) contains m elements that are
135
- equivalent to each other and \[`first2`, `last2`) contains n elements
136
- that are equivalent to them, the first min(m, n) elements shall be
137
- copied from the first range to the output range, in order.
138
 
139
  #### `set_difference` <a id="set.difference">[[set.difference]]</a>
140
 
141
  ``` cpp
142
  template<class InputIterator1, class InputIterator2,
143
  class OutputIterator>
144
- OutputIterator
145
  set_difference(InputIterator1 first1, InputIterator1 last1,
146
  InputIterator2 first2, InputIterator2 last2,
147
  OutputIterator result);
148
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
149
  class ForwardIterator>
@@ -153,46 +222,69 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
153
  ForwardIterator2 first2, ForwardIterator2 last2,
154
  ForwardIterator result);
155
 
156
  template<class InputIterator1, class InputIterator2,
157
  class OutputIterator, class Compare>
158
- OutputIterator
159
  set_difference(InputIterator1 first1, InputIterator1 last1,
160
  InputIterator2 first2, InputIterator2 last2,
161
  OutputIterator result, Compare comp);
162
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
163
  class ForwardIterator, class Compare>
164
  ForwardIterator
165
  set_difference(ExecutionPolicy&& exec,
166
  ForwardIterator1 first1, ForwardIterator1 last1,
167
  ForwardIterator2 first2, ForwardIterator2 last2,
168
  ForwardIterator result, Compare comp);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
169
  ```
170
 
171
- *Requires:* The resulting range shall not overlap with either of the
 
 
 
 
 
172
  original ranges.
173
 
174
  *Effects:* Copies the elements of the range \[`first1`, `last1`) which
175
  are not present in the range \[`first2`, `last2`) to the range beginning
176
  at `result`. The elements in the constructed range are sorted.
177
 
178
- *Returns:* The end of the constructed range.
 
 
 
 
179
 
180
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
181
- comparisons.
182
 
183
  *Remarks:* If \[`first1`, `last1`) contains m elements that are
184
  equivalent to each other and \[`first2`, `last2`) contains n elements
185
  that are equivalent to them, the last max(m - n, 0) elements from
186
- \[`first1`, `last1`) shall be copied to the output range.
187
 
188
  #### `set_symmetric_difference` <a id="set.symmetric.difference">[[set.symmetric.difference]]</a>
189
 
190
  ``` cpp
191
  template<class InputIterator1, class InputIterator2,
192
  class OutputIterator>
193
- OutputIterator
194
  set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
195
  InputIterator2 first2, InputIterator2 last2,
196
  OutputIterator result);
197
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
198
  class ForwardIterator>
@@ -202,39 +294,65 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
202
  ForwardIterator2 first2, ForwardIterator2 last2,
203
  ForwardIterator result);
204
 
205
  template<class InputIterator1, class InputIterator2,
206
  class OutputIterator, class Compare>
207
- OutputIterator
208
  set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
209
  InputIterator2 first2, InputIterator2 last2,
210
  OutputIterator result, Compare comp);
211
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
212
  class ForwardIterator, class Compare>
213
  ForwardIterator
214
  set_symmetric_difference(ExecutionPolicy&& exec,
215
  ForwardIterator1 first1, ForwardIterator1 last1,
216
  ForwardIterator2 first2, ForwardIterator2 last2,
217
  ForwardIterator result, Compare comp);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
218
  ```
219
 
220
- *Requires:* The resulting range shall not overlap with either of the
 
 
 
 
 
221
  original ranges.
222
 
223
  *Effects:* Copies the elements of the range \[`first1`, `last1`) that
224
  are not present in the range \[`first2`, `last2`), and the elements of
225
  the range \[`first2`, `last2`) that are not present in the range
226
  \[`first1`, `last1`) to the range beginning at `result`. The elements in
227
  the constructed range are sorted.
228
 
229
- *Returns:* The end of the constructed range.
 
 
 
 
230
 
231
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
232
- comparisons.
233
 
234
- *Remarks:* If \[`first1`, `last1`) contains m elements that are
235
- equivalent to each other and \[`first2`, `last2`) contains n elements
236
- that are equivalent to them, then |m - n| of those elements shall be
237
- copied to the output range: the last m - n of these elements from
238
- \[`first1`, `last1`) if m > n, and the last n - m of these elements from
239
- \[`first2`, `last2`) if m < n.
 
240
 
 
1
  ### Set operations on sorted structures <a id="alg.set.operations">[[alg.set.operations]]</a>
2
 
3
+ This subclause defines all the basic set operations on sorted
4
+ structures. They also work with `multiset`s [[multiset]] containing
5
+ multiple copies of equivalent elements. The semantics of the set
6
+ operations are generalized to `multiset`s in a standard way by defining
7
+ `set_union` to contain the maximum number of occurrences of every
8
+ element, `set_intersection` to contain the minimum, and so on.
9
 
10
  #### `includes` <a id="includes">[[includes]]</a>
11
 
12
  ``` cpp
13
  template<class InputIterator1, class InputIterator2>
14
+ constexpr bool includes(InputIterator1 first1, InputIterator1 last1,
15
  InputIterator2 first2, InputIterator2 last2);
16
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
17
  bool includes(ExecutionPolicy&& exec,
18
  ForwardIterator1 first1, ForwardIterator1 last1,
19
  ForwardIterator2 first2, ForwardIterator2 last2);
20
 
21
  template<class InputIterator1, class InputIterator2, class Compare>
22
+ constexpr bool includes(InputIterator1 first1, InputIterator1 last1,
23
  InputIterator2 first2, InputIterator2 last2,
24
  Compare comp);
25
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
26
  bool includes(ExecutionPolicy&& exec,
27
  ForwardIterator1 first1, ForwardIterator1 last1,
28
  ForwardIterator2 first2, ForwardIterator2 last2,
29
  Compare comp);
30
+
31
+ template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
32
+ class Proj1 = identity, class Proj2 = identity,
33
+ indirect_strict_weak_order<projected<I1, Proj1>,
34
+ projected<I2, Proj2>> Comp = ranges::less>
35
+ constexpr bool ranges::includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
36
+ Proj1 proj1 = {}, Proj2 proj2 = {});
37
+ template<input_range R1, input_range R2, class Proj1 = identity,
38
+ class Proj2 = identity,
39
+ indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
40
+ projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
41
+ constexpr bool ranges::includes(R1&& r1, R2&& r2, Comp comp = {},
42
+ Proj1 proj1 = {}, Proj2 proj2 = {});
43
  ```
44
 
45
+ Let `comp` be `less{}`, `proj1` be `identity{}`, and `proj2` be
46
+ `identity{}`, for the overloads with no parameters by those names.
47
+
48
+ *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
49
+ `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
50
+ respectively.
51
+
52
+ *Returns:* `true` if and only if \[`first2`, `last2`) is a subsequence
53
+ of \[`first1`, `last1`).
54
+
55
+ [*Note 1*: A sequence S is a subsequence of another sequence T if S can
56
+ be obtained from T by removing some, all, or none of T’s elements and
57
+ keeping the remaining elements in the same order. — *end note*]
58
 
59
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
60
+ comparisons and applications of each projection.
61
 
62
  #### `set_union` <a id="set.union">[[set.union]]</a>
63
 
64
  ``` cpp
65
  template<class InputIterator1, class InputIterator2,
66
  class OutputIterator>
67
+ constexpr OutputIterator
68
  set_union(InputIterator1 first1, InputIterator1 last1,
69
  InputIterator2 first2, InputIterator2 last2,
70
  OutputIterator result);
71
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
72
  class ForwardIterator>
 
76
  ForwardIterator2 first2, ForwardIterator2 last2,
77
  ForwardIterator result);
78
 
79
  template<class InputIterator1, class InputIterator2,
80
  class OutputIterator, class Compare>
81
+ constexpr OutputIterator
82
  set_union(InputIterator1 first1, InputIterator1 last1,
83
  InputIterator2 first2, InputIterator2 last2,
84
  OutputIterator result, Compare comp);
85
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
86
  class ForwardIterator, class Compare>
87
  ForwardIterator
88
  set_union(ExecutionPolicy&& exec,
89
  ForwardIterator1 first1, ForwardIterator1 last1,
90
  ForwardIterator2 first2, ForwardIterator2 last2,
91
  ForwardIterator result, Compare comp);
92
+
93
+ template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
94
+ weakly_incrementable O, class Comp = ranges::less,
95
+ class Proj1 = identity, class Proj2 = identity>
96
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
97
+ constexpr ranges::set_union_result<I1, I2, O>
98
+ ranges::set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
99
+ Proj1 proj1 = {}, Proj2 proj2 = {});
100
+ template<input_range R1, input_range R2, weakly_incrementable O,
101
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
102
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
103
+ constexpr ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
104
+ ranges::set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
105
+ Proj1 proj1 = {}, Proj2 proj2 = {});
106
  ```
107
 
108
+ Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
109
+ overloads with no parameters by those names.
110
+
111
+ *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
112
+ `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
113
+ respectively. The resulting range does not overlap with either of the
114
  original ranges.
115
 
116
  *Effects:* Constructs a sorted union of the elements from the two
117
  ranges; that is, the set of elements that are present in one or both of
118
  the ranges.
119
 
120
+ *Returns:* Let `result_last` be the end of the constructed range.
121
+ Returns
122
+
123
+ - `result_last` for the overloads in namespace `std`.
124
+ - `{last1, last2, result_last}` for the overloads in namespace `ranges`.
125
 
126
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
127
+ comparisons and applications of each projection.
128
 
129
+ *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
130
+ m elements that are equivalent to each other and \[`first2`, `last2`)
131
+ contains n elements that are equivalent to them, then all m elements
132
+ from the first range are copied to the output range, in order, and then
133
+ the final max(n - m, 0) elements from the second range are copied to the
134
+ output range, in order.
135
 
136
  #### `set_intersection` <a id="set.intersection">[[set.intersection]]</a>
137
 
138
  ``` cpp
139
  template<class InputIterator1, class InputIterator2,
140
  class OutputIterator>
141
+ constexpr OutputIterator
142
  set_intersection(InputIterator1 first1, InputIterator1 last1,
143
  InputIterator2 first2, InputIterator2 last2,
144
  OutputIterator result);
145
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
146
  class ForwardIterator>
 
150
  ForwardIterator2 first2, ForwardIterator2 last2,
151
  ForwardIterator result);
152
 
153
  template<class InputIterator1, class InputIterator2,
154
  class OutputIterator, class Compare>
155
+ constexpr OutputIterator
156
  set_intersection(InputIterator1 first1, InputIterator1 last1,
157
  InputIterator2 first2, InputIterator2 last2,
158
  OutputIterator result, Compare comp);
159
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
160
  class ForwardIterator, class Compare>
161
  ForwardIterator
162
  set_intersection(ExecutionPolicy&& exec,
163
  ForwardIterator1 first1, ForwardIterator1 last1,
164
  ForwardIterator2 first2, ForwardIterator2 last2,
165
  ForwardIterator result, Compare comp);
166
+
167
+ template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
168
+ weakly_incrementable O, class Comp = ranges::less,
169
+ class Proj1 = identity, class Proj2 = identity>
170
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
171
+ constexpr ranges::set_intersection_result<I1, I2, O>
172
+ ranges::set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
173
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
174
+ template<input_range R1, input_range R2, weakly_incrementable O,
175
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
176
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
177
+ constexpr ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
178
+ ranges::set_intersection(R1&& r1, R2&& r2, O result,
179
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
180
  ```
181
 
182
+ Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
183
+ overloads with no parameters by those names.
184
+
185
+ *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
186
+ `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
187
+ respectively. The resulting range does not overlap with either of the
188
  original ranges.
189
 
190
  *Effects:* Constructs a sorted intersection of the elements from the two
191
  ranges; that is, the set of elements that are present in both of the
192
  ranges.
193
 
194
+ *Returns:* Let `result_last` be the end of the constructed range.
195
+ Returns
196
+
197
+ - `result_last` for the overloads in namespace `std`.
198
+ - `{last1, last2, result_last}` for the overloads in namespace `ranges`.
199
 
200
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
201
+ comparisons and applications of each projection.
202
 
203
+ *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
204
+ m elements that are equivalent to each other and \[`first2`, `last2`)
205
+ contains n elements that are equivalent to them, the first min(m, n)
206
+ elements are copied from the first range to the output range, in order.
207
 
208
  #### `set_difference` <a id="set.difference">[[set.difference]]</a>
209
 
210
  ``` cpp
211
  template<class InputIterator1, class InputIterator2,
212
  class OutputIterator>
213
+ constexpr OutputIterator
214
  set_difference(InputIterator1 first1, InputIterator1 last1,
215
  InputIterator2 first2, InputIterator2 last2,
216
  OutputIterator result);
217
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
218
  class ForwardIterator>
 
222
  ForwardIterator2 first2, ForwardIterator2 last2,
223
  ForwardIterator result);
224
 
225
  template<class InputIterator1, class InputIterator2,
226
  class OutputIterator, class Compare>
227
+ constexpr OutputIterator
228
  set_difference(InputIterator1 first1, InputIterator1 last1,
229
  InputIterator2 first2, InputIterator2 last2,
230
  OutputIterator result, Compare comp);
231
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
232
  class ForwardIterator, class Compare>
233
  ForwardIterator
234
  set_difference(ExecutionPolicy&& exec,
235
  ForwardIterator1 first1, ForwardIterator1 last1,
236
  ForwardIterator2 first2, ForwardIterator2 last2,
237
  ForwardIterator result, Compare comp);
238
+
239
+ template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
240
+ weakly_incrementable O, class Comp = ranges::less,
241
+ class Proj1 = identity, class Proj2 = identity>
242
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
243
+ constexpr ranges::set_difference_result<I1, O>
244
+ ranges::set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
245
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
246
+ template<input_range R1, input_range R2, weakly_incrementable O,
247
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
248
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
249
+ constexpr ranges::set_difference_result<borrowed_iterator_t<R1>, O>
250
+ ranges::set_difference(R1&& r1, R2&& r2, O result,
251
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
252
  ```
253
 
254
+ Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
255
+ overloads with no parameters by those names.
256
+
257
+ *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
258
+ `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
259
+ respectively. The resulting range does not overlap with either of the
260
  original ranges.
261
 
262
  *Effects:* Copies the elements of the range \[`first1`, `last1`) which
263
  are not present in the range \[`first2`, `last2`) to the range beginning
264
  at `result`. The elements in the constructed range are sorted.
265
 
266
+ *Returns:* Let `result_last` be the end of the constructed range.
267
+ Returns
268
+
269
+ - `result_last` for the overloads in namespace `std`.
270
+ - `{last1, result_last}` for the overloads in namespace `ranges`.
271
 
272
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
273
+ comparisons and applications of each projection.
274
 
275
  *Remarks:* If \[`first1`, `last1`) contains m elements that are
276
  equivalent to each other and \[`first2`, `last2`) contains n elements
277
  that are equivalent to them, the last max(m - n, 0) elements from
278
+ \[`first1`, `last1`) is copied to the output range, in order.
279
 
280
  #### `set_symmetric_difference` <a id="set.symmetric.difference">[[set.symmetric.difference]]</a>
281
 
282
  ``` cpp
283
  template<class InputIterator1, class InputIterator2,
284
  class OutputIterator>
285
+ constexpr OutputIterator
286
  set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
287
  InputIterator2 first2, InputIterator2 last2,
288
  OutputIterator result);
289
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
290
  class ForwardIterator>
 
294
  ForwardIterator2 first2, ForwardIterator2 last2,
295
  ForwardIterator result);
296
 
297
  template<class InputIterator1, class InputIterator2,
298
  class OutputIterator, class Compare>
299
+ constexpr OutputIterator
300
  set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
301
  InputIterator2 first2, InputIterator2 last2,
302
  OutputIterator result, Compare comp);
303
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
304
  class ForwardIterator, class Compare>
305
  ForwardIterator
306
  set_symmetric_difference(ExecutionPolicy&& exec,
307
  ForwardIterator1 first1, ForwardIterator1 last1,
308
  ForwardIterator2 first2, ForwardIterator2 last2,
309
  ForwardIterator result, Compare comp);
310
+
311
+ template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
312
+ weakly_incrementable O, class Comp = ranges::less,
313
+ class Proj1 = identity, class Proj2 = identity>
314
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
315
+ constexpr ranges::set_symmetric_difference_result<I1, I2, O>
316
+ ranges::set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
317
+ Comp comp = {}, Proj1 proj1 = {},
318
+ Proj2 proj2 = {});
319
+ template<input_range R1, input_range R2, weakly_incrementable O,
320
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
321
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
322
+ constexpr ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>,
323
+ borrowed_iterator_t<R2>, O>
324
+ ranges::set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
325
+ Proj1 proj1 = {}, Proj2 proj2 = {});
326
  ```
327
 
328
+ Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
329
+ overloads with no parameters by those names.
330
+
331
+ *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
332
+ `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
333
+ respectively. The resulting range does not overlap with either of the
334
  original ranges.
335
 
336
  *Effects:* Copies the elements of the range \[`first1`, `last1`) that
337
  are not present in the range \[`first2`, `last2`), and the elements of
338
  the range \[`first2`, `last2`) that are not present in the range
339
  \[`first1`, `last1`) to the range beginning at `result`. The elements in
340
  the constructed range are sorted.
341
 
342
+ *Returns:* Let `result_last` be the end of the constructed range.
343
+ Returns
344
+
345
+ - `result_last` for the overloads in namespace `std`.
346
+ - `{last1, last2, result_last}` for the overloads in namespace `ranges`.
347
 
348
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
349
+ comparisons and applications of each projection.
350
 
351
+ *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
352
+ m elements that are equivalent to each other and \[`first2`, `last2`)
353
+ contains n elements that are equivalent to them, then |m - n| of those
354
+ elements shall be copied to the output range: the last m - n of these
355
+ elements from \[`first1`, `last1`) if m > n, and the last n - m of these
356
+ elements from \[`first2`, `last2`) if m < n. In either case, the
357
+ elements are copied in order.
358