ceph/src/boost/boost/container/detail/tree.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost
   4 // Software License, Version 1.0. (See accompanying file
   5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 //
   7 // See http://www.boost.org/libs/container for documentation.
   8 //
   9 //////////////////////////////////////////////////////////////////////////////
  10
  11 #ifndef BOOST_CONTAINER_TREE_HPP
  12 #define BOOST_CONTAINER_TREE_HPP
  13
  14 #ifndef BOOST_CONFIG_HPP
  15 #  include <boost/config.hpp>
  16 #endif
  17
  18 #if defined(BOOST_HAS_PRAGMA_ONCE)
  19 #  pragma once
  20 #endif
  21
  22 #include <boost/container/detail/config_begin.hpp>
  23 #include <boost/container/detail/workaround.hpp>
  24 // container
  25 #include <boost/container/allocator_traits.hpp>
  26 #include <boost/container/container_fwd.hpp>
  27 #include <boost/container/options.hpp>
  28 #include <boost/container/node_handle.hpp>
  29
  30 // container/detail
  31 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
  32 #include <boost/container/detail/compare_functors.hpp>
  33 #include <boost/container/detail/destroyers.hpp>
  34 #include <boost/container/detail/iterator.hpp>
  35 #include <boost/container/detail/iterators.hpp>
  36 #include <boost/container/detail/node_alloc_holder.hpp>
  37 #include <boost/container/detail/pair.hpp>
  38 #include <boost/container/detail/type_traits.hpp>
  39 // intrusive
  40 #include <boost/intrusive/pointer_traits.hpp>
  41 #include <boost/intrusive/rbtree.hpp>
  42 #include <boost/intrusive/avltree.hpp>
  43 #include <boost/intrusive/splaytree.hpp>
  44 #include <boost/intrusive/sgtree.hpp>
  45 // intrusive/detail
  46 #include <boost/intrusive/detail/minimal_pair_header.hpp>   //pair
  47 #include <boost/intrusive/detail/tree_value_compare.hpp>    //tree_value_compare
  48 // move
  49 #include <boost/move/utility_core.hpp>
  50 // move/detail
  51 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
  52 #include <boost/move/detail/fwd_macros.hpp>
  53 #endif
  54 #include <boost/move/detail/move_helpers.hpp>
  55 // other
  56 #include <boost/core/no_exceptions_support.hpp>
  57
  58
  59
  60 #include <boost/container/detail/std_fwd.hpp>
  61
  62 namespace boost {
  63 namespace container {
  64 namespace container_detail {
  65
  66 using boost::intrusive::tree_value_compare;
  67
  68 template<class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
  69 struct intrusive_tree_hook;
  70
  71 template<class VoidPointer, bool OptimizeSize>
  72 struct intrusive_tree_hook<VoidPointer, boost::container::red_black_tree, OptimizeSize>
  73 {
  74    typedef typename container_detail::bi::make_set_base_hook
  75       < container_detail::bi::void_pointer<VoidPointer>
  76       , container_detail::bi::link_mode<container_detail::bi::normal_link>
  77       , container_detail::bi::optimize_size<OptimizeSize>
  78       >::type  type;
  79 };
  80
  81 template<class VoidPointer, bool OptimizeSize>
  82 struct intrusive_tree_hook<VoidPointer, boost::container::avl_tree, OptimizeSize>
  83 {
  84    typedef typename container_detail::bi::make_avl_set_base_hook
  85       < container_detail::bi::void_pointer<VoidPointer>
  86       , container_detail::bi::link_mode<container_detail::bi::normal_link>
  87       , container_detail::bi::optimize_size<OptimizeSize>
  88       >::type  type;
  89 };
  90
  91 template<class VoidPointer, bool OptimizeSize>
  92 struct intrusive_tree_hook<VoidPointer, boost::container::scapegoat_tree, OptimizeSize>
  93 {
  94    typedef typename container_detail::bi::make_bs_set_base_hook
  95       < container_detail::bi::void_pointer<VoidPointer>
  96       , container_detail::bi::link_mode<container_detail::bi::normal_link>
  97       >::type  type;
  98 };
  99
 100 template<class VoidPointer, bool OptimizeSize>
 101 struct intrusive_tree_hook<VoidPointer, boost::container::splay_tree, OptimizeSize>
 102 {
 103    typedef typename container_detail::bi::make_bs_set_base_hook
 104       < container_detail::bi::void_pointer<VoidPointer>
 105       , container_detail::bi::link_mode<container_detail::bi::normal_link>
 106       >::type  type;
 107 };
 108
 109 //This trait is used to type-pun std::pair because in C++03
 110 //compilers std::pair is useless for C++11 features
 111 template<class T>
 112 struct tree_internal_data_type
 113 {
 114    typedef T type;
 115 };
 116
 117 template<class T1, class T2>
 118 struct tree_internal_data_type< std::pair<T1, T2> >
 119 {
 120    typedef pair<typename boost::move_detail::remove_const<T1>::type, T2> type;
 121 };
 122
 123 //The node to be store in the tree
 124 template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
 125 struct tree_node
 126    :  public intrusive_tree_hook<VoidPointer, tree_type_value, OptimizeSize>::type
 127 {
 128    private:
 129    //BOOST_COPYABLE_AND_MOVABLE(tree_node)
 130    tree_node();
 131
 132    public:
 133    typedef typename intrusive_tree_hook
 134       <VoidPointer, tree_type_value, OptimizeSize>::type hook_type;
 135    typedef T value_type;
 136    typedef typename tree_internal_data_type<T>::type     internal_type;
 137
 138    typedef tree_node< T, VoidPointer
 139                     , tree_type_value, OptimizeSize>     node_t;
 140
 141    BOOST_CONTAINER_FORCEINLINE T &get_data()
 142    {
 143       T* ptr = reinterpret_cast<T*>(&this->m_data);
 144       return *ptr;
 145    }
 146
 147    BOOST_CONTAINER_FORCEINLINE const T &get_data() const
 148    {
 149       const T* ptr = reinterpret_cast<const T*>(&this->m_data);
 150       return *ptr;
 151    }
 152
 153    internal_type m_data;
 154
 155    template<class T1, class T2>
 156    BOOST_CONTAINER_FORCEINLINE void do_assign(const std::pair<const T1, T2> &p)
 157    {
 158       const_cast<T1&>(m_data.first) = p.first;
 159       m_data.second  = p.second;
 160    }
 161
 162    template<class T1, class T2>
 163    BOOST_CONTAINER_FORCEINLINE void do_assign(const pair<const T1, T2> &p)
 164    {
 165       const_cast<T1&>(m_data.first) = p.first;
 166       m_data.second  = p.second;
 167    }
 168
 169    template<class V>
 170    BOOST_CONTAINER_FORCEINLINE void do_assign(const V &v)
 171    {  m_data = v; }
 172
 173    template<class T1, class T2>
 174    BOOST_CONTAINER_FORCEINLINE void do_move_assign(std::pair<const T1, T2> &p)
 175    {
 176       const_cast<T1&>(m_data.first) = ::boost::move(p.first);
 177       m_data.second = ::boost::move(p.second);
 178    }
 179
 180    template<class T1, class T2>
 181    BOOST_CONTAINER_FORCEINLINE void do_move_assign(pair<const T1, T2> &p)
 182    {
 183       const_cast<T1&>(m_data.first) = ::boost::move(p.first);
 184       m_data.second  = ::boost::move(p.second);
 185    }
 186
 187    template<class V>
 188    BOOST_CONTAINER_FORCEINLINE void do_move_assign(V &v)
 189    {  m_data = ::boost::move(v); }
 190 };
 191
 192 template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
 193 struct iiterator_node_value_type< tree_node<T, VoidPointer, tree_type_value, OptimizeSize> > {
 194   typedef T type;
 195 };
 196
 197 template<class Node, class Icont>
 198 class insert_equal_end_hint_functor
 199 {
 200    Icont &icont_;
 201
 202    public:
 203    BOOST_CONTAINER_FORCEINLINE insert_equal_end_hint_functor(Icont &icont)
 204       :  icont_(icont)
 205    {}
 206
 207    BOOST_CONTAINER_FORCEINLINE void operator()(Node &n)
 208    {  this->icont_.insert_equal(this->icont_.cend(), n); }
 209 };
 210
 211 template<class Node, class Icont>
 212 class push_back_functor
 213 {
 214    Icont &icont_;
 215
 216    public:
 217    BOOST_CONTAINER_FORCEINLINE push_back_functor(Icont &icont)
 218       :  icont_(icont)
 219    {}
 220
 221    BOOST_CONTAINER_FORCEINLINE void operator()(Node &n)
 222    {  this->icont_.push_back(n); }
 223 };
 224
 225 }//namespace container_detail {
 226
 227 namespace container_detail {
 228
 229 template< class NodeType, class NodeCompareType
 230         , class SizeType,  class HookType
 231         , boost::container::tree_type_enum tree_type_value>
 232 struct intrusive_tree_dispatch;
 233
 234 template<class NodeType, class NodeCompareType, class SizeType, class HookType>
 235 struct intrusive_tree_dispatch
 236    <NodeType, NodeCompareType, SizeType, HookType, boost::container::red_black_tree>
 237 {
 238    typedef typename container_detail::bi::make_rbtree
 239       <NodeType
 240       ,container_detail::bi::compare<NodeCompareType>
 241       ,container_detail::bi::base_hook<HookType>
 242       ,container_detail::bi::constant_time_size<true>
 243       ,container_detail::bi::size_type<SizeType>
 244       >::type  type;
 245 };
 246
 247 template<class NodeType, class NodeCompareType, class SizeType, class HookType>
 248 struct intrusive_tree_dispatch
 249    <NodeType, NodeCompareType, SizeType, HookType, boost::container::avl_tree>
 250 {
 251    typedef typename container_detail::bi::make_avltree
 252       <NodeType
 253       ,container_detail::bi::compare<NodeCompareType>
 254       ,container_detail::bi::base_hook<HookType>
 255       ,container_detail::bi::constant_time_size<true>
 256       ,container_detail::bi::size_type<SizeType>
 257       >::type  type;
 258 };
 259
 260 template<class NodeType, class NodeCompareType, class SizeType, class HookType>
 261 struct intrusive_tree_dispatch
 262    <NodeType, NodeCompareType, SizeType, HookType, boost::container::scapegoat_tree>
 263 {
 264    typedef typename container_detail::bi::make_sgtree
 265       <NodeType
 266       ,container_detail::bi::compare<NodeCompareType>
 267       ,container_detail::bi::base_hook<HookType>
 268       ,container_detail::bi::floating_point<true>
 269       ,container_detail::bi::size_type<SizeType>
 270       >::type  type;
 271 };
 272
 273 template<class NodeType, class NodeCompareType, class SizeType, class HookType>
 274 struct intrusive_tree_dispatch
 275    <NodeType, NodeCompareType, SizeType, HookType, boost::container::splay_tree>
 276 {
 277    typedef typename container_detail::bi::make_splaytree
 278       <NodeType
 279       ,container_detail::bi::compare<NodeCompareType>
 280       ,container_detail::bi::base_hook<HookType>
 281       ,container_detail::bi::constant_time_size<true>
 282       ,container_detail::bi::size_type<SizeType>
 283       >::type  type;
 284 };
 285
 286 template<class Allocator, class ValueCompare, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
 287 struct intrusive_tree_type
 288 {
 289    private:
 290    typedef typename boost::container::
 291       allocator_traits<Allocator>::value_type              value_type;
 292    typedef typename boost::container::
 293       allocator_traits<Allocator>::void_pointer            void_pointer;
 294    typedef typename boost::container::
 295       allocator_traits<Allocator>::size_type               size_type;
 296    typedef typename container_detail::tree_node
 297          < value_type, void_pointer
 298          , tree_type_value, OptimizeSize>                   node_t;
 299    typedef value_to_node_compare
 300       <node_t, ValueCompare>                                node_compare_type;
 301    //Deducing the hook type from node_t (e.g. node_t::hook_type) would
 302    //provoke an early instantiation of node_t that could ruin recursive
 303    //tree definitions, so retype the complete type to avoid any problem.
 304    typedef typename intrusive_tree_hook
 305       <void_pointer, tree_type_value
 306       , OptimizeSize>::type                        hook_type;
 307    public:
 308    typedef typename intrusive_tree_dispatch
 309       < node_t, node_compare_type
 310       , size_type, hook_type
 311       , tree_type_value>::type                     type;
 312 };
 313
 314 //Trait to detect manually rebalanceable tree types
 315 template<boost::container::tree_type_enum tree_type_value>
 316 struct is_manually_balanceable
 317 {  static const bool value = true;  };
 318
 319 template<>  struct is_manually_balanceable<red_black_tree>
 320 {  static const bool value = false; };
 321
 322 template<>  struct is_manually_balanceable<avl_tree>
 323 {  static const bool value = false; };
 324
 325 //Proxy traits to implement different operations depending on the
 326 //is_manually_balanceable<>::value
 327 template< boost::container::tree_type_enum tree_type_value
 328         , bool IsManuallyRebalanceable = is_manually_balanceable<tree_type_value>::value>
 329 struct intrusive_tree_proxy
 330 {
 331    template<class Icont>
 332    BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &)   {}
 333 };
 334
 335 template<boost::container::tree_type_enum tree_type_value>
 336 struct intrusive_tree_proxy<tree_type_value, true>
 337 {
 338    template<class Icont>
 339    BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &c)
 340    {  c.rebalance(); }
 341 };
 342
 343 }  //namespace container_detail {
 344
 345 namespace container_detail {
 346
 347 //This functor will be used with Intrusive clone functions to obtain
 348 //already allocated nodes from a intrusive container instead of
 349 //allocating new ones. When the intrusive container runs out of nodes
 350 //the node holder is used instead.
 351 template<class AllocHolder, bool DoMove>
 352 class RecyclingCloner
 353 {
 354    typedef typename AllocHolder::intrusive_container  intrusive_container;
 355    typedef typename AllocHolder::Node                 node_t;
 356    typedef typename AllocHolder::NodePtr              node_ptr_type;
 357
 358    public:
 359    RecyclingCloner(AllocHolder &holder, intrusive_container &itree)
 360       :  m_holder(holder), m_icont(itree)
 361    {}
 362
 363    BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<true>)
 364    {  p->do_move_assign(const_cast<node_t &>(other).m_data);   }
 365
 366    BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<false>)
 367    {  p->do_assign(other.m_data);   }
 368
 369    node_ptr_type operator()(const node_t &other) const
 370    {
 371       if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){
 372          //First recycle a node (this can't throw)
 373          BOOST_TRY{
 374             //This can throw
 375             this->do_assign(p, other, bool_<DoMove>());
 376             return p;
 377          }
 378          BOOST_CATCH(...){
 379             //If there is an exception destroy the whole source
 380             m_holder.destroy_node(p);
 381             while((p = m_icont.unlink_leftmost_without_rebalance())){
 382                m_holder.destroy_node(p);
 383             }
 384             BOOST_RETHROW
 385          }
 386          BOOST_CATCH_END
 387       }
 388       else{
 389          return m_holder.create_node(other.m_data);
 390       }
 391    }
 392
 393    AllocHolder &m_holder;
 394    intrusive_container &m_icont;
 395 };
 396
 397 template<class KeyCompare, class KeyOfValue>
 398 struct key_node_compare
 399    :  public boost::intrusive::detail::ebo_functor_holder<KeyCompare>
 400 {
 401    BOOST_CONTAINER_FORCEINLINE explicit key_node_compare(const KeyCompare &comp)
 402       :  base_t(comp)
 403    {}
 404
 405    typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t;
 406    typedef KeyCompare                  key_compare;
 407    typedef KeyOfValue                  key_of_value;
 408    typedef typename KeyOfValue::type   key_type;
 409
 410    BOOST_CONTAINER_FORCEINLINE const key_compare &key_comp() const
 411    {  return static_cast<const key_compare &>(*this);  }
 412
 413    BOOST_CONTAINER_FORCEINLINE key_compare &key_comp()
 414    {  return static_cast<key_compare &>(*this);  }
 415
 416    BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const
 417    {  return this->key_comp()(key1, key2);  }
 418
 419    template<class U>
 420    BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const U &nonkey2) const
 421    {  return this->key_comp()(key1, key_of_value()(nonkey2.get_data()));  }
 422
 423    template<class U>
 424    BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2) const
 425    {  return this->key_comp()(key_of_value()(nonkey1.get_data()), key2);  }
 426
 427    template<class U, class V>
 428    BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const V &nonkey2) const
 429    {  return this->key_comp()(key_of_value()(nonkey1.get_data()), key_of_value()(nonkey2.get_data()));  }
 430 };
 431
 432 template <class T, class KeyOfValue,
 433           class Compare, class Allocator,
 434           class Options = tree_assoc_defaults>
 435 class tree
 436    : public container_detail::node_alloc_holder
 437       < Allocator
 438       , typename container_detail::intrusive_tree_type
 439          < Allocator, tree_value_compare
 440             <typename allocator_traits<Allocator>::pointer, Compare, KeyOfValue>
 441          , Options::tree_type, Options::optimize_size>::type
 442       >
 443 {
 444    typedef tree_value_compare
 445       < typename allocator_traits<Allocator>::pointer
 446       , Compare, KeyOfValue>                                ValComp;
 447    typedef typename container_detail::intrusive_tree_type
 448          < Allocator, ValComp, Options::tree_type
 449          , Options::optimize_size>::type                    Icont;
 450    typedef container_detail::node_alloc_holder
 451       <Allocator, Icont>                                    AllocHolder;
 452    typedef typename AllocHolder::NodePtr                    NodePtr;
 453    typedef tree < T, KeyOfValue
 454                 , Compare, Allocator, Options>              ThisType;
 455    typedef typename AllocHolder::NodeAlloc                  NodeAlloc;
 456    typedef boost::container::
 457       allocator_traits<NodeAlloc>                           allocator_traits_type;
 458    typedef typename AllocHolder::ValAlloc                   ValAlloc;
 459    typedef typename AllocHolder::Node                       Node;
 460    typedef typename Icont::iterator                         iiterator;
 461    typedef typename Icont::const_iterator                   iconst_iterator;
 462    typedef container_detail::allocator_destroyer<NodeAlloc> Destroyer;
 463    typedef typename AllocHolder::alloc_version              alloc_version;
 464    typedef intrusive_tree_proxy<Options::tree_type>         intrusive_tree_proxy_t;
 465
 466    BOOST_COPYABLE_AND_MOVABLE(tree)
 467
 468    public:
 469
 470    typedef typename KeyOfValue::type                  key_type;
 471    typedef T                                          value_type;
 472    typedef Allocator                                  allocator_type;
 473    typedef Compare                                    key_compare;
 474    typedef ValComp                                    value_compare;
 475    typedef typename boost::container::
 476       allocator_traits<Allocator>::pointer            pointer;
 477    typedef typename boost::container::
 478       allocator_traits<Allocator>::const_pointer      const_pointer;
 479    typedef typename boost::container::
 480       allocator_traits<Allocator>::reference          reference;
 481    typedef typename boost::container::
 482       allocator_traits<Allocator>::const_reference    const_reference;
 483    typedef typename boost::container::
 484       allocator_traits<Allocator>::size_type          size_type;
 485    typedef typename boost::container::
 486       allocator_traits<Allocator>::difference_type    difference_type;
 487    typedef container_detail::iterator_from_iiterator
 488       <iiterator, false>                              iterator;
 489    typedef container_detail::iterator_from_iiterator
 490       <iiterator, true >                              const_iterator;
 491    typedef boost::container::reverse_iterator
 492       <iterator>                                      reverse_iterator;
 493    typedef boost::container::reverse_iterator
 494       <const_iterator>                                const_reverse_iterator;
 495    typedef node_handle
 496       < NodeAlloc, void>                              node_type;
 497    typedef insert_return_type_base
 498       <iterator, node_type>                           insert_return_type;
 499
 500    typedef NodeAlloc                                  stored_allocator_type;
 501
 502    private:
 503
 504    typedef key_node_compare<key_compare, KeyOfValue>  KeyNodeCompare;
 505
 506    public:
 507
 508    BOOST_CONTAINER_FORCEINLINE tree()
 509       : AllocHolder()
 510    {}
 511
 512    BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp)
 513       : AllocHolder(ValComp(comp))
 514    {}
 515
 516    BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a)
 517       : AllocHolder(ValComp(comp), a)
 518    {}
 519
 520    BOOST_CONTAINER_FORCEINLINE explicit tree(const allocator_type& a)
 521       : AllocHolder(a)
 522    {}
 523
 524    template <class InputIterator>
 525    tree(bool unique_insertion, InputIterator first, InputIterator last)
 526       : AllocHolder(value_compare(key_compare()))
 527    {
 528       this->tree_construct(unique_insertion, first, last);
 529       //AllocHolder clears in case of exception
 530    }
 531
 532    template <class InputIterator>
 533    tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp)
 534       : AllocHolder(value_compare(comp))
 535    {
 536       this->tree_construct(unique_insertion, first, last);
 537       //AllocHolder clears in case of exception
 538    }
 539
 540    template <class InputIterator>
 541    tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a)
 542       : AllocHolder(value_compare(comp), a)
 543    {
 544       this->tree_construct(unique_insertion, first, last);
 545       //AllocHolder clears in case of exception
 546    }
 547
 548    //construct with ordered range
 549    template <class InputIterator>
 550    tree( ordered_range_t, InputIterator first, InputIterator last)
 551       : AllocHolder(value_compare(key_compare()))
 552    {
 553       this->tree_construct(ordered_range_t(), first, last);
 554    }
 555
 556    template <class InputIterator>
 557    tree( ordered_range_t, InputIterator first, InputIterator last, const key_compare& comp)
 558       : AllocHolder(value_compare(comp))
 559    {
 560       this->tree_construct(ordered_range_t(), first, last);
 561    }
 562
 563    template <class InputIterator>
 564    tree( ordered_range_t, InputIterator first, InputIterator last
 565          , const key_compare& comp, const allocator_type& a)
 566       : AllocHolder(value_compare(comp), a)
 567    {
 568       this->tree_construct(ordered_range_t(), first, last);
 569    }
 570
 571    private:
 572
 573    template <class InputIterator>
 574    void tree_construct(bool unique_insertion, InputIterator first, InputIterator last)
 575    {
 576       //Use cend() as hint to achieve linear time for
 577       //ordered ranges as required by the standard
 578       //for the constructor
 579       if(unique_insertion){
 580          const const_iterator end_it(this->cend());
 581          for ( ; first != last; ++first){
 582             this->insert_unique_convertible(end_it, *first);
 583          }
 584       }
 585       else{
 586          this->tree_construct_non_unique(first, last);
 587       }
 588    }
 589
 590    template <class InputIterator>
 591    void tree_construct_non_unique(InputIterator first, InputIterator last
 592       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 593       , typename container_detail::enable_if_or
 594          < void
 595          , container_detail::is_same<alloc_version, version_1>
 596          , container_detail::is_input_iterator<InputIterator>
 597          >::type * = 0
 598       #endif
 599          )
 600    {
 601       //Use cend() as hint to achieve linear time for
 602       //ordered ranges as required by the standard
 603       //for the constructor
 604       const const_iterator end_it(this->cend());
 605       for ( ; first != last; ++first){
 606          this->insert_equal_convertible(end_it, *first);
 607       }
 608    }
 609
 610    template <class InputIterator>
 611    void tree_construct_non_unique(InputIterator first, InputIterator last
 612       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 613       , typename container_detail::disable_if_or
 614          < void
 615          , container_detail::is_same<alloc_version, version_1>
 616          , container_detail::is_input_iterator<InputIterator>
 617          >::type * = 0
 618       #endif
 619          )
 620    {
 621       //Optimized allocation and construction
 622       this->allocate_many_and_construct
 623          ( first, boost::container::iterator_distance(first, last)
 624          , insert_equal_end_hint_functor<Node, Icont>(this->icont()));
 625    }
 626
 627    template <class InputIterator>
 628    void tree_construct( ordered_range_t, InputIterator first, InputIterator last
 629          #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 630       , typename container_detail::disable_if_or
 631          < void
 632          , container_detail::is_same<alloc_version, version_1>
 633          , container_detail::is_input_iterator<InputIterator>
 634          >::type * = 0
 635          #endif
 636          )
 637    {
 638       //Optimized allocation and construction
 639       this->allocate_many_and_construct
 640          ( first, boost::container::iterator_distance(first, last)
 641          , container_detail::push_back_functor<Node, Icont>(this->icont()));
 642       //AllocHolder clears in case of exception
 643    }
 644
 645    template <class InputIterator>
 646    void tree_construct( ordered_range_t, InputIterator first, InputIterator last
 647          #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 648       , typename container_detail::enable_if_or
 649          < void
 650          , container_detail::is_same<alloc_version, version_1>
 651          , container_detail::is_input_iterator<InputIterator>
 652          >::type * = 0
 653          #endif
 654          )
 655    {
 656       for ( ; first != last; ++first){
 657          this->push_back_impl(*first);
 658       }
 659    }
 660
 661    public:
 662
 663    BOOST_CONTAINER_FORCEINLINE tree(const tree& x)
 664       :  AllocHolder(x, x.value_comp())
 665    {
 666       this->icont().clone_from
 667          (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
 668    }
 669
 670    BOOST_CONTAINER_FORCEINLINE tree(BOOST_RV_REF(tree) x)
 671       BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value)
 672       :  AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp())
 673    {}
 674
 675    BOOST_CONTAINER_FORCEINLINE tree(const tree& x, const allocator_type &a)
 676       :  AllocHolder(x.value_comp(), a)
 677    {
 678       this->icont().clone_from
 679          (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
 680       //AllocHolder clears in case of exception
 681    }
 682
 683    tree(BOOST_RV_REF(tree) x, const allocator_type &a)
 684       :  AllocHolder(x.value_comp(), a)
 685    {
 686       if(this->node_alloc() == x.node_alloc()){
 687          this->icont().swap(x.icont());
 688       }
 689       else{
 690          this->icont().clone_from
 691             (boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc()));
 692       }
 693       //AllocHolder clears in case of exception
 694    }
 695
 696    BOOST_CONTAINER_FORCEINLINE ~tree()
 697    {} //AllocHolder clears the tree
 698
 699    tree& operator=(BOOST_COPY_ASSIGN_REF(tree) x)
 700    {
 701       if (&x != this){
 702          NodeAlloc &this_alloc     = this->get_stored_allocator();
 703          const NodeAlloc &x_alloc  = x.get_stored_allocator();
 704          container_detail::bool_<allocator_traits<NodeAlloc>::
 705             propagate_on_container_copy_assignment::value> flag;
 706          if(flag && this_alloc != x_alloc){
 707             this->clear();
 708          }
 709          this->AllocHolder::copy_assign_alloc(x);
 710          //Transfer all the nodes to a temporary tree
 711          //If anything goes wrong, all the nodes will be destroyed
 712          //automatically
 713          Icont other_tree(::boost::move(this->icont()));
 714
 715          //Now recreate the source tree reusing nodes stored by other_tree
 716          this->icont().clone_from
 717             (x.icont()
 718             , RecyclingCloner<AllocHolder, false>(*this, other_tree)
 719             , Destroyer(this->node_alloc()));
 720
 721          //If there are remaining nodes, destroy them
 722          NodePtr p;
 723          while((p = other_tree.unlink_leftmost_without_rebalance())){
 724             AllocHolder::destroy_node(p);
 725          }
 726       }
 727       return *this;
 728    }
 729
 730    tree& operator=(BOOST_RV_REF(tree) x)
 731       BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
 732                           allocator_traits_type::is_always_equal::value) &&
 733                            boost::container::container_detail::is_nothrow_move_assignable<Compare>::value)
 734    {
 735       BOOST_ASSERT(this != &x);
 736       NodeAlloc &this_alloc = this->node_alloc();
 737       NodeAlloc &x_alloc    = x.node_alloc();
 738       const bool propagate_alloc = allocator_traits<NodeAlloc>::
 739             propagate_on_container_move_assignment::value;
 740       const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
 741       //Resources can be transferred if both allocators are
 742       //going to be equal after this function (either propagated or already equal)
 743       if(propagate_alloc || allocators_equal){
 744          //Destroy
 745          this->clear();
 746          //Move allocator if needed
 747          this->AllocHolder::move_assign_alloc(x);
 748          //Obtain resources
 749          this->icont() = boost::move(x.icont());
 750       }
 751       //Else do a one by one move
 752       else{
 753          //Transfer all the nodes to a temporary tree
 754          //If anything goes wrong, all the nodes will be destroyed
 755          //automatically
 756          Icont other_tree(::boost::move(this->icont()));
 757
 758          //Now recreate the source tree reusing nodes stored by other_tree
 759          this->icont().clone_from
 760             (::boost::move(x.icont())
 761             , RecyclingCloner<AllocHolder, true>(*this, other_tree)
 762             , Destroyer(this->node_alloc()));
 763
 764          //If there are remaining nodes, destroy them
 765          NodePtr p;
 766          while((p = other_tree.unlink_leftmost_without_rebalance())){
 767             AllocHolder::destroy_node(p);
 768          }
 769       }
 770       return *this;
 771    }
 772
 773    public:
 774    // accessors:
 775    BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const
 776    {  return this->icont().value_comp().predicate(); }
 777
 778    BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const
 779    {  return this->icont().value_comp().predicate().key_comp(); }
 780
 781    BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const
 782    {  return allocator_type(this->node_alloc()); }
 783
 784    BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const
 785    {  return this->node_alloc(); }
 786
 787    BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator()
 788    {  return this->node_alloc(); }
 789
 790    BOOST_CONTAINER_FORCEINLINE iterator begin()
 791    { return iterator(this->icont().begin()); }
 792
 793    BOOST_CONTAINER_FORCEINLINE const_iterator begin() const
 794    {  return this->cbegin();  }
 795
 796    BOOST_CONTAINER_FORCEINLINE iterator end()
 797    {  return iterator(this->icont().end());  }
 798
 799    BOOST_CONTAINER_FORCEINLINE const_iterator end() const
 800    {  return this->cend();  }
 801
 802    BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin()
 803    {  return reverse_iterator(end());  }
 804
 805    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const
 806    {  return this->crbegin();  }
 807
 808    BOOST_CONTAINER_FORCEINLINE reverse_iterator rend()
 809    {  return reverse_iterator(begin());   }
 810
 811    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const
 812    {  return this->crend();   }
 813
 814    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
 815    //!
 816    //! <b>Throws</b>: Nothing.
 817    //!
 818    //! <b>Complexity</b>: Constant.
 819    BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const
 820    { return const_iterator(this->non_const_icont().begin()); }
 821
 822    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
 823    //!
 824    //! <b>Throws</b>: Nothing.
 825    //!
 826    //! <b>Complexity</b>: Constant.
 827    BOOST_CONTAINER_FORCEINLINE const_iterator cend() const
 828    { return const_iterator(this->non_const_icont().end()); }
 829
 830    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
 831    //! of the reversed container.
 832    //!
 833    //! <b>Throws</b>: Nothing.
 834    //!
 835    //! <b>Complexity</b>: Constant.
 836    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const
 837    { return const_reverse_iterator(cend()); }
 838
 839    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
 840    //! of the reversed container.
 841    //!
 842    //! <b>Throws</b>: Nothing.
 843    //!
 844    //! <b>Complexity</b>: Constant.
 845    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const
 846    { return const_reverse_iterator(cbegin()); }
 847
 848    BOOST_CONTAINER_FORCEINLINE bool empty() const
 849    {  return !this->size();  }
 850
 851    BOOST_CONTAINER_FORCEINLINE size_type size() const
 852    {  return this->icont().size();   }
 853
 854    BOOST_CONTAINER_FORCEINLINE size_type max_size() const
 855    {  return AllocHolder::max_size();  }
 856
 857    BOOST_CONTAINER_FORCEINLINE void swap(ThisType& x)
 858       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
 859                                  && boost::container::container_detail::is_nothrow_swappable<Compare>::value )
 860    {  AllocHolder::swap(x);   }
 861
 862    public:
 863
 864    typedef typename Icont::insert_commit_data insert_commit_data;
 865
 866    // insert/erase
 867    std::pair<iterator,bool> insert_unique_check
 868       (const key_type& key, insert_commit_data &data)
 869    {
 870       std::pair<iiterator, bool> ret =
 871          this->icont().insert_unique_check(key, KeyNodeCompare(key_comp()), data);
 872       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
 873    }
 874
 875    std::pair<iterator,bool> insert_unique_check
 876       (const_iterator hint, const key_type& key, insert_commit_data &data)
 877    {
 878       BOOST_ASSERT((priv_is_linked)(hint));
 879       std::pair<iiterator, bool> ret =
 880          this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(key_comp()), data);
 881       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
 882    }
 883
 884    template<class MovableConvertible>
 885    iterator insert_unique_commit
 886       (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data)
 887    {
 888       NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v));
 889       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
 890       iterator ret(this->icont().insert_unique_commit(*tmp, data));
 891       destroy_deallocator.release();
 892       return ret;
 893    }
 894
 895    template<class MovableConvertible>
 896    std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) v)
 897    {
 898       insert_commit_data data;
 899       std::pair<iterator,bool> ret =
 900          this->insert_unique_check(KeyOfValue()(v), data);
 901       if(ret.second){
 902          ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
 903       }
 904       return ret;
 905    }
 906
 907    private:
 908
 909    template<class KeyConvertible, class M>
 910    iiterator priv_insert_or_assign_commit
 911       (BOOST_FWD_REF(KeyConvertible) key, BOOST_FWD_REF(M) obj, insert_commit_data &data)
 912    {
 913       NodePtr tmp = AllocHolder::create_node(boost::forward<KeyConvertible>(key), boost::forward<M>(obj));
 914       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
 915       iiterator ret(this->icont().insert_unique_commit(*tmp, data));
 916       destroy_deallocator.release();
 917       return ret;
 918    }
 919
 920    bool priv_is_linked(const_iterator const position) const
 921    {
 922       iiterator const cur(position.get());
 923       return   cur == this->icont().end() ||
 924                cur == this->icont().root() ||
 925                iiterator(cur).go_parent().go_left()  == cur ||
 926                iiterator(cur).go_parent().go_right() == cur;
 927    }
 928
 929    template<class MovableConvertible>
 930    void push_back_impl(BOOST_FWD_REF(MovableConvertible) v)
 931    {
 932       NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
 933       //push_back has no-throw guarantee so avoid any deallocator/destroyer
 934       this->icont().push_back(*tmp);
 935    }
 936
 937    std::pair<iterator, bool> emplace_unique_impl(NodePtr p)
 938    {
 939       value_type &v = p->get_data();
 940       insert_commit_data data;
 941       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc());
 942       std::pair<iterator,bool> ret =
 943          this->insert_unique_check(KeyOfValue()(v), data);
 944       if(!ret.second){
 945          return ret;
 946       }
 947       //No throw insertion part, release rollback
 948       destroy_deallocator.release();
 949       return std::pair<iterator,bool>
 950          ( iterator(this->icont().insert_unique_commit(*p, data))
 951          , true );
 952    }
 953
 954    iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p)
 955    {
 956       BOOST_ASSERT((priv_is_linked)(hint));
 957       value_type &v = p->get_data();
 958       insert_commit_data data;
 959       std::pair<iterator,bool> ret =
 960          this->insert_unique_check(hint, KeyOfValue()(v), data);
 961       if(!ret.second){
 962          Destroyer(this->node_alloc())(p);
 963          return ret.first;
 964       }
 965       return iterator(this->icont().insert_unique_commit(*p, data));
 966    }
 967
 968    public:
 969
 970    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 971
 972    template <class... Args>
 973    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args)
 974    {  return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...));   }
 975
 976    template <class... Args>
 977    BOOST_CONTAINER_FORCEINLINE iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args)
 978    {  return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...));   }
 979
 980    template <class... Args>
 981    iterator emplace_equal(BOOST_FWD_REF(Args)... args)
 982    {
 983       NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
 984       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
 985       iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
 986       destroy_deallocator.release();
 987       return ret;
 988    }
 989
 990    template <class... Args>
 991    iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args)
 992    {
 993       BOOST_ASSERT((priv_is_linked)(hint));
 994       NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
 995       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
 996       iterator ret(this->icont().insert_equal(hint.get(), *tmp));
 997       destroy_deallocator.release();
 998       return ret;
 999    }
1000
1001    template <class KeyType, class... Args>
1002    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace
1003       (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args)
1004    {
1005       insert_commit_data data;
1006       const key_type & k = key;  //Support emulated rvalue references
1007       std::pair<iiterator, bool> ret =
1008          hint == const_iterator() ? this->icont().insert_unique_check(            k, KeyNodeCompare(key_comp()), data)
1009                                   : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);
1010       if(ret.second){
1011          ret.first = this->icont().insert_unique_commit
1012             (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key), boost::forward<Args>(args)...), data);
1013       }
1014       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
1015    }
1016
1017    #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1018
1019    #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \
1020    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1021    std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\
1022    {  return this->emplace_unique_impl(AllocHolder::create_node(BOOST_MOVE_FWD##N));  }\
1023    \
1024    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1025    iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1026    {  return this->emplace_unique_hint_impl(hint, 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_equal(BOOST_MOVE_UREF##N)\
1030    {\
1031       NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
1032       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
1033       iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\
1034       destroy_deallocator.release();\
1035       return ret;\
1036    }\
1037    \
1038    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1039    iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1040    {\
1041       BOOST_ASSERT((priv_is_linked)(hint));\
1042       NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
1043       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
1044       iterator ret(this->icont().insert_equal(hint.get(), *tmp));\
1045       destroy_deallocator.release();\
1046       return ret;\
1047    }\
1048    \
1049    template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\
1050    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\
1051       try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1052    {\
1053       insert_commit_data data;\
1054       const key_type & k = key;\
1055       std::pair<iiterator, bool> ret =\
1056          hint == const_iterator() ? this->icont().insert_unique_check(            k, KeyNodeCompare(key_comp()), data)\
1057                                   : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);\
1058       if(ret.second){\
1059          ret.first = this->icont().insert_unique_commit\
1060             (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N), data);\
1061       }\
1062       return std::pair<iterator, bool>(iterator(ret.first), ret.second);\
1063    }\
1064    //
1065    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE)
1066    #undef BOOST_CONTAINER_TREE_EMPLACE_CODE
1067
1068    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1069
1070    template<class MovableConvertible>
1071    iterator insert_unique_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
1072    {
1073       BOOST_ASSERT((priv_is_linked)(hint));
1074       insert_commit_data data;
1075       std::pair<iterator,bool> ret =
1076          this->insert_unique_check(hint, KeyOfValue()(v), data);
1077       if(!ret.second)
1078          return ret.first;
1079       return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
1080    }
1081
1082    BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_unique, value_type, iterator, this->insert_unique_convertible, const_iterator, const_iterator)
1083
1084    template <class InputIterator>
1085    void insert_unique(InputIterator first, InputIterator last)
1086    {
1087       for( ; first != last; ++first)
1088          this->insert_unique(*first);
1089    }
1090
1091    iterator insert_equal(const value_type& v)
1092    {
1093       NodePtr tmp(AllocHolder::create_node(v));
1094       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
1095       iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
1096       destroy_deallocator.release();
1097       return ret;
1098    }
1099
1100    template<class MovableConvertible>
1101    iterator insert_equal(BOOST_FWD_REF(MovableConvertible) v)
1102    {
1103       NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
1104       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
1105       iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
1106       destroy_deallocator.release();
1107       return ret;
1108    }
1109
1110    template<class MovableConvertible>
1111    iterator insert_equal_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
1112    {
1113       BOOST_ASSERT((priv_is_linked)(hint));
1114       NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
1115       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
1116       iterator ret(this->icont().insert_equal(hint.get(), *tmp));
1117       destroy_deallocator.release();
1118       return ret;
1119    }
1120
1121    BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_equal, value_type, iterator, this->insert_equal_convertible, const_iterator, const_iterator)
1122
1123    template <class InputIterator>
1124    void insert_equal(InputIterator first, InputIterator last)
1125    {
1126       for( ; first != last; ++first)
1127          this->insert_equal(*first);
1128    }
1129
1130    template<class KeyType, class M>
1131    std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj)
1132    {
1133       insert_commit_data data;
1134       const key_type & k = key;  //Support emulated rvalue references
1135       std::pair<iiterator, bool> ret =
1136          hint == const_iterator() ? this->icont().insert_unique_check(k, KeyNodeCompare(key_comp()), data)
1137                                   : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);
1138       if(ret.second){
1139          ret.first = this->priv_insert_or_assign_commit(boost::forward<KeyType>(key), boost::forward<M>(obj), data);
1140       }
1141       else{
1142          ret.first->get_data().second = boost::forward<M>(obj);
1143       }
1144       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
1145    }
1146
1147    iterator erase(const_iterator position)
1148    {
1149       BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position));
1150       return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc())));
1151    }
1152
1153    BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& k)
1154    {  return AllocHolder::erase_key(k, KeyNodeCompare(key_comp()), alloc_version()); }
1155
1156    iterator erase(const_iterator first, const_iterator last)
1157    {
1158       BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first)));
1159       BOOST_ASSERT(first == last || (priv_is_linked)(last));
1160       return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version()));
1161    }
1162
1163    node_type extract(const key_type& k)
1164    {
1165       iterator const it = this->find(k);
1166       if(this->end() != it){
1167          return this->extract(it);
1168       }
1169       return node_type();
1170    }
1171
1172    node_type extract(const_iterator position)
1173    {
1174       BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position));
1175       iiterator const iit(position.get());
1176       this->icont().erase(iit);
1177       return node_type(iit.operator->(), this->node_alloc());
1178    }
1179
1180    insert_return_type insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1181    {
1182       return this->insert_unique_node(this->end(), boost::move(nh));
1183    }
1184
1185    insert_return_type insert_unique_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1186    {
1187       insert_return_type irt; //inserted == false, node.empty()
1188       if(!nh.empty()){
1189          insert_commit_data data;
1190          std::pair<iterator,bool> ret =
1191             this->insert_unique_check(hint, KeyOfValue()(nh.value()), data);
1192          if(ret.second){
1193             irt.inserted = true;
1194             irt.position = iterator(this->icont().insert_unique_commit(*nh.get(), data));
1195             nh.release();
1196          }
1197          else{
1198             irt.position = ret.first;
1199             irt.node = boost::move(nh);
1200          }
1201       }
1202       else{
1203          irt.position = this->end();
1204       }
1205       return BOOST_MOVE_RET(insert_return_type, irt);
1206    }
1207
1208    iterator insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1209    {
1210       if(nh.empty()){
1211          return this->end();
1212       }
1213       else{
1214          NodePtr const p(nh.release());
1215          return iterator(this->icont().insert_equal(*p));
1216       }
1217    }
1218
1219    iterator insert_equal_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1220    {
1221       if(nh.empty()){
1222          return this->end();
1223       }
1224       else{
1225          NodePtr const p(nh.release());
1226          return iterator(this->icont().insert_equal(hint.get(), *p));
1227       }
1228    }
1229
1230    template<class C2>
1231    BOOST_CONTAINER_FORCEINLINE void merge_unique(tree<T, KeyOfValue, C2, Allocator, Options>& source)
1232    {  return this->icont().merge_unique(source.icont()); }
1233
1234    template<class C2>
1235    BOOST_CONTAINER_FORCEINLINE void merge_equal(tree<T, KeyOfValue, C2, Allocator, Options>& source)
1236    {  return this->icont().merge_equal(source.icont());  }
1237    BOOST_CONTAINER_FORCEINLINE void clear()
1238    {  AllocHolder::clear(alloc_version());  }
1239
1240    // search operations. Const and non-const overloads even if no iterator is returned
1241    // so splay implementations can to their rebalancing when searching in non-const versions
1242    BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& k)
1243    {  return iterator(this->icont().find(k, KeyNodeCompare(key_comp())));  }
1244
1245    BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& k) const
1246    {  return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp())));  }
1247
1248    BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& k) const
1249    {  return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); }
1250
1251    BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k)
1252    {  return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp())));  }
1253
1254    BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& k) const
1255    {  return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp())));  }
1256
1257    BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& k)
1258    {  return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp())));   }
1259
1260    BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& k) const
1261    {  return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp())));  }
1262
1263    std::pair<iterator,iterator> equal_range(const key_type& k)
1264    {
1265       std::pair<iiterator, iiterator> ret =
1266          this->icont().equal_range(k, KeyNodeCompare(key_comp()));
1267       return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
1268    }
1269
1270    std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
1271    {
1272       std::pair<iiterator, iiterator> ret =
1273          this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp()));
1274       return std::pair<const_iterator,const_iterator>
1275          (const_iterator(ret.first), const_iterator(ret.second));
1276    }
1277
1278    std::pair<iterator,iterator> lower_bound_range(const key_type& k)
1279    {
1280       std::pair<iiterator, iiterator> ret =
1281          this->icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
1282       return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
1283    }
1284
1285    std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
1286    {
1287       std::pair<iiterator, iiterator> ret =
1288          this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
1289       return std::pair<const_iterator,const_iterator>
1290          (const_iterator(ret.first), const_iterator(ret.second));
1291    }
1292
1293    BOOST_CONTAINER_FORCEINLINE void rebalance()
1294    {  intrusive_tree_proxy_t::rebalance(this->icont());   }
1295
1296    BOOST_CONTAINER_FORCEINLINE friend bool operator==(const tree& x, const tree& y)
1297    {  return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());  }
1298
1299    BOOST_CONTAINER_FORCEINLINE friend bool operator<(const tree& x, const tree& y)
1300    {  return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());  }
1301
1302    BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const tree& x, const tree& y)
1303    {  return !(x == y);  }
1304
1305    BOOST_CONTAINER_FORCEINLINE friend bool operator>(const tree& x, const tree& y)
1306    {  return y < x;  }
1307
1308    BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const tree& x, const tree& y)
1309    {  return !(y < x);  }
1310
1311    BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const tree& x, const tree& y)
1312    {  return !(x < y);  }
1313
1314    BOOST_CONTAINER_FORCEINLINE friend void swap(tree& x, tree& y)
1315    {  x.swap(y);  }
1316 };
1317
1318 } //namespace container_detail {
1319 } //namespace container {
1320
1321 template <class T>
1322 struct has_trivial_destructor_after_move;
1323
1324 //!has_trivial_destructor_after_move<> == true_type
1325 //!specialization for optimizations
1326 template <class T, class KeyOfValue, class Compare, class Allocator, class Options>
1327 struct has_trivial_destructor_after_move
1328    <
1329       ::boost::container::container_detail::tree
1330          <T, KeyOfValue, Compare, Allocator, Options>
1331    >
1332 {
1333    typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1334    static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
1335                              ::boost::has_trivial_destructor_after_move<pointer>::value &&
1336                              ::boost::has_trivial_destructor_after_move<Compare>::value;
1337 };
1338
1339 } //namespace boost  {
1340
1341 #include <boost/container/detail/config_end.hpp>
1342
1343 #endif //BOOST_CONTAINER_TREE_HPP