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#include <set>
11#include <boost/container/set.hpp>
12#include <boost/container/adaptive_pool.hpp>
13
14#include "print_container.hpp"
15#include "movable_int.hpp"
16#include "dummy_test_allocator.hpp"
17#include "set_test.hpp"
18#include "propagate_allocator_test.hpp"
19#include "emplace_test.hpp"
20#include "../../intrusive/test/iterator_test.hpp"
21#include <utility> //for std::pair
22
23using namespace boost::container;
24
25//Test recursive structures
26class recursive_set
27{
28public:
29 recursive_set()
30 {}
31
32 recursive_set(const recursive_set &x)
33 : set_(x.set_)
34 {}
35
36 recursive_set & operator=(const recursive_set &x)
37 { id_ = x.id_; set_ = x.set_; return *this; }
38
39 int id_;
40 set<recursive_set> set_;
41 set<recursive_set>::iterator it_;
42 set<recursive_set>::const_iterator cit_;
43 set<recursive_set>::reverse_iterator rit_;
44 set<recursive_set>::const_reverse_iterator crit_;
45
46 friend bool operator< (const recursive_set &a, const recursive_set &b)
47 { return a.id_ < b.id_; }
48};
49
50//Test recursive structures
51class recursive_multiset
52{
53 public:
54 recursive_multiset()
55 {}
56
57 recursive_multiset(const recursive_multiset &x)
58 : multiset_(x.multiset_)
59 {}
60
61 recursive_multiset & operator=(const recursive_multiset &x)
62 { id_ = x.id_; multiset_ = x.multiset_; return *this; }
63
64 int id_;
65 multiset<recursive_multiset> multiset_;
66 multiset<recursive_multiset>::iterator it_;
67 multiset<recursive_multiset>::const_iterator cit_;
68 multiset<recursive_multiset>::reverse_iterator rit_;
69 multiset<recursive_multiset>::const_reverse_iterator crit_;
70
71 friend bool operator< (const recursive_multiset &a, const recursive_multiset &b)
72 { return a.id_ < b.id_; }
73};
74
75template<class C>
76void test_move()
77{
78 //Now test move semantics
79 C original;
80 original.emplace();
81 C move_ctor(boost::move(original));
82 C move_assign;
83 move_assign.emplace();
84 move_assign = boost::move(move_ctor);
85 move_assign.swap(original);
86}
87
88bool node_type_test()
89{
90 using namespace boost::container;
91 {
92 typedef set<test::movable_int> set_type;
93 set_type src;
94 {
95 test::movable_int mv_1(1), mv_2(2), mv_3(3);
96 src.emplace(args: boost::move(t&: mv_1));
97 src.emplace(args: boost::move(t&: mv_2));
98 src.emplace(args: boost::move(t&: mv_3));
99 }
100 if(src.size() != 3)
101 return false;
102
103 set_type dst;
104 {
105 test::movable_int mv_3(3);
106 dst.emplace(args: boost::move(t&: mv_3));
107 }
108
109 if(dst.size() != 1)
110 return false;
111
112 const test::movable_int mv_1(1);
113 const test::movable_int mv_2(2);
114 const test::movable_int mv_3(3);
115 const test::movable_int mv_33(33);
116 set_type::insert_return_type r;
117
118 r = dst.insert(nh: src.extract(k: mv_33)); // Key version, try to insert empty node
119 if(! (r.position == dst.end() && r.inserted == false && r.node.empty()) )
120 return false;
121 r = dst.insert(nh: src.extract(position: src.find(k: mv_1))); // Iterator version, successful
122 if(! (r.position == dst.find(k: mv_1) && r.inserted == true && r.node.empty()) )
123 return false;
124 r = dst.insert(hint: dst.begin(), nh: src.extract(k: mv_2)); // Key type version, successful
125 if(! (r.position == dst.find(k: mv_2) && r.inserted == true && r.node.empty()) )
126 return false;
127 r = dst.insert(nh: src.extract(k: mv_3)); // Key type version, unsuccessful
128
129 if(!src.empty())
130 return false;
131 if(dst.size() != 3)
132 return false;
133 if(! (r.position == dst.find(k: mv_3) && r.inserted == false && r.node.value() == mv_3) )
134 return false;
135 }
136
137 {
138 typedef multiset<test::movable_int> multiset_type;
139 multiset_type src;
140 {
141 test::movable_int mv_1(1), mv_2(2), mv_3(3), mv_3bis(3);
142 src.emplace(args: boost::move(t&: mv_1));
143 src.emplace(args: boost::move(t&: mv_2));
144 src.emplace(args: boost::move(t&: mv_3));
145 src.emplace_hint(p: src.begin(), args: boost::move(t&: mv_3bis));
146 }
147 if(src.size() != 4)
148 return false;
149
150 multiset_type dst;
151 {
152 test::movable_int mv_3(3);
153 dst.emplace(args: boost::move(t&: mv_3));
154 }
155
156 if(dst.size() != 1)
157 return false;
158
159 const test::movable_int mv_1(1);
160 const test::movable_int mv_2(2);
161 const test::movable_int mv_3(3);
162 const test::movable_int mv_4(4);
163 multiset_type::iterator r;
164
165 multiset_type::node_type nt(src.extract(k: mv_3));
166 r = dst.insert(hint: dst.begin(), nh: boost::move(t&: nt));
167 if(! (*r == mv_3 && dst.find(k: mv_3) == r && nt.empty()) )
168 return false;
169
170 nt = src.extract(position: src.find(k: mv_1));
171 r = dst.insert(nh: boost::move(t&: nt)); // Iterator version, successful
172 if(! (*r == mv_1 && nt.empty()) )
173 return false;
174
175 nt = src.extract(k: mv_2);
176 r = dst.insert(nh: boost::move(t&: nt)); // Key type version, successful
177 if(! (*r == mv_2 && nt.empty()) )
178 return false;
179
180 r = dst.insert(nh: src.extract(k: mv_3)); // Key type version, successful
181 if(! (*r == mv_3 && r == --multiset_type::iterator(dst.upper_bound(k: mv_3)) && nt.empty()) )
182 return false;
183
184 r = dst.insert(nh: src.extract(k: mv_4)); // Key type version, unsuccessful
185 if(! (r == dst.end()) )
186 return false;
187
188 if(!src.empty())
189 return false;
190 if(dst.size() != 5)
191 return false;
192 }
193 return true;
194}
195
196struct boost_container_set;
197struct boost_container_multiset;
198
199namespace boost {
200namespace container {
201namespace test {
202
203template<>
204struct alloc_propagate_base<boost_container_set>
205{
206 template <class T, class Allocator>
207 struct apply
208 {
209 typedef boost::container::set<T, std::less<T>, Allocator> type;
210 };
211};
212
213template<>
214struct alloc_propagate_base<boost_container_multiset>
215{
216 template <class T, class Allocator>
217 struct apply
218 {
219 typedef boost::container::multiset<T, std::less<T>, Allocator> type;
220 };
221};
222
223bool constructor_template_auto_deduction_test()
224{
225#ifndef BOOST_CONTAINER_NO_CXX17_CTAD
226 using namespace boost::container;
227 const std::size_t NumElements = 100;
228 {
229 std::set<int> int_set;
230 for (std::size_t i = 0; i != NumElements; ++i) {
231 int_set.insert(x: static_cast<int>(i));
232 }
233 std::multiset<int> int_mset;
234 for (std::size_t i = 0; i != NumElements; ++i) {
235 int_mset.insert(x: static_cast<int>(i));
236 }
237
238 typedef std::less<int> comp_int_t;
239 typedef std::allocator<int> alloc_int_t;
240
241 //range
242 {
243 auto fset = set(int_set.begin(), int_set.end());
244 if (!CheckEqualContainers(cont_a: int_set, cont_b: fset))
245 return false;
246 auto fmset = multiset(int_mset.begin(), int_mset.end());
247 if (!CheckEqualContainers(cont_a: int_mset, cont_b: fmset))
248 return false;
249 }
250 //range+comp
251 {
252 auto fset = set(int_set.begin(), int_set.end(), comp_int_t());
253 if (!CheckEqualContainers(cont_a: int_set, cont_b: fset))
254 return false;
255 auto fmset = multiset(int_mset.begin(), int_mset.end(), comp_int_t());
256 if (!CheckEqualContainers(cont_a: int_mset, cont_b: fmset))
257 return false;
258 }
259 //range+comp+alloc
260 {
261 auto fset = set(int_set.begin(), int_set.end(), comp_int_t(), alloc_int_t());
262 if (!CheckEqualContainers(cont_a: int_set, cont_b: fset))
263 return false;
264 auto fmset = multiset(int_mset.begin(), int_mset.end(), comp_int_t(), alloc_int_t());
265 if (!CheckEqualContainers(cont_a: int_mset, cont_b: fmset))
266 return false;
267 }
268 //range+alloc
269 {
270 auto fset = set(int_set.begin(), int_set.end(), alloc_int_t());
271 if (!CheckEqualContainers(cont_a: int_set, cont_b: fset))
272 return false;
273 auto fmset = multiset(int_mset.begin(), int_mset.end(), alloc_int_t());
274 if (!CheckEqualContainers(cont_a: int_mset, cont_b: fmset))
275 return false;
276 }
277
278 //ordered_unique_range / ordered_range
279
280 //range
281 {
282 auto fset = set(ordered_unique_range, int_set.begin(), int_set.end());
283 if (!CheckEqualContainers(cont_a: int_set, cont_b: fset))
284 return false;
285 auto fmset = multiset(ordered_range, int_mset.begin(), int_mset.end());
286 if (!CheckEqualContainers(cont_a: int_mset, cont_b: fmset))
287 return false;
288 }
289 //range+comp
290 {
291 auto fset = set(ordered_unique_range, int_set.begin(), int_set.end(), comp_int_t());
292 if (!CheckEqualContainers(cont_a: int_set, cont_b: fset))
293 return false;
294 auto fmset = multiset(ordered_range, int_mset.begin(), int_mset.end(), comp_int_t());
295 if (!CheckEqualContainers(cont_a: int_mset, cont_b: fmset))
296 return false;
297 }
298 //range+comp+alloc
299 {
300 auto fset = set(ordered_unique_range, int_set.begin(), int_set.end(), comp_int_t(), alloc_int_t());
301 if (!CheckEqualContainers(cont_a: int_set, cont_b: fset))
302 return false;
303 auto fmset = multiset(ordered_range, int_mset.begin(), int_mset.end(), comp_int_t(), alloc_int_t());
304 if (!CheckEqualContainers(cont_a: int_mset, cont_b: fmset))
305 return false;
306 }
307 //range+alloc
308 {
309 auto fset = set(ordered_unique_range, int_set.begin(), int_set.end(), alloc_int_t());
310 if (!CheckEqualContainers(cont_a: int_set, cont_b: fset))
311 return false;
312 auto fmset = multiset(ordered_range, int_mset.begin(), int_mset.end(), alloc_int_t());
313 if (!CheckEqualContainers(cont_a: int_mset, cont_b: fmset))
314 return false;
315 }
316 }
317#endif
318 return true;
319}
320
321}}} //boost::container::test
322
323template<class VoidAllocator, boost::container::tree_type_enum tree_type_value>
324struct GetAllocatorSet
325{
326 template<class ValueType>
327 struct apply
328 {
329 typedef set < ValueType
330 , std::less<ValueType>
331 , typename allocator_traits<VoidAllocator>
332 ::template portable_rebind_alloc<ValueType>::type
333 , typename boost::container::tree_assoc_options
334 < boost::container::tree_type<tree_type_value>
335 >::type
336 > set_type;
337
338 typedef multiset < ValueType
339 , std::less<ValueType>
340 , typename allocator_traits<VoidAllocator>
341 ::template portable_rebind_alloc<ValueType>::type
342 , typename boost::container::tree_assoc_options
343 < boost::container::tree_type<tree_type_value>
344 >::type
345 > multiset_type;
346 };
347};
348
349void test_merge_from_different_comparison()
350{
351 set<int> set1;
352 set<int, std::greater<int> > set2;
353 set1.merge(source&: set2);
354}
355
356bool test_heterogeneous_lookups()
357{
358 typedef set<int, test::less_transparent> set_t;
359 typedef multiset<int, test::less_transparent> mset_t;
360
361 set_t set1;
362 mset_t mset1;
363
364 const set_t &cset1 = set1;
365 const mset_t &cmset1 = mset1;
366
367 set1.insert(x: 1);
368 set1.insert(x: 1);
369 set1.insert(x: 2);
370 set1.insert(x: 2);
371 set1.insert(x: 3);
372
373 mset1.insert(x: 1);
374 mset1.insert(x: 1);
375 mset1.insert(x: 2);
376 mset1.insert(x: 2);
377 mset1.insert(x: 3);
378
379 const test::non_copymovable_int find_me(2);
380
381 //find
382 if(*set1.find(k: find_me) != 2)
383 return false;
384 if(*cset1.find(k: find_me) != 2)
385 return false;
386 if(*mset1.find(k: find_me) != 2)
387 return false;
388 if(*cmset1.find(k: find_me) != 2)
389 return false;
390
391 //count
392 if(set1.count(x: find_me) != 1)
393 return false;
394 if(cset1.count(x: find_me) != 1)
395 return false;
396 if(mset1.count(k: find_me) != 2)
397 return false;
398 if(cmset1.count(k: find_me) != 2)
399 return false;
400
401 //contains
402 if(!set1.contains(x: find_me))
403 return false;
404 if(!cset1.contains(x: find_me))
405 return false;
406 if(!mset1.contains(x: find_me))
407 return false;
408 if(!cmset1.contains(x: find_me))
409 return false;
410
411 //lower_bound
412 if(*set1.lower_bound(k: find_me) != 2)
413 return false;
414 if(*cset1.lower_bound(k: find_me) != 2)
415 return false;
416 if(*mset1.lower_bound(k: find_me) != 2)
417 return false;
418 if(*cmset1.lower_bound(k: find_me) != 2)
419 return false;
420
421 //upper_bound
422 if(*set1.upper_bound(k: find_me) != 3)
423 return false;
424 if(*cset1.upper_bound(k: find_me) != 3)
425 return false;
426 if(*mset1.upper_bound(k: find_me) != 3)
427 return false;
428 if(*cmset1.upper_bound(k: find_me) != 3)
429 return false;
430
431 //equal_range
432 if(*set1.equal_range(x: find_me).first != 2)
433 return false;
434 if(*cset1.equal_range(x: find_me).second != 3)
435 return false;
436 if(*mset1.equal_range(k: find_me).first != 2)
437 return false;
438 if(*cmset1.equal_range(k: find_me).second != 3)
439 return false;
440
441 return true;
442}
443
444int main ()
445{
446 //Recursive container instantiation
447 {
448 set<recursive_set> set_;
449 multiset<recursive_multiset> multiset_;
450 }
451 //Allocator argument container
452 {
453 set<int> set_((set<int>::allocator_type()));
454 multiset<int> multiset_((multiset<int>::allocator_type()));
455 }
456 //Now test move semantics
457 {
458 test_move<set<recursive_set> >();
459 test_move<multiset<recursive_multiset> >();
460 }
461 //Test std::pair value type as tree has workarounds to make old std::pair
462 //implementations movable that can break things
463 {
464 boost::container::set<std::pair<int,int> > s;
465 std::pair<int,int> p(0, 0);
466 s.insert(x: p);
467 s.emplace(args&: p);
468 }
469
470 if (!boost::container::test::instantiate_constructors<set<int>, multiset<int> >())
471 return 1;
472
473 test_merge_from_different_comparison();
474
475 ////////////////////////////////////
476 // Constructor Template Auto Deduction test
477 ////////////////////////////////////
478 if (!test::constructor_template_auto_deduction_test()) {
479 return 1;
480 }
481
482 if(!test_heterogeneous_lookups())
483 return 1;
484
485 ////////////////////////////////////
486 // Testing allocator implementations
487 ////////////////////////////////////
488 {
489 typedef std::set<int> MyStdSet;
490 typedef std::multiset<int> MyStdMultiSet;
491
492 if (0 != test::set_test
493 < GetAllocatorSet<std::allocator<void>, red_black_tree>::apply<int>::set_type
494 , MyStdSet
495 , GetAllocatorSet<std::allocator<void>, red_black_tree>::apply<int>::multiset_type
496 , MyStdMultiSet>()) {
497 std::cout << "Error in set_test<std::allocator<void>, red_black_tree>" << std::endl;
498 return 1;
499 }
500
501 if (0 != test::set_test
502 < GetAllocatorSet<new_allocator<void>, avl_tree>::apply<int>::set_type
503 , MyStdSet
504 , GetAllocatorSet<new_allocator<void>, avl_tree>::apply<int>::multiset_type
505 , MyStdMultiSet>()) {
506 std::cout << "Error in set_test<new_allocator<void>, avl_tree>" << std::endl;
507 return 1;
508 }
509
510 if (0 != test::set_test
511 < GetAllocatorSet<adaptive_pool<void>, scapegoat_tree>::apply<int>::set_type
512 , MyStdSet
513 , GetAllocatorSet<adaptive_pool<void>, scapegoat_tree>::apply<int>::multiset_type
514 , MyStdMultiSet>()) {
515 std::cout << "Error in set_test<adaptive_pool<void>, scapegoat_tree>" << std::endl;
516 return 1;
517 }
518
519 ///////////
520
521 if (0 != test::set_test
522 < GetAllocatorSet<new_allocator<void>, splay_tree>::apply<test::movable_int>::set_type
523 , MyStdSet
524 , GetAllocatorSet<new_allocator<void>, splay_tree>::apply<test::movable_int>::multiset_type
525 , MyStdMultiSet>()) {
526 std::cout << "Error in set_test<new_allocator<void>, splay_tree>" << std::endl;
527 return 1;
528 }
529
530 if (0 != test::set_test
531 < GetAllocatorSet<new_allocator<void>, red_black_tree>::apply<test::copyable_int>::set_type
532 , MyStdSet
533 , GetAllocatorSet<new_allocator<void>, red_black_tree>::apply<test::copyable_int>::multiset_type
534 , MyStdMultiSet>()) {
535 std::cout << "Error in set_test<new_allocator<void>, red_black_tree>" << std::endl;
536 return 1;
537 }
538
539 if (0 != test::set_test
540 < GetAllocatorSet<new_allocator<void>, red_black_tree>::apply<test::movable_and_copyable_int>::set_type
541 , MyStdSet
542 , GetAllocatorSet<new_allocator<void>, red_black_tree>::apply<test::movable_and_copyable_int>::multiset_type
543 , MyStdMultiSet>()) {
544 std::cout << "Error in set_test<new_allocator<void>, red_black_tree>" << std::endl;
545 return 1;
546 }
547 }
548
549 ////////////////////////////////////
550 // Emplace testing
551 ////////////////////////////////////
552 const test::EmplaceOptions SetOptions = (test::EmplaceOptions)(test::EMPLACE_HINT | test::EMPLACE_ASSOC);
553 if(!boost::container::test::test_emplace<set<test::EmplaceInt>, SetOptions>())
554 return 1;
555 if(!boost::container::test::test_emplace<multiset<test::EmplaceInt>, SetOptions>())
556 return 1;
557
558 ////////////////////////////////////
559 // Allocator propagation testing
560 ////////////////////////////////////
561 if(!boost::container::test::test_propagate_allocator<boost_container_set>())
562 return 1;
563
564 if(!boost::container::test::test_propagate_allocator<boost_container_multiset>())
565 return 1;
566
567 if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for<set<int> >())
568 return 1;
569
570 if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for<multiset<int> >())
571 return 1;
572
573 ////////////////////////////////////
574 // Test optimize_size option
575 ////////////////////////////////////
576 //
577 // set
578 //
579 typedef set< int*, std::less<int*>, std::allocator<int*>
580 , tree_assoc_options< optimize_size<false>, tree_type<red_black_tree> >::type > rbset_size_optimized_no;
581
582 typedef set< int*, std::less<int*>, std::allocator<int*>
583 , tree_assoc_options< optimize_size<true>, tree_type<avl_tree> >::type > avlset_size_optimized_yes;
584 //
585 // multiset
586 //
587 typedef multiset< int*, std::less<int*>, std::allocator<int*>
588 , tree_assoc_options< optimize_size<true>, tree_type<red_black_tree> >::type > rbmset_size_optimized_yes;
589
590 typedef multiset< int*, std::less<int*>, std::allocator<int*>
591 , tree_assoc_options< optimize_size<false>, tree_type<avl_tree> >::type > avlmset_size_optimized_no;
592
593 BOOST_CONTAINER_STATIC_ASSERT(sizeof(rbmset_size_optimized_yes) < sizeof(rbset_size_optimized_no));
594 BOOST_CONTAINER_STATIC_ASSERT(sizeof(avlset_size_optimized_yes) < sizeof(avlmset_size_optimized_no));
595
596 ////////////////////////////////////
597 // Iterator testing
598 ////////////////////////////////////
599 {
600 typedef boost::container::set<int> cont_int;
601 cont_int a; a.insert(x: 0); a.insert(x: 1); a.insert(x: 2);
602 boost::intrusive::test::test_iterator_bidirectional< cont_int >(c&: a);
603 if(boost::report_errors() != 0) {
604 return 1;
605 }
606 }
607 {
608 typedef boost::container::multiset<int> cont_int;
609 cont_int a; a.insert(x: 0); a.insert(x: 1); a.insert(x: 2);
610 boost::intrusive::test::test_iterator_bidirectional< cont_int >(c&: a);
611 if(boost::report_errors() != 0) {
612 return 1;
613 }
614 }
615
616 ////////////////////////////////////
617 // Node extraction/insertion testing functions
618 ////////////////////////////////////
619 if(!node_type_test())
620 return 1;
621
622 ////////////////////////////////////
623 // has_trivial_destructor_after_move testing
624 ////////////////////////////////////
625 // set, default allocator
626 {
627 typedef boost::container::set<int> cont;
628 typedef boost::container::dtl::tree<int, void, std::less<int>, void, void> tree;
629 BOOST_CONTAINER_STATIC_ASSERT_MSG(
630 !(boost::has_trivial_destructor_after_move<cont>::value !=
631 boost::has_trivial_destructor_after_move<tree>::value)
632 , "has_trivial_destructor_after_move(set, default allocator) test failed");
633 }
634 // set, std::allocator
635 {
636 typedef boost::container::set<int, std::less<int>, std::allocator<int> > cont;
637 typedef boost::container::dtl::tree<int, void, std::less<int>, std::allocator<int>, void> tree;
638 BOOST_CONTAINER_STATIC_ASSERT_MSG(
639 !(boost::has_trivial_destructor_after_move<cont>::value !=
640 boost::has_trivial_destructor_after_move<tree>::value)
641 , "has_trivial_destructor_after_move(set, std::allocator) test failed");
642 }
643 // multiset, default allocator
644 {
645 typedef boost::container::multiset<int> cont;
646 typedef boost::container::dtl::tree<int, void, std::less<int>, void, void> tree;
647 BOOST_CONTAINER_STATIC_ASSERT_MSG(
648 !(boost::has_trivial_destructor_after_move<cont>::value !=
649 boost::has_trivial_destructor_after_move<tree>::value)
650 , "has_trivial_destructor_after_move(multiset, default allocator) test failed");
651 }
652 // multiset, std::allocator
653 {
654 typedef boost::container::multiset<int, std::less<int>, std::allocator<int> > cont;
655 typedef boost::container::dtl::tree<int, void, std::less<int>, std::allocator<int>, void> tree;
656 BOOST_CONTAINER_STATIC_ASSERT_MSG(
657 !(boost::has_trivial_destructor_after_move<cont>::value !=
658 boost::has_trivial_destructor_after_move<tree>::value)
659 , "has_trivial_destructor_after_move(multiset, std::allocator) test failed");
660 }
661
662 return 0;
663}
664

source code of boost/libs/container/test/set_test.cpp