1 //////////////////////////////////////////////////////////////////////////////
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)
7 // See http://www.boost.org/libs/container for documentation.
9 //////////////////////////////////////////////////////////////////////////////
10 #include <boost/container/detail/config_begin.hpp>
12 #include <boost/container/set.hpp>
13 #include <boost/container/adaptive_pool.hpp>
15 #include "print_container.hpp"
16 #include "movable_int.hpp"
17 #include "dummy_test_allocator.hpp"
18 #include "set_test.hpp"
19 #include "propagate_allocator_test.hpp"
20 #include "emplace_test.hpp"
21 #include "../../intrusive/test/iterator_test.hpp"
23 using namespace boost::container
;
28 //Explicit instantiation to detect compilation errors
32 < test::movable_and_copyable_int
33 , std::less
<test::movable_and_copyable_int
>
34 , test::simple_allocator
<test::movable_and_copyable_int
>
38 < test::movable_and_copyable_int
39 , std::less
<test::movable_and_copyable_int
>
40 , adaptive_pool
<test::movable_and_copyable_int
>
44 template class multiset
45 < test::movable_and_copyable_int
46 , std::less
<test::movable_and_copyable_int
>
47 , test::simple_allocator
<test::movable_and_copyable_int
>
50 template class multiset
51 < test::movable_and_copyable_int
52 , std::less
<test::movable_and_copyable_int
>
53 , adaptive_pool
<test::movable_and_copyable_int
>
56 namespace container_detail
{
58 //Instantiate base class as previous instantiations don't instantiate inherited members
60 < test::movable_and_copyable_int
61 , identity
<test::movable_and_copyable_int
>
62 , std::less
<test::movable_and_copyable_int
>
63 , test::simple_allocator
<test::movable_and_copyable_int
>
68 < test::movable_and_copyable_int
69 , identity
<test::movable_and_copyable_int
>
70 , std::less
<test::movable_and_copyable_int
>
71 , std::allocator
<test::movable_and_copyable_int
>
76 < test::movable_and_copyable_int
77 , identity
<test::movable_and_copyable_int
>
78 , std::less
<test::movable_and_copyable_int
>
79 , adaptive_pool
<test::movable_and_copyable_int
>
83 } //container_detail {
87 //Test recursive structures
91 recursive_set
& operator=(const recursive_set
&x
)
92 { id_
= x
.id_
; set_
= x
.set_
; return *this; }
95 set
<recursive_set
> set_
;
96 set
<recursive_set
>::iterator it_
;
97 set
<recursive_set
>::const_iterator cit_
;
98 set
<recursive_set
>::reverse_iterator rit_
;
99 set
<recursive_set
>::const_reverse_iterator crit_
;
101 friend bool operator< (const recursive_set
&a
, const recursive_set
&b
)
102 { return a
.id_
< b
.id_
; }
105 //Test recursive structures
106 class recursive_multiset
109 recursive_multiset
& operator=(const recursive_multiset
&x
)
110 { id_
= x
.id_
; multiset_
= x
.multiset_
; return *this; }
113 multiset
<recursive_multiset
> multiset_
;
114 multiset
<recursive_multiset
>::iterator it_
;
115 multiset
<recursive_multiset
>::const_iterator cit_
;
116 multiset
<recursive_multiset
>::reverse_iterator rit_
;
117 multiset
<recursive_multiset
>::const_reverse_iterator crit_
;
119 friend bool operator< (const recursive_multiset
&a
, const recursive_multiset
&b
)
120 { return a
.id_
< b
.id_
; }
126 //Now test move semantics
129 C
move_ctor(boost::move(original
));
131 move_assign
.emplace();
132 move_assign
= boost::move(move_ctor
);
133 move_assign
.swap(original
);
136 bool node_type_test()
138 using namespace boost::container
;
140 typedef set
<test::movable_int
> set_type
;
143 test::movable_int
mv_1(1), mv_2(2), mv_3(3);
144 src
.emplace(boost::move(mv_1
));
145 src
.emplace(boost::move(mv_2
));
146 src
.emplace(boost::move(mv_3
));
153 test::movable_int
mv_3(3);
154 dst
.emplace(boost::move(mv_3
));
160 const test::movable_int
mv_1(1);
161 const test::movable_int
mv_2(2);
162 const test::movable_int
mv_3(3);
163 const test::movable_int
mv_33(33);
164 set_type::insert_return_type r
;
166 r
= dst
.insert(src
.extract(mv_33
)); // Key version, try to insert empty node
167 if(! (r
.position
== dst
.end() && r
.inserted
== false && r
.node
.empty()) )
169 r
= dst
.insert(src
.extract(src
.find(mv_1
))); // Iterator version, successful
170 if(! (r
.position
== dst
.find(mv_1
) && r
.inserted
== true && r
.node
.empty()) )
172 r
= dst
.insert(dst
.begin(), src
.extract(mv_2
)); // Key type version, successful
173 if(! (r
.position
== dst
.find(mv_2
) && r
.inserted
== true && r
.node
.empty()) )
175 r
= dst
.insert(src
.extract(mv_3
)); // Key type version, unsuccessful
181 if(! (r
.position
== dst
.find(mv_3
) && r
.inserted
== false && r
.node
.value() == mv_3
) )
186 typedef multiset
<test::movable_int
> multiset_type
;
189 test::movable_int
mv_1(1), mv_2(2), mv_3(3), mv_3bis(3);
190 src
.emplace(boost::move(mv_1
));
191 src
.emplace(boost::move(mv_2
));
192 src
.emplace(boost::move(mv_3
));
193 src
.emplace_hint(src
.begin(), boost::move(mv_3bis
));
200 test::movable_int
mv_3(3);
201 dst
.emplace(boost::move(mv_3
));
207 const test::movable_int
mv_1(1);
208 const test::movable_int
mv_2(2);
209 const test::movable_int
mv_3(3);
210 const test::movable_int
mv_4(4);
211 multiset_type::iterator r
;
213 multiset_type::node_type
nt(src
.extract(mv_3
));
214 r
= dst
.insert(dst
.begin(), boost::move(nt
));
215 if(! (*r
== mv_3
&& dst
.find(mv_3
) == r
&& nt
.empty()) )
218 nt
= src
.extract(src
.find(mv_1
));
219 r
= dst
.insert(boost::move(nt
)); // Iterator version, successful
220 if(! (*r
== mv_1
&& nt
.empty()) )
223 nt
= src
.extract(mv_2
);
224 r
= dst
.insert(boost::move(nt
)); // Key type version, successful
225 if(! (*r
== mv_2
&& nt
.empty()) )
228 r
= dst
.insert(src
.extract(mv_3
)); // Key type version, successful
229 if(! (*r
== mv_3
&& r
== --multiset_type::iterator(dst
.upper_bound(mv_3
)) && nt
.empty()) )
232 r
= dst
.insert(src
.extract(mv_4
)); // Key type version, unsuccessful
233 if(! (r
== dst
.end()) )
244 struct boost_container_set
;
245 struct boost_container_multiset
;
248 namespace container
{
252 struct alloc_propagate_base
<boost_container_set
>
254 template <class T
, class Allocator
>
257 typedef boost::container::set
<T
, std::less
<T
>, Allocator
> type
;
262 struct alloc_propagate_base
<boost_container_multiset
>
264 template <class T
, class Allocator
>
267 typedef boost::container::multiset
<T
, std::less
<T
>, Allocator
> type
;
271 }}} //boost::container::test
273 template<class VoidAllocator
, boost::container::tree_type_enum tree_type_value
>
274 struct GetAllocatorSet
276 template<class ValueType
>
279 typedef set
< ValueType
280 , std::less
<ValueType
>
281 , typename allocator_traits
<VoidAllocator
>
282 ::template portable_rebind_alloc
<ValueType
>::type
283 , typename
boost::container::tree_assoc_options
284 < boost::container::tree_type
<tree_type_value
>
288 typedef multiset
< ValueType
289 , std::less
<ValueType
>
290 , typename allocator_traits
<VoidAllocator
>
291 ::template portable_rebind_alloc
<ValueType
>::type
292 , typename
boost::container::tree_assoc_options
293 < boost::container::tree_type
<tree_type_value
>
299 template<class VoidAllocator
, boost::container::tree_type_enum tree_type_value
>
300 int test_set_variants()
302 typedef typename GetAllocatorSet
<VoidAllocator
, tree_type_value
>::template apply
<int>::set_type MySet
;
303 typedef typename GetAllocatorSet
<VoidAllocator
, tree_type_value
>::template apply
<test::movable_int
>::set_type MyMoveSet
;
304 typedef typename GetAllocatorSet
<VoidAllocator
, tree_type_value
>::template apply
<test::movable_and_copyable_int
>::set_type MyCopyMoveSet
;
305 typedef typename GetAllocatorSet
<VoidAllocator
, tree_type_value
>::template apply
<test::copyable_int
>::set_type MyCopySet
;
307 typedef typename GetAllocatorSet
<VoidAllocator
, tree_type_value
>::template apply
<int>::multiset_type MyMultiSet
;
308 typedef typename GetAllocatorSet
<VoidAllocator
, tree_type_value
>::template apply
<test::movable_int
>::multiset_type MyMoveMultiSet
;
309 typedef typename GetAllocatorSet
<VoidAllocator
, tree_type_value
>::template apply
<test::movable_and_copyable_int
>::multiset_type MyCopyMoveMultiSet
;
310 typedef typename GetAllocatorSet
<VoidAllocator
, tree_type_value
>::template apply
<test::copyable_int
>::multiset_type MyCopyMultiSet
;
312 typedef std::set
<int> MyStdSet
;
313 typedef std::multiset
<int> MyStdMultiSet
;
315 if (0 != test::set_test
<
320 std::cout
<< "Error in set_test<MyBoostSet>" << std::endl
;
324 if (0 != test::set_test
<
329 std::cout
<< "Error in set_test<MyBoostSet>" << std::endl
;
333 if (0 != test::set_test
<
338 std::cout
<< "Error in set_test<MyBoostSet>" << std::endl
;
342 if (0 != test::set_test
<
347 std::cout
<< "Error in set_test<MyBoostSet>" << std::endl
;
354 void test_merge_from_different_comparison()
357 set
<int, std::greater
<int> > set2
;
364 //Recursive container instantiation
366 set
<recursive_set
> set_
;
367 multiset
<recursive_multiset
> multiset_
;
369 //Allocator argument container
371 set
<int> set_((set
<int>::allocator_type()));
372 multiset
<int> multiset_((multiset
<int>::allocator_type()));
374 //Now test move semantics
376 test_move
<set
<recursive_set
> >();
377 test_move
<multiset
<recursive_multiset
> >();
379 //Test std::pair value type as tree has workarounds to make old std::pair
380 //implementations movable that can break things
382 boost::container::set
<std::pair
<int,int> > s
;
383 std::pair
<int,int> p(0, 0);
388 test_merge_from_different_comparison();
390 ////////////////////////////////////
391 // Testing allocator implementations
392 ////////////////////////////////////
394 if(test_set_variants
< std::allocator
<void>, red_black_tree
>()){
395 std::cerr
<< "test_set_variants< std::allocator<void> > failed" << std::endl
;
398 // boost::container::adaptive_pool
399 if(test_set_variants
< adaptive_pool
<void>, red_black_tree
>()){
400 std::cerr
<< "test_set_variants< adaptive_pool<void> > failed" << std::endl
;
404 ////////////////////////////////////
405 // Tree implementations
406 ////////////////////////////////////
408 if(test_set_variants
< std::allocator
<void>, avl_tree
>()){
409 std::cerr
<< "test_set_variants< std::allocator<void>, avl_tree > failed" << std::endl
;
413 if(test_set_variants
< std::allocator
<void>, scapegoat_tree
>()){
414 std::cerr
<< "test_set_variants< std::allocator<void>, scapegoat_tree > failed" << std::endl
;
418 if(test_set_variants
< std::allocator
<void>, splay_tree
>()){
419 std::cerr
<< "test_set_variants< std::allocator<void>, splay_tree > failed" << std::endl
;
423 ////////////////////////////////////
425 ////////////////////////////////////
426 const test::EmplaceOptions SetOptions
= (test::EmplaceOptions
)(test::EMPLACE_HINT
| test::EMPLACE_ASSOC
);
427 if(!boost::container::test::test_emplace
<set
<test::EmplaceInt
>, SetOptions
>())
429 if(!boost::container::test::test_emplace
<multiset
<test::EmplaceInt
>, SetOptions
>())
432 ////////////////////////////////////
433 // Allocator propagation testing
434 ////////////////////////////////////
435 if(!boost::container::test::test_propagate_allocator
<boost_container_set
>())
438 if(!boost::container::test::test_propagate_allocator
<boost_container_multiset
>())
441 if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for
<set
<int> >())
444 if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for
<multiset
<int> >())
447 ////////////////////////////////////
448 // Test optimize_size option
449 ////////////////////////////////////
453 typedef set
< int*, std::less
<int*>, std::allocator
<int*>
454 , tree_assoc_options
< optimize_size
<false>, tree_type
<red_black_tree
> >::type
> rbset_size_optimized_no
;
455 typedef set
< int*, std::less
<int*>, std::allocator
<int*>
456 , tree_assoc_options
< optimize_size
<true>, tree_type
<red_black_tree
> >::type
> rbset_size_optimized_yes
;
457 BOOST_STATIC_ASSERT(sizeof(rbset_size_optimized_yes
) < sizeof(rbset_size_optimized_no
));
459 typedef set
< int*, std::less
<int*>, std::allocator
<int*>
460 , tree_assoc_options
< optimize_size
<false>, tree_type
<avl_tree
> >::type
> avlset_size_optimized_no
;
461 typedef set
< int*, std::less
<int*>, std::allocator
<int*>
462 , tree_assoc_options
< optimize_size
<true>, tree_type
<avl_tree
> >::type
> avlset_size_optimized_yes
;
463 BOOST_STATIC_ASSERT(sizeof(avlset_size_optimized_yes
) < sizeof(avlset_size_optimized_no
));
467 typedef multiset
< int*, std::less
<int*>, std::allocator
<int*>
468 , tree_assoc_options
< optimize_size
<false>, tree_type
<red_black_tree
> >::type
> rbmset_size_optimized_no
;
469 typedef multiset
< int*, std::less
<int*>, std::allocator
<int*>
470 , tree_assoc_options
< optimize_size
<true>, tree_type
<red_black_tree
> >::type
> rbmset_size_optimized_yes
;
471 BOOST_STATIC_ASSERT(sizeof(rbmset_size_optimized_yes
) < sizeof(rbmset_size_optimized_no
));
473 typedef multiset
< int*, std::less
<int*>, std::allocator
<int*>
474 , tree_assoc_options
< optimize_size
<false>, tree_type
<avl_tree
> >::type
> avlmset_size_optimized_no
;
475 typedef multiset
< int*, std::less
<int*>, std::allocator
<int*>
476 , tree_assoc_options
< optimize_size
<true>, tree_type
<avl_tree
> >::type
> avlmset_size_optimized_yes
;
477 BOOST_STATIC_ASSERT(sizeof(avlmset_size_optimized_yes
) < sizeof(avlmset_size_optimized_no
));
479 ////////////////////////////////////
481 ////////////////////////////////////
483 typedef boost::container::set
<int> cont_int
;
484 cont_int a
; a
.insert(0); a
.insert(1); a
.insert(2);
485 boost::intrusive::test::test_iterator_bidirectional
< cont_int
>(a
);
486 if(boost::report_errors() != 0) {
491 typedef boost::container::multiset
<int> cont_int
;
492 cont_int a
; a
.insert(0); a
.insert(1); a
.insert(2);
493 boost::intrusive::test::test_iterator_bidirectional
< cont_int
>(a
);
494 if(boost::report_errors() != 0) {
499 ////////////////////////////////////
500 // Node extraction/insertion testing functions
501 ////////////////////////////////////
502 if(!node_type_test())
508 #include <boost/container/detail/config_end.hpp>