1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 // UNSUPPORTED: c++03, c++11, c++14, c++17
10 // UNSUPPORTED: GCC-ALWAYS_INLINE-FIXME
11
12 // <algorithm>
13
14 // template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
15 // weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity,
16 // class Proj2 = identity>
17 // requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
18 // constexpr merge_result<I1, I2, O>
19 // merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
20 // Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
21 //
22 // template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less,
23 // class Proj1 = identity, class Proj2 = identity>
24 // requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
25 // constexpr merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
26 // merge(R1&& r1, R2&& r2, O result,
27 // Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
28
29 #include <algorithm>
30 #include <array>
31 #include <concepts>
32
33 #include "almost_satisfies_types.h"
34 #include "MoveOnly.h"
35 #include "test_iterators.h"
36 #include "../sortable_helpers.h"
37
38 // Test iterator overload's constraints:
39 // =====================================
40 template <
41 class InIter1,
42 class InIter2,
43 class OutIter,
44 class Sent1 = sentinel_wrapper<InIter1>,
45 class Sent2 = sentinel_wrapper<InIter2>>
46 concept HasMergeIter =
47 requires(InIter1&& inIter1, InIter2&& inIter2, OutIter&& outIter, Sent1&& sent1, Sent2&& sent2) {
48 std::ranges::merge(
49 std::forward<InIter1>(inIter1),
50 std::forward<Sent1>(sent1),
51 std::forward<InIter2>(inIter2),
52 std::forward<Sent2>(sent2),
53 std::forward<OutIter>(outIter));
54 };
55
56 static_assert(HasMergeIter<int*, int*, int*, int*, int*>);
57
58 // !std::input_iterator<I1>
59 static_assert(!HasMergeIter<InputIteratorNotDerivedFrom, int*, int*>);
60
61 // !std::sentinel_for<S1, I1>
62 static_assert(!HasMergeIter<int*, int*, int*, SentinelForNotSemiregular>);
63
64 // !std::input_iterator<I2>
65 static_assert(!HasMergeIter<int*, InputIteratorNotDerivedFrom, int*>);
66
67 // !std::sentinel_for<S2, I2>
68 static_assert(!HasMergeIter<int*, int*, int*, int*, SentinelForNotSemiregular>);
69
70 // !std::weakly_incrementable<O>
71 static_assert(!HasMergeIter<int*, int*, WeaklyIncrementableNotMovable>);
72
73 // !std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
74 static_assert(!HasMergeIter<MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*>);
75
76 // Test range overload's constraints:
77 // =====================================
78
79 template <class Range1, class Range2, class OutIter>
80 concept HasMergeRange =
81 requires(Range1&& range1, Range2&& range2, OutIter&& outIter) {
82 std::ranges::merge(std::forward<Range1>(range1), std::forward<Range2>(range2), std::forward<OutIter>(outIter));
83 };
84
85 static_assert(HasMergeRange<UncheckedRange<int*>, UncheckedRange<int*>, int* >);
86
87 // !std::input_range<R2>
88 static_assert(!HasMergeRange<UncheckedRange<InputIteratorNotDerivedFrom>, UncheckedRange<int*>, int*>);
89
90 // !std::input_range<R2>
91 static_assert(!HasMergeRange<UncheckedRange<int*>, UncheckedRange<InputIteratorNotDerivedFrom>, int*>);
92
93 // !std::weakly_incrementable<O>
94 static_assert(!HasMergeRange<UncheckedRange<int*>, UncheckedRange<int*>, WeaklyIncrementableNotMovable >);
95
96 // !mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
97 static_assert(!HasMergeRange< UncheckedRange<MoveOnly*>, UncheckedRange<MoveOnly*>, MoveOnly*>);
98
99 using std::ranges::merge_result;
100
101 template <class In1, class In2, class Out, std::size_t N1, std::size_t N2>
testMergeImpl(std::array<int,N1> in1,std::array<int,N2> in2,const auto & expected)102 constexpr void testMergeImpl(std::array<int, N1> in1, std::array<int, N2> in2, const auto& expected) {
103 // TODO: std::ranges::merge calls std::ranges::copy
104 // std::ranges::copy(contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>, contiguous_iterator<int*>) doesn't seem to work.
105 // It seems that std::ranges::copy calls std::copy, which unwraps contiguous_iterator<int*> into int*,
106 // and then it failed because there is no == between int* and sentinel_wrapper<contiguous_iterator<int*>>
107 using Sent1 = std::conditional_t<std::contiguous_iterator<In1>, In1, sentinel_wrapper<In1>>;
108 using Sent2 = std::conditional_t<std::contiguous_iterator<In2>, In2, sentinel_wrapper<In2>>;
109
110 // iterator overload
111 {
112 std::array<int, N1 + N2> out;
113 std::same_as<merge_result<In1, In2, Out>> decltype(auto) result = std::ranges::merge(
114 In1{in1.data()},
115 Sent1{In1{in1.data() + in1.size()}},
116 In2{in2.data()},
117 Sent2{In2{in2.data() + in2.size()}},
118 Out{out.data()});
119 assert(std::ranges::equal(out, expected));
120
121 assert(base(result.in1) == in1.data() + in1.size());
122 assert(base(result.in2) == in2.data() + in2.size());
123 assert(base(result.out) == out.data() + out.size());
124 }
125
126 // range overload
127 {
128 std::array<int, N1 + N2> out;
129 std::ranges::subrange r1{In1{in1.data()}, Sent1{In1{in1.data() + in1.size()}}};
130 std::ranges::subrange r2{In2{in2.data()}, Sent2{In2{in2.data() + in2.size()}}};
131 std::same_as<merge_result<In1, In2, Out>> decltype(auto) result = std::ranges::merge(r1, r2, Out{out.data()});
132 assert(std::ranges::equal(out, expected));
133
134 assert(base(result.in1) == in1.data() + in1.size());
135 assert(base(result.in2) == in2.data() + in2.size());
136 assert(base(result.out) == out.data() + out.size());
137 }
138 }
139
140 template <class In1, class In2, class Out>
testImpl()141 constexpr void testImpl() {
142 // range 1 shorter than range2
143 {
144 std::array in1{0, 1, 5, 6, 9, 10};
145 std::array in2{3, 6, 7, 9, 13, 15, 100};
146 std::array expected{0, 1, 3, 5, 6, 6, 7, 9, 9, 10, 13, 15, 100};
147 testMergeImpl<In1, In2, Out>(in1, in2, expected);
148 }
149
150 // range 2 shorter than range 1
151 {
152 std::array in1{2, 6, 8, 12};
153 std::array in2{0, 1, 2};
154 std::array expected{0, 1, 2, 2, 6, 8, 12};
155 testMergeImpl<In1, In2, Out>(in1, in2, expected);
156 }
157
158 // range 1 == range 2
159 {
160 std::array in1{0, 1, 2};
161 std::array in2{0, 1, 2};
162 std::array expected{0, 0, 1, 1, 2, 2};
163 testMergeImpl<In1, In2, Out>(in1, in2, expected);
164 }
165
166 // All elements in range 1 are greater than every element in range 2
167 {
168 std::array in1{8, 8, 10, 12};
169 std::array in2{0, 0, 1};
170 std::array expected{0, 0, 1, 8, 8, 10, 12};
171 testMergeImpl<In1, In2, Out>(in1, in2, expected);
172 }
173
174 // All elements in range 2 are greater than every element in range 1
175 {
176 std::array in1{0, 1, 1};
177 std::array in2{7, 7};
178 std::array expected{0, 1, 1, 7, 7};
179 testMergeImpl<In1, In2, Out>(in1, in2, expected);
180 }
181
182 // range 1 is empty
183 {
184 std::array<int, 0> in1{};
185 std::array in2{3, 4, 5};
186 std::array expected{3, 4, 5};
187 testMergeImpl<In1, In2, Out>(in1, in2, expected);
188 }
189
190 // range 2 is empty
191 {
192 std::array in1{3, 4, 5};
193 std::array<int, 0> in2{};
194 std::array expected{3, 4, 5};
195 testMergeImpl<In1, In2, Out>(in1, in2, expected);
196 }
197
198 // both ranges are empty
199 {
200 std::array<int, 0> in1{};
201 std::array<int, 0> in2{};
202 std::array<int, 0> expected{};
203 testMergeImpl<In1, In2, Out>(in1, in2, expected);
204 }
205
206 // check that ranges::dangling is returned for non-borrowed_range and iterator_t is returned for borrowed_range
207 {
208 std::array r1{3, 6, 7, 9};
209 std::array r2{2, 3, 4};
210 std::array<int, 7> out;
211 std::same_as<merge_result<std::array<int, 4>::iterator, std::ranges::dangling, int*>> decltype(auto) result =
212 std::ranges::merge(r1, NonBorrowedRange<In2>{r2.data(), r2.size()}, out.data());
213 assert(base(result.in1) == r1.end());
214 assert(base(result.out) == out.data() + out.size());
215 assert(std::ranges::equal(out, std::array{2, 3, 3, 4, 6, 7, 9}));
216 }
217 }
218
219 template <class InIter2, class OutIter>
withAllPermutationsOfInIter1()220 constexpr void withAllPermutationsOfInIter1() {
221 testImpl<cpp20_input_iterator<int*>, InIter2, OutIter>();
222 testImpl<forward_iterator<int*>, InIter2, OutIter>();
223 testImpl<bidirectional_iterator<int*>, InIter2, OutIter>();
224 testImpl<random_access_iterator<int*>, InIter2, OutIter>();
225 testImpl<contiguous_iterator<int*>, InIter2, OutIter>();
226 }
227
228 template <class OutIter>
withAllPermutationsOfInIter1AndInIter2()229 constexpr bool withAllPermutationsOfInIter1AndInIter2() {
230 withAllPermutationsOfInIter1<cpp20_input_iterator<int*>, OutIter>();
231 withAllPermutationsOfInIter1<forward_iterator<int*>, OutIter>();
232 withAllPermutationsOfInIter1<bidirectional_iterator<int*>, OutIter>();
233 withAllPermutationsOfInIter1<random_access_iterator<int*>, OutIter>();
234 withAllPermutationsOfInIter1<contiguous_iterator<int*>, OutIter>();
235 return true;
236 }
237
runAllIteratorPermutationsTests()238 constexpr void runAllIteratorPermutationsTests() {
239 withAllPermutationsOfInIter1AndInIter2<cpp20_output_iterator<int*>>();
240 withAllPermutationsOfInIter1AndInIter2<cpp20_input_iterator<int*>>();
241 withAllPermutationsOfInIter1AndInIter2<forward_iterator<int*>>();
242 withAllPermutationsOfInIter1AndInIter2<bidirectional_iterator<int*>>();
243 withAllPermutationsOfInIter1AndInIter2<random_access_iterator<int*>>();
244 withAllPermutationsOfInIter1AndInIter2<contiguous_iterator<int*>>();
245
246 static_assert(withAllPermutationsOfInIter1AndInIter2<cpp20_output_iterator<int*>>());
247 static_assert(withAllPermutationsOfInIter1AndInIter2<cpp20_input_iterator<int*>>());
248 static_assert(withAllPermutationsOfInIter1AndInIter2<forward_iterator<int*>>());
249 static_assert(withAllPermutationsOfInIter1AndInIter2<bidirectional_iterator<int*>>());
250 static_assert(withAllPermutationsOfInIter1AndInIter2<random_access_iterator<int*>>());
251 static_assert(withAllPermutationsOfInIter1AndInIter2<contiguous_iterator<int*>>());
252 }
253
test()254 constexpr bool test() {
255 // check that every element is copied exactly once
256 {
257 std::array<TracedCopy, 3> r1{3, 5, 8};
258 std::array<TracedCopy, 3> r2{1, 3, 8};
259
260 // iterator overload
261 {
262 std::array<TracedCopy, 6> out;
263 auto result = std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
264
265 assert(result.in1 == r1.end());
266 assert(result.in2 == r2.end());
267 assert(result.out == out.data() + out.size());
268 assert(std::ranges::equal(out, std::array<TracedCopy, 6>{1, 3, 3, 5, 8, 8}));
269
270 assert(std::ranges::all_of(out, &TracedCopy::copiedOnce));
271 }
272
273 // range overload
274 {
275 std::array<TracedCopy, 6> out;
276 auto result = std::ranges::merge(r1, r2, out.data());
277
278 assert(result.in1 == r1.end());
279 assert(result.in2 == r2.end());
280 assert(result.out == out.data() + out.size());
281 assert(std::ranges::equal(out, std::array<TracedCopy, 6>{1, 3, 3, 5, 8, 8}));
282
283 assert(std::ranges::all_of(out, &TracedCopy::copiedOnce));
284 }
285 }
286
287 struct IntAndID {
288 int data;
289 int id;
290
291 constexpr auto operator==(const IntAndID& o) const { return data == o.data; }
292 constexpr auto operator<=>(const IntAndID& o) const { return data <=> o.data; }
293 };
294
295 // Algorithm is stable: equal elements should be merged in the original order
296 {
297 std::array<IntAndID, 3> r1{{{0, 0}, {0, 1}, {0, 2}}};
298 std::array<IntAndID, 3> r2{{{1, 0}, {1, 1}, {1, 2}}};
299
300 // iterator overload
301 {
302 std::array<IntAndID, 6> out;
303 std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
304
305 assert(std::ranges::equal(out, std::array{0, 0, 0, 1, 1, 1}, {}, &IntAndID::data));
306 // ID should be in their original order
307 assert(std::ranges::equal(out, std::array{0, 1, 2, 0, 1, 2}, {}, &IntAndID::id));
308 }
309
310 // range overload
311 {
312 std::array<IntAndID, 6> out;
313 std::ranges::merge(r1, r2, out.data());
314
315 assert(std::ranges::equal(out, std::array{0, 0, 0, 1, 1, 1}, {}, &IntAndID::data));
316 // ID should be in their original order
317 assert(std::ranges::equal(out, std::array{0, 1, 2, 0, 1, 2}, {}, &IntAndID::id));
318 }
319 }
320
321 // Equal elements in R1 should be merged before equal elements in R2
322 {
323 std::array<IntAndID, 3> r1{{{0, 1}, {1, 1}, {2, 1}}};
324 std::array<IntAndID, 3> r2{{{0, 2}, {1, 2}, {2, 2}}};
325
326 // iterator overload
327 {
328 std::array<IntAndID, 6> out;
329 std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
330
331 assert(std::ranges::equal(out, std::array{0, 0, 1, 1, 2, 2}, {}, &IntAndID::data));
332 // ID 1 (from R1) should be in front of ID 2 (from R2)
333 assert(std::ranges::equal(out, std::array{1, 2, 1, 2, 1, 2}, {}, &IntAndID::id));
334 }
335
336 // range overload
337 {
338 std::array<IntAndID, 6> out;
339 std::ranges::merge(r1, r2, out.data());
340
341 assert(std::ranges::equal(out, std::array{0, 0, 1, 1, 2, 2}, {}, &IntAndID::data));
342 // ID 1 (from R1) should be in front of ID 2 (from R2)
343 assert(std::ranges::equal(out, std::array{1, 2, 1, 2, 1, 2}, {}, &IntAndID::id));
344 }
345 }
346
347 struct Data {
348 int data;
349
350 constexpr bool smallerThan(const Data& o) const { return data < o.data; }
351 };
352
353 // Test custom comparator
354 {
355 std::array r1{Data{4}, Data{8}, Data{12}};
356 std::array r2{Data{5}, Data{9}};
357 using Iter1 = std::array<Data, 3>::iterator;
358 using Iter2 = std::array<Data, 2>::iterator;
359
360 // iterator overload
361 {
362 std::array<Data, 5> out;
363 std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
364 std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), [](const Data& x, const Data& y) {
365 return x.data < y.data;
366 });
367
368 assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
369
370 assert(result.in1 == r1.end());
371 assert(result.in2 == r2.end());
372 assert(result.out == out.data() + out.size());
373 }
374
375 // range overload
376 {
377 std::array<Data, 5> out;
378 std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
379 std::ranges::merge(r1, r2, out.data(), [](const Data& x, const Data& y) { return x.data < y.data; });
380
381 assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
382
383 assert(result.in1 == r1.end());
384 assert(result.in2 == r2.end());
385 assert(result.out == out.data() + out.size());
386 }
387
388 // member pointer Comparator iterator overload
389 {
390 std::array<Data, 5> out;
391 std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
392 std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), &Data::smallerThan);
393
394 assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
395
396 assert(result.in1 == r1.end());
397 assert(result.in2 == r2.end());
398 assert(result.out == out.data() + out.size());
399 }
400
401 // member pointer Comparator range overload
402 {
403 std::array<Data, 5> out;
404 std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
405 std::ranges::merge(r1, r2, out.data(), &Data::smallerThan);
406
407 assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
408
409 assert(result.in1 == r1.end());
410 assert(result.in2 == r2.end());
411 assert(result.out == out.data() + out.size());
412 }
413 }
414
415 // Test Projection
416 {
417 std::array r1{Data{4}, Data{8}, Data{12}};
418 std::array r2{Data{5}, Data{9}};
419 using Iter1 = std::array<Data, 3>::iterator;
420 using Iter2 = std::array<Data, 2>::iterator;
421
422 const auto proj = [](const Data& d) { return d.data; };
423
424 // iterator overload
425 {
426 std::array<Data, 5> out;
427 std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
428 std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), std::ranges::less{}, proj, proj);
429
430 assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
431
432 assert(result.in1 == r1.end());
433 assert(result.in2 == r2.end());
434 assert(result.out == out.data() + out.size());
435 }
436
437 // range overload
438 {
439 std::array<Data, 5> out;
440 std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
441 std::ranges::merge(r1, r2, out.data(), std::ranges::less{}, proj, proj);
442
443 assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
444
445 assert(result.in1 == r1.end());
446 assert(result.in2 == r2.end());
447 assert(result.out == out.data() + out.size());
448 }
449
450 // member pointer Projection iterator overload
451 {
452 std::array<Data, 5> out;
453 std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
454 std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), {}, &Data::data, &Data::data);
455
456 assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
457
458 assert(result.in1 == r1.end());
459 assert(result.in2 == r2.end());
460 assert(result.out == out.data() + out.size());
461 }
462
463 // member pointer Projection range overload
464 {
465 std::array<Data, 5> out;
466 std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
467 std::ranges::merge(r1, r2, out.data(), std::ranges::less{}, &Data::data, &Data::data);
468
469 assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
470
471 assert(result.in1 == r1.end());
472 assert(result.in2 == r2.end());
473 assert(result.out == out.data() + out.size());
474 }
475 }
476
477 // Complexity: at most N - 1 comparisons and applications of each projection.
478 {
479 Data r1[] = {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}};
480 Data r2[] = {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}};
481 std::array expected{0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9};
482
483 // iterator overload
484 {
485 std::array<Data, 20> out;
486 std::size_t numberOfComp = 0;
487 std::size_t numberOfProj1 = 0;
488 std::size_t numberOfProj2 = 0;
489
490 const auto comp = [&numberOfComp](int x, int y) {
491 ++numberOfComp;
492 return x < y;
493 };
494
495 const auto proj1 = [&numberOfProj1](const Data& d) {
496 ++numberOfProj1;
497 return d.data;
498 };
499
500 const auto proj2 = [&numberOfProj2](const Data& d) {
501 ++numberOfProj2;
502 return d.data;
503 };
504
505 std::ranges::merge(r1, r1 + 10, r2, r2 + 10, out.data(), comp, proj1, proj2);
506 assert(std::ranges::equal(out, expected, {}, &Data::data));
507 assert(numberOfComp < out.size());
508 assert(numberOfProj1 < out.size());
509 assert(numberOfProj2 < out.size());
510 }
511
512 // range overload
513 {
514 std::array<Data, 20> out;
515 std::size_t numberOfComp = 0;
516 std::size_t numberOfProj1 = 0;
517 std::size_t numberOfProj2 = 0;
518
519 const auto comp = [&numberOfComp](int x, int y) {
520 ++numberOfComp;
521 return x < y;
522 };
523
524 const auto proj1 = [&numberOfProj1](const Data& d) {
525 ++numberOfProj1;
526 return d.data;
527 };
528
529 const auto proj2 = [&numberOfProj2](const Data& d) {
530 ++numberOfProj2;
531 return d.data;
532 };
533
534 std::ranges::merge(r1, r2, out.data(), comp, proj1, proj2);
535 assert(std::ranges::equal(out, expected, {}, &Data::data));
536 assert(numberOfComp < out.size());
537 assert(numberOfProj1 < out.size());
538 assert(numberOfProj2 < out.size());
539 }
540 }
541
542 // Comparator convertible to bool
543 {
544 struct ConvertibleToBool {
545 bool b;
546 constexpr operator bool() const { return b; }
547 };
548 Data r1[] = {{2}, {4}};
549 Data r2[] = {{3}, {4}, {5}};
550
551 const auto comp = [](const Data& x, const Data& y) { return ConvertibleToBool{x.data < y.data}; };
552
553 // iterator overload
554 {
555 std::array<Data, 5> out;
556 std::ranges::merge(r1, r1 + 2, r2, r2 + 3, out.data(), comp);
557 assert(std::ranges::equal(out, std::array{2, 3, 4, 4, 5}, {}, &Data::data));
558 }
559
560 // range overload
561 {
562 std::array<Data, 5> out;
563 std::ranges::merge(r1, r2, out.data(), comp);
564 assert(std::ranges::equal(out, std::array{2, 3, 4, 4, 5}, {}, &Data::data));
565 }
566 }
567
568 return true;
569 }
570
main(int,char **)571 int main(int, char**) {
572 test();
573 static_assert(test());
574
575 runAllIteratorPermutationsTests();
576
577 return 0;
578 }
579