Horizon
Loading...
Searching...
No Matches
set_algorithm.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2014-present
5//
6// Use, modification and distribution is subject to the
7// Boost Software License, Version 1.0. (See accompanying
8// file LICENSE_1_0.txt or copy at
9// http://www.boost.org/LICENSE_1_0.txt)
10//
11// Project home: https://github.com/ericniebler/range-v3
12//
13//===----------------------------------------------------------------------===//
14//
15// The LLVM Compiler Infrastructure
16//
17// This file is dual licensed under the MIT and the University of Illinois Open
18// Source Licenses. See LICENSE.TXT for details.
19//
20//===----------------------------------------------------------------------===//
21#ifndef RANGES_V3_ALGORITHM_SET_ALGORITHM_HPP
22#define RANGES_V3_ALGORITHM_SET_ALGORITHM_HPP
23
24#include <utility>
25
26#include <range/v3/range_fwd.hpp>
27
28#include <range/v3/algorithm/copy.hpp>
29#include <range/v3/algorithm/result_types.hpp>
30#include <range/v3/functional/comparisons.hpp>
31#include <range/v3/functional/identity.hpp>
32#include <range/v3/functional/invoke.hpp>
33#include <range/v3/iterator/concepts.hpp>
34#include <range/v3/iterator/traits.hpp>
35#include <range/v3/range/access.hpp>
36#include <range/v3/range/concepts.hpp>
37#include <range/v3/range/dangling.hpp>
38#include <range/v3/range/traits.hpp>
39#include <range/v3/utility/static_const.hpp>
40
41#include <range/v3/detail/prologue.hpp>
42
43namespace ranges
44{
47 RANGES_FUNC_BEGIN(includes)
48
49
50 template(typename I1,
51 typename S1,
52 typename I2,
53 typename S2,
54 typename C = less,
55 typename P1 = identity,
56 typename P2 = identity)(
57 requires input_iterator<I1> AND sentinel_for<S1, I1> AND
58 input_iterator<I2> AND sentinel_for<S2, I2> AND
59 indirect_strict_weak_order<C, projected<I1, P1>, projected<I2, P2>>)
60 constexpr bool RANGES_FUNC(includes)(I1 begin1,
61 S1 end1,
62 I2 begin2,
63 S2 end2,
64 C pred = C{},
65 P1 proj1 = P1{},
66 P2 proj2 = P2{}) //
67 {
68 for(; begin2 != end2; ++begin1)
69 {
70 if(begin1 == end1 ||
71 invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1)))
72 return false;
73 if(!invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
74 ++begin2;
75 }
76 return true;
77 }
78
80 template(typename Rng1,
81 typename Rng2,
82 typename C = less,
83 typename P1 = identity,
84 typename P2 = identity)(
85 requires input_range<Rng1> AND input_range<Rng2> AND
86 indirect_strict_weak_order<C,
87 projected<iterator_t<Rng1>, P1>,
88 projected<iterator_t<Rng2>, P2>>)
89 constexpr bool RANGES_FUNC(includes)(
90 Rng1 && rng1, Rng2 && rng2, C pred = C{}, P1 proj1 = P1{}, P2 proj2 = P2{}) //
91 {
92 return (*this)(begin(rng1),
93 end(rng1),
94 begin(rng2),
95 end(rng2),
96 std::move(pred),
97 std::move(proj1),
98 std::move(proj2));
99 }
100
101 RANGES_FUNC_END(includes)
102
103 namespace cpp20
104 {
105 using ranges::includes;
106 }
107
108 template<typename I1, typename I2, typename O>
109 using set_union_result = detail::in1_in2_out_result<I1, I2, O>;
110
111 RANGES_FUNC_BEGIN(set_union)
112
113
114 template(typename I1,
115 typename S1,
116 typename I2,
117 typename S2,
118 typename O,
119 typename C = less,
120 typename P1 = identity,
121 typename P2 = identity)(
122 requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND
123 mergeable<I1, I2, O, C, P1, P2>)
124 constexpr set_union_result<I1, I2, O> RANGES_FUNC(set_union)(I1 begin1,
125 S1 end1,
126 I2 begin2,
127 S2 end2,
128 O out,
129 C pred = C{},
130 P1 proj1 = P1{},
131 P2 proj2 = P2{}) //
132 {
133 for(; begin1 != end1; ++out)
134 {
135 if(begin2 == end2)
136 {
137 auto tmp = ranges::copy(begin1, end1, out);
138 return {tmp.in, begin2, tmp.out};
139 }
140 if(invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1)))
141 {
142 *out = *begin2;
143 ++begin2;
144 }
145 else
146 {
147 *out = *begin1;
148 if(!invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
149 ++begin2;
150 ++begin1;
151 }
152 }
153 auto tmp = ranges::copy(begin2, end2, out);
154 return {begin1, tmp.in, tmp.out};
155 }
156
158 template(typename Rng1,
159 typename Rng2,
160 typename O,
161 typename C = less,
162 typename P1 = identity,
163 typename P2 = identity)(
164 requires range<Rng1> AND range<Rng2> AND
165 mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>)
166 constexpr set_union_result<borrowed_iterator_t<Rng1>, borrowed_iterator_t<Rng2>, O> //
167 RANGES_FUNC(set_union)(Rng1 && rng1,
168 Rng2 && rng2,
169 O out,
170 C pred = C{},
171 P1 proj1 = P1{},
172 P2 proj2 = P2{}) //
173 {
174 return (*this)(begin(rng1),
175 end(rng1),
176 begin(rng2),
177 end(rng2),
178 std::move(out),
179 std::move(pred),
180 std::move(proj1),
181 std::move(proj2));
182 }
183
184 RANGES_FUNC_END(set_union)
185
186 namespace cpp20
187 {
188 using ranges::set_union;
189 using ranges::set_union_result;
190 } // namespace cpp20
191
192 RANGES_FUNC_BEGIN(set_intersection)
193
194
195 template(typename I1,
196 typename S1,
197 typename I2,
198 typename S2,
199 typename O,
200 typename C = less,
201 typename P1 = identity,
202 typename P2 = identity)(
203 requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND
204 mergeable<I1, I2, O, C, P1, P2>)
205 constexpr O RANGES_FUNC(set_intersection)(I1 begin1,
206 S1 end1,
207 I2 begin2,
208 S2 end2,
209 O out,
210 C pred = C{},
211 P1 proj1 = P1{},
212 P2 proj2 = P2{}) //
213 {
214 while(begin1 != end1 && begin2 != end2)
215 {
216 if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
217 ++begin1;
218 else
219 {
220 if(!invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1)))
221 {
222 *out = *begin1;
223 ++out;
224 ++begin1;
225 }
226 ++begin2;
227 }
228 }
229 return out;
230 }
231
233 template(typename Rng1,
234 typename Rng2,
235 typename O,
236 typename C = less,
237 typename P1 = identity,
238 typename P2 = identity)(
239 requires range<Rng1> AND range<Rng2> AND
240 mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>)
241 constexpr O RANGES_FUNC(set_intersection)(Rng1 && rng1,
242 Rng2 && rng2,
243 O out,
244 C pred = C{},
245 P1 proj1 = P1{},
246 P2 proj2 = P2{}) //
247 {
248 return (*this)(begin(rng1),
249 end(rng1),
250 begin(rng2),
251 end(rng2),
252 std::move(out),
253 std::move(pred),
254 std::move(proj1),
255 std::move(proj2));
256 }
257
258 RANGES_FUNC_END(set_intersection)
259
260 namespace cpp20
261 {
262 using ranges::set_intersection;
263 }
264
265 template<typename I, typename O>
266 using set_difference_result = detail::in1_out_result<I, O>;
267
268 RANGES_FUNC_BEGIN(set_difference)
269
270
271 template(typename I1,
272 typename S1,
273 typename I2,
274 typename S2,
275 typename O,
276 typename C = less,
277 typename P1 = identity,
278 typename P2 = identity)(
279 requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND
280 mergeable<I1, I2, O, C, P1, P2>)
281 constexpr set_difference_result<I1, O> RANGES_FUNC(set_difference)(I1 begin1,
282 S1 end1,
283 I2 begin2,
284 S2 end2,
285 O out,
286 C pred = C{},
287 P1 proj1 = P1{},
288 P2 proj2 = P2{}) //
289 {
290 while(begin1 != end1)
291 {
292 if(begin2 == end2)
293 {
294 auto tmp = ranges::copy(begin1, end1, out);
295 return {tmp.in, tmp.out};
296 }
297 if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
298 {
299 *out = *begin1;
300 ++out;
301 ++begin1;
302 }
303 else
304 {
305 if(!invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1)))
306 ++begin1;
307 ++begin2;
308 }
309 }
310 return {begin1, out};
311 }
312
314 template(typename Rng1,
315 typename Rng2,
316 typename O,
317 typename C = less,
318 typename P1 = identity,
319 typename P2 = identity)(
320 requires range<Rng1> AND range<Rng2> AND
321 mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>)
322 constexpr set_difference_result<borrowed_iterator_t<Rng1>, O> //
323 RANGES_FUNC(set_difference)(Rng1 && rng1,
324 Rng2 && rng2,
325 O out,
326 C pred = C{},
327 P1 proj1 = P1{},
328 P2 proj2 = P2{}) //
329 {
330 return (*this)(begin(rng1),
331 end(rng1),
332 begin(rng2),
333 end(rng2),
334 std::move(out),
335 std::move(pred),
336 std::move(proj1),
337 std::move(proj2));
338 }
339
340 RANGES_FUNC_END(set_difference)
341
342 namespace cpp20
343 {
344 using ranges::set_difference;
345 using ranges::set_difference_result;
346 } // namespace cpp20
347
348 template<typename I1, typename I2, typename O>
349 using set_symmetric_difference_result = detail::in1_in2_out_result<I1, I2, O>;
350
351 RANGES_FUNC_BEGIN(set_symmetric_difference)
352
353
354 template(typename I1,
355 typename S1,
356 typename I2,
357 typename S2,
358 typename O,
359 typename C = less,
360 typename P1 = identity,
361 typename P2 = identity)(
362 requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND
363 mergeable<I1, I2, O, C, P1, P2>)
364 constexpr set_symmetric_difference_result<I1, I2, O> //
365 RANGES_FUNC(set_symmetric_difference)(I1 begin1,
366 S1 end1,
367 I2 begin2,
368 S2 end2,
369 O out,
370 C pred = C{},
371 P1 proj1 = P1{},
372 P2 proj2 = P2{}) //
373 {
374 while(begin1 != end1)
375 {
376 if(begin2 == end2)
377 {
378 auto tmp = ranges::copy(begin1, end1, out);
379 return {tmp.in, begin2, tmp.out};
380 }
381 if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
382 {
383 *out = *begin1;
384 ++out;
385 ++begin1;
386 }
387 else
388 {
389 if(invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1)))
390 {
391 *out = *begin2;
392 ++out;
393 }
394 else
395 ++begin1;
396 ++begin2;
397 }
398 }
399 auto tmp = ranges::copy(begin2, end2, out);
400 return {begin1, tmp.in, tmp.out};
401 }
402
404 template(typename Rng1,
405 typename Rng2,
406 typename O,
407 typename C = less,
408 typename P1 = identity,
409 typename P2 = identity)(
410 requires range<Rng1> AND range<Rng2> AND
411 mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>)
412 constexpr set_symmetric_difference_result<borrowed_iterator_t<Rng1>,
413 borrowed_iterator_t<Rng2>,
414 O>
415 RANGES_FUNC(set_symmetric_difference)(Rng1 && rng1,
416 Rng2 && rng2,
417 O out,
418 C pred = C{},
419 P1 proj1 = P1{},
420 P2 proj2 = P2{}) //
421 {
422 return (*this)(begin(rng1),
423 end(rng1),
424 begin(rng2),
425 end(rng2),
426 std::move(out),
427 std::move(pred),
428 std::move(proj1),
429 std::move(proj2));
430 }
431
432 RANGES_FUNC_END(set_symmetric_difference)
433
434 namespace cpp20
435 {
436 using ranges::set_symmetric_difference;
437 using ranges::set_symmetric_difference_result;
438 } // namespace cpp20
440} // namespace ranges
441
442#include <range/v3/detail/epilogue.hpp>
443
444#endif
ranges::indirect_strict_weak_order
The indirect_strict_weak_order concept.
ranges::input_iterator
The input_iterator concept.
ranges::input_range
The input_range concept.
ranges::range
The range concept.
ranges::sentinel_for
The sentinel_for concept.
ranges::iterator_t
decltype(begin(declval(Rng &))) iterator_t
Definition access.hpp:698
meta::invoke
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition meta.hpp:541
ranges::cpp20
Definition adjacent_find.hpp:67
range_fwd.hpp
ranges::identity
Definition identity.hpp:25
ranges::less
Definition comparisons.hpp:50
Generated by doxygen 1.15.0