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/map.hpp>
11 #include <boost/container/adaptive_pool.hpp>
15 #include "print_container.hpp"
16 #include "movable_int.hpp"
17 #include "dummy_test_allocator.hpp"
18 #include "map_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
;
25 typedef std::pair
<const test::movable_and_copyable_int
, test::movable_and_copyable_int
> pair_t
;
33 recursive_map(const recursive_map
&x
)
37 recursive_map
& operator=(const recursive_map
&x
)
38 { id_
= x
.id_
; map_
= x
.map_
; return *this; }
41 map
<recursive_map
, recursive_map
> map_
;
42 map
<recursive_map
, recursive_map
>::iterator it_
;
43 map
<recursive_map
, recursive_map
>::const_iterator cit_
;
44 map
<recursive_map
, recursive_map
>::reverse_iterator rit_
;
45 map
<recursive_map
, recursive_map
>::const_reverse_iterator crit_
;
47 friend bool operator< (const recursive_map
&a
, const recursive_map
&b
)
48 { return a
.id_
< b
.id_
; }
51 class recursive_multimap
57 recursive_multimap(const recursive_multimap
&x
)
58 : multimap_(x
.multimap_
)
61 recursive_multimap
& operator=(const recursive_multimap
&x
)
62 { id_
= x
.id_
; multimap_
= x
.multimap_
; return *this; }
65 multimap
<recursive_multimap
, recursive_multimap
> multimap_
;
66 multimap
<recursive_multimap
, recursive_multimap
>::iterator it_
;
67 multimap
<recursive_multimap
, recursive_multimap
>::const_iterator cit_
;
68 multimap
<recursive_multimap
, recursive_multimap
>::reverse_iterator rit_
;
69 multimap
<recursive_multimap
, recursive_multimap
>::const_reverse_iterator crit_
;
71 friend bool operator< (const recursive_multimap
&a
, const recursive_multimap
&b
)
72 { return a
.id_
< b
.id_
; }
78 //Now test move semantics
81 C
move_ctor(boost::move(original
));
83 move_assign
.emplace();
84 move_assign
= boost::move(move_ctor
);
85 move_assign
.swap(original
);
90 using namespace boost::container
;
92 typedef map
<test::movable_int
, test::movable_int
> map_type
;
95 test::movable_int
mv_1(1), mv_2(2), mv_3(3), mv_11(11), mv_12(12), mv_13(13);
96 src
.try_emplace(boost::move(mv_1
), boost::move(mv_11
));
97 src
.try_emplace(boost::move(mv_2
), boost::move(mv_12
));
98 src
.try_emplace(boost::move(mv_3
), boost::move(mv_13
));
105 test::movable_int
mv_3(3), mv_33(33);
106 dst
.try_emplace(boost::move(mv_3
), boost::move(mv_33
));
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 const test::movable_int
mv_13(13);
117 map_type::insert_return_type r
;
119 r
= dst
.insert(src
.extract(mv_33
)); // Key version, try to insert empty node
120 if(! (r
.position
== dst
.end() && r
.inserted
== false && r
.node
.empty()) )
122 r
= dst
.insert(src
.extract(src
.find(mv_1
))); // Iterator version, successful
123 if(! (r
.position
== dst
.find(mv_1
) && r
.inserted
== true && r
.node
.empty()) )
125 r
= dst
.insert(dst
.begin(), src
.extract(mv_2
)); // Key type version, successful
126 if(! (r
.position
== dst
.find(mv_2
) && r
.inserted
== true && r
.node
.empty()) )
128 r
= dst
.insert(src
.extract(mv_3
)); // Key type version, unsuccessful
134 if(! (r
.position
== dst
.find(mv_3
) && r
.inserted
== false && r
.node
.key() == mv_3
&& r
.node
.mapped() == mv_13
) )
139 typedef multimap
<test::movable_int
, test::movable_int
> multimap_type
;
142 test::movable_int
mv_1(1), mv_2(2), mv_3(3), mv_3bis(3), mv_11(11), mv_12(12), mv_13(13), mv_23(23);
143 src
.emplace(boost::move(mv_1
), boost::move(mv_11
));
144 src
.emplace(boost::move(mv_2
), boost::move(mv_12
));
145 src
.emplace(boost::move(mv_3
), boost::move(mv_13
));
146 src
.emplace_hint(src
.begin(), boost::move(mv_3bis
), boost::move(mv_23
));
153 test::movable_int
mv_3(3), mv_33(33);
154 dst
.emplace(boost::move(mv_3
), boost::move(mv_33
));
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_4(4);
164 const test::movable_int
mv_33(33);
165 const test::movable_int
mv_13(13);
166 const test::movable_int
mv_23(23);
167 multimap_type::iterator r
;
169 multimap_type::node_type
nt(src
.extract(mv_3
));
170 r
= dst
.insert(dst
.begin(), boost::move(nt
));
171 if(! (r
->first
== mv_3
&& r
->second
== mv_23
&& dst
.find(mv_3
) == r
&& nt
.empty()) )
174 nt
= src
.extract(src
.find(mv_1
));
175 r
= dst
.insert(boost::move(nt
)); // Iterator version, successful
176 if(! (r
->first
== mv_1
&& nt
.empty()) )
179 nt
= src
.extract(mv_2
);
180 r
= dst
.insert(boost::move(nt
)); // Key type version, successful
181 if(! (r
->first
== mv_2
&& nt
.empty()) )
184 r
= dst
.insert(src
.extract(mv_3
)); // Key type version, successful
185 if(! (r
->first
== mv_3
&& r
->second
== mv_13
&& r
== --multimap_type::iterator(dst
.upper_bound(mv_3
)) && nt
.empty()) )
188 r
= dst
.insert(src
.extract(mv_4
)); // Key type version, unsuccessful
189 if(! (r
== dst
.end()) )
200 template<class VoidAllocator
, boost::container::tree_type_enum tree_type_value
>
201 struct GetAllocatorMap
203 template<class ValueType
>
206 typedef map
< ValueType
208 , std::less
<ValueType
>
209 , typename allocator_traits
<VoidAllocator
>
210 ::template portable_rebind_alloc
< std::pair
<const ValueType
, ValueType
> >::type
211 , typename
boost::container::tree_assoc_options
212 < boost::container::tree_type
<tree_type_value
>
216 typedef multimap
< ValueType
218 , std::less
<ValueType
>
219 , typename allocator_traits
<VoidAllocator
>
220 ::template portable_rebind_alloc
< std::pair
<const ValueType
, ValueType
> >::type
221 , typename
boost::container::tree_assoc_options
222 < boost::container::tree_type
<tree_type_value
>
228 struct boost_container_map
;
229 struct boost_container_multimap
;
231 namespace boost
{ namespace container
{ namespace test
{
234 struct alloc_propagate_base
<boost_container_map
>
236 template <class T
, class Allocator
>
239 typedef typename
boost::container::allocator_traits
<Allocator
>::
240 template portable_rebind_alloc
<std::pair
<const T
, T
> >::type TypeAllocator
;
241 typedef boost::container::map
<T
, T
, std::less
<T
>, TypeAllocator
> type
;
246 struct alloc_propagate_base
<boost_container_multimap
>
248 template <class T
, class Allocator
>
251 typedef typename
boost::container::allocator_traits
<Allocator
>::
252 template portable_rebind_alloc
<std::pair
<const T
, T
> >::type TypeAllocator
;
253 typedef boost::container::multimap
<T
, T
, std::less
<T
>, TypeAllocator
> type
;
257 void test_merge_from_different_comparison()
260 map
<int, int, std::greater
<int> > map2
;
264 bool test_heterogeneous_lookups()
266 typedef map
<int, char, less_transparent
> map_t
;
267 typedef multimap
<int, char, less_transparent
> mmap_t
;
268 typedef map_t::value_type value_type
;
273 const map_t
&cmap1
= map1
;
274 const mmap_t
&cmmap1
= mmap1
;
276 if(!map1
.insert_or_assign(1, 'a').second
)
278 if( map1
.insert_or_assign(1, 'b').second
)
280 if(!map1
.insert_or_assign(2, 'c').second
)
282 if( map1
.insert_or_assign(2, 'd').second
)
284 if(!map1
.insert_or_assign(3, 'e').second
)
287 if(map1
.insert_or_assign(1, 'a').second
)
289 if(map1
.insert_or_assign(1, 'b').second
)
291 if(map1
.insert_or_assign(2, 'c').second
)
293 if(map1
.insert_or_assign(2, 'd').second
)
295 if(map1
.insert_or_assign(3, 'e').second
)
298 mmap1
.insert(value_type(1, 'a'));
299 mmap1
.insert(value_type(1, 'b'));
300 mmap1
.insert(value_type(2, 'c'));
301 mmap1
.insert(value_type(2, 'd'));
302 mmap1
.insert(value_type(3, 'e'));
304 const test::non_copymovable_int
find_me(2);
307 if(map1
.find(find_me
)->second
!= 'd')
309 if(cmap1
.find(find_me
)->second
!= 'd')
311 if(mmap1
.find(find_me
)->second
!= 'c')
313 if(cmmap1
.find(find_me
)->second
!= 'c')
317 if(map1
.count(find_me
) != 1)
319 if(cmap1
.count(find_me
) != 1)
321 if(mmap1
.count(find_me
) != 2)
323 if(cmmap1
.count(find_me
) != 2)
327 if(!map1
.contains(find_me
))
329 if(!cmap1
.contains(find_me
))
331 if(!mmap1
.contains(find_me
))
333 if(!cmmap1
.contains(find_me
))
337 if(map1
.lower_bound(find_me
)->second
!= 'd')
339 if(cmap1
.lower_bound(find_me
)->second
!= 'd')
341 if(mmap1
.lower_bound(find_me
)->second
!= 'c')
343 if(cmmap1
.lower_bound(find_me
)->second
!= 'c')
347 if(map1
.upper_bound(find_me
)->second
!= 'e')
349 if(cmap1
.upper_bound(find_me
)->second
!= 'e')
351 if(mmap1
.upper_bound(find_me
)->second
!= 'e')
353 if(cmmap1
.upper_bound(find_me
)->second
!= 'e')
357 if(map1
.equal_range(find_me
).first
->second
!= 'd')
359 if(cmap1
.equal_range(find_me
).second
->second
!= 'e')
361 if(mmap1
.equal_range(find_me
).first
->second
!= 'c')
363 if(cmmap1
.equal_range(find_me
).second
->second
!= 'e')
369 bool constructor_template_auto_deduction_test()
372 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
373 using namespace boost::container
;
374 const std::size_t NumElements
= 100;
376 std::map
<int, int> int_map
;
377 for(std::size_t i
= 0; i
!= NumElements
; ++i
){
378 int_map
.insert(std::map
<int, int>::value_type(static_cast<int>(i
), static_cast<int>(i
)));
380 std::multimap
<int, int> int_mmap
;
381 for (std::size_t i
= 0; i
!= NumElements
; ++i
) {
382 int_mmap
.insert(std::multimap
<int, int>::value_type(static_cast<int>(i
), static_cast<int>(i
)));
385 typedef std::less
<int> comp_int_t
;
386 typedef std::allocator
<std::pair
<const int, int> > alloc_pair_int_t
;
390 auto fmap
= map(int_map
.begin(), int_map
.end());
391 if (!CheckEqualContainers(int_map
, fmap
))
393 auto fmmap
= multimap(int_mmap
.begin(), int_mmap
.end());
394 if (!CheckEqualContainers(int_mmap
, fmmap
))
399 auto fmap
= map(int_map
.begin(), int_map
.end(), comp_int_t());
400 if (!CheckEqualContainers(int_map
, fmap
))
402 auto fmmap
= multimap(int_mmap
.begin(), int_mmap
.end(), comp_int_t());
403 if (!CheckEqualContainers(int_mmap
, fmmap
))
408 auto fmap
= map(int_map
.begin(), int_map
.end(), comp_int_t(), alloc_pair_int_t());
409 if (!CheckEqualContainers(int_map
, fmap
))
411 auto fmmap
= multimap(int_mmap
.begin(), int_mmap
.end(), comp_int_t(), alloc_pair_int_t());
412 if (!CheckEqualContainers(int_mmap
, fmmap
))
417 auto fmap
= map(int_map
.begin(), int_map
.end(), alloc_pair_int_t());
418 if (!CheckEqualContainers(int_map
, fmap
))
420 auto fmmap
= multimap(int_mmap
.begin(), int_mmap
.end(), alloc_pair_int_t());
421 if (!CheckEqualContainers(int_mmap
, fmmap
))
425 //ordered_unique_range / ordered_range
429 auto fmap
= map(ordered_unique_range
, int_map
.begin(), int_map
.end());
430 if(!CheckEqualContainers(int_map
, fmap
))
432 auto fmmap
= multimap(ordered_range
, int_mmap
.begin(), int_mmap
.end());
433 if(!CheckEqualContainers(int_mmap
, fmmap
))
438 auto fmap
= map(ordered_unique_range
, int_map
.begin(), int_map
.end(), comp_int_t());
439 if (!CheckEqualContainers(int_map
, fmap
))
441 auto fmmap
= multimap(ordered_range
, int_mmap
.begin(), int_mmap
.end(), comp_int_t());
442 if (!CheckEqualContainers(int_mmap
, fmmap
))
447 auto fmap
= map(ordered_unique_range
, int_map
.begin(), int_map
.end(), comp_int_t(), alloc_pair_int_t());
448 if (!CheckEqualContainers(int_map
, fmap
))
450 auto fmmap
= multimap(ordered_range
, int_mmap
.begin(), int_mmap
.end(), comp_int_t(), alloc_pair_int_t());
451 if (!CheckEqualContainers(int_mmap
, fmmap
))
456 auto fmap
= map(ordered_unique_range
, int_map
.begin(), int_map
.end(),alloc_pair_int_t());
457 if (!CheckEqualContainers(int_map
, fmap
))
459 auto fmmap
= multimap(ordered_range
, int_mmap
.begin(), int_mmap
.end(),alloc_pair_int_t());
460 if (!CheckEqualContainers(int_mmap
, fmmap
))
469 }}} //namespace boost::container::test
473 //Recursive container instantiation
475 map
<recursive_map
, recursive_map
> map_
;
476 multimap
<recursive_multimap
, recursive_multimap
> multimap_
;
478 //Allocator argument container
480 map
<int, int> map_((map
<int, int>::allocator_type()));
481 multimap
<int, int> multimap_((multimap
<int, int>::allocator_type()));
483 //Now test move semantics
485 test_move
<map
<recursive_map
, recursive_map
> >();
486 test_move
<multimap
<recursive_multimap
, recursive_multimap
> >();
489 //Test std::pair value type as tree has workarounds to make old std::pair
490 //implementations movable that can break things
492 boost::container::map
<pair_t
, pair_t
> s
;
493 std::pair
<const pair_t
,pair_t
> p
;
498 ////////////////////////////////////
499 // Testing allocator implementations
500 ////////////////////////////////////
502 typedef std::map
<int, int> MyStdMap
;
503 typedef std::multimap
<int, int> MyStdMultiMap
;
505 if (0 != test::map_test
506 < GetAllocatorMap
<std::allocator
<void>, red_black_tree
>::apply
<int>::map_type
508 , GetAllocatorMap
<std::allocator
<void>, red_black_tree
>::apply
<int>::multimap_type
509 , MyStdMultiMap
>()) {
510 std::cout
<< "Error in map_test<std::allocator<void>, red_black_tree>" << std::endl
;
514 if (0 != test::map_test
515 < GetAllocatorMap
<new_allocator
<void>, avl_tree
>::apply
<int>::map_type
517 , GetAllocatorMap
<new_allocator
<void>, avl_tree
>::apply
<int>::multimap_type
518 , MyStdMultiMap
>()) {
519 std::cout
<< "Error in map_test<new_allocator<void>, avl_tree>" << std::endl
;
523 if (0 != test::map_test
524 < GetAllocatorMap
<adaptive_pool
<void>, scapegoat_tree
>::apply
<int>::map_type
526 , GetAllocatorMap
<adaptive_pool
<void>, scapegoat_tree
>::apply
<int>::multimap_type
527 , MyStdMultiMap
>()) {
528 std::cout
<< "Error in map_test<adaptive_pool<void>, scapegoat_tree>" << std::endl
;
534 if (0 != test::map_test
535 < GetAllocatorMap
<new_allocator
<void>, splay_tree
>::apply
<test::movable_int
>::map_type
537 , GetAllocatorMap
<new_allocator
<void>, splay_tree
>::apply
<test::movable_int
>::multimap_type
538 , MyStdMultiMap
>()) {
539 std::cout
<< "Error in map_test<new_allocator<void>, splay_tree>" << std::endl
;
543 if (0 != test::map_test
544 < GetAllocatorMap
<new_allocator
<void>, red_black_tree
>::apply
<test::copyable_int
>::map_type
546 , GetAllocatorMap
<new_allocator
<void>, red_black_tree
>::apply
<test::copyable_int
>::multimap_type
547 , MyStdMultiMap
>()) {
548 std::cout
<< "Error in map_test<new_allocator<void>, red_black_tree>" << std::endl
;
552 if (0 != test::map_test
553 < GetAllocatorMap
<new_allocator
<void>, red_black_tree
>::apply
<test::movable_and_copyable_int
>::map_type
555 , GetAllocatorMap
<new_allocator
<void>, red_black_tree
>::apply
<test::movable_and_copyable_int
>::multimap_type
556 , MyStdMultiMap
>()) {
557 std::cout
<< "Error in map_test<new_allocator<void>, red_black_tree>" << std::endl
;
562 ////////////////////////////////////
564 ////////////////////////////////////
565 const test::EmplaceOptions MapOptions
= (test::EmplaceOptions
)(test::EMPLACE_HINT_PAIR
| test::EMPLACE_ASSOC_PAIR
);
566 if(!boost::container::test::test_emplace
<map
<test::EmplaceInt
, test::EmplaceInt
>, MapOptions
>())
568 if(!boost::container::test::test_emplace
<multimap
<test::EmplaceInt
, test::EmplaceInt
>, MapOptions
>())
571 ////////////////////////////////////
572 // Allocator propagation testing
573 ////////////////////////////////////
574 if(!boost::container::test::test_propagate_allocator
<boost_container_map
>())
577 if(!boost::container::test::test_propagate_allocator
<boost_container_multimap
>())
580 if (!boost::container::test::test_map_support_for_initialization_list_for
<map
<int, int> >())
583 if (!boost::container::test::test_map_support_for_initialization_list_for
<multimap
<int, int> >())
586 ////////////////////////////////////
588 ////////////////////////////////////
590 typedef boost::container::map
<int, int> cont_int
;
591 cont_int a
; a
.insert(cont_int::value_type(0, 9)); a
.insert(cont_int::value_type(1, 9)); a
.insert(cont_int::value_type(2, 9));
592 boost::intrusive::test::test_iterator_bidirectional
< cont_int
>(a
);
593 if(boost::report_errors() != 0) {
598 typedef boost::container::multimap
<int, int> cont_int
;
599 cont_int a
; a
.insert(cont_int::value_type(0, 9)); a
.insert(cont_int::value_type(1, 9)); a
.insert(cont_int::value_type(2, 9));
600 boost::intrusive::test::test_iterator_bidirectional
< cont_int
>(a
);
601 if(boost::report_errors() != 0) {
606 ////////////////////////////////////
607 // Node extraction/insertion testing functions
608 ////////////////////////////////////
609 if(!node_type_test())
612 ////////////////////////////////////
613 // Constructor Template Auto Deduction test
614 ////////////////////////////////////
615 if (!test::constructor_template_auto_deduction_test()) {
619 if (!boost::container::test::instantiate_constructors
<map
<int, int>, multimap
<int, int> >())
622 test::test_merge_from_different_comparison();
624 if(!test::test_heterogeneous_lookups())
627 ////////////////////////////////////
628 // Test optimize_size option
629 ////////////////////////////////////
633 typedef map
< int*, int*, std::less
<int*>, std::allocator
< std::pair
<int *const, int*> >
634 , tree_assoc_options
< optimize_size
<false>, tree_type
<red_black_tree
> >::type
> rbmap_size_optimized_no
;
636 typedef map
< int*, int*, std::less
<int*>, std::allocator
< std::pair
<int *const, int*> >
637 , tree_assoc_options
< optimize_size
<true>, tree_type
<avl_tree
> >::type
> avlmap_size_optimized_yes
;
641 typedef multimap
< int*, int*, std::less
<int*>, std::allocator
< std::pair
<int *const, int*> >
642 , tree_assoc_options
< optimize_size
<true>, tree_type
<red_black_tree
> >::type
> rbmmap_size_optimized_yes
;
643 typedef multimap
< int*, int*, std::less
<int*>, std::allocator
< std::pair
<int *const, int*> >
644 , tree_assoc_options
< optimize_size
<false>, tree_type
<avl_tree
> >::type
> avlmmap_size_optimized_no
;
646 BOOST_STATIC_ASSERT(sizeof(rbmmap_size_optimized_yes
) < sizeof(rbmap_size_optimized_no
));
647 BOOST_STATIC_ASSERT(sizeof(avlmap_size_optimized_yes
) < sizeof(avlmmap_size_optimized_no
));
649 ////////////////////////////////////
650 // has_trivial_destructor_after_move testing
651 ////////////////////////////////////
653 typedef std::pair
<const int, int> value_type
;
659 typedef boost::container::map
<int, int> cont
;
660 typedef boost::container::dtl::tree
<value_type
, int, std::less
<int>, void, void> tree
;
661 BOOST_STATIC_ASSERT_MSG(
662 !(boost::has_trivial_destructor_after_move
<cont
>::value
!=
663 boost::has_trivial_destructor_after_move
<tree
>::value
)
664 , "has_trivial_destructor_after_move(map, default allocator) test failed");
668 typedef boost::container::map
<int, int, std::less
<int>, std::allocator
<value_type
> > cont
;
669 typedef boost::container::dtl::tree
<value_type
, int, std::less
<int>, std::allocator
<value_type
>, void> tree
;
670 BOOST_STATIC_ASSERT_MSG(
671 !(boost::has_trivial_destructor_after_move
<cont
>::value
!=
672 boost::has_trivial_destructor_after_move
<tree
>::value
)
673 , "has_trivial_destructor_after_move(map, std::allocator) test failed");
681 typedef boost::container::multimap
<int, int> cont
;
682 typedef boost::container::dtl::tree
<value_type
, int, std::less
<int>, void, void> tree
;
683 BOOST_STATIC_ASSERT_MSG(
684 !(boost::has_trivial_destructor_after_move
<cont
>::value
!=
685 boost::has_trivial_destructor_after_move
<tree
>::value
)
686 , "has_trivial_destructor_after_move(multimap, default allocator) test failed");
690 typedef boost::container::multimap
<int, int, std::less
<int>, std::allocator
<value_type
> > cont
;
691 typedef boost::container::dtl::tree
<value_type
, int, std::less
<int>, std::allocator
<value_type
>, void> tree
;
692 BOOST_STATIC_ASSERT_MSG(
693 !(boost::has_trivial_destructor_after_move
<cont
>::value
!=
694 boost::has_trivial_destructor_after_move
<tree
>::value
)
695 , "has_trivial_destructor_after_move(multimap, std::allocator) test failed");