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// <algorithm>
10
11// UNSUPPORTED: c++03, c++11, c++14, c++17
12
13// Algorithmic complexity tests for both std::set_intersection and std::ranges::set_intersection
14
15// template<InputIterator InIter1, InputIterator InIter2, typename OutIter>
16// requires OutputIterator<OutIter, InIter1::reference>
17// && OutputIterator<OutIter, InIter2::reference>
18// && HasLess<InIter2::value_type, InIter1::value_type>
19// && HasLess<InIter1::value_type, InIter2::value_type>
20// constexpr OutIter // constexpr after C++17
21// set_intersection(InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2,
22// OutIter result);
23//
24// template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
25// weakly_incrementable O, class Comp = ranges::less,
26// class Proj1 = identity, class Proj2 = identity>
27// requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
28// constexpr set_intersection_result<I1, I2, O>
29// set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
30// Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
31//
32// template<input_range R1, input_range R2, weakly_incrementable O,
33// class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
34// requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
35// constexpr set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
36// set_intersection(R1&& r1, R2&& r2, O result,
37// Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
38
39#include <algorithm>
40#include <array>
41#include <cstddef>
42#include <ranges>
43
44#include "test_iterators.h"
45
46namespace {
47
48// __debug_less will perform an additional comparison in an assertion
49static constexpr unsigned std_less_comparison_count_multiplier() noexcept {
50#if _LIBCPP_HARDENING_MODE == _LIBCPP_HARDENING_MODE_DEBUG
51 return 2;
52#else
53 return 1;
54#endif
55}
56
57struct [[nodiscard]] OperationCounts {
58 std::size_t comparisons{};
59 struct PerInput {
60 std::size_t proj{};
61 IteratorOpCounts iterops;
62
63 [[nodiscard]] constexpr bool isNotBetterThan(const PerInput& other) {
64 return proj >= other.proj && iterops.increments + iterops.decrements + iterops.zero_moves >=
65 other.iterops.increments + other.iterops.decrements + other.iterops.zero_moves;
66 }
67 };
68 std::array<PerInput, 2> in;
69
70 [[nodiscard]] constexpr bool isNotBetterThan(const OperationCounts& expect) {
71 return std_less_comparison_count_multiplier() * comparisons >= expect.comparisons &&
72 in[0].isNotBetterThan(expect.in[0]) && in[1].isNotBetterThan(expect.in[1]);
73 }
74};
75
76template <std::size_t ResultSize>
77struct counted_set_intersection_result {
78 std::array<int, ResultSize> result;
79 OperationCounts opcounts;
80
81 constexpr counted_set_intersection_result() = default;
82
83 constexpr explicit counted_set_intersection_result(std::array<int, ResultSize>&& contents) : result{contents} {}
84
85 constexpr void assertNotBetterThan(const counted_set_intersection_result& other) {
86 assert(result == other.result);
87 assert(opcounts.isNotBetterThan(other.opcounts));
88 }
89};
90
91template <std::size_t ResultSize>
92counted_set_intersection_result(std::array<int, ResultSize>) -> counted_set_intersection_result<ResultSize>;
93
94template <template <class...> class InIterType1,
95 template <class...>
96 class InIterType2,
97 class OutIterType,
98 std::size_t ResultSize,
99 std::ranges::input_range R1,
100 std::ranges::input_range R2>
101constexpr counted_set_intersection_result<ResultSize> counted_set_intersection(const R1& in1, const R2& in2) {
102 counted_set_intersection_result<ResultSize> out;
103
104 const auto comp = [&out](int x, int y) {
105 ++out.opcounts.comparisons;
106 return x < y;
107 };
108
109 operation_counting_iterator b1(InIterType1<decltype(in1.begin())>(in1.begin()), &out.opcounts.in[0].iterops);
110 operation_counting_iterator e1(InIterType1<decltype(in1.end()) >(in1.end()), &out.opcounts.in[0].iterops);
111
112 operation_counting_iterator b2(InIterType2<decltype(in2.begin())>(in2.begin()), &out.opcounts.in[1].iterops);
113 operation_counting_iterator e2(InIterType2<decltype(in2.end()) >(in2.end()), &out.opcounts.in[1].iterops);
114
115 std::set_intersection(b1, e1, b2, e2, OutIterType(out.result.data()), comp);
116
117 return out;
118}
119
120template <template <class...> class InIterType1,
121 template <class...>
122 class InIterType2,
123 class OutIterType,
124 std::size_t ResultSize,
125 std::ranges::input_range R1,
126 std::ranges::input_range R2>
127constexpr counted_set_intersection_result<ResultSize> counted_ranges_set_intersection(const R1& in1, const R2& in2) {
128 counted_set_intersection_result<ResultSize> out;
129
130 const auto comp = [&out](int x, int y) {
131 ++out.opcounts.comparisons;
132 return x < y;
133 };
134
135 const auto proj1 = [&out](const int& i) {
136 ++out.opcounts.in[0].proj;
137 return i;
138 };
139
140 const auto proj2 = [&out](const int& i) {
141 ++out.opcounts.in[1].proj;
142 return i;
143 };
144
145 operation_counting_iterator b1(InIterType1<decltype(in1.begin())>(in1.begin()), &out.opcounts.in[0].iterops);
146 operation_counting_iterator e1(InIterType1<decltype(in1.end()) >(in1.end()), &out.opcounts.in[0].iterops);
147
148 operation_counting_iterator b2(InIterType2<decltype(in2.begin())>(in2.begin()), &out.opcounts.in[1].iterops);
149 operation_counting_iterator e2(InIterType2<decltype(in2.end()) >(in2.end()), &out.opcounts.in[1].iterops);
150
151 std::ranges::subrange r1{b1, sentinel_wrapper<decltype(e1)>{e1}};
152 std::ranges::subrange r2{b2, sentinel_wrapper<decltype(e2)>{e2}};
153 std::same_as<std::ranges::set_intersection_result<decltype(e1), decltype(e2), OutIterType>> decltype(auto) result =
154 std::ranges::set_intersection(r1, r2, OutIterType{out.result.data()}, comp, proj1, proj2);
155 assert(base(result.in1) == base(e1));
156 assert(base(result.in2) == base(e2));
157 assert(base(result.out) == out.result.data() + out.result.size());
158
159 return out;
160}
161
162template <template <typename...> class In1, template <typename...> class In2, class Out>
163constexpr void testComplexityParameterizedIter() {
164 // Worst-case complexity:
165 // Let N=(last1 - first1) and M=(last2 - first2)
166 // At most 2*(N+M) - 1 comparisons and applications of each projection.
167 // At most 2*(N+M) iterator mutations.
168 {
169 std::array r1{1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
170 std::array r2{2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
171
172 counted_set_intersection_result<0> expected;
173 expected.opcounts.comparisons = 37;
174 expected.opcounts.in[0].proj = 37;
175 expected.opcounts.in[0].iterops.increments = 30;
176 expected.opcounts.in[0].iterops.decrements = 0;
177 expected.opcounts.in[1] = expected.opcounts.in[0];
178
179 expected.assertNotBetterThan(counted_set_intersection<In1, In2, Out, expected.result.size()>(r1, r2));
180 expected.assertNotBetterThan(counted_ranges_set_intersection<In1, In2, Out, expected.result.size()>(r1, r2));
181 }
182
183 {
184 std::array r1{1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
185 std::array r2{1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
186
187 counted_set_intersection_result expected(std::array{1, 3, 5, 7, 9, 11, 13, 15, 17, 19});
188 expected.opcounts.comparisons = 38;
189 expected.opcounts.in[0].proj = 38;
190 expected.opcounts.in[0].iterops.increments = 30;
191 expected.opcounts.in[0].iterops.decrements = 0;
192 expected.opcounts.in[1] = expected.opcounts.in[0];
193
194 expected.assertNotBetterThan(counted_set_intersection<In1, In2, Out, expected.result.size()>(r1, r2));
195 expected.assertNotBetterThan(counted_ranges_set_intersection<In1, In2, Out, expected.result.size()>(r1, r2));
196 }
197
198 // Lower complexity when there is low overlap between ranges: we can make 2*log(X) comparisons when one range
199 // has X elements that can be skipped over (and then 1 more to confirm that the value we found is equal).
200 {
201 std::array r1{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
202 std::array r2{15};
203
204 counted_set_intersection_result expected(std::array{15});
205 expected.opcounts.comparisons = 9;
206 expected.opcounts.in[0].proj = 9;
207 expected.opcounts.in[0].iterops.increments = 23;
208 expected.opcounts.in[0].iterops.decrements = 0;
209 expected.opcounts.in[1].proj = 9;
210 expected.opcounts.in[1].iterops.increments = 1;
211 expected.opcounts.in[1].iterops.decrements = 0;
212
213 expected.assertNotBetterThan(counted_set_intersection<In1, In2, Out, expected.result.size()>(r1, r2));
214 expected.assertNotBetterThan(counted_ranges_set_intersection<In1, In2, Out, expected.result.size()>(r1, r2));
215 }
216
217 {
218 std::array r1{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
219 std::array r2{0, 16};
220 counted_set_intersection_result<0> expected;
221
222 expected.opcounts.comparisons = 10;
223 expected.opcounts.in[0].proj = 10;
224 expected.opcounts.in[0].iterops.increments = 24;
225 expected.opcounts.in[0].iterops.decrements = 0;
226 expected.opcounts.in[1].proj = 10;
227 expected.opcounts.in[1].iterops.increments = 4;
228 expected.opcounts.in[1].iterops.decrements = 0;
229
230 expected.assertNotBetterThan(counted_set_intersection<In1, In2, Out, expected.result.size()>(r1, r2));
231 expected.assertNotBetterThan(counted_ranges_set_intersection<In1, In2, Out, expected.result.size()>(r1, r2));
232 }
233}
234
235template <template <typename...> class In2, class Out>
236constexpr void testComplexityParameterizedIterPermutateIn1() {
237 //common_input_iterator
238 testComplexityParameterizedIter<forward_iterator, In2, Out>();
239 testComplexityParameterizedIter<bidirectional_iterator, In2, Out>();
240 testComplexityParameterizedIter<random_access_iterator, In2, Out>();
241}
242
243template <class Out>
244constexpr void testComplexityParameterizedIterPermutateIn1In2() {
245 testComplexityParameterizedIterPermutateIn1<forward_iterator, Out>();
246 testComplexityParameterizedIterPermutateIn1<bidirectional_iterator, Out>();
247 testComplexityParameterizedIterPermutateIn1<random_access_iterator, Out>();
248}
249
250constexpr bool testComplexity() {
251 testComplexityParameterizedIterPermutateIn1In2<forward_iterator<int*>>();
252 testComplexityParameterizedIterPermutateIn1In2<bidirectional_iterator<int*>>();
253 testComplexityParameterizedIterPermutateIn1In2<random_access_iterator<int*>>();
254 return true;
255}
256
257template <template <typename...> class In1, template <typename...> class In2, class Out>
258constexpr void testComplexityGuaranteesParameterizedIter() {
259 // now a more generic validation of the complexity guarantees when searching for a single value
260 for (unsigned range_size = 1; range_size < 20; ++range_size) {
261 std::ranges::iota_view<int, int> r1(0, range_size);
262 for (int i : r1) {
263 // At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons
264 counted_set_intersection_result<1> expected(std::array{i});
265 expected.opcounts.comparisons = 2 * (r1.size() + 1) - 1;
266 expected.opcounts.in[0].proj = expected.opcounts.comparisons;
267 expected.opcounts.in[1].proj = expected.opcounts.comparisons;
268 expected.opcounts.in[0].iterops.increments = 2 * r1.size();
269 expected.opcounts.in[1].iterops.increments = 2;
270 expected.opcounts.in[0].iterops.decrements = expected.opcounts.in[0].iterops.increments;
271 expected.opcounts.in[1].iterops.decrements = expected.opcounts.in[1].iterops.increments;
272
273 expected.assertNotBetterThan(
274 counted_set_intersection<In1, In2, Out, expected.result.size()>(r1, expected.result));
275 expected.assertNotBetterThan(
276 counted_ranges_set_intersection<In1, In2, Out, expected.result.size()>(r1, expected.result));
277 }
278 }
279}
280
281template <template <typename...> class In2, class Out>
282constexpr void testComplexityGuaranteesParameterizedIterPermutateIn1() {
283 //common_input_iterator
284 testComplexityGuaranteesParameterizedIter<forward_iterator, In2, Out>();
285 testComplexityGuaranteesParameterizedIter<bidirectional_iterator, In2, Out>();
286 testComplexityGuaranteesParameterizedIter<random_access_iterator, In2, Out>();
287}
288
289template <class Out>
290constexpr void testComplexityGuaranteesParameterizedIterPermutateIn1In2() {
291 testComplexityGuaranteesParameterizedIterPermutateIn1<forward_iterator, Out>();
292 testComplexityGuaranteesParameterizedIterPermutateIn1<bidirectional_iterator, Out>();
293 testComplexityGuaranteesParameterizedIterPermutateIn1<random_access_iterator, Out>();
294}
295
296constexpr bool testComplexityGuarantees() {
297 testComplexityGuaranteesParameterizedIterPermutateIn1In2<forward_iterator<int*>>();
298 testComplexityGuaranteesParameterizedIterPermutateIn1In2<bidirectional_iterator<int*>>();
299 testComplexityGuaranteesParameterizedIterPermutateIn1In2<random_access_iterator<int*>>();
300 return true;
301}
302
303constexpr bool testComplexityBasic() {
304 // Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.
305 std::array<int, 5> r1{1, 3, 5, 7, 9};
306 std::array<int, 5> r2{2, 4, 6, 8, 10};
307 std::array<int, 0> expected{};
308
309 const std::size_t maxOperation = std_less_comparison_count_multiplier() * (2 * (r1.size() + r2.size()) - 1);
310
311 // std::set_intersection
312 {
313 std::array<int, 0> out{};
314 std::size_t numberOfComp = 0;
315
316 const auto comp = [&numberOfComp](int x, int y) {
317 ++numberOfComp;
318 return x < y;
319 };
320
321 std::set_intersection(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), comp);
322
323 assert(std::ranges::equal(out, expected));
324 assert(numberOfComp <= maxOperation);
325 }
326
327 // ranges::set_intersection iterator overload
328 {
329 std::array<int, 0> out{};
330 std::size_t numberOfComp = 0;
331 std::size_t numberOfProj1 = 0;
332 std::size_t numberOfProj2 = 0;
333
334 const auto comp = [&numberOfComp](int x, int y) {
335 ++numberOfComp;
336 return x < y;
337 };
338
339 const auto proj1 = [&numberOfProj1](int d) {
340 ++numberOfProj1;
341 return d;
342 };
343
344 const auto proj2 = [&numberOfProj2](int d) {
345 ++numberOfProj2;
346 return d;
347 };
348
349 std::ranges::set_intersection(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), comp, proj1, proj2);
350
351 assert(std::ranges::equal(out, expected));
352 assert(numberOfComp <= maxOperation);
353 assert(numberOfProj1 <= maxOperation);
354 assert(numberOfProj2 <= maxOperation);
355 }
356
357 // ranges::set_intersection range overload
358 {
359 std::array<int, 0> out{};
360 std::size_t numberOfComp = 0;
361 std::size_t numberOfProj1 = 0;
362 std::size_t numberOfProj2 = 0;
363
364 const auto comp = [&numberOfComp](int x, int y) {
365 ++numberOfComp;
366 return x < y;
367 };
368
369 const auto proj1 = [&numberOfProj1](int d) {
370 ++numberOfProj1;
371 return d;
372 };
373
374 const auto proj2 = [&numberOfProj2](int d) {
375 ++numberOfProj2;
376 return d;
377 };
378
379 std::ranges::set_intersection(r1, r2, out.data(), comp, proj1, proj2);
380
381 assert(std::ranges::equal(out, expected));
382 assert(numberOfComp < maxOperation);
383 assert(numberOfProj1 < maxOperation);
384 assert(numberOfProj2 < maxOperation);
385 }
386 return true;
387}
388
389} // unnamed namespace
390
391int main(int, char**) {
392 testComplexityBasic();
393 testComplexity();
394 testComplexityGuarantees();
395
396 static_assert(testComplexityBasic());
397 static_assert(testComplexity());
398
399 // we hit maximum constexpr evaluation step limit even if we split this into
400 // the 3 types of the first type layer, so let's skip the constexpr validation
401 // static_assert(testComplexityGuarantees());
402
403 return 0;
404}
405

Provided by KDAB

Privacy Policy
Improve your Profiling and Debugging skills
Find out more

source code of libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.intersection/set_intersection_complexity.pass.cpp