]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ////////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2004-2013. Distributed under the Boost | |
4 | // Software License, Version 1.0. (See accompanying file | |
5 | // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
6 | // | |
7 | // See http://www.boost.org/libs/container for documentation. | |
8 | // | |
9 | ////////////////////////////////////////////////////////////////////////////// | |
10 | ||
92f5a8d4 | 11 | #include <iostream> |
7c673cae | 12 | #include <set> |
92f5a8d4 TL |
13 | #include <utility> |
14 | #include <vector> | |
b32b8144 | 15 | |
7c673cae | 16 | #include <boost/container/flat_set.hpp> |
b32b8144 | 17 | #include <boost/container/detail/container_or_allocator_rebind.hpp> |
7c673cae FG |
18 | |
19 | #include "print_container.hpp" | |
20 | #include "dummy_test_allocator.hpp" | |
21 | #include "movable_int.hpp" | |
22 | #include "set_test.hpp" | |
23 | #include "propagate_allocator_test.hpp" | |
24 | #include "emplace_test.hpp" | |
25 | #include "container_common_tests.hpp" | |
7c673cae FG |
26 | #include "../../intrusive/test/iterator_test.hpp" |
27 | ||
28 | using namespace boost::container; | |
29 | ||
7c673cae FG |
30 | //Test recursive structures |
31 | class recursive_flat_set | |
32 | { | |
33 | public: | |
34 | recursive_flat_set(const recursive_flat_set &c) | |
35 | : id_(c.id_), flat_set_(c.flat_set_) | |
36 | {} | |
37 | ||
38 | recursive_flat_set & operator =(const recursive_flat_set &c) | |
39 | { | |
40 | id_ = c.id_; | |
41 | flat_set_= c.flat_set_; | |
42 | return *this; | |
43 | } | |
44 | int id_; | |
45 | flat_set<recursive_flat_set> flat_set_; | |
46 | flat_set<recursive_flat_set>::iterator it_; | |
47 | flat_set<recursive_flat_set>::const_iterator cit_; | |
48 | flat_set<recursive_flat_set>::reverse_iterator rit_; | |
49 | flat_set<recursive_flat_set>::const_reverse_iterator crit_; | |
50 | ||
51 | friend bool operator< (const recursive_flat_set &a, const recursive_flat_set &b) | |
52 | { return a.id_ < b.id_; } | |
53 | }; | |
54 | ||
55 | ||
56 | //Test recursive structures | |
57 | class recursive_flat_multiset | |
58 | { | |
59 | public: | |
60 | recursive_flat_multiset(const recursive_flat_multiset &c) | |
61 | : id_(c.id_), flat_multiset_(c.flat_multiset_) | |
62 | {} | |
63 | ||
64 | recursive_flat_multiset & operator =(const recursive_flat_multiset &c) | |
65 | { | |
66 | id_ = c.id_; | |
67 | flat_multiset_= c.flat_multiset_; | |
68 | return *this; | |
69 | } | |
70 | int id_; | |
71 | flat_multiset<recursive_flat_multiset> flat_multiset_; | |
72 | flat_multiset<recursive_flat_multiset>::iterator it_; | |
73 | flat_multiset<recursive_flat_multiset>::const_iterator cit_; | |
74 | flat_multiset<recursive_flat_multiset>::reverse_iterator rit_; | |
75 | flat_multiset<recursive_flat_multiset>::const_reverse_iterator crit_; | |
76 | ||
77 | friend bool operator< (const recursive_flat_multiset &a, const recursive_flat_multiset &b) | |
78 | { return a.id_ < b.id_; } | |
79 | }; | |
80 | ||
81 | ||
82 | template<class C> | |
83 | void test_move() | |
84 | { | |
85 | //Now test move semantics | |
86 | C original; | |
87 | C move_ctor(boost::move(original)); | |
88 | C move_assign; | |
89 | move_assign = boost::move(move_ctor); | |
90 | move_assign.swap(original); | |
91 | } | |
92 | ||
93 | namespace boost{ | |
94 | namespace container { | |
95 | namespace test{ | |
96 | ||
97 | bool flat_tree_ordered_insertion_test() | |
98 | { | |
99 | using namespace boost::container; | |
100 | const std::size_t NumElements = 100; | |
101 | ||
102 | //Ordered insertion multiset | |
103 | { | |
104 | std::multiset<int> int_mset; | |
105 | for(std::size_t i = 0; i != NumElements; ++i){ | |
106 | int_mset.insert(static_cast<int>(i)); | |
107 | } | |
108 | //Construction insertion | |
109 | flat_multiset<int> fmset(ordered_range, int_mset.begin(), int_mset.end()); | |
110 | if(!CheckEqualContainers(int_mset, fmset)) | |
111 | return false; | |
112 | //Insertion when empty | |
113 | fmset.clear(); | |
114 | fmset.insert(ordered_range, int_mset.begin(), int_mset.end()); | |
115 | if(!CheckEqualContainers(int_mset, fmset)) | |
116 | return false; | |
117 | //Re-insertion | |
118 | fmset.insert(ordered_range, int_mset.begin(), int_mset.end()); | |
119 | std::multiset<int> int_mset2(int_mset); | |
120 | int_mset2.insert(int_mset.begin(), int_mset.end()); | |
121 | if(!CheckEqualContainers(int_mset2, fmset)) | |
122 | return false; | |
123 | //Re-re-insertion | |
124 | fmset.insert(ordered_range, int_mset2.begin(), int_mset2.end()); | |
125 | std::multiset<int> int_mset4(int_mset2); | |
126 | int_mset4.insert(int_mset2.begin(), int_mset2.end()); | |
127 | if(!CheckEqualContainers(int_mset4, fmset)) | |
128 | return false; | |
129 | //Re-re-insertion of even | |
130 | std::multiset<int> int_even_mset; | |
131 | for(std::size_t i = 0; i < NumElements; i+=2){ | |
132 | int_mset.insert(static_cast<int>(i)); | |
133 | } | |
134 | fmset.insert(ordered_range, int_even_mset.begin(), int_even_mset.end()); | |
135 | int_mset4.insert(int_even_mset.begin(), int_even_mset.end()); | |
136 | if(!CheckEqualContainers(int_mset4, fmset)) | |
137 | return false; | |
138 | ||
139 | //Re-re-insertion using in-place merge | |
140 | fmset.reserve(fmset.size() + int_mset2.size()); | |
141 | fmset.insert(ordered_range, int_mset2.begin(), int_mset2.end()); | |
142 | std::multiset<int> int_mset5(int_mset2); | |
143 | int_mset4.insert(int_mset5.begin(), int_mset5.end()); | |
144 | if(!CheckEqualContainers(int_mset4, fmset)) | |
145 | return false; | |
146 | //Re-re-insertion of even | |
147 | std::multiset<int> int_even_mset2; | |
148 | for(std::size_t i = 0; i < NumElements; i+=2){ | |
149 | int_even_mset2.insert(static_cast<int>(i)); | |
150 | } | |
151 | fmset.reserve(fmset.size() + int_even_mset2.size()); | |
152 | fmset.insert(ordered_range, int_even_mset2.begin(), int_even_mset2.end()); | |
153 | int_mset4.insert(int_even_mset2.begin(), int_even_mset2.end()); | |
154 | if(!CheckEqualContainers(int_mset4, fmset)) | |
155 | return false; | |
156 | } | |
157 | ||
158 | //Ordered insertion set | |
159 | { | |
160 | std::set<int> int_set; | |
161 | for(std::size_t i = 0; i != NumElements; ++i){ | |
162 | int_set.insert(static_cast<int>(i)); | |
163 | } | |
164 | //Construction insertion | |
165 | flat_set<int> fset(ordered_unique_range, int_set.begin(), int_set.end()); | |
166 | if(!CheckEqualContainers(int_set, fset)) | |
167 | return false; | |
168 | //Insertion when empty | |
169 | fset.clear(); | |
170 | fset.insert(ordered_unique_range, int_set.begin(), int_set.end()); | |
171 | if(!CheckEqualContainers(int_set, fset)) | |
172 | return false; | |
173 | //Re-insertion | |
174 | fset.insert(ordered_unique_range, int_set.begin(), int_set.end()); | |
175 | std::set<int> int_set2(int_set); | |
176 | int_set2.insert(int_set.begin(), int_set.end()); | |
177 | if(!CheckEqualContainers(int_set2, fset)) | |
178 | return false; | |
179 | //Re-re-insertion | |
180 | fset.insert(ordered_unique_range, int_set2.begin(), int_set2.end()); | |
181 | std::set<int> int_set4(int_set2); | |
182 | int_set4.insert(int_set2.begin(), int_set2.end()); | |
183 | if(!CheckEqualContainers(int_set4, fset)) | |
184 | return false; | |
185 | //Re-re-insertion of even | |
186 | std::set<int> int_even_set; | |
187 | for(std::size_t i = 0; i < NumElements; i+=2){ | |
188 | int_even_set.insert(static_cast<int>(i)); | |
189 | } | |
190 | fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end()); | |
191 | int_set4.insert(int_even_set.begin(), int_even_set.end()); | |
192 | if(!CheckEqualContainers(int_set4, fset)) | |
193 | return false; | |
194 | //Partial Re-re-insertion of even | |
195 | int_even_set.clear(); | |
196 | for(std::size_t i = 0; i < NumElements; i+=4){ | |
197 | int_even_set.insert(static_cast<int>(i)); | |
198 | } | |
199 | fset.clear(); | |
200 | int_set4.clear(); | |
201 | //insert 0,4,8,12... | |
202 | fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end()); | |
203 | int_set4.insert(int_even_set.begin(), int_even_set.end()); | |
204 | if(!CheckEqualContainers(int_set4, fset)) | |
205 | return false; | |
206 | for(std::size_t i = 2; i < NumElements; i+=4){ | |
207 | int_even_set.insert(static_cast<int>(i)); | |
208 | } | |
209 | //insert 0,2,4,6,8,10,12... | |
210 | fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end()); | |
211 | int_set4.insert(int_even_set.begin(), int_even_set.end()); | |
212 | if(!CheckEqualContainers(int_set4, fset)) | |
213 | return false; | |
214 | int_even_set.clear(); | |
215 | for(std::size_t i = 0; i < NumElements; i+=8){ | |
216 | int_even_set.insert(static_cast<int>(i)); | |
217 | } | |
218 | fset.clear(); | |
219 | int_set4.clear(); | |
220 | //insert 0,8,16... | |
221 | fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end()); | |
222 | int_set4.insert(int_even_set.begin(), int_even_set.end()); | |
223 | if(!CheckEqualContainers(int_set4, fset)) | |
224 | return false; | |
225 | for(std::size_t i = 0; i < NumElements; i+=2){ | |
226 | int_even_set.insert(static_cast<int>(i)); | |
227 | } | |
228 | //insert 0,2,4,6,8,10,12... | |
229 | fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end()); | |
230 | int_set4.insert(int_even_set.begin(), int_even_set.end()); | |
231 | if(!CheckEqualContainers(int_set4, fset)) | |
232 | return false; | |
233 | ||
234 | ||
235 | int_even_set.clear(); | |
236 | for(std::size_t i = 0; i < NumElements; i+=8){ | |
237 | int_even_set.insert(static_cast<int>(i)); | |
238 | int_even_set.insert(static_cast<int>(i+2)); | |
239 | } | |
240 | int_even_set.insert(static_cast<int>(NumElements-2)); | |
241 | fset.clear(); | |
242 | int_set4.clear(); | |
243 | //insert 0,2,8,10... | |
244 | fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end()); | |
245 | int_set4.insert(int_even_set.begin(), int_even_set.end()); | |
246 | if(!CheckEqualContainers(int_set4, fset)) | |
247 | return false; | |
248 | for(std::size_t i = 0; i < NumElements; i+=2){ | |
249 | int_even_set.insert(static_cast<int>(i)); | |
250 | } | |
251 | //insert 0,2,4,6,8,10,12... | |
252 | fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end()); | |
253 | int_set4.insert(int_even_set.begin(), int_even_set.end()); | |
254 | if(!CheckEqualContainers(int_set4, fset)) | |
255 | return false; | |
11fdf7f2 TL |
256 | |
257 | //add even/odd values with not enough capacity | |
258 | flat_set<int>().swap(fset); | |
259 | int_set4.clear(); | |
260 | int_set.clear(); | |
261 | ||
262 | fset.reserve(int_even_set.size()); | |
263 | fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end()); | |
264 | int_set4.insert(int_even_set.begin(), int_even_set.end()); | |
265 | ||
266 | for(std::size_t i = 0; i < NumElements*2; i+=2){ | |
267 | int_set.insert(static_cast<int>(i)); | |
268 | int_set.insert(static_cast<int>(i+1)); | |
269 | } | |
270 | ||
271 | fset.insert(ordered_unique_range, int_set.begin(), int_set.end()); | |
272 | int_set4.insert(int_set.begin(), int_set.end()); | |
273 | if(!CheckEqualContainers(int_set4, fset)) | |
274 | return false; | |
7c673cae FG |
275 | } |
276 | ||
277 | return true; | |
278 | } | |
279 | ||
92f5a8d4 TL |
280 | bool constructor_template_auto_deduction_test() |
281 | { | |
282 | ||
283 | #ifndef BOOST_CONTAINER_NO_CXX17_CTAD | |
284 | using namespace boost::container; | |
285 | const std::size_t NumElements = 100; | |
286 | { | |
287 | std::set<int> int_set; | |
288 | for (std::size_t i = 0; i != NumElements; ++i) { | |
289 | int_set.insert(static_cast<int>(i)); | |
290 | } | |
291 | std::multiset<int> int_mset; | |
292 | for (std::size_t i = 0; i != NumElements; ++i) { | |
293 | int_mset.insert(static_cast<int>(i)); | |
294 | } | |
295 | ||
296 | typedef std::less<int> comp_int_t; | |
297 | typedef std::allocator<int> alloc_int_t; | |
298 | ||
299 | //range | |
300 | { | |
301 | auto fset = flat_set(int_set.begin(), int_set.end()); | |
302 | if (!CheckEqualContainers(int_set, fset)) | |
303 | return false; | |
304 | auto fmset = flat_multiset(int_mset.begin(), int_mset.end()); | |
305 | if (!CheckEqualContainers(int_mset, fmset)) | |
306 | return false; | |
307 | } | |
308 | //range+comp | |
309 | { | |
310 | auto fset = flat_set(int_set.begin(), int_set.end(), comp_int_t()); | |
311 | if (!CheckEqualContainers(int_set, fset)) | |
312 | return false; | |
313 | auto fmset = flat_multiset(int_mset.begin(), int_mset.end(), comp_int_t()); | |
314 | if (!CheckEqualContainers(int_mset, fmset)) | |
315 | return false; | |
316 | } | |
317 | //range+comp+alloc | |
318 | { | |
319 | auto fset = flat_set(int_set.begin(), int_set.end(), comp_int_t(), alloc_int_t()); | |
320 | if (!CheckEqualContainers(int_set, fset)) | |
321 | return false; | |
322 | auto fmset = flat_multiset(int_mset.begin(), int_mset.end(), comp_int_t(), alloc_int_t()); | |
323 | if (!CheckEqualContainers(int_mset, fmset)) | |
324 | return false; | |
325 | } | |
326 | //range+alloc | |
327 | { | |
328 | auto fset = flat_set(int_set.begin(), int_set.end(), alloc_int_t()); | |
329 | if (!CheckEqualContainers(int_set, fset)) | |
330 | return false; | |
331 | auto fmset = flat_multiset(int_mset.begin(), int_mset.end(), alloc_int_t()); | |
332 | if (!CheckEqualContainers(int_mset, fmset)) | |
333 | return false; | |
334 | } | |
335 | ||
336 | //ordered_unique_range / ordered_range | |
337 | ||
338 | //range | |
339 | { | |
340 | auto fset = flat_set(ordered_unique_range, int_set.begin(), int_set.end()); | |
341 | if (!CheckEqualContainers(int_set, fset)) | |
342 | return false; | |
343 | auto fmset = flat_multiset(ordered_range, int_mset.begin(), int_mset.end()); | |
344 | if (!CheckEqualContainers(int_mset, fmset)) | |
345 | return false; | |
346 | } | |
347 | //range+comp | |
348 | { | |
349 | auto fset = flat_set(ordered_unique_range, int_set.begin(), int_set.end(), comp_int_t()); | |
350 | if (!CheckEqualContainers(int_set, fset)) | |
351 | return false; | |
352 | auto fmset = flat_multiset(ordered_range, int_mset.begin(), int_mset.end(), comp_int_t()); | |
353 | if (!CheckEqualContainers(int_mset, fmset)) | |
354 | return false; | |
355 | } | |
356 | //range+comp+alloc | |
357 | { | |
358 | auto fset = flat_set(ordered_unique_range, int_set.begin(), int_set.end(), comp_int_t(), alloc_int_t()); | |
359 | if (!CheckEqualContainers(int_set, fset)) | |
360 | return false; | |
361 | auto fmset = flat_multiset(ordered_range, int_mset.begin(), int_mset.end(), comp_int_t(), alloc_int_t()); | |
362 | if (!CheckEqualContainers(int_mset, fmset)) | |
363 | return false; | |
364 | } | |
365 | //range+alloc | |
366 | { | |
367 | auto fset = flat_set(ordered_unique_range, int_set.begin(), int_set.end(), alloc_int_t()); | |
368 | if (!CheckEqualContainers(int_set, fset)) | |
369 | return false; | |
370 | auto fmset = flat_multiset(ordered_range, int_mset.begin(), int_mset.end(), alloc_int_t()); | |
371 | if (!CheckEqualContainers(int_mset, fmset)) | |
372 | return false; | |
373 | } | |
374 | } | |
375 | #endif | |
376 | ||
377 | return true; | |
378 | } | |
379 | ||
b32b8144 FG |
380 | template< class RandomIt > |
381 | void random_shuffle( RandomIt first, RandomIt last ) | |
382 | { | |
383 | typedef typename boost::container::iterator_traits<RandomIt>::difference_type difference_type; | |
384 | difference_type n = last - first; | |
385 | for (difference_type i = n-1; i > 0; --i) { | |
386 | difference_type j = std::rand() % (i+1); | |
387 | if(j != i) { | |
388 | boost::adl_move_swap(first[i], first[j]); | |
389 | } | |
390 | } | |
391 | } | |
7c673cae | 392 | |
b32b8144 FG |
393 | bool flat_tree_extract_adopt_test() |
394 | { | |
395 | using namespace boost::container; | |
396 | const std::size_t NumElements = 100; | |
7c673cae | 397 | |
b32b8144 FG |
398 | //extract/adopt set |
399 | { | |
400 | //Construction insertion | |
401 | flat_set<int> fset; | |
402 | ||
403 | for(std::size_t i = 0; i != NumElements; ++i){ | |
404 | fset.insert(static_cast<int>(i)); | |
405 | } | |
406 | ||
407 | flat_set<int> fset_copy(fset); | |
408 | flat_set<int>::sequence_type seq(fset.extract_sequence()); | |
409 | if(!fset.empty()) | |
410 | return false; | |
411 | if(!CheckEqualContainers(seq, fset_copy)) | |
412 | return false; | |
413 | ||
414 | seq.insert(seq.end(), fset_copy.begin(), fset_copy.end()); | |
415 | boost::container::test::random_shuffle(seq.begin(), seq.end()); | |
416 | fset.adopt_sequence(boost::move(seq)); | |
417 | if(!CheckEqualContainers(fset, fset_copy)) | |
418 | return false; | |
419 | } | |
420 | ||
421 | //extract/adopt set, ordered_unique_range | |
422 | { | |
423 | //Construction insertion | |
424 | flat_set<int> fset; | |
425 | ||
426 | for(std::size_t i = 0; i != NumElements; ++i){ | |
427 | fset.insert(static_cast<int>(i)); | |
428 | } | |
429 | ||
430 | flat_set<int> fset_copy(fset); | |
431 | flat_set<int>::sequence_type seq(fset.extract_sequence()); | |
432 | if(!fset.empty()) | |
433 | return false; | |
434 | if(!CheckEqualContainers(seq, fset_copy)) | |
435 | return false; | |
436 | ||
437 | fset.adopt_sequence(ordered_unique_range, boost::move(seq)); | |
438 | if(!CheckEqualContainers(fset, fset_copy)) | |
439 | return false; | |
440 | } | |
441 | ||
442 | //extract/adopt multiset | |
443 | { | |
444 | //Construction insertion | |
445 | flat_multiset<int> fmset; | |
446 | ||
447 | for(std::size_t i = 0; i != NumElements; ++i){ | |
448 | fmset.insert(static_cast<int>(i)); | |
449 | fmset.insert(static_cast<int>(i)); | |
450 | } | |
451 | ||
452 | flat_multiset<int> fmset_copy(fmset); | |
453 | flat_multiset<int>::sequence_type seq(fmset.extract_sequence()); | |
454 | if(!fmset.empty()) | |
455 | return false; | |
456 | if(!CheckEqualContainers(seq, fmset_copy)) | |
457 | return false; | |
458 | ||
459 | boost::container::test::random_shuffle(seq.begin(), seq.end()); | |
460 | fmset.adopt_sequence(boost::move(seq)); | |
461 | if(!CheckEqualContainers(fmset, fmset_copy)) | |
462 | return false; | |
463 | } | |
464 | ||
465 | //extract/adopt multiset, ordered_range | |
466 | { | |
467 | //Construction insertion | |
468 | flat_multiset<int> fmset; | |
469 | ||
470 | for(std::size_t i = 0; i != NumElements; ++i){ | |
471 | fmset.insert(static_cast<int>(i)); | |
472 | fmset.insert(static_cast<int>(i)); | |
473 | } | |
474 | ||
475 | flat_multiset<int> fmset_copy(fmset); | |
476 | flat_multiset<int>::sequence_type seq(fmset.extract_sequence()); | |
477 | if(!fmset.empty()) | |
478 | return false; | |
479 | if(!CheckEqualContainers(seq, fmset_copy)) | |
480 | return false; | |
481 | ||
482 | fmset.adopt_sequence(ordered_range, boost::move(seq)); | |
483 | if(!CheckEqualContainers(fmset, fmset_copy)) | |
484 | return false; | |
485 | } | |
486 | ||
487 | return true; | |
488 | } | |
489 | ||
92f5a8d4 TL |
490 | bool test_heterogeneous_lookups() |
491 | { | |
492 | typedef flat_set<int, test::less_transparent> set_t; | |
493 | typedef flat_multiset<int, test::less_transparent> mset_t; | |
494 | ||
495 | set_t set1; | |
496 | mset_t mset1; | |
497 | ||
498 | const set_t &cset1 = set1; | |
499 | const mset_t &cmset1 = mset1; | |
500 | ||
501 | set1.insert(1); | |
502 | set1.insert(1); | |
503 | set1.insert(2); | |
504 | set1.insert(2); | |
505 | set1.insert(3); | |
506 | ||
507 | mset1.insert(1); | |
508 | mset1.insert(1); | |
509 | mset1.insert(2); | |
510 | mset1.insert(2); | |
511 | mset1.insert(3); | |
512 | ||
513 | const test::non_copymovable_int find_me(2); | |
514 | ||
515 | //find | |
516 | if(*set1.find(find_me) != 2) | |
517 | return false; | |
518 | if(*cset1.find(find_me) != 2) | |
519 | return false; | |
520 | if(*mset1.find(find_me) != 2) | |
521 | return false; | |
522 | if(*cmset1.find(find_me) != 2) | |
523 | return false; | |
524 | ||
525 | //count | |
526 | if(set1.count(find_me) != 1) | |
527 | return false; | |
528 | if(cset1.count(find_me) != 1) | |
529 | return false; | |
530 | if(mset1.count(find_me) != 2) | |
531 | return false; | |
532 | if(cmset1.count(find_me) != 2) | |
533 | return false; | |
534 | ||
535 | //contains | |
536 | if(!set1.contains(find_me)) | |
537 | return false; | |
538 | if(!cset1.contains(find_me)) | |
539 | return false; | |
540 | if(!mset1.contains(find_me)) | |
541 | return false; | |
542 | if(!cmset1.contains(find_me)) | |
543 | return false; | |
544 | ||
545 | //lower_bound | |
546 | if(*set1.lower_bound(find_me) != 2) | |
547 | return false; | |
548 | if(*cset1.lower_bound(find_me) != 2) | |
549 | return false; | |
550 | if(*mset1.lower_bound(find_me) != 2) | |
551 | return false; | |
552 | if(*cmset1.lower_bound(find_me) != 2) | |
553 | return false; | |
554 | ||
555 | //upper_bound | |
556 | if(*set1.upper_bound(find_me) != 3) | |
557 | return false; | |
558 | if(*cset1.upper_bound(find_me) != 3) | |
559 | return false; | |
560 | if(*mset1.upper_bound(find_me) != 3) | |
561 | return false; | |
562 | if(*cmset1.upper_bound(find_me) != 3) | |
563 | return false; | |
564 | ||
565 | //equal_range | |
566 | if(*set1.equal_range(find_me).first != 2) | |
567 | return false; | |
568 | if(*cset1.equal_range(find_me).second != 3) | |
569 | return false; | |
570 | if(*mset1.equal_range(find_me).first != 2) | |
571 | return false; | |
572 | if(*cmset1.equal_range(find_me).second != 3) | |
573 | return false; | |
574 | ||
575 | return true; | |
576 | } | |
577 | ||
578 | // An ordered sequence of std:pair is also ordered by std::pair::first. | |
579 | struct with_lookup_by_first | |
580 | { | |
581 | typedef void is_transparent; | |
582 | inline bool operator()(std::pair<int, int> a, std::pair<int, int> b) const | |
583 | { | |
584 | return a < b; | |
585 | } | |
586 | inline bool operator()(std::pair<int, int> a, int first) const | |
587 | { | |
588 | return a.first < first; | |
589 | } | |
590 | inline bool operator()(int first, std::pair<int, int> b) const | |
591 | { | |
592 | return first < b.first; | |
593 | } | |
594 | }; | |
595 | ||
596 | bool test_heterogeneous_lookup_by_partial_key() | |
597 | { | |
598 | typedef flat_set<std::pair<int, int>, with_lookup_by_first> set_t; | |
599 | ||
600 | set_t set1; | |
601 | set1.insert(std::pair<int, int>(0, 1)); | |
602 | set1.insert(std::pair<int, int>(0, 2)); | |
603 | ||
604 | std::pair<set_t::iterator, set_t::iterator> const first_0_range = set1.equal_range(0); | |
605 | if(2 != (first_0_range.second - first_0_range.first)) | |
606 | return false; | |
607 | ||
608 | if(2 != set1.count(0)) | |
609 | return false; | |
610 | return true; | |
611 | } | |
612 | ||
b32b8144 FG |
613 | }}} |
614 | ||
615 | template<class VoidAllocatorOrContainer> | |
616 | struct GetSetContainer | |
7c673cae FG |
617 | { |
618 | template<class ValueType> | |
619 | struct apply | |
620 | { | |
621 | typedef flat_set < ValueType | |
622 | , std::less<ValueType> | |
11fdf7f2 | 623 | , typename boost::container::dtl::container_or_allocator_rebind<VoidAllocatorOrContainer, ValueType>::type |
7c673cae FG |
624 | > set_type; |
625 | ||
626 | typedef flat_multiset < ValueType | |
627 | , std::less<ValueType> | |
11fdf7f2 | 628 | , typename boost::container::dtl::container_or_allocator_rebind<VoidAllocatorOrContainer, ValueType>::type |
7c673cae FG |
629 | > multiset_type; |
630 | }; | |
631 | }; | |
632 | ||
7c673cae FG |
633 | template<typename FlatSetType> |
634 | bool test_support_for_initialization_list_for() | |
635 | { | |
636 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
637 | const std::initializer_list<int> il | |
638 | = {1, 2}; | |
639 | ||
640 | const FlatSetType expected(il.begin(), il.end()); | |
641 | { | |
642 | const FlatSetType sil = il; | |
643 | if (sil != expected) | |
644 | return false; | |
645 | ||
646 | const FlatSetType sil_ordered(ordered_unique_range, il); | |
647 | if(sil_ordered != expected) | |
648 | return false; | |
649 | ||
650 | FlatSetType sil_assign = {99}; | |
651 | sil_assign = il; | |
652 | if(sil_assign != expected) | |
653 | return false; | |
654 | } | |
655 | { | |
656 | FlatSetType sil; | |
657 | sil.insert(il); | |
658 | if(sil != expected) | |
659 | return false; | |
660 | } | |
661 | return true; | |
662 | #endif | |
663 | return true; | |
664 | } | |
665 | ||
666 | struct boost_container_flat_set; | |
667 | struct boost_container_flat_multiset; | |
668 | ||
669 | namespace boost { | |
670 | namespace container { | |
671 | namespace test { | |
672 | ||
673 | template<> | |
674 | struct alloc_propagate_base<boost_container_flat_set> | |
675 | { | |
676 | template <class T, class Allocator> | |
677 | struct apply | |
678 | { | |
679 | typedef boost::container::flat_set<T, std::less<T>, Allocator> type; | |
680 | }; | |
681 | }; | |
682 | ||
683 | template<> | |
684 | struct alloc_propagate_base<boost_container_flat_multiset> | |
685 | { | |
686 | template <class T, class Allocator> | |
687 | struct apply | |
688 | { | |
689 | typedef boost::container::flat_multiset<T, std::less<T>, Allocator> type; | |
690 | }; | |
691 | }; | |
692 | ||
693 | }}} //boost::container::test | |
694 | ||
695 | int main() | |
696 | { | |
697 | using namespace boost::container::test; | |
698 | ||
699 | //Allocator argument container | |
700 | { | |
701 | flat_set<int> set_((flat_set<int>::allocator_type())); | |
702 | flat_multiset<int> multiset_((flat_multiset<int>::allocator_type())); | |
703 | } | |
704 | //Now test move semantics | |
705 | { | |
706 | test_move<flat_set<recursive_flat_set> >(); | |
707 | test_move<flat_multiset<recursive_flat_multiset> >(); | |
708 | } | |
709 | //Now test nth/index_of | |
710 | { | |
711 | flat_set<int> set; | |
712 | flat_multiset<int> mset; | |
713 | ||
714 | set.insert(0); | |
715 | set.insert(1); | |
716 | set.insert(2); | |
717 | mset.insert(0); | |
718 | mset.insert(1); | |
719 | mset.insert(2); | |
720 | if(!boost::container::test::test_nth_index_of(set)) | |
721 | return 1; | |
722 | if(!boost::container::test::test_nth_index_of(mset)) | |
723 | return 1; | |
724 | } | |
725 | ||
726 | //////////////////////////////////// | |
727 | // Ordered insertion test | |
728 | //////////////////////////////////// | |
729 | if(!flat_tree_ordered_insertion_test()){ | |
730 | return 1; | |
731 | } | |
732 | ||
92f5a8d4 TL |
733 | //////////////////////////////////// |
734 | // Constructor Template Auto Deduction test | |
735 | //////////////////////////////////// | |
736 | if (!constructor_template_auto_deduction_test()) { | |
737 | return 1; | |
738 | } | |
739 | ||
b32b8144 FG |
740 | //////////////////////////////////// |
741 | // Extract/Adopt test | |
742 | //////////////////////////////////// | |
743 | if(!flat_tree_extract_adopt_test()){ | |
744 | return 1; | |
745 | } | |
746 | ||
747 | if (!boost::container::test::instantiate_constructors<flat_set<int>, flat_multiset<int> >()) | |
748 | return 1; | |
749 | ||
92f5a8d4 | 750 | if(!test_heterogeneous_lookups()){ |
7c673cae FG |
751 | return 1; |
752 | } | |
92f5a8d4 TL |
753 | |
754 | if(!test_heterogeneous_lookup_by_partial_key()){ | |
7c673cae FG |
755 | return 1; |
756 | } | |
757 | ||
92f5a8d4 TL |
758 | //////////////////////////////////// |
759 | // Testing allocator implementations | |
760 | //////////////////////////////////// | |
761 | { | |
762 | typedef std::set<int> MyStdSet; | |
763 | typedef std::multiset<int> MyStdMultiSet; | |
764 | ||
765 | if (0 != test::set_test | |
766 | < GetSetContainer<std::allocator<void> >::apply<int>::set_type | |
767 | , MyStdSet | |
768 | , GetSetContainer<std::allocator<void> >::apply<int>::multiset_type | |
769 | , MyStdMultiSet>()) { | |
770 | std::cout << "Error in set_test<std::allocator<void> >" << std::endl; | |
771 | return 1; | |
772 | } | |
773 | ||
774 | if (0 != test::set_test | |
775 | < GetSetContainer<new_allocator<void> >::apply<int>::set_type | |
776 | , MyStdSet | |
777 | , GetSetContainer<new_allocator<void> >::apply<int>::multiset_type | |
778 | , MyStdMultiSet>()) { | |
779 | std::cout << "Error in set_test<new_allocator<void> >" << std::endl; | |
780 | return 1; | |
781 | } | |
782 | ||
783 | if (0 != test::set_test | |
784 | < GetSetContainer<new_allocator<void> >::apply<test::movable_int>::set_type | |
785 | , MyStdSet | |
786 | , GetSetContainer<new_allocator<void> >::apply<test::movable_int>::multiset_type | |
787 | , MyStdMultiSet>()) { | |
788 | std::cout << "Error in set_test<new_allocator<void> >" << std::endl; | |
789 | return 1; | |
790 | } | |
791 | ||
792 | if (0 != test::set_test | |
793 | < GetSetContainer<new_allocator<void> >::apply<test::copyable_int>::set_type | |
794 | , MyStdSet | |
795 | , GetSetContainer<new_allocator<void> >::apply<test::copyable_int>::multiset_type | |
796 | , MyStdMultiSet>()) { | |
797 | std::cout << "Error in set_test<new_allocator<void> >" << std::endl; | |
798 | return 1; | |
799 | } | |
800 | ||
801 | if (0 != test::set_test | |
802 | < GetSetContainer<new_allocator<void> >::apply<test::movable_and_copyable_int>::set_type | |
803 | , MyStdSet | |
804 | , GetSetContainer<new_allocator<void> >::apply<test::movable_and_copyable_int>::multiset_type | |
805 | , MyStdMultiSet>()) { | |
806 | std::cout << "Error in set_test<new_allocator<void> >" << std::endl; | |
807 | return 1; | |
808 | } | |
809 | } | |
810 | ||
7c673cae FG |
811 | //////////////////////////////////// |
812 | // Emplace testing | |
813 | //////////////////////////////////// | |
814 | const test::EmplaceOptions SetOptions = (test::EmplaceOptions)(test::EMPLACE_HINT | test::EMPLACE_ASSOC); | |
815 | ||
816 | if(!boost::container::test::test_emplace<flat_set<test::EmplaceInt>, SetOptions>()) | |
817 | return 1; | |
818 | if(!boost::container::test::test_emplace<flat_multiset<test::EmplaceInt>, SetOptions>()) | |
819 | return 1; | |
820 | ||
821 | if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for<flat_set<int> >()) | |
822 | return 1; | |
823 | ||
824 | if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for<flat_multiset<int> >()) | |
825 | return 1; | |
826 | ||
827 | //////////////////////////////////// | |
828 | // Allocator propagation testing | |
829 | //////////////////////////////////// | |
830 | if(!boost::container::test::test_propagate_allocator<boost_container_flat_set>()) | |
831 | return 1; | |
832 | ||
833 | if(!boost::container::test::test_propagate_allocator<boost_container_flat_multiset>()) | |
834 | return 1; | |
835 | ||
836 | //////////////////////////////////// | |
837 | // Iterator testing | |
838 | //////////////////////////////////// | |
839 | { | |
840 | typedef boost::container::flat_set<int> cont_int; | |
841 | cont_int a; a.insert(0); a.insert(1); a.insert(2); | |
842 | boost::intrusive::test::test_iterator_random< cont_int >(a); | |
843 | if(boost::report_errors() != 0) { | |
844 | return 1; | |
845 | } | |
846 | } | |
847 | { | |
848 | typedef boost::container::flat_multiset<int> cont_int; | |
849 | cont_int a; a.insert(0); a.insert(1); a.insert(2); | |
850 | boost::intrusive::test::test_iterator_random< cont_int >(a); | |
851 | if(boost::report_errors() != 0) { | |
852 | return 1; | |
853 | } | |
854 | } | |
855 | ||
92f5a8d4 TL |
856 | //////////////////////////////////// |
857 | // has_trivial_destructor_after_move testing | |
858 | //////////////////////////////////// | |
859 | { | |
860 | typedef boost::container::dtl::identity<int> key_of_value_t; | |
861 | // flat_set, default | |
862 | { | |
863 | typedef boost::container::flat_set<int> cont; | |
864 | typedef boost::container::dtl::flat_tree<int, key_of_value_t, std::less<int>, void> tree; | |
20effc67 TL |
865 | BOOST_STATIC_ASSERT_MSG ( boost::has_trivial_destructor_after_move<cont>::value == |
866 | boost::has_trivial_destructor_after_move<tree>::value | |
867 | , "has_trivial_destructor_after_move(flat_set, default) test failed"); | |
92f5a8d4 TL |
868 | } |
869 | // flat_set, vector | |
870 | { | |
871 | typedef boost::container::vector<int> alloc_or_cont_t; | |
872 | typedef boost::container::flat_set<int, std::less<int>, alloc_or_cont_t> cont; | |
873 | typedef boost::container::dtl::flat_tree<int, key_of_value_t, std::less<int>, alloc_or_cont_t> tree; | |
20effc67 TL |
874 | BOOST_STATIC_ASSERT_MSG ( boost::has_trivial_destructor_after_move<cont>::value == |
875 | boost::has_trivial_destructor_after_move<tree>::value | |
876 | , "has_trivial_destructor_after_move(flat_set, vector) test failed"); | |
92f5a8d4 TL |
877 | } |
878 | // flat_set, std::vector | |
879 | { | |
880 | typedef std::vector<int> alloc_or_cont_t; | |
881 | typedef boost::container::flat_set<int, std::less<int>, alloc_or_cont_t> cont; | |
882 | typedef boost::container::dtl::flat_tree<int, key_of_value_t, std::less<int>, alloc_or_cont_t> tree; | |
20effc67 TL |
883 | BOOST_STATIC_ASSERT_MSG ( boost::has_trivial_destructor_after_move<cont>::value == |
884 | boost::has_trivial_destructor_after_move<tree>::value | |
885 | , "has_trivial_destructor_after_move(flat_set, std::vector) test failed"); | |
92f5a8d4 TL |
886 | } |
887 | // flat_multiset, default | |
888 | { | |
889 | typedef boost::container::flat_multiset<int> cont; | |
890 | typedef boost::container::dtl::flat_tree<int, key_of_value_t, std::less<int>, void> tree; | |
20effc67 TL |
891 | BOOST_STATIC_ASSERT_MSG ( boost::has_trivial_destructor_after_move<cont>::value == |
892 | boost::has_trivial_destructor_after_move<tree>::value | |
893 | , "has_trivial_destructor_after_move(flat_multiset, default) test failed"); | |
92f5a8d4 TL |
894 | } |
895 | // flat_multiset, vector | |
896 | { | |
897 | typedef boost::container::vector<int> alloc_or_cont_t; | |
898 | typedef boost::container::flat_multiset<int, std::less<int>, alloc_or_cont_t> cont; | |
899 | typedef boost::container::dtl::flat_tree<int, key_of_value_t, std::less<int>, alloc_or_cont_t> tree; | |
20effc67 TL |
900 | BOOST_STATIC_ASSERT_MSG ( boost::has_trivial_destructor_after_move<cont>::value == |
901 | boost::has_trivial_destructor_after_move<tree>::value | |
902 | , "has_trivial_destructor_after_move(flat_multiset, vector) test failed"); | |
92f5a8d4 TL |
903 | } |
904 | // flat_multiset, std::vector | |
905 | { | |
906 | typedef std::vector<int> alloc_or_cont_t; | |
907 | typedef boost::container::flat_multiset<int, std::less<int>, alloc_or_cont_t> cont; | |
908 | typedef boost::container::dtl::flat_tree<int, key_of_value_t, std::less<int>, alloc_or_cont_t> tree; | |
20effc67 TL |
909 | BOOST_STATIC_ASSERT_MSG ( boost::has_trivial_destructor_after_move<cont>::value == |
910 | boost::has_trivial_destructor_after_move<tree>::value | |
911 | , "has_trivial_destructor_after_move(flat_multiset, std::vector) test failed"); | |
92f5a8d4 TL |
912 | } |
913 | } | |
914 | ||
7c673cae FG |
915 | return 0; |
916 | } |