container/detail/tree.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost
0004 // Software License, Version 1.0. (See accompanying file
0005 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // See http://www.boost.org/libs/container for documentation.
0008 //
0009 //////////////////////////////////////////////////////////////////////////////
0010
0011 #ifndef BOOST_CONTAINER_TREE_HPP
0012 #define BOOST_CONTAINER_TREE_HPP
0013
0014 #ifndef BOOST_CONFIG_HPP
0015 #  include <boost/config.hpp>
0016 #endif
0017
0018 #if defined(BOOST_HAS_PRAGMA_ONCE)
0019 #  pragma once
0020 #endif
0021
0022 #include <boost/container/detail/config_begin.hpp>
0023 #include <boost/container/detail/workaround.hpp>
0024 // container
0025 #include <boost/container/allocator_traits.hpp>
0026 #include <boost/container/container_fwd.hpp>
0027 #include <boost/container/options.hpp>
0028 #include <boost/container/node_handle.hpp>
0029
0030 // container/detail
0031 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
0032 #include <boost/container/detail/compare_functors.hpp>
0033 #include <boost/container/detail/destroyers.hpp>
0034 #include <boost/container/detail/iterator.hpp>
0035 #include <boost/container/detail/iterators.hpp>
0036 #include <boost/container/detail/node_alloc_holder.hpp>
0037 #include <boost/container/detail/pair.hpp>
0038 #include <boost/container/detail/type_traits.hpp>
0039 // intrusive
0040 #include <boost/intrusive/pointer_traits.hpp>
0041 #include <boost/intrusive/rbtree.hpp>
0042 #include <boost/intrusive/avltree.hpp>
0043 #include <boost/intrusive/splaytree.hpp>
0044 #include <boost/intrusive/sgtree.hpp>
0045 // intrusive/detail
0046 #include <boost/intrusive/detail/minimal_pair_header.hpp>   //pair
0047 #include <boost/intrusive/detail/tree_value_compare.hpp>    //tree_value_compare
0048 // move
0049 #include <boost/move/utility_core.hpp>
0050 // move/detail
0051 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0052 #include <boost/move/detail/fwd_macros.hpp>
0053 #endif
0054 #include <boost/move/detail/move_helpers.hpp>
0055 #include <boost/move/detail/force_ptr.hpp>
0056
0057
0058
0059 #include <boost/container/detail/std_fwd.hpp>
0060
0061 namespace boost {
0062 namespace container {
0063 namespace dtl {
0064
0065 using boost::intrusive::tree_value_compare;
0066
0067 template<class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
0068 struct intrusive_tree_hook;
0069
0070 template<class VoidPointer, bool OptimizeSize>
0071 struct intrusive_tree_hook<VoidPointer, boost::container::red_black_tree, OptimizeSize>
0072 {
0073    typedef typename dtl::bi::make_set_base_hook
0074       < dtl::bi::void_pointer<VoidPointer>
0075       , dtl::bi::link_mode<dtl::bi::normal_link>
0076       , dtl::bi::optimize_size<OptimizeSize>
0077       >::type  type;
0078 };
0079
0080 template<class VoidPointer, bool OptimizeSize>
0081 struct intrusive_tree_hook<VoidPointer, boost::container::avl_tree, OptimizeSize>
0082 {
0083    typedef typename dtl::bi::make_avl_set_base_hook
0084       < dtl::bi::void_pointer<VoidPointer>
0085       , dtl::bi::link_mode<dtl::bi::normal_link>
0086       , dtl::bi::optimize_size<OptimizeSize>
0087       >::type  type;
0088 };
0089
0090 template<class VoidPointer, bool OptimizeSize>
0091 struct intrusive_tree_hook<VoidPointer, boost::container::scapegoat_tree, OptimizeSize>
0092 {
0093    typedef typename dtl::bi::make_bs_set_base_hook
0094       < dtl::bi::void_pointer<VoidPointer>
0095       , dtl::bi::link_mode<dtl::bi::normal_link>
0096       >::type  type;
0097 };
0098
0099 template<class VoidPointer, bool OptimizeSize>
0100 struct intrusive_tree_hook<VoidPointer, boost::container::splay_tree, OptimizeSize>
0101 {
0102    typedef typename dtl::bi::make_bs_set_base_hook
0103       < dtl::bi::void_pointer<VoidPointer>
0104       , dtl::bi::link_mode<dtl::bi::normal_link>
0105       >::type  type;
0106 };
0107
0108 //This trait is used to type-pun std::pair because in C++03
0109 //compilers std::pair is useless for C++11 features
0110 template<class T>
0111 struct tree_internal_data_type
0112 {
0113    typedef T type;
0114 };
0115
0116 template<class T1, class T2>
0117 struct tree_internal_data_type< std::pair<T1, T2> >
0118 {
0119    typedef pair<typename boost::move_detail::remove_const<T1>::type, T2> type;
0120 };
0121
0122 template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
0123 struct iiterator_node_value_type< base_node<T, intrusive_tree_hook<VoidPointer, tree_type_value, OptimizeSize>, true > >
0124 {
0125   typedef T type;
0126 };
0127
0128 template<class Node, class Icont>
0129 class insert_equal_end_hint_functor
0130 {
0131    Icont &icont_;
0132
0133    public:
0134    BOOST_CONTAINER_FORCEINLINE insert_equal_end_hint_functor(Icont &icont)
0135       :  icont_(icont)
0136    {}
0137
0138    BOOST_CONTAINER_FORCEINLINE void operator()(Node &n)
0139    {  this->icont_.insert_equal(this->icont_.cend(), n); }
0140 };
0141
0142 template<class Node, class Icont>
0143 class push_back_functor
0144 {
0145    Icont &icont_;
0146
0147    public:
0148    BOOST_CONTAINER_FORCEINLINE push_back_functor(Icont &icont)
0149       :  icont_(icont)
0150    {}
0151
0152    BOOST_CONTAINER_FORCEINLINE void operator()(Node &n)
0153    {  this->icont_.push_back(n); }
0154 };
0155
0156 }//namespace dtl {
0157
0158 namespace dtl {
0159
0160 template< class NodeType
0161         , class KeyOfNode
0162         , class KeyCompare
0163         , class HookType
0164         , boost::container::tree_type_enum tree_type_value>
0165 struct intrusive_tree_dispatch;
0166
0167 template<class NodeType, class KeyOfNode, class KeyCompare, class HookType>
0168 struct intrusive_tree_dispatch
0169    <NodeType, KeyOfNode, KeyCompare, HookType, boost::container::red_black_tree>
0170 {
0171    typedef typename dtl::bi::make_rbtree
0172       <NodeType
0173       ,dtl::bi::key_of_value<KeyOfNode>
0174       ,dtl::bi::compare<KeyCompare>
0175       ,dtl::bi::base_hook<HookType>
0176       ,dtl::bi::constant_time_size<true>
0177       >::type  type;
0178 };
0179
0180 template<class NodeType, class KeyOfNode, class KeyCompare, class HookType>
0181 struct intrusive_tree_dispatch
0182    <NodeType, KeyOfNode, KeyCompare, HookType, boost::container::avl_tree>
0183 {
0184    typedef typename dtl::bi::make_avltree
0185       <NodeType
0186       ,dtl::bi::key_of_value<KeyOfNode>
0187       ,dtl::bi::compare<KeyCompare>
0188       ,dtl::bi::base_hook<HookType>
0189       ,dtl::bi::constant_time_size<true>
0190       >::type  type;
0191 };
0192
0193 template<class NodeType, class KeyOfNode, class KeyCompare, class HookType>
0194 struct intrusive_tree_dispatch
0195    <NodeType, KeyOfNode, KeyCompare, HookType, boost::container::scapegoat_tree>
0196 {
0197    typedef typename dtl::bi::make_sgtree
0198       <NodeType
0199       ,dtl::bi::key_of_value<KeyOfNode>
0200       ,dtl::bi::compare<KeyCompare>
0201       ,dtl::bi::base_hook<HookType>
0202       ,dtl::bi::floating_point<true>
0203       >::type  type;
0204 };
0205
0206 template<class NodeType, class KeyOfNode, class KeyCompare, class HookType>
0207 struct intrusive_tree_dispatch
0208    <NodeType, KeyOfNode, KeyCompare, HookType, boost::container::splay_tree>
0209 {
0210    typedef typename dtl::bi::make_splaytree
0211       <NodeType
0212       ,dtl::bi::key_of_value<KeyOfNode>
0213       ,dtl::bi::compare<KeyCompare>
0214       ,dtl::bi::base_hook<HookType>
0215       ,dtl::bi::constant_time_size<true>
0216       >::type  type;
0217 };
0218
0219 template < class Allocator
0220          , class KeyOfValue
0221          , class KeyCompare
0222          , boost::container::tree_type_enum tree_type_value
0223          , bool OptimizeSize>
0224 struct intrusive_tree_type
0225 {
0226    private:
0227    typedef typename boost::container::
0228       allocator_traits<Allocator>::value_type               value_type;
0229    typedef typename boost::container::
0230       allocator_traits<Allocator>::void_pointer             void_pointer;
0231    typedef base_node<value_type, intrusive_tree_hook
0232       <void_pointer, tree_type_value, OptimizeSize>, true > node_t;
0233    //Deducing the hook type from node_t (e.g. node_t::hook_type) would
0234    //provoke an early instantiation of node_t that could ruin recursive
0235    //tree definitions, so retype the complete type to avoid any problem.
0236    typedef typename intrusive_tree_hook
0237       <void_pointer, tree_type_value
0238       , OptimizeSize>::type                                 hook_type;
0239
0240    typedef key_of_node
0241       <node_t, KeyOfValue>                                  key_of_node_t;
0242
0243    public:
0244    typedef typename intrusive_tree_dispatch
0245       < node_t
0246       , key_of_node_t
0247       , KeyCompare
0248       , hook_type
0249       , tree_type_value>::type                     type;
0250 };
0251
0252 //Trait to detect manually rebalanceable tree types
0253 template<boost::container::tree_type_enum tree_type_value>
0254 struct is_manually_balanceable
0255 {  static const bool value = true;  };
0256
0257 template<>  struct is_manually_balanceable<red_black_tree>
0258 {  static const bool value = false; };
0259
0260 template<>  struct is_manually_balanceable<avl_tree>
0261 {  static const bool value = false; };
0262
0263 //Proxy traits to implement different operations depending on the
0264 //is_manually_balanceable<>::value
0265 template< boost::container::tree_type_enum tree_type_value
0266         , bool IsManuallyRebalanceable = is_manually_balanceable<tree_type_value>::value>
0267 struct intrusive_tree_proxy
0268 {
0269    template<class Icont>
0270    BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &)   {}
0271 };
0272
0273 template<boost::container::tree_type_enum tree_type_value>
0274 struct intrusive_tree_proxy<tree_type_value, true>
0275 {
0276    template<class Icont>
0277    BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &c)
0278    {  c.rebalance(); }
0279 };
0280
0281 }  //namespace dtl {
0282
0283 namespace dtl {
0284
0285 //This functor will be used with Intrusive clone functions to obtain
0286 //already allocated nodes from a intrusive container instead of
0287 //allocating new ones. When the intrusive container runs out of nodes
0288 //the node holder is used instead.
0289 template<class AllocHolder, bool DoMove>
0290 class RecyclingCloner
0291 {
0292    typedef typename AllocHolder::intrusive_container  intrusive_container;
0293    typedef typename AllocHolder::Node                 node_t;
0294    typedef typename AllocHolder::NodePtr              node_ptr_type;
0295
0296    public:
0297    RecyclingCloner(AllocHolder &holder, intrusive_container &itree)
0298       :  m_holder(holder), m_icont(itree)
0299    {}
0300
0301    BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type p, node_t &other, bool_<true>)
0302    {  p->do_move_assign(other.get_real_data());   }
0303
0304    BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type p, const node_t &other, bool_<false>)
0305    {  p->do_assign(other.get_real_data());   }
0306
0307    node_ptr_type operator()
0308       (typename dtl::if_c<DoMove, node_t &, const node_t&>::type other) const
0309    {
0310       if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){
0311          //First recycle a node (this can't throw)
0312          BOOST_CONTAINER_TRY{
0313             //This can throw
0314             this->do_assign(p, other, bool_<DoMove>());
0315             return p;
0316          }
0317          BOOST_CONTAINER_CATCH(...){
0318             //If there is an exception destroy the whole source
0319             m_holder.destroy_node(p);
0320             while((p = m_icont.unlink_leftmost_without_rebalance())){
0321                m_holder.destroy_node(p);
0322             }
0323             BOOST_CONTAINER_RETHROW
0324          }
0325          BOOST_CONTAINER_CATCH_END
0326       }
0327       else{
0328          return m_holder.create_node(boost::move(other.get_real_data()));
0329       }
0330    }
0331
0332    AllocHolder &m_holder;
0333    intrusive_container &m_icont;
0334 };
0335
0336 template<class Options>
0337 struct get_tree_opt
0338 {
0339    typedef Options type;
0340 };
0341
0342 template<>
0343 struct get_tree_opt<void>
0344 {
0345    typedef tree_assoc_defaults type;
0346 };
0347
0348 template<class, class KeyOfValue>
0349 struct tree_key_of_value
0350 {
0351    typedef KeyOfValue type;
0352 };
0353
0354 template<class T>
0355 struct tree_key_of_value<T, void>
0356 {
0357    typedef dtl::identity<T> type;
0358 };
0359
0360 template<class T1, class T2>
0361 struct tree_key_of_value<std::pair<T1, T2>, int>
0362 {
0363    typedef dtl::select1st<T1> type;
0364 };
0365
0366 template<class T1, class T2>
0367 struct tree_key_of_value<boost::container::dtl::pair<T1, T2>, int>
0368 {
0369    typedef dtl::select1st<T1> type;
0370 };
0371
0372
0373 template <class T, class KeyOfValue, class Compare, class Allocator, class Options>
0374 struct make_intrusive_tree_type
0375    : dtl::intrusive_tree_type
0376          < typename real_allocator<T, Allocator>::type
0377          , typename tree_key_of_value<T, KeyOfValue>::type
0378          , Compare
0379          , get_tree_opt<Options>::type::tree_type
0380          , get_tree_opt<Options>::type::optimize_size
0381          >
0382 {};
0383
0384
0385 template <class T, class KeyOfValue, class Compare, class Allocator, class Options>
0386 class tree
0387    : public dtl::node_alloc_holder
0388       < typename real_allocator<T, Allocator>::type
0389       , typename make_intrusive_tree_type<T, KeyOfValue, Compare, Allocator, Options>::type
0390       >
0391 {
0392    typedef tree < T, KeyOfValue
0393                 , Compare, Allocator, Options>              ThisType;
0394    public:
0395    typedef typename real_allocator<T, Allocator>::type      allocator_type;
0396
0397    private:
0398    typedef allocator_traits<allocator_type>                 allocator_traits_t;
0399    typedef typename tree_key_of_value<T, KeyOfValue>::type  key_of_value_t;
0400    typedef tree_value_compare
0401       < typename allocator_traits_t::pointer
0402       , Compare
0403       , key_of_value_t>                                     ValComp;
0404    typedef typename get_tree_opt<Options>::type             options_type;
0405    typedef typename make_intrusive_tree_type
0406       <T, KeyOfValue, Compare, Allocator, Options>::type    Icont;
0407    typedef dtl::node_alloc_holder
0408       <allocator_type, Icont>                               AllocHolder;
0409    typedef typename AllocHolder::NodePtr                    NodePtr;
0410
0411    typedef typename AllocHolder::NodeAlloc                  NodeAlloc;
0412    typedef boost::container::
0413       allocator_traits<NodeAlloc>                           allocator_traits_type;
0414    typedef typename AllocHolder::ValAlloc                   ValAlloc;
0415    typedef typename AllocHolder::Node                       Node;
0416    typedef typename Icont::iterator                         iiterator;
0417    typedef typename Icont::const_iterator                   iconst_iterator;
0418    typedef dtl::allocator_node_destroyer<NodeAlloc> Destroyer;
0419    typedef typename AllocHolder::alloc_version              alloc_version;
0420    typedef intrusive_tree_proxy<options_type::tree_type>    intrusive_tree_proxy_t;
0421
0422    BOOST_COPYABLE_AND_MOVABLE(tree)
0423
0424    public:
0425
0426    typedef typename dtl::remove_const
0427       <typename key_of_value_t::type>::type                 key_type;
0428    typedef T                                                value_type;
0429    typedef Compare                                          key_compare;
0430    typedef ValComp                                          value_compare;
0431    typedef typename boost::container::
0432       allocator_traits<allocator_type>::pointer             pointer;
0433    typedef typename boost::container::
0434       allocator_traits<allocator_type>::const_pointer       const_pointer;
0435    typedef typename boost::container::
0436       allocator_traits<allocator_type>::reference           reference;
0437    typedef typename boost::container::
0438       allocator_traits<allocator_type>::const_reference     const_reference;
0439    typedef typename boost::container::
0440       allocator_traits<allocator_type>::size_type           size_type;
0441    typedef typename boost::container::
0442       allocator_traits<allocator_type>::difference_type     difference_type;
0443    typedef dtl::iterator_from_iiterator
0444       <iiterator, false>                                    iterator;
0445    typedef dtl::iterator_from_iiterator
0446       <iiterator, true >                                    const_iterator;
0447    typedef boost::container::reverse_iterator
0448       <iterator>                                            reverse_iterator;
0449    typedef boost::container::reverse_iterator
0450       <const_iterator>                                      const_reverse_iterator;
0451    typedef node_handle
0452       < NodeAlloc, void>                                    node_type;
0453    typedef insert_return_type_base
0454       <iterator, node_type>                                 insert_return_type;
0455
0456    typedef NodeAlloc                                        stored_allocator_type;
0457
0458    private:
0459
0460    typedef key_node_pred<key_compare, key_of_value_t, Node>  KeyNodeCompare;
0461
0462    public:
0463
0464    BOOST_CONTAINER_FORCEINLINE tree()
0465       : AllocHolder()
0466    {}
0467
0468    BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp)
0469       : AllocHolder(ValComp(comp))
0470    {}
0471
0472    BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a)
0473       : AllocHolder(ValComp(comp), a)
0474    {}
0475
0476    BOOST_CONTAINER_FORCEINLINE explicit tree(const allocator_type& a)
0477       : AllocHolder(a)
0478    {}
0479
0480    template <class InputIterator>
0481    tree(bool unique_insertion, InputIterator first, InputIterator last)
0482       : AllocHolder(value_compare(key_compare()))
0483    {
0484       this->tree_construct(unique_insertion, first, last);
0485       //AllocHolder clears in case of exception
0486    }
0487
0488    template <class InputIterator>
0489    tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp)
0490       : AllocHolder(value_compare(comp))
0491    {
0492       this->tree_construct(unique_insertion, first, last);
0493       //AllocHolder clears in case of exception
0494    }
0495
0496    template <class InputIterator>
0497    tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a)
0498       : AllocHolder(value_compare(comp), a)
0499    {
0500       this->tree_construct(unique_insertion, first, last);
0501       //AllocHolder clears in case of exception
0502    }
0503
0504    //construct with ordered range
0505    template <class InputIterator>
0506    tree( ordered_range_t, InputIterator first, InputIterator last)
0507       : AllocHolder(value_compare(key_compare()))
0508    {
0509       this->tree_construct(ordered_range_t(), first, last);
0510    }
0511
0512    template <class InputIterator>
0513    tree( ordered_range_t, InputIterator first, InputIterator last, const key_compare& comp)
0514       : AllocHolder(value_compare(comp))
0515    {
0516       this->tree_construct(ordered_range_t(), first, last);
0517    }
0518
0519    template <class InputIterator>
0520    tree( ordered_range_t, InputIterator first, InputIterator last
0521          , const key_compare& comp, const allocator_type& a)
0522       : AllocHolder(value_compare(comp), a)
0523    {
0524       this->tree_construct(ordered_range_t(), first, last);
0525    }
0526
0527    private:
0528
0529    template <class InputIterator>
0530    void tree_construct(bool unique_insertion, InputIterator first, InputIterator last)
0531    {
0532       //Use cend() as hint to achieve linear time for
0533       //ordered ranges as required by the standard
0534       //for the constructor
0535       if(unique_insertion){
0536          const const_iterator end_it(this->cend());
0537          for ( ; first != last; ++first){
0538             this->insert_unique_hint_convertible(end_it, *first);
0539          }
0540       }
0541       else{
0542          this->tree_construct_non_unique(first, last);
0543       }
0544    }
0545
0546    template <class InputIterator>
0547    void tree_construct_non_unique(InputIterator first, InputIterator last
0548       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0549       , typename dtl::enable_if_or
0550          < void
0551          , dtl::is_same<alloc_version, version_1>
0552          , dtl::is_input_iterator<InputIterator>
0553          >::type * = 0
0554       #endif
0555          )
0556    {
0557       //Use cend() as hint to achieve linear time for
0558       //ordered ranges as required by the standard
0559       //for the constructor
0560       const const_iterator end_it(this->cend());
0561       for ( ; first != last; ++first){
0562          this->insert_equal_hint_convertible(end_it, *first);
0563       }
0564    }
0565
0566    template <class InputIterator>
0567    void tree_construct_non_unique(InputIterator first, InputIterator last
0568       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0569       , typename dtl::disable_if_or
0570          < void
0571          , dtl::is_same<alloc_version, version_1>
0572          , dtl::is_input_iterator<InputIterator>
0573          >::type * = 0
0574       #endif
0575          )
0576    {
0577       //Optimized allocation and construction
0578       this->allocate_many_and_construct
0579          ( first, boost::container::iterator_udistance(first, last)
0580          , insert_equal_end_hint_functor<Node, Icont>(this->icont()));
0581    }
0582
0583    template <class InputIterator>
0584    void tree_construct( ordered_range_t, InputIterator first, InputIterator last
0585          #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0586       , typename dtl::disable_if_or
0587          < void
0588          , dtl::is_same<alloc_version, version_1>
0589          , dtl::is_input_iterator<InputIterator>
0590          >::type * = 0
0591          #endif
0592          )
0593    {
0594       //Optimized allocation and construction
0595       this->allocate_many_and_construct
0596          ( first, boost::container::iterator_udistance(first, last)
0597          , dtl::push_back_functor<Node, Icont>(this->icont()));
0598       //AllocHolder clears in case of exception
0599    }
0600
0601    template <class InputIterator>
0602    void tree_construct( ordered_range_t, InputIterator first, InputIterator last
0603          #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0604       , typename dtl::enable_if_or
0605          < void
0606          , dtl::is_same<alloc_version, version_1>
0607          , dtl::is_input_iterator<InputIterator>
0608          >::type * = 0
0609          #endif
0610          )
0611    {
0612       for ( ; first != last; ++first){
0613          this->push_back_impl(*first);
0614       }
0615    }
0616
0617    public:
0618
0619    BOOST_CONTAINER_FORCEINLINE tree(const tree& x)
0620       :  AllocHolder(x, x.value_comp())
0621    {
0622       this->icont().clone_from
0623          (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
0624    }
0625
0626    BOOST_CONTAINER_FORCEINLINE tree(BOOST_RV_REF(tree) x)
0627       BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
0628       :  AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp())
0629    {}
0630
0631    BOOST_CONTAINER_FORCEINLINE tree(const tree& x, const allocator_type &a)
0632       :  AllocHolder(x.value_comp(), a)
0633    {
0634       this->icont().clone_from
0635          (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
0636       //AllocHolder clears in case of exception
0637    }
0638
0639    tree(BOOST_RV_REF(tree) x, const allocator_type &a)
0640       :  AllocHolder(x.value_comp(), a)
0641    {
0642       if(this->node_alloc() == x.node_alloc()){
0643          this->icont().swap(x.icont());
0644       }
0645       else{
0646          this->icont().clone_from
0647             (boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc()));
0648       }
0649       //AllocHolder clears in case of exception
0650    }
0651
0652    BOOST_CONTAINER_FORCEINLINE ~tree()
0653    {} //AllocHolder clears the tree
0654
0655    tree& operator=(BOOST_COPY_ASSIGN_REF(tree) x)
0656    {
0657       if (BOOST_LIKELY(this != &x)) {
0658          NodeAlloc &this_alloc     = this->get_stored_allocator();
0659          const NodeAlloc &x_alloc  = x.get_stored_allocator();
0660          dtl::bool_<allocator_traits<NodeAlloc>::
0661             propagate_on_container_copy_assignment::value> flag;
0662          if(flag && this_alloc != x_alloc){
0663             this->clear();
0664          }
0665          this->AllocHolder::copy_assign_alloc(x);
0666          //Transfer all the nodes to a temporary tree
0667          //If anything goes wrong, all the nodes will be destroyed
0668          //automatically
0669          Icont other_tree(::boost::move(this->icont()));
0670
0671          //Now recreate the source tree reusing nodes stored by other_tree
0672          this->icont().clone_from
0673             (x.icont()
0674             , RecyclingCloner<AllocHolder, false>(*this, other_tree)
0675             , Destroyer(this->node_alloc()));
0676
0677          //If there are remaining nodes, destroy them
0678          NodePtr p;
0679          while((p = other_tree.unlink_leftmost_without_rebalance())){
0680             AllocHolder::destroy_node(p);
0681          }
0682       }
0683       return *this;
0684    }
0685
0686    tree& operator=(BOOST_RV_REF(tree) x)
0687       BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
0688                           allocator_traits_type::is_always_equal::value) &&
0689                            boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
0690    {
0691       if (BOOST_LIKELY(this != &x)) {
0692          NodeAlloc &this_alloc = this->node_alloc();
0693          NodeAlloc &x_alloc    = x.node_alloc();
0694          const bool propagate_alloc = allocator_traits<NodeAlloc>::
0695                propagate_on_container_move_assignment::value;
0696          const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
0697          //Resources can be transferred if both allocators are
0698          //going to be equal after this function (either propagated or already equal)
0699          if(propagate_alloc || allocators_equal){
0700             //Destroy
0701             this->clear();
0702             //Move allocator if needed
0703             this->AllocHolder::move_assign_alloc(x);
0704             //Obtain resources
0705             this->icont() = boost::move(x.icont());
0706          }
0707          //Else do a one by one move
0708          else{
0709             //Transfer all the nodes to a temporary tree
0710             //If anything goes wrong, all the nodes will be destroyed
0711             //automatically
0712             Icont other_tree(::boost::move(this->icont()));
0713
0714             //Now recreate the source tree reusing nodes stored by other_tree
0715             this->icont().clone_from
0716                (::boost::move(x.icont())
0717                , RecyclingCloner<AllocHolder, true>(*this, other_tree)
0718                , Destroyer(this->node_alloc()));
0719
0720             //If there are remaining nodes, destroy them
0721             NodePtr p;
0722             while((p = other_tree.unlink_leftmost_without_rebalance())){
0723                AllocHolder::destroy_node(p);
0724             }
0725          }
0726       }
0727       return *this;
0728    }
0729
0730    public:
0731    // accessors:
0732    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0733       value_compare value_comp() const
0734    {  return value_compare(this->key_comp()); }
0735
0736    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0737       key_compare key_comp() const
0738    {  return this->icont().key_comp(); }
0739
0740    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0741       allocator_type get_allocator() const
0742    {  return allocator_type(this->node_alloc()); }
0743
0744    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0745       const stored_allocator_type &get_stored_allocator() const
0746    {  return this->node_alloc(); }
0747
0748    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0749       stored_allocator_type &get_stored_allocator()
0750    {  return this->node_alloc(); }
0751
0752    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0753       iterator begin()
0754    { return iterator(this->icont().begin()); }
0755
0756    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0757       const_iterator begin() const
0758    {  return this->cbegin();  }
0759
0760    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0761       iterator end()
0762    {  return iterator(this->icont().end());  }
0763
0764    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0765       const_iterator end() const
0766    {  return this->cend();  }
0767
0768    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0769       reverse_iterator rbegin()
0770    {  return reverse_iterator(end());  }
0771
0772
0773    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0774       const_reverse_iterator rbegin() const
0775    {  return this->crbegin();  }
0776
0777    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0778       reverse_iterator rend()
0779    {  return reverse_iterator(begin());   }
0780
0781    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0782       const_reverse_iterator rend() const
0783    {  return this->crend();   }
0784
0785    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
0786    //!
0787    //! <b>Throws</b>: Nothing.
0788    //!
0789    //! <b>Complexity</b>: Constant.
0790    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0791       const_iterator cbegin() const
0792    { return const_iterator(this->non_const_icont().begin()); }
0793
0794    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
0795    //!
0796    //! <b>Throws</b>: Nothing.
0797    //!
0798    //! <b>Complexity</b>: Constant.
0799    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0800       const_iterator cend() const
0801    { return const_iterator(this->non_const_icont().end()); }
0802
0803    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
0804    //! of the reversed container.
0805    //!
0806    //! <b>Throws</b>: Nothing.
0807    //!
0808    //! <b>Complexity</b>: Constant.
0809    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0810       const_reverse_iterator crbegin() const
0811    { return const_reverse_iterator(cend()); }
0812
0813    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
0814    //! of the reversed container.
0815    //!
0816    //! <b>Throws</b>: Nothing.
0817    //!
0818    //! <b>Complexity</b>: Constant.
0819    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0820       const_reverse_iterator crend() const
0821    { return const_reverse_iterator(cbegin()); }
0822
0823    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0824       bool empty() const
0825    {  return !this->size();  }
0826
0827    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0828       size_type size() const
0829    {  return this->icont().size();   }
0830
0831    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
0832       size_type max_size() const
0833    {  return AllocHolder::max_size();  }
0834
0835    BOOST_CONTAINER_FORCEINLINE void swap(ThisType& x)
0836       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
0837                                  && boost::container::dtl::is_nothrow_swappable<Compare>::value )
0838    {  AllocHolder::swap(x);   }
0839
0840    public:
0841
0842    typedef typename Icont::insert_commit_data insert_commit_data;
0843
0844    // insert/erase
0845    std::pair<iterator,bool> insert_unique_check
0846       (const key_type& key, insert_commit_data &data)
0847    {
0848       std::pair<iiterator, bool> ret =
0849          this->icont().insert_unique_check(key, data);
0850       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
0851    }
0852
0853    std::pair<iterator,bool> insert_unique_check
0854       (const_iterator hint, const key_type& key, insert_commit_data &data)
0855    {
0856       BOOST_ASSERT((priv_is_linked)(hint));
0857       std::pair<iiterator, bool> ret =
0858          this->icont().insert_unique_check(hint.get(), key, data);
0859       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
0860    }
0861
0862    template<class MovableConvertible>
0863    iterator insert_unique_commit
0864       (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data)
0865    {
0866       NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v));
0867       scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
0868       iterator ret(this->icont().insert_unique_commit(*tmp, data));
0869       destroy_deallocator.release();
0870       return ret;
0871    }
0872
0873    template<class MovableConvertible>
0874    std::pair<iterator,bool> insert_unique_convertible(BOOST_FWD_REF(MovableConvertible) v)
0875    {
0876       insert_commit_data data;
0877       std::pair<iterator,bool> ret =
0878          this->insert_unique_check(key_of_value_t()(v), data);
0879       if(ret.second){
0880          ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
0881       }
0882       return ret;
0883    }
0884
0885    template<class MovableConvertible>
0886    iterator insert_unique_hint_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
0887    {
0888       BOOST_ASSERT((priv_is_linked)(hint));
0889       insert_commit_data data;
0890       std::pair<iterator,bool> ret =
0891          this->insert_unique_check(hint, key_of_value_t()(v), data);
0892       if(!ret.second)
0893          return ret.first;
0894       return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
0895    }
0896
0897
0898    private:
0899
0900    template<class KeyConvertible, class M>
0901    iiterator priv_insert_or_assign_commit
0902       (BOOST_FWD_REF(KeyConvertible) key, BOOST_FWD_REF(M) obj, insert_commit_data &data)
0903    {
0904       NodePtr tmp = AllocHolder::create_node(boost::forward<KeyConvertible>(key), boost::forward<M>(obj));
0905       scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
0906       iiterator ret(this->icont().insert_unique_commit(*tmp, data));
0907       destroy_deallocator.release();
0908       return ret;
0909    }
0910
0911    bool priv_is_linked(const_iterator const position) const
0912    {
0913       iiterator const cur(position.get());
0914       return   cur == this->icont().end() ||
0915                cur == this->icont().root() ||
0916                iiterator(cur).go_parent().go_left()  == cur ||
0917                iiterator(cur).go_parent().go_right() == cur;
0918    }
0919
0920    template<class MovableConvertible>
0921    void push_back_impl(BOOST_FWD_REF(MovableConvertible) v)
0922    {
0923       NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
0924       //push_back has no-throw guarantee so avoid any deallocator/destroyer
0925       this->icont().push_back(*tmp);
0926    }
0927
0928    std::pair<iterator, bool> emplace_unique_node(NodePtr p)
0929    {
0930       value_type &v = p->get_data();
0931       insert_commit_data data;
0932       scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc());
0933       std::pair<iterator,bool> ret =
0934          this->insert_unique_check(key_of_value_t()(v), data);
0935       if(!ret.second){
0936          return ret;
0937       }
0938       //No throw insertion part, release rollback
0939       destroy_deallocator.release();
0940       return std::pair<iterator,bool>
0941          ( iterator(this->icont().insert_unique_commit(*p, data))
0942          , true );
0943    }
0944
0945    iterator emplace_hint_unique_node(const_iterator hint, NodePtr p)
0946    {
0947       BOOST_ASSERT((priv_is_linked)(hint));
0948       value_type &v = p->get_data();
0949       insert_commit_data data;
0950       std::pair<iterator,bool> ret =
0951          this->insert_unique_check(hint, key_of_value_t()(v), data);
0952       if(!ret.second){
0953          //Destroy unneeded node
0954          Destroyer(this->node_alloc())(p);
0955          return ret.first;
0956       }
0957       return iterator(this->icont().insert_unique_commit(*p, data));
0958    }
0959
0960    public:
0961
0962    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0963
0964    template <class... Args>
0965    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args)
0966    {  return this->emplace_unique_node(AllocHolder::create_node(boost::forward<Args>(args)...));   }
0967
0968    template <class... Args>
0969    BOOST_CONTAINER_FORCEINLINE iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args)
0970    {  return this->emplace_hint_unique_node(hint, AllocHolder::create_node(boost::forward<Args>(args)...));   }
0971
0972    template <class... Args>
0973    iterator emplace_equal(BOOST_FWD_REF(Args)... args)
0974    {
0975       NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
0976       scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
0977       iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
0978       destroy_deallocator.release();
0979       return ret;
0980    }
0981
0982    template <class... Args>
0983    iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args)
0984    {
0985       BOOST_ASSERT((priv_is_linked)(hint));
0986       NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
0987       scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
0988       iterator ret(this->icont().insert_equal(hint.get(), *tmp));
0989       destroy_deallocator.release();
0990       return ret;
0991    }
0992
0993    template <class KeyType, class... Args>
0994    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace
0995       (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args)
0996    {
0997       insert_commit_data data;
0998       const key_type & k = key;  //Support emulated rvalue references
0999       std::pair<iiterator, bool> ret =
1000          hint == const_iterator() ? this->icont().insert_unique_check(            k, data)
1001                                   : this->icont().insert_unique_check(hint.get(), k, data);
1002       if(ret.second){
1003          ret.first = this->icont().insert_unique_commit
1004             (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key), boost::forward<Args>(args)...), data);
1005       }
1006       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
1007    }
1008
1009    #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1010
1011    #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \
1012    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1013    std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\
1014    {  return this->emplace_unique_node(AllocHolder::create_node(BOOST_MOVE_FWD##N));  }\
1015    \
1016    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1017    iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1018    {  return this->emplace_hint_unique_node(hint, AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\
1019    \
1020    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1021    iterator emplace_equal(BOOST_MOVE_UREF##N)\
1022    {\
1023       NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
1024       scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
1025       iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\
1026       destroy_deallocator.release();\
1027       return ret;\
1028    }\
1029    \
1030    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1031    iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1032    {\
1033       BOOST_ASSERT((priv_is_linked)(hint));\
1034       NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
1035       scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
1036       iterator ret(this->icont().insert_equal(hint.get(), *tmp));\
1037       destroy_deallocator.release();\
1038       return ret;\
1039    }\
1040    \
1041    template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\
1042    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\
1043       try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1044    {\
1045       insert_commit_data data;\
1046       const key_type & k = key;\
1047       std::pair<iiterator, bool> ret =\
1048          hint == const_iterator() ? this->icont().insert_unique_check(            k, data)\
1049                                   : this->icont().insert_unique_check(hint.get(), k, data);\
1050       if(ret.second){\
1051          ret.first = this->icont().insert_unique_commit\
1052             (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N), data);\
1053       }\
1054       return std::pair<iterator, bool>(iterator(ret.first), ret.second);\
1055    }\
1056    //
1057    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE)
1058    #undef BOOST_CONTAINER_TREE_EMPLACE_CODE
1059
1060    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1061
1062    //BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_unique, value_type, iterator, this->insert_unique_hint_convertible, const_iterator, const_iterator)
1063
1064    template <class InputIterator>
1065    void insert_unique_range(InputIterator first, InputIterator last)
1066    {
1067       for( ; first != last; ++first)
1068          this->insert_unique_convertible(*first);
1069    }
1070
1071    template<class MovableConvertible>
1072    iterator insert_equal_convertible(BOOST_FWD_REF(MovableConvertible) v)
1073    {
1074       NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
1075       scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
1076       iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
1077       destroy_deallocator.release();
1078       return ret;
1079    }
1080
1081    template<class MovableConvertible>
1082    iterator insert_equal_hint_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
1083    {
1084       BOOST_ASSERT((priv_is_linked)(hint));
1085       NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
1086       scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
1087       iterator ret(this->icont().insert_equal(hint.get(), *tmp));
1088       destroy_deallocator.release();
1089       return ret;
1090    }
1091
1092    BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG
1093       (insert_equal, value_type, iterator, this->insert_equal_hint_convertible, const_iterator, const_iterator)
1094
1095    template <class InputIterator>
1096    void insert_equal_range(InputIterator first, InputIterator last)
1097    {
1098       for( ; first != last; ++first)
1099          this->insert_equal_convertible(*first);
1100    }
1101
1102    template<class KeyType, class M>
1103    std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj)
1104    {
1105       insert_commit_data data;
1106       const key_type & k = key;  //Support emulated rvalue references
1107       std::pair<iiterator, bool> ret =
1108          hint == const_iterator() ? this->icont().insert_unique_check(k, data)
1109                                   : this->icont().insert_unique_check(hint.get(), k, data);
1110       if(ret.second){
1111          ret.first = this->priv_insert_or_assign_commit(boost::forward<KeyType>(key), boost::forward<M>(obj), data);
1112       }
1113       else{
1114          ret.first->get_data().second = boost::forward<M>(obj);
1115       }
1116       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
1117    }
1118
1119    iterator erase(const_iterator position)
1120    {
1121       BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position));
1122       return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc())));
1123    }
1124
1125    BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& k)
1126    {  return AllocHolder::erase_key(k, alloc_version()); }
1127
1128    size_type erase_unique(const key_type& k)
1129    {
1130       iterator i = this->find(k);
1131       size_type ret = static_cast<size_type>(i != this->end());
1132       if (ret)
1133          this->erase(i);
1134       return ret;
1135    }
1136
1137    iterator erase(const_iterator first, const_iterator last)
1138    {
1139       BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first)));
1140       BOOST_ASSERT(first == last || (priv_is_linked)(last));
1141       return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version()));
1142    }
1143
1144    node_type extract(const key_type& k)
1145    {
1146       iterator const it = this->find(k);
1147       if(this->end() != it){
1148          return this->extract(it);
1149       }
1150       return node_type();
1151    }
1152
1153    node_type extract(const_iterator position)
1154    {
1155       BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position));
1156       iiterator const iit(position.get());
1157       this->icont().erase(iit);
1158       return node_type(iit.operator->(), this->node_alloc());
1159    }
1160
1161    insert_return_type insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1162    {
1163       return this->insert_unique_node(this->end(), boost::move(nh));
1164    }
1165
1166    insert_return_type insert_unique_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1167    {
1168       insert_return_type irt; //inserted == false, node.empty()
1169       if(!nh.empty()){
1170          insert_commit_data data;
1171          std::pair<iterator,bool> ret =
1172             this->insert_unique_check(hint, key_of_value_t()(nh.value()), data);
1173          if(ret.second){
1174             irt.inserted = true;
1175             irt.position = iterator(this->icont().insert_unique_commit(*nh.get(), data));
1176             nh.release();
1177          }
1178          else{
1179             irt.position = ret.first;
1180             irt.node = boost::move(nh);
1181          }
1182       }
1183       else{
1184          irt.position = this->end();
1185       }
1186       return BOOST_MOVE_RET(insert_return_type, irt);
1187    }
1188
1189    iterator insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1190    {
1191       if(nh.empty()){
1192          return this->end();
1193       }
1194       else{
1195          NodePtr const p(nh.release());
1196          return iterator(this->icont().insert_equal(*p));
1197       }
1198    }
1199
1200    iterator insert_equal_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1201    {
1202       if(nh.empty()){
1203          return this->end();
1204       }
1205       else{
1206          NodePtr const p(nh.release());
1207          return iterator(this->icont().insert_equal(hint.get(), *p));
1208       }
1209    }
1210
1211    template<class C2>
1212    BOOST_CONTAINER_FORCEINLINE void merge_unique(tree<T, KeyOfValue, C2, Allocator, Options>& source)
1213    {  return this->icont().merge_unique(source.icont()); }
1214
1215    template<class C2>
1216    BOOST_CONTAINER_FORCEINLINE void merge_equal(tree<T, KeyOfValue, C2, Allocator, Options>& source)
1217    {  return this->icont().merge_equal(source.icont());  }
1218    BOOST_CONTAINER_FORCEINLINE void clear()
1219    {  AllocHolder::clear(alloc_version());  }
1220
1221    // search operations. Const and non-const overloads even if no iterator is returned
1222    // so splay implementations can to their rebalancing when searching in non-const versions
1223    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1224       iterator find(const key_type& k)
1225    {  return iterator(this->icont().find(k));  }
1226
1227    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1228       const_iterator find(const key_type& k) const
1229    {  return const_iterator(this->non_const_icont().find(k));  }
1230
1231    template <class K>
1232    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1233       typename dtl::enable_if_transparent<key_compare, K, iterator>::type
1234          find(const K& k)
1235    {  return iterator(this->icont().find(k, KeyNodeCompare()));  }
1236
1237    template <class K>
1238    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1239       typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
1240          find(const K& k) const
1241    {  return const_iterator(this->non_const_icont().find(k, KeyNodeCompare()));  }
1242
1243    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1244       size_type count(const key_type& k) const
1245    {  return size_type(this->icont().count(k)); }
1246
1247    template <class K>
1248    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1249       typename dtl::enable_if_transparent<key_compare, K, size_type>::type
1250          count(const K& k) const
1251    {  return size_type(this->icont().count(k, KeyNodeCompare())); }
1252
1253    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1254       bool contains(const key_type& x) const
1255    {  return this->find(x) != this->cend();  }
1256
1257    template<typename K>
1258    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1259       typename dtl::enable_if_transparent<key_compare, K, bool>::type
1260          contains(const K& x) const
1261    {  return this->find(x) != this->cend();  }
1262
1263    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1264       iterator lower_bound(const key_type& k)
1265    {  return iterator(this->icont().lower_bound(k));  }
1266
1267    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1268       const_iterator lower_bound(const key_type& k) const
1269    {  return const_iterator(this->non_const_icont().lower_bound(k));  }
1270
1271    template <class K>
1272    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1273       typename dtl::enable_if_transparent<key_compare, K, iterator>::type
1274          lower_bound(const K& k)
1275    {  return iterator(this->icont().lower_bound(k, KeyNodeCompare()));  }
1276
1277    template <class K>
1278    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1279       typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
1280          lower_bound(const K& k) const
1281    {  return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare()));  }
1282
1283    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1284       iterator upper_bound(const key_type& k)
1285    {  return iterator(this->icont().upper_bound(k));   }
1286
1287    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1288       const_iterator upper_bound(const key_type& k) const
1289    {  return const_iterator(this->non_const_icont().upper_bound(k));  }
1290
1291    template <class K>
1292    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1293       typename dtl::enable_if_transparent<key_compare, K, iterator>::type
1294          upper_bound(const K& k)
1295    {  return iterator(this->icont().upper_bound(k, KeyNodeCompare()));   }
1296
1297    template <class K>
1298    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1299       typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
1300          upper_bound(const K& k) const
1301    {  return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare()));  }
1302
1303    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1304       std::pair<iterator,iterator> equal_range(const key_type& k)
1305    {
1306       std::pair<iiterator, iiterator> ret = this->icont().equal_range(k);
1307       return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
1308    }
1309
1310    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1311       std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
1312    {
1313       std::pair<iiterator, iiterator> ret =
1314          this->non_const_icont().equal_range(k);
1315       return std::pair<const_iterator,const_iterator>
1316          (const_iterator(ret.first), const_iterator(ret.second));
1317    }
1318
1319    template <class K>
1320    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1321       typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type
1322          equal_range(const K& k)
1323    {
1324       std::pair<iiterator, iiterator> ret =
1325          this->icont().equal_range(k, KeyNodeCompare());
1326       return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
1327    }
1328
1329    template <class K>
1330    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1331       typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type
1332          equal_range(const K& k) const
1333    {
1334       std::pair<iiterator, iiterator> ret =
1335          this->non_const_icont().equal_range(k, KeyNodeCompare());
1336       return std::pair<const_iterator,const_iterator>
1337          (const_iterator(ret.first), const_iterator(ret.second));
1338    }
1339
1340    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1341       std::pair<iterator,iterator> lower_bound_range(const key_type& k)
1342    {
1343       std::pair<iiterator, iiterator> ret =
1344          this->icont().lower_bound_range(k);
1345       return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
1346    }
1347
1348    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1349       std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
1350    {
1351       std::pair<iiterator, iiterator> ret =
1352          this->non_const_icont().lower_bound_range(k);
1353       return std::pair<const_iterator,const_iterator>
1354          (const_iterator(ret.first), const_iterator(ret.second));
1355    }
1356
1357    template <class K>
1358    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1359       typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type
1360          lower_bound_range(const K& k)
1361    {
1362       std::pair<iiterator, iiterator> ret =
1363          this->icont().lower_bound_range(k, KeyNodeCompare());
1364       return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
1365    }
1366
1367    template <class K>
1368    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1369       typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type
1370          lower_bound_range(const K& k) const
1371    {
1372       std::pair<iiterator, iiterator> ret =
1373          this->non_const_icont().lower_bound_range(k, KeyNodeCompare());
1374       return std::pair<const_iterator,const_iterator>
1375          (const_iterator(ret.first), const_iterator(ret.second));
1376    }
1377
1378    BOOST_CONTAINER_FORCEINLINE void rebalance()
1379    {  intrusive_tree_proxy_t::rebalance(this->icont());   }
1380
1381    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1382       friend bool operator==(const tree& x, const tree& y)
1383    {  return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());  }
1384
1385    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1386       friend bool operator<(const tree& x, const tree& y)
1387    {  return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());  }
1388
1389    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1390       friend bool operator!=(const tree& x, const tree& y)
1391    {  return !(x == y);  }
1392
1393    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1394       friend bool operator>(const tree& x, const tree& y)
1395    {  return y < x;  }
1396
1397    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1398       friend bool operator<=(const tree& x, const tree& y)
1399    {  return !(y < x);  }
1400
1401    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1402       friend bool operator>=(const tree& x, const tree& y)
1403    {  return !(x < y);  }
1404
1405    BOOST_CONTAINER_FORCEINLINE friend void swap(tree& x, tree& y)
1406       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
1407                                  && boost::container::dtl::is_nothrow_swappable<Compare>::value )
1408    {  x.swap(y);  }
1409 };
1410
1411 } //namespace dtl {
1412 } //namespace container {
1413
1414 template <class T>
1415 struct has_trivial_destructor_after_move;
1416
1417 //!has_trivial_destructor_after_move<> == true_type
1418 //!specialization for optimizations
1419 template <class T, class KeyOfValue, class Compare, class Allocator, class Options>
1420 struct has_trivial_destructor_after_move
1421    <
1422       ::boost::container::dtl::tree
1423          <T, KeyOfValue, Compare, Allocator, Options>
1424    >
1425 {
1426    typedef typename ::boost::container::dtl::tree<T, KeyOfValue, Compare, Allocator, Options>::allocator_type allocator_type;
1427    typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
1428    static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value &&
1429                              ::boost::has_trivial_destructor_after_move<pointer>::value &&
1430                              ::boost::has_trivial_destructor_after_move<Compare>::value;
1431 };
1432
1433 } //namespace boost  {
1434
1435 #include <boost/container/detail/config_end.hpp>
1436
1437 #endif //BOOST_CONTAINER_TREE_HPP