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