1 //////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2005-2015. 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 //////////////////////////////////////////////////////////////////////////////
11 #ifndef BOOST_CONTAINER_TREE_HPP
12 #define BOOST_CONTAINER_TREE_HPP
14 #ifndef BOOST_CONFIG_HPP
15 # include <boost/config.hpp>
18 #if defined(BOOST_HAS_PRAGMA_ONCE)
22 #include <boost/container/detail/config_begin.hpp>
23 #include <boost/container/detail/workaround.hpp>
25 #include <boost/container/allocator_traits.hpp>
26 #include <boost/container/container_fwd.hpp>
27 #include <boost/container/options.hpp>
28 #include <boost/container/node_handle.hpp>
31 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
32 #include <boost/container/detail/compare_functors.hpp>
33 #include <boost/container/detail/destroyers.hpp>
34 #include <boost/container/detail/iterator.hpp>
35 #include <boost/container/detail/iterators.hpp>
36 #include <boost/container/detail/node_alloc_holder.hpp>
37 #include <boost/container/detail/pair.hpp>
38 #include <boost/container/detail/type_traits.hpp>
40 #include <boost/intrusive/pointer_traits.hpp>
41 #include <boost/intrusive/rbtree.hpp>
42 #include <boost/intrusive/avltree.hpp>
43 #include <boost/intrusive/splaytree.hpp>
44 #include <boost/intrusive/sgtree.hpp>
46 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
47 #include <boost/intrusive/detail/tree_value_compare.hpp> //tree_value_compare
49 #include <boost/move/utility_core.hpp>
51 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
52 #include <boost/move/detail/fwd_macros.hpp>
54 #include <boost/move/detail/move_helpers.hpp>
56 #include <boost/core/no_exceptions_support.hpp>
60 #include <boost/container/detail/std_fwd.hpp>
66 using boost::intrusive::tree_value_compare;
68 template<class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
69 struct intrusive_tree_hook;
71 template<class VoidPointer, bool OptimizeSize>
72 struct intrusive_tree_hook<VoidPointer, boost::container::red_black_tree, OptimizeSize>
74 typedef typename dtl::bi::make_set_base_hook
75 < dtl::bi::void_pointer<VoidPointer>
76 , dtl::bi::link_mode<dtl::bi::normal_link>
77 , dtl::bi::optimize_size<OptimizeSize>
81 template<class VoidPointer, bool OptimizeSize>
82 struct intrusive_tree_hook<VoidPointer, boost::container::avl_tree, OptimizeSize>
84 typedef typename dtl::bi::make_avl_set_base_hook
85 < dtl::bi::void_pointer<VoidPointer>
86 , dtl::bi::link_mode<dtl::bi::normal_link>
87 , dtl::bi::optimize_size<OptimizeSize>
91 template<class VoidPointer, bool OptimizeSize>
92 struct intrusive_tree_hook<VoidPointer, boost::container::scapegoat_tree, OptimizeSize>
94 typedef typename dtl::bi::make_bs_set_base_hook
95 < dtl::bi::void_pointer<VoidPointer>
96 , dtl::bi::link_mode<dtl::bi::normal_link>
100 template<class VoidPointer, bool OptimizeSize>
101 struct intrusive_tree_hook<VoidPointer, boost::container::splay_tree, OptimizeSize>
103 typedef typename dtl::bi::make_bs_set_base_hook
104 < dtl::bi::void_pointer<VoidPointer>
105 , dtl::bi::link_mode<dtl::bi::normal_link>
109 //This trait is used to type-pun std::pair because in C++03
110 //compilers std::pair is useless for C++11 features
112 struct tree_internal_data_type
117 template<class T1, class T2>
118 struct tree_internal_data_type< std::pair<T1, T2> >
120 typedef pair<typename boost::move_detail::remove_const<T1>::type, T2> type;
123 //The node to be store in the tree
124 template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
126 : public intrusive_tree_hook<VoidPointer, tree_type_value, OptimizeSize>::type
129 typedef typename intrusive_tree_hook
130 <VoidPointer, tree_type_value, OptimizeSize>::type hook_type;
131 typedef T value_type;
132 typedef typename tree_internal_data_type<T>::type internal_type;
134 typedef tree_node< T, VoidPointer
135 , tree_type_value, OptimizeSize> node_t;
137 typedef typename boost::container::dtl::aligned_storage
138 <sizeof(T), boost::container::dtl::alignment_of<T>::value>::type storage_t;
141 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600) && (BOOST_GCC < 80000)
142 #pragma GCC diagnostic push
143 #pragma GCC diagnostic ignored "-Wstrict-aliasing"
144 #define BOOST_CONTAINER_DISABLE_ALIASING_WARNING
147 BOOST_CONTAINER_FORCEINLINE T &get_data()
148 { return *reinterpret_cast<T*>(this->m_storage.data); }
150 BOOST_CONTAINER_FORCEINLINE const T &get_data() const
151 { return *reinterpret_cast<const T*>(this->m_storage.data); }
153 BOOST_CONTAINER_FORCEINLINE T *get_data_ptr()
154 { return reinterpret_cast<T*>(this->m_storage.data); }
156 BOOST_CONTAINER_FORCEINLINE const T *get_data_ptr() const
157 { return reinterpret_cast<T*>(this->m_storage.data); }
159 BOOST_CONTAINER_FORCEINLINE internal_type &get_real_data()
160 { return *reinterpret_cast<internal_type*>(this->m_storage.data); }
162 BOOST_CONTAINER_FORCEINLINE const internal_type &get_real_data() const
163 { return *reinterpret_cast<const internal_type*>(this->m_storage.data); }
165 BOOST_CONTAINER_FORCEINLINE internal_type *get_real_data_ptr()
166 { return reinterpret_cast<internal_type*>(this->m_storage.data); }
168 BOOST_CONTAINER_FORCEINLINE const internal_type *get_real_data_ptr() const
169 { return reinterpret_cast<internal_type*>(this->m_storage.data); }
171 BOOST_CONTAINER_FORCEINLINE ~tree_node()
172 { reinterpret_cast<internal_type*>(this->m_storage.data)->~internal_type(); }
174 #if defined(BOOST_CONTAINER_DISABLE_ALIASING_WARNING)
175 #pragma GCC diagnostic pop
176 #undef BOOST_CONTAINER_DISABLE_ALIASING_WARNING
179 BOOST_CONTAINER_FORCEINLINE void destroy_header()
180 { static_cast<hook_type*>(this)->~hook_type(); }
182 template<class T1, class T2>
183 BOOST_CONTAINER_FORCEINLINE void do_assign(const std::pair<const T1, T2> &p)
185 const_cast<T1&>(this->get_real_data().first) = p.first;
186 this->get_real_data().second = p.second;
189 template<class T1, class T2>
190 BOOST_CONTAINER_FORCEINLINE void do_assign(const pair<const T1, T2> &p)
192 const_cast<T1&>(this->get_real_data().first) = p.first;
193 this->get_real_data().second = p.second;
197 BOOST_CONTAINER_FORCEINLINE void do_assign(const V &v)
198 { this->get_real_data() = v; }
200 template<class T1, class T2>
201 BOOST_CONTAINER_FORCEINLINE void do_move_assign(std::pair<const T1, T2> &p)
203 const_cast<T1&>(this->get_real_data().first) = ::boost::move(p.first);
204 this->get_real_data().second = ::boost::move(p.second);
207 template<class T1, class T2>
208 BOOST_CONTAINER_FORCEINLINE void do_move_assign(pair<const T1, T2> &p)
210 const_cast<T1&>(this->get_real_data().first) = ::boost::move(p.first);
211 this->get_real_data().second = ::boost::move(p.second);
215 BOOST_CONTAINER_FORCEINLINE void do_move_assign(V &v)
216 { this->get_real_data() = ::boost::move(v); }
219 template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
220 struct iiterator_node_value_type< tree_node<T, VoidPointer, tree_type_value, OptimizeSize> > {
224 template<class Node, class Icont>
225 class insert_equal_end_hint_functor
230 BOOST_CONTAINER_FORCEINLINE insert_equal_end_hint_functor(Icont &icont)
234 BOOST_CONTAINER_FORCEINLINE void operator()(Node &n)
235 { this->icont_.insert_equal(this->icont_.cend(), n); }
238 template<class Node, class Icont>
239 class push_back_functor
244 BOOST_CONTAINER_FORCEINLINE push_back_functor(Icont &icont)
248 BOOST_CONTAINER_FORCEINLINE void operator()(Node &n)
249 { this->icont_.push_back(n); }
256 template< class NodeType, class NodeCompareType
257 , class SizeType, class HookType
258 , boost::container::tree_type_enum tree_type_value>
259 struct intrusive_tree_dispatch;
261 template<class NodeType, class NodeCompareType, class SizeType, class HookType>
262 struct intrusive_tree_dispatch
263 <NodeType, NodeCompareType, SizeType, HookType, boost::container::red_black_tree>
265 typedef typename dtl::bi::make_rbtree
267 ,dtl::bi::compare<NodeCompareType>
268 ,dtl::bi::base_hook<HookType>
269 ,dtl::bi::constant_time_size<true>
270 ,dtl::bi::size_type<SizeType>
274 template<class NodeType, class NodeCompareType, class SizeType, class HookType>
275 struct intrusive_tree_dispatch
276 <NodeType, NodeCompareType, SizeType, HookType, boost::container::avl_tree>
278 typedef typename dtl::bi::make_avltree
280 ,dtl::bi::compare<NodeCompareType>
281 ,dtl::bi::base_hook<HookType>
282 ,dtl::bi::constant_time_size<true>
283 ,dtl::bi::size_type<SizeType>
287 template<class NodeType, class NodeCompareType, class SizeType, class HookType>
288 struct intrusive_tree_dispatch
289 <NodeType, NodeCompareType, SizeType, HookType, boost::container::scapegoat_tree>
291 typedef typename dtl::bi::make_sgtree
293 ,dtl::bi::compare<NodeCompareType>
294 ,dtl::bi::base_hook<HookType>
295 ,dtl::bi::floating_point<true>
296 ,dtl::bi::size_type<SizeType>
300 template<class NodeType, class NodeCompareType, class SizeType, class HookType>
301 struct intrusive_tree_dispatch
302 <NodeType, NodeCompareType, SizeType, HookType, boost::container::splay_tree>
304 typedef typename dtl::bi::make_splaytree
306 ,dtl::bi::compare<NodeCompareType>
307 ,dtl::bi::base_hook<HookType>
308 ,dtl::bi::constant_time_size<true>
309 ,dtl::bi::size_type<SizeType>
313 template<class Allocator, class ValueCompare, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
314 struct intrusive_tree_type
317 typedef typename boost::container::
318 allocator_traits<Allocator>::value_type value_type;
319 typedef typename boost::container::
320 allocator_traits<Allocator>::void_pointer void_pointer;
321 typedef typename boost::container::
322 allocator_traits<Allocator>::size_type size_type;
323 typedef typename dtl::tree_node
324 < value_type, void_pointer
325 , tree_type_value, OptimizeSize> node_t;
326 typedef value_to_node_compare
327 <node_t, ValueCompare> node_compare_type;
328 //Deducing the hook type from node_t (e.g. node_t::hook_type) would
329 //provoke an early instantiation of node_t that could ruin recursive
330 //tree definitions, so retype the complete type to avoid any problem.
331 typedef typename intrusive_tree_hook
332 <void_pointer, tree_type_value
333 , OptimizeSize>::type hook_type;
335 typedef typename intrusive_tree_dispatch
336 < node_t, node_compare_type
337 , size_type, hook_type
338 , tree_type_value>::type type;
341 //Trait to detect manually rebalanceable tree types
342 template<boost::container::tree_type_enum tree_type_value>
343 struct is_manually_balanceable
344 { static const bool value = true; };
346 template<> struct is_manually_balanceable<red_black_tree>
347 { static const bool value = false; };
349 template<> struct is_manually_balanceable<avl_tree>
350 { static const bool value = false; };
352 //Proxy traits to implement different operations depending on the
353 //is_manually_balanceable<>::value
354 template< boost::container::tree_type_enum tree_type_value
355 , bool IsManuallyRebalanceable = is_manually_balanceable<tree_type_value>::value>
356 struct intrusive_tree_proxy
358 template<class Icont>
359 BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &) {}
362 template<boost::container::tree_type_enum tree_type_value>
363 struct intrusive_tree_proxy<tree_type_value, true>
365 template<class Icont>
366 BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &c)
374 //This functor will be used with Intrusive clone functions to obtain
375 //already allocated nodes from a intrusive container instead of
376 //allocating new ones. When the intrusive container runs out of nodes
377 //the node holder is used instead.
378 template<class AllocHolder, bool DoMove>
379 class RecyclingCloner
381 typedef typename AllocHolder::intrusive_container intrusive_container;
382 typedef typename AllocHolder::Node node_t;
383 typedef typename AllocHolder::NodePtr node_ptr_type;
386 RecyclingCloner(AllocHolder &holder, intrusive_container &itree)
387 : m_holder(holder), m_icont(itree)
390 BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<true>)
391 { p->do_move_assign(const_cast<node_t &>(other).get_real_data()); }
393 BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<false>)
394 { p->do_assign(other.get_real_data()); }
396 node_ptr_type operator()(const node_t &other) const
398 if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){
399 //First recycle a node (this can't throw)
402 this->do_assign(p, other, bool_<DoMove>());
406 //If there is an exception destroy the whole source
407 m_holder.destroy_node(p);
408 while((p = m_icont.unlink_leftmost_without_rebalance())){
409 m_holder.destroy_node(p);
416 return m_holder.create_node(other.get_real_data());
420 AllocHolder &m_holder;
421 intrusive_container &m_icont;
425 template<class KeyCompare, class KeyOfValue>
426 struct key_node_compare
427 : public boost::intrusive::detail::ebo_functor_holder<KeyCompare>
429 BOOST_CONTAINER_FORCEINLINE explicit key_node_compare(const KeyCompare &comp)
433 typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t;
434 typedef KeyCompare key_compare;
435 typedef KeyOfValue key_of_value;
436 typedef typename KeyOfValue::type key_type;
439 template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
440 BOOST_CONTAINER_FORCEINLINE static const key_type &
441 key_from(const tree_node<T, VoidPointer, tree_type_value, OptimizeSize> &n)
443 return key_of_value()(n.get_data());
447 BOOST_CONTAINER_FORCEINLINE static const T &
453 BOOST_CONTAINER_FORCEINLINE const key_compare &key_comp() const
454 { return static_cast<const key_compare &>(*this); }
456 BOOST_CONTAINER_FORCEINLINE key_compare &key_comp()
457 { return static_cast<key_compare &>(*this); }
459 BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const
460 { return this->key_comp()(key1, key2); }
463 BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const U &nonkey2) const
464 { return this->key_comp()(key1, this->key_from(nonkey2)); }
467 BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2) const
468 { return this->key_comp()(this->key_from(nonkey1), key2); }
470 template<class U, class V>
471 BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const V &nonkey2) const
472 { return this->key_comp()(this->key_from(nonkey1), this->key_from(nonkey2)); }
475 template<class Options>
478 typedef Options type;
482 struct get_tree_opt<void>
484 typedef tree_assoc_defaults type;
487 template<class, class KeyOfValue>
488 struct real_key_of_value
490 typedef KeyOfValue type;
494 struct real_key_of_value<T, void>
496 typedef dtl::identity<T> type;
499 template<class T1, class T2>
500 struct real_key_of_value<std::pair<T1, T2>, int>
502 typedef dtl::select1st<T1> type;
505 template<class T1, class T2>
506 struct real_key_of_value<boost::container::pair<T1, T2>, int>
508 typedef dtl::select1st<T1> type;
511 template <class T, class KeyOfValue, class Compare, class Allocator, class Options>
513 : public dtl::node_alloc_holder
514 < typename real_allocator<T, Allocator>::type
515 , typename dtl::intrusive_tree_type
516 < typename real_allocator<T, Allocator>::type
518 <typename allocator_traits<typename real_allocator<T, Allocator>::type>::pointer, Compare, typename real_key_of_value<T, KeyOfValue>::type>
519 , get_tree_opt<Options>::type::tree_type
520 , get_tree_opt<Options>::type::optimize_size
524 typedef tree < T, KeyOfValue
525 , Compare, Allocator, Options> ThisType;
527 typedef typename real_allocator<T, Allocator>::type allocator_type;
530 typedef allocator_traits<allocator_type> allocator_traits_t;
531 typedef typename real_key_of_value<T, KeyOfValue>::type key_of_value_t;
532 typedef tree_value_compare
533 < typename allocator_traits_t::pointer
535 , key_of_value_t> ValComp;
536 typedef typename get_tree_opt<Options>::type options_type;
537 typedef typename dtl::intrusive_tree_type
538 < allocator_type, ValComp
539 , options_type::tree_type
540 , options_type::optimize_size
542 typedef dtl::node_alloc_holder
543 <allocator_type, Icont> AllocHolder;
544 typedef typename AllocHolder::NodePtr NodePtr;
546 typedef typename AllocHolder::NodeAlloc NodeAlloc;
547 typedef boost::container::
548 allocator_traits<NodeAlloc> allocator_traits_type;
549 typedef typename AllocHolder::ValAlloc ValAlloc;
550 typedef typename AllocHolder::Node Node;
551 typedef typename Icont::iterator iiterator;
552 typedef typename Icont::const_iterator iconst_iterator;
553 typedef dtl::allocator_destroyer<NodeAlloc> Destroyer;
554 typedef typename AllocHolder::alloc_version alloc_version;
555 typedef intrusive_tree_proxy<options_type::tree_type> intrusive_tree_proxy_t;
557 BOOST_COPYABLE_AND_MOVABLE(tree)
561 typedef typename key_of_value_t::type key_type;
562 typedef T value_type;
563 typedef Compare key_compare;
564 typedef ValComp value_compare;
565 typedef typename boost::container::
566 allocator_traits<allocator_type>::pointer pointer;
567 typedef typename boost::container::
568 allocator_traits<allocator_type>::const_pointer const_pointer;
569 typedef typename boost::container::
570 allocator_traits<allocator_type>::reference reference;
571 typedef typename boost::container::
572 allocator_traits<allocator_type>::const_reference const_reference;
573 typedef typename boost::container::
574 allocator_traits<allocator_type>::size_type size_type;
575 typedef typename boost::container::
576 allocator_traits<allocator_type>::difference_type difference_type;
577 typedef dtl::iterator_from_iiterator
578 <iiterator, false> iterator;
579 typedef dtl::iterator_from_iiterator
580 <iiterator, true > const_iterator;
581 typedef boost::container::reverse_iterator
582 <iterator> reverse_iterator;
583 typedef boost::container::reverse_iterator
584 <const_iterator> const_reverse_iterator;
586 < NodeAlloc, void> node_type;
587 typedef insert_return_type_base
588 <iterator, node_type> insert_return_type;
590 typedef NodeAlloc stored_allocator_type;
594 typedef key_node_compare<key_compare, key_of_value_t> KeyNodeCompare;
598 BOOST_CONTAINER_FORCEINLINE tree()
602 BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp)
603 : AllocHolder(ValComp(comp))
606 BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a)
607 : AllocHolder(ValComp(comp), a)
610 BOOST_CONTAINER_FORCEINLINE explicit tree(const allocator_type& a)
614 template <class InputIterator>
615 tree(bool unique_insertion, InputIterator first, InputIterator last)
616 : AllocHolder(value_compare(key_compare()))
618 this->tree_construct(unique_insertion, first, last);
619 //AllocHolder clears in case of exception
622 template <class InputIterator>
623 tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp)
624 : AllocHolder(value_compare(comp))
626 this->tree_construct(unique_insertion, first, last);
627 //AllocHolder clears in case of exception
630 template <class InputIterator>
631 tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a)
632 : AllocHolder(value_compare(comp), a)
634 this->tree_construct(unique_insertion, first, last);
635 //AllocHolder clears in case of exception
638 //construct with ordered range
639 template <class InputIterator>
640 tree( ordered_range_t, InputIterator first, InputIterator last)
641 : AllocHolder(value_compare(key_compare()))
643 this->tree_construct(ordered_range_t(), first, last);
646 template <class InputIterator>
647 tree( ordered_range_t, InputIterator first, InputIterator last, const key_compare& comp)
648 : AllocHolder(value_compare(comp))
650 this->tree_construct(ordered_range_t(), first, last);
653 template <class InputIterator>
654 tree( ordered_range_t, InputIterator first, InputIterator last
655 , const key_compare& comp, const allocator_type& a)
656 : AllocHolder(value_compare(comp), a)
658 this->tree_construct(ordered_range_t(), first, last);
663 template <class InputIterator>
664 void tree_construct(bool unique_insertion, InputIterator first, InputIterator last)
666 //Use cend() as hint to achieve linear time for
667 //ordered ranges as required by the standard
668 //for the constructor
669 if(unique_insertion){
670 const const_iterator end_it(this->cend());
671 for ( ; first != last; ++first){
672 this->insert_unique_convertible(end_it, *first);
676 this->tree_construct_non_unique(first, last);
680 template <class InputIterator>
681 void tree_construct_non_unique(InputIterator first, InputIterator last
682 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
683 , typename dtl::enable_if_or
685 , dtl::is_same<alloc_version, version_1>
686 , dtl::is_input_iterator<InputIterator>
691 //Use cend() as hint to achieve linear time for
692 //ordered ranges as required by the standard
693 //for the constructor
694 const const_iterator end_it(this->cend());
695 for ( ; first != last; ++first){
696 this->insert_equal_convertible(end_it, *first);
700 template <class InputIterator>
701 void tree_construct_non_unique(InputIterator first, InputIterator last
702 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
703 , typename dtl::disable_if_or
705 , dtl::is_same<alloc_version, version_1>
706 , dtl::is_input_iterator<InputIterator>
711 //Optimized allocation and construction
712 this->allocate_many_and_construct
713 ( first, boost::container::iterator_distance(first, last)
714 , insert_equal_end_hint_functor<Node, Icont>(this->icont()));
717 template <class InputIterator>
718 void tree_construct( ordered_range_t, InputIterator first, InputIterator last
719 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
720 , typename dtl::disable_if_or
722 , dtl::is_same<alloc_version, version_1>
723 , dtl::is_input_iterator<InputIterator>
728 //Optimized allocation and construction
729 this->allocate_many_and_construct
730 ( first, boost::container::iterator_distance(first, last)
731 , dtl::push_back_functor<Node, Icont>(this->icont()));
732 //AllocHolder clears in case of exception
735 template <class InputIterator>
736 void tree_construct( ordered_range_t, InputIterator first, InputIterator last
737 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
738 , typename dtl::enable_if_or
740 , dtl::is_same<alloc_version, version_1>
741 , dtl::is_input_iterator<InputIterator>
746 for ( ; first != last; ++first){
747 this->push_back_impl(*first);
753 BOOST_CONTAINER_FORCEINLINE tree(const tree& x)
754 : AllocHolder(x, x.value_comp())
756 this->icont().clone_from
757 (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
760 BOOST_CONTAINER_FORCEINLINE tree(BOOST_RV_REF(tree) x)
761 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
762 : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp())
765 BOOST_CONTAINER_FORCEINLINE tree(const tree& x, const allocator_type &a)
766 : AllocHolder(x.value_comp(), a)
768 this->icont().clone_from
769 (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
770 //AllocHolder clears in case of exception
773 tree(BOOST_RV_REF(tree) x, const allocator_type &a)
774 : AllocHolder(x.value_comp(), a)
776 if(this->node_alloc() == x.node_alloc()){
777 this->icont().swap(x.icont());
780 this->icont().clone_from
781 (boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc()));
783 //AllocHolder clears in case of exception
786 BOOST_CONTAINER_FORCEINLINE ~tree()
787 {} //AllocHolder clears the tree
789 tree& operator=(BOOST_COPY_ASSIGN_REF(tree) x)
791 if (BOOST_LIKELY(this != &x)) {
792 NodeAlloc &this_alloc = this->get_stored_allocator();
793 const NodeAlloc &x_alloc = x.get_stored_allocator();
794 dtl::bool_<allocator_traits<NodeAlloc>::
795 propagate_on_container_copy_assignment::value> flag;
796 if(flag && this_alloc != x_alloc){
799 this->AllocHolder::copy_assign_alloc(x);
800 //Transfer all the nodes to a temporary tree
801 //If anything goes wrong, all the nodes will be destroyed
803 Icont other_tree(::boost::move(this->icont()));
805 //Now recreate the source tree reusing nodes stored by other_tree
806 this->icont().clone_from
808 , RecyclingCloner<AllocHolder, false>(*this, other_tree)
809 , Destroyer(this->node_alloc()));
811 //If there are remaining nodes, destroy them
813 while((p = other_tree.unlink_leftmost_without_rebalance())){
814 AllocHolder::destroy_node(p);
820 tree& operator=(BOOST_RV_REF(tree) x)
821 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
822 allocator_traits_type::is_always_equal::value) &&
823 boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
825 if (BOOST_LIKELY(this != &x)) {
826 NodeAlloc &this_alloc = this->node_alloc();
827 NodeAlloc &x_alloc = x.node_alloc();
828 const bool propagate_alloc = allocator_traits<NodeAlloc>::
829 propagate_on_container_move_assignment::value;
830 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
831 //Resources can be transferred if both allocators are
832 //going to be equal after this function (either propagated or already equal)
833 if(propagate_alloc || allocators_equal){
836 //Move allocator if needed
837 this->AllocHolder::move_assign_alloc(x);
839 this->icont() = boost::move(x.icont());
841 //Else do a one by one move
843 //Transfer all the nodes to a temporary tree
844 //If anything goes wrong, all the nodes will be destroyed
846 Icont other_tree(::boost::move(this->icont()));
848 //Now recreate the source tree reusing nodes stored by other_tree
849 this->icont().clone_from
850 (::boost::move(x.icont())
851 , RecyclingCloner<AllocHolder, true>(*this, other_tree)
852 , Destroyer(this->node_alloc()));
854 //If there are remaining nodes, destroy them
856 while((p = other_tree.unlink_leftmost_without_rebalance())){
857 AllocHolder::destroy_node(p);
866 BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const
867 { return this->icont().value_comp().predicate(); }
869 BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const
870 { return this->icont().value_comp().predicate().key_comp(); }
872 BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const
873 { return allocator_type(this->node_alloc()); }
875 BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const
876 { return this->node_alloc(); }
878 BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator()
879 { return this->node_alloc(); }
881 BOOST_CONTAINER_FORCEINLINE iterator begin()
882 { return iterator(this->icont().begin()); }
884 BOOST_CONTAINER_FORCEINLINE const_iterator begin() const
885 { return this->cbegin(); }
887 BOOST_CONTAINER_FORCEINLINE iterator end()
888 { return iterator(this->icont().end()); }
890 BOOST_CONTAINER_FORCEINLINE const_iterator end() const
891 { return this->cend(); }
893 BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin()
894 { return reverse_iterator(end()); }
896 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const
897 { return this->crbegin(); }
899 BOOST_CONTAINER_FORCEINLINE reverse_iterator rend()
900 { return reverse_iterator(begin()); }
902 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const
903 { return this->crend(); }
905 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
907 //! <b>Throws</b>: Nothing.
909 //! <b>Complexity</b>: Constant.
910 BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const
911 { return const_iterator(this->non_const_icont().begin()); }
913 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
915 //! <b>Throws</b>: Nothing.
917 //! <b>Complexity</b>: Constant.
918 BOOST_CONTAINER_FORCEINLINE const_iterator cend() const
919 { return const_iterator(this->non_const_icont().end()); }
921 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
922 //! of the reversed container.
924 //! <b>Throws</b>: Nothing.
926 //! <b>Complexity</b>: Constant.
927 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const
928 { return const_reverse_iterator(cend()); }
930 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
931 //! of the reversed container.
933 //! <b>Throws</b>: Nothing.
935 //! <b>Complexity</b>: Constant.
936 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const
937 { return const_reverse_iterator(cbegin()); }
939 BOOST_CONTAINER_FORCEINLINE bool empty() const
940 { return !this->size(); }
942 BOOST_CONTAINER_FORCEINLINE size_type size() const
943 { return this->icont().size(); }
945 BOOST_CONTAINER_FORCEINLINE size_type max_size() const
946 { return AllocHolder::max_size(); }
948 BOOST_CONTAINER_FORCEINLINE void swap(ThisType& x)
949 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
950 && boost::container::dtl::is_nothrow_swappable<Compare>::value )
951 { AllocHolder::swap(x); }
955 typedef typename Icont::insert_commit_data insert_commit_data;
958 std::pair<iterator,bool> insert_unique_check
959 (const key_type& key, insert_commit_data &data)
961 std::pair<iiterator, bool> ret =
962 this->icont().insert_unique_check(key, KeyNodeCompare(key_comp()), data);
963 return std::pair<iterator, bool>(iterator(ret.first), ret.second);
966 std::pair<iterator,bool> insert_unique_check
967 (const_iterator hint, const key_type& key, insert_commit_data &data)
969 BOOST_ASSERT((priv_is_linked)(hint));
970 std::pair<iiterator, bool> ret =
971 this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(key_comp()), data);
972 return std::pair<iterator, bool>(iterator(ret.first), ret.second);
975 template<class MovableConvertible>
976 iterator insert_unique_commit
977 (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data)
979 NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v));
980 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
981 iterator ret(this->icont().insert_unique_commit(*tmp, data));
982 destroy_deallocator.release();
986 template<class MovableConvertible>
987 std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) v)
989 insert_commit_data data;
990 std::pair<iterator,bool> ret =
991 this->insert_unique_check(key_of_value_t()(v), data);
993 ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
1000 template<class KeyConvertible, class M>
1001 iiterator priv_insert_or_assign_commit
1002 (BOOST_FWD_REF(KeyConvertible) key, BOOST_FWD_REF(M) obj, insert_commit_data &data)
1004 NodePtr tmp = AllocHolder::create_node(boost::forward<KeyConvertible>(key), boost::forward<M>(obj));
1005 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
1006 iiterator ret(this->icont().insert_unique_commit(*tmp, data));
1007 destroy_deallocator.release();
1011 bool priv_is_linked(const_iterator const position) const
1013 iiterator const cur(position.get());
1014 return cur == this->icont().end() ||
1015 cur == this->icont().root() ||
1016 iiterator(cur).go_parent().go_left() == cur ||
1017 iiterator(cur).go_parent().go_right() == cur;
1020 template<class MovableConvertible>
1021 void push_back_impl(BOOST_FWD_REF(MovableConvertible) v)
1023 NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
1024 //push_back has no-throw guarantee so avoid any deallocator/destroyer
1025 this->icont().push_back(*tmp);
1028 std::pair<iterator, bool> emplace_unique_impl(NodePtr p)
1030 value_type &v = p->get_data();
1031 insert_commit_data data;
1032 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc());
1033 std::pair<iterator,bool> ret =
1034 this->insert_unique_check(key_of_value_t()(v), data);
1038 //No throw insertion part, release rollback
1039 destroy_deallocator.release();
1040 return std::pair<iterator,bool>
1041 ( iterator(this->icont().insert_unique_commit(*p, data))
1045 iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p)
1047 BOOST_ASSERT((priv_is_linked)(hint));
1048 value_type &v = p->get_data();
1049 insert_commit_data data;
1050 std::pair<iterator,bool> ret =
1051 this->insert_unique_check(hint, key_of_value_t()(v), data);
1053 Destroyer(this->node_alloc())(p);
1056 return iterator(this->icont().insert_unique_commit(*p, data));
1061 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1063 template <class... Args>
1064 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args)
1065 { return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...)); }
1067 template <class... Args>
1068 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args)
1069 { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); }
1071 template <class... Args>
1072 iterator emplace_equal(BOOST_FWD_REF(Args)... args)
1074 NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
1075 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
1076 iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
1077 destroy_deallocator.release();
1081 template <class... Args>
1082 iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args)
1084 BOOST_ASSERT((priv_is_linked)(hint));
1085 NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
1086 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
1087 iterator ret(this->icont().insert_equal(hint.get(), *tmp));
1088 destroy_deallocator.release();
1092 template <class KeyType, class... Args>
1093 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace
1094 (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args)
1096 insert_commit_data data;
1097 const key_type & k = key; //Support emulated rvalue references
1098 std::pair<iiterator, bool> ret =
1099 hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)
1100 : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);
1102 ret.first = this->icont().insert_unique_commit
1103 (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key), boost::forward<Args>(args)...), data);
1105 return std::pair<iterator, bool>(iterator(ret.first), ret.second);
1108 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1110 #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \
1111 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1112 std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\
1113 { return this->emplace_unique_impl(AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\
1115 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1116 iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1117 { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\
1119 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1120 iterator emplace_equal(BOOST_MOVE_UREF##N)\
1122 NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
1123 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
1124 iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\
1125 destroy_deallocator.release();\
1129 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1130 iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1132 BOOST_ASSERT((priv_is_linked)(hint));\
1133 NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
1134 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
1135 iterator ret(this->icont().insert_equal(hint.get(), *tmp));\
1136 destroy_deallocator.release();\
1140 template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\
1141 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\
1142 try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1144 insert_commit_data data;\
1145 const key_type & k = key;\
1146 std::pair<iiterator, bool> ret =\
1147 hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)\
1148 : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);\
1150 ret.first = this->icont().insert_unique_commit\
1151 (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N), data);\
1153 return std::pair<iterator, bool>(iterator(ret.first), ret.second);\
1156 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE)
1157 #undef BOOST_CONTAINER_TREE_EMPLACE_CODE
1159 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1161 template<class MovableConvertible>
1162 iterator insert_unique_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
1164 BOOST_ASSERT((priv_is_linked)(hint));
1165 insert_commit_data data;
1166 std::pair<iterator,bool> ret =
1167 this->insert_unique_check(hint, key_of_value_t()(v), data);
1170 return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
1173 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_unique, value_type, iterator, this->insert_unique_convertible, const_iterator, const_iterator)
1175 template <class InputIterator>
1176 void insert_unique(InputIterator first, InputIterator last)
1178 for( ; first != last; ++first)
1179 this->insert_unique(*first);
1182 iterator insert_equal(const value_type& v)
1184 NodePtr tmp(AllocHolder::create_node(v));
1185 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
1186 iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
1187 destroy_deallocator.release();
1191 template<class MovableConvertible>
1192 iterator insert_equal(BOOST_FWD_REF(MovableConvertible) v)
1194 NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
1195 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
1196 iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
1197 destroy_deallocator.release();
1201 template<class MovableConvertible>
1202 iterator insert_equal_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
1204 BOOST_ASSERT((priv_is_linked)(hint));
1205 NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
1206 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
1207 iterator ret(this->icont().insert_equal(hint.get(), *tmp));
1208 destroy_deallocator.release();
1212 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_equal, value_type, iterator, this->insert_equal_convertible, const_iterator, const_iterator)
1214 template <class InputIterator>
1215 void insert_equal(InputIterator first, InputIterator last)
1217 for( ; first != last; ++first)
1218 this->insert_equal(*first);
1221 template<class KeyType, class M>
1222 std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj)
1224 insert_commit_data data;
1225 const key_type & k = key; //Support emulated rvalue references
1226 std::pair<iiterator, bool> ret =
1227 hint == const_iterator() ? this->icont().insert_unique_check(k, KeyNodeCompare(key_comp()), data)
1228 : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);
1230 ret.first = this->priv_insert_or_assign_commit(boost::forward<KeyType>(key), boost::forward<M>(obj), data);
1233 ret.first->get_data().second = boost::forward<M>(obj);
1235 return std::pair<iterator, bool>(iterator(ret.first), ret.second);
1238 iterator erase(const_iterator position)
1240 BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position));
1241 return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc())));
1244 BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& k)
1245 { return AllocHolder::erase_key(k, KeyNodeCompare(key_comp()), alloc_version()); }
1247 iterator erase(const_iterator first, const_iterator last)
1249 BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first)));
1250 BOOST_ASSERT(first == last || (priv_is_linked)(last));
1251 return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version()));
1254 node_type extract(const key_type& k)
1256 iterator const it = this->find(k);
1257 if(this->end() != it){
1258 return this->extract(it);
1263 node_type extract(const_iterator position)
1265 BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position));
1266 iiterator const iit(position.get());
1267 this->icont().erase(iit);
1268 return node_type(iit.operator->(), this->node_alloc());
1271 insert_return_type insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1273 return this->insert_unique_node(this->end(), boost::move(nh));
1276 insert_return_type insert_unique_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1278 insert_return_type irt; //inserted == false, node.empty()
1280 insert_commit_data data;
1281 std::pair<iterator,bool> ret =
1282 this->insert_unique_check(hint, key_of_value_t()(nh.value()), data);
1284 irt.inserted = true;
1285 irt.position = iterator(this->icont().insert_unique_commit(*nh.get(), data));
1289 irt.position = ret.first;
1290 irt.node = boost::move(nh);
1294 irt.position = this->end();
1296 return BOOST_MOVE_RET(insert_return_type, irt);
1299 iterator insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1305 NodePtr const p(nh.release());
1306 return iterator(this->icont().insert_equal(*p));
1310 iterator insert_equal_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1316 NodePtr const p(nh.release());
1317 return iterator(this->icont().insert_equal(hint.get(), *p));
1322 BOOST_CONTAINER_FORCEINLINE void merge_unique(tree<T, KeyOfValue, C2, Allocator, Options>& source)
1323 { return this->icont().merge_unique(source.icont()); }
1326 BOOST_CONTAINER_FORCEINLINE void merge_equal(tree<T, KeyOfValue, C2, Allocator, Options>& source)
1327 { return this->icont().merge_equal(source.icont()); }
1328 BOOST_CONTAINER_FORCEINLINE void clear()
1329 { AllocHolder::clear(alloc_version()); }
1331 // search operations. Const and non-const overloads even if no iterator is returned
1332 // so splay implementations can to their rebalancing when searching in non-const versions
1333 BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& k)
1334 { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); }
1336 BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& k) const
1337 { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); }
1340 BOOST_CONTAINER_FORCEINLINE
1341 typename dtl::enable_if_transparent<key_compare, K, iterator>::type
1343 { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); }
1346 BOOST_CONTAINER_FORCEINLINE
1347 typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
1348 find(const K& k) const
1349 { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); }
1351 BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& k) const
1352 { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); }
1355 BOOST_CONTAINER_FORCEINLINE
1356 typename dtl::enable_if_transparent<key_compare, K, size_type>::type
1357 count(const K& k) const
1358 { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); }
1360 BOOST_CONTAINER_FORCEINLINE bool contains(const key_type& x) const
1361 { return this->find(x) != this->cend(); }
1363 template<typename K>
1364 BOOST_CONTAINER_FORCEINLINE
1365 typename dtl::enable_if_transparent<key_compare, K, bool>::type
1366 contains(const K& x) const
1367 { return this->find(x) != this->cend(); }
1369 BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k)
1370 { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
1372 BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& k) const
1373 { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
1376 BOOST_CONTAINER_FORCEINLINE
1377 typename dtl::enable_if_transparent<key_compare, K, iterator>::type
1378 lower_bound(const K& k)
1379 { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
1382 BOOST_CONTAINER_FORCEINLINE
1383 typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
1384 lower_bound(const K& k) const
1385 { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
1387 BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& k)
1388 { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
1390 BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& k) const
1391 { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
1394 BOOST_CONTAINER_FORCEINLINE
1395 typename dtl::enable_if_transparent<key_compare, K, iterator>::type
1396 upper_bound(const K& k)
1397 { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
1400 BOOST_CONTAINER_FORCEINLINE
1401 typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
1402 upper_bound(const K& k) const
1403 { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
1405 std::pair<iterator,iterator> equal_range(const key_type& k)
1407 std::pair<iiterator, iiterator> ret =
1408 this->icont().equal_range(k, KeyNodeCompare(key_comp()));
1409 return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
1412 std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
1414 std::pair<iiterator, iiterator> ret =
1415 this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp()));
1416 return std::pair<const_iterator,const_iterator>
1417 (const_iterator(ret.first), const_iterator(ret.second));
1421 BOOST_CONTAINER_FORCEINLINE
1422 typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type
1423 equal_range(const K& k)
1425 std::pair<iiterator, iiterator> ret =
1426 this->icont().equal_range(k, KeyNodeCompare(key_comp()));
1427 return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
1431 BOOST_CONTAINER_FORCEINLINE
1432 typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type
1433 equal_range(const K& k) const
1435 std::pair<iiterator, iiterator> ret =
1436 this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp()));
1437 return std::pair<const_iterator,const_iterator>
1438 (const_iterator(ret.first), const_iterator(ret.second));
1441 std::pair<iterator,iterator> lower_bound_range(const key_type& k)
1443 std::pair<iiterator, iiterator> ret =
1444 this->icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
1445 return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
1448 std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
1450 std::pair<iiterator, iiterator> ret =
1451 this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
1452 return std::pair<const_iterator,const_iterator>
1453 (const_iterator(ret.first), const_iterator(ret.second));
1457 BOOST_CONTAINER_FORCEINLINE
1458 typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type
1459 lower_bound_range(const K& k)
1461 std::pair<iiterator, iiterator> ret =
1462 this->icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
1463 return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
1467 BOOST_CONTAINER_FORCEINLINE
1468 typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type
1469 lower_bound_range(const K& k) const
1471 std::pair<iiterator, iiterator> ret =
1472 this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
1473 return std::pair<const_iterator,const_iterator>
1474 (const_iterator(ret.first), const_iterator(ret.second));
1477 BOOST_CONTAINER_FORCEINLINE void rebalance()
1478 { intrusive_tree_proxy_t::rebalance(this->icont()); }
1480 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const tree& x, const tree& y)
1481 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1483 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const tree& x, const tree& y)
1484 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1486 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const tree& x, const tree& y)
1487 { return !(x == y); }
1489 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const tree& x, const tree& y)
1492 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const tree& x, const tree& y)
1493 { return !(y < x); }
1495 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const tree& x, const tree& y)
1496 { return !(x < y); }
1498 BOOST_CONTAINER_FORCEINLINE friend void swap(tree& x, tree& y)
1499 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1500 && boost::container::dtl::is_nothrow_swappable<Compare>::value )
1505 } //namespace container {
1508 struct has_trivial_destructor_after_move;
1510 //!has_trivial_destructor_after_move<> == true_type
1511 //!specialization for optimizations
1512 template <class T, class KeyOfValue, class Compare, class Allocator, class Options>
1513 struct has_trivial_destructor_after_move
1515 ::boost::container::dtl::tree
1516 <T, KeyOfValue, Compare, Allocator, Options>
1519 typedef typename ::boost::container::dtl::tree<T, KeyOfValue, Compare, Allocator, Options>::allocator_type allocator_type;
1520 typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
1521 static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value &&
1522 ::boost::has_trivial_destructor_after_move<pointer>::value &&
1523 ::boost::has_trivial_destructor_after_move<Compare>::value;
1526 } //namespace boost {
1528 #include <boost/container/detail/config_end.hpp>
1530 #endif //BOOST_CONTAINER_TREE_HPP