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