Chris@16: //////////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@101: // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
Chris@16: // Software License, Version 1.0. (See accompanying file
Chris@16: // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // See http://www.boost.org/libs/container for documentation.
Chris@16: //
Chris@16: //////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: #ifndef BOOST_CONTAINER_TREE_HPP
Chris@16: #define BOOST_CONTAINER_TREE_HPP
Chris@16: 
Chris@101: #ifndef BOOST_CONFIG_HPP
Chris@101: #  include <boost/config.hpp>
Chris@101: #endif
Chris@101: 
Chris@101: #if defined(BOOST_HAS_PRAGMA_ONCE)
Chris@101: #  pragma once
Chris@101: #endif
Chris@101: 
Chris@101: #include <boost/container/detail/config_begin.hpp>
Chris@16: #include <boost/container/detail/workaround.hpp>
Chris@101: // container
Chris@101: #include <boost/container/allocator_traits.hpp>
Chris@16: #include <boost/container/container_fwd.hpp>
Chris@101: #include <boost/container/options.hpp>
Chris@16: 
Chris@101: // container/detail
Chris@101: #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
Chris@101: #include <boost/container/detail/compare_functors.hpp>
Chris@101: #include <boost/container/detail/destroyers.hpp>
Chris@101: #include <boost/container/detail/iterator.hpp>
Chris@16: #include <boost/container/detail/iterators.hpp>
Chris@16: #include <boost/container/detail/node_alloc_holder.hpp>
Chris@16: #include <boost/container/detail/pair.hpp>
Chris@16: #include <boost/container/detail/type_traits.hpp>
Chris@101: // intrusive
Chris@101: #include <boost/intrusive/pointer_traits.hpp>
Chris@101: #include <boost/intrusive/rbtree.hpp>
Chris@101: #include <boost/intrusive/avltree.hpp>
Chris@101: #include <boost/intrusive/splaytree.hpp>
Chris@101: #include <boost/intrusive/sgtree.hpp>
Chris@101: // intrusive/detail
Chris@101: #include <boost/intrusive/detail/minimal_pair_header.hpp>   //pair
Chris@101: // move
Chris@101: #include <boost/move/utility_core.hpp>
Chris@101: // move/detail
Chris@101: #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@101: #include <boost/move/detail/fwd_macros.hpp>
Chris@16: #endif
Chris@101: // other
Chris@101: #include <boost/core/no_exceptions_support.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace container {
Chris@16: namespace container_detail {
Chris@16: 
Chris@101: template<class Key, class T, class Compare, class KeyOfValue>
Chris@16: struct tree_value_compare
Chris@101:    :  public Compare
Chris@16: {
Chris@101:    typedef T        value_type;
Chris@101:    typedef Compare   key_compare;
Chris@16:    typedef KeyOfValue   key_of_value;
Chris@16:    typedef Key          key_type;
Chris@16: 
Chris@16:    explicit tree_value_compare(const key_compare &kcomp)
Chris@101:       :  Compare(kcomp)
Chris@16:    {}
Chris@16: 
Chris@16:    tree_value_compare()
Chris@101:       :  Compare()
Chris@16:    {}
Chris@16: 
Chris@16:    const key_compare &key_comp() const
Chris@16:    {  return static_cast<const key_compare &>(*this);  }
Chris@16: 
Chris@16:    key_compare &key_comp()
Chris@16:    {  return static_cast<key_compare &>(*this);  }
Chris@16: 
Chris@101:    template<class U>
Chris@16:    struct is_key
Chris@16:    {
Chris@101:       static const bool value = is_same<const U, const key_type>::value;
Chris@16:    };
Chris@16: 
Chris@101:    template<class U>
Chris@101:    typename enable_if_c<is_key<U>::value, const key_type &>::type
Chris@101:       key_forward(const U &key) const
Chris@16:    {  return key; }
Chris@16: 
Chris@101:    template<class U>
Chris@101:    typename enable_if_c<!is_key<U>::value, const key_type &>::type
Chris@101:       key_forward(const U &key) const
Chris@16:    {  return KeyOfValue()(key);  }
Chris@16: 
Chris@16:    template<class KeyType, class KeyType2>
Chris@16:    bool operator()(const KeyType &key1, const KeyType2 &key2) const
Chris@16:    {  return key_compare::operator()(this->key_forward(key1), this->key_forward(key2));  }
Chris@101: 
Chris@101:    template<class KeyType, class KeyType2>
Chris@101:    bool operator()(const KeyType &key1, const KeyType2 &key2)
Chris@101:    {  return key_compare::operator()(this->key_forward(key1), this->key_forward(key2));  }
Chris@16: };
Chris@16: 
Chris@101: template<class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
Chris@101: struct intrusive_tree_hook;
Chris@101: 
Chris@101: template<class VoidPointer, bool OptimizeSize>
Chris@101: struct intrusive_tree_hook<VoidPointer, boost::container::red_black_tree, OptimizeSize>
Chris@16: {
Chris@16:    typedef typename container_detail::bi::make_set_base_hook
Chris@16:       < container_detail::bi::void_pointer<VoidPointer>
Chris@16:       , container_detail::bi::link_mode<container_detail::bi::normal_link>
Chris@101:       , container_detail::bi::optimize_size<OptimizeSize>
Chris@101:       >::type  type;
Chris@101: };
Chris@101: 
Chris@101: template<class VoidPointer, bool OptimizeSize>
Chris@101: struct intrusive_tree_hook<VoidPointer, boost::container::avl_tree, OptimizeSize>
Chris@101: {
Chris@101:    typedef typename container_detail::bi::make_avl_set_base_hook
Chris@101:       < container_detail::bi::void_pointer<VoidPointer>
Chris@101:       , container_detail::bi::link_mode<container_detail::bi::normal_link>
Chris@101:       , container_detail::bi::optimize_size<OptimizeSize>
Chris@101:       >::type  type;
Chris@101: };
Chris@101: 
Chris@101: template<class VoidPointer, bool OptimizeSize>
Chris@101: struct intrusive_tree_hook<VoidPointer, boost::container::scapegoat_tree, OptimizeSize>
Chris@101: {
Chris@101:    typedef typename container_detail::bi::make_bs_set_base_hook
Chris@101:       < container_detail::bi::void_pointer<VoidPointer>
Chris@101:       , container_detail::bi::link_mode<container_detail::bi::normal_link>
Chris@101:       >::type  type;
Chris@101: };
Chris@101: 
Chris@101: template<class VoidPointer, bool OptimizeSize>
Chris@101: struct intrusive_tree_hook<VoidPointer, boost::container::splay_tree, OptimizeSize>
Chris@101: {
Chris@101:    typedef typename container_detail::bi::make_bs_set_base_hook
Chris@101:       < container_detail::bi::void_pointer<VoidPointer>
Chris@101:       , container_detail::bi::link_mode<container_detail::bi::normal_link>
Chris@16:       >::type  type;
Chris@16: };
Chris@16: 
Chris@16: //This trait is used to type-pun std::pair because in C++03
Chris@16: //compilers std::pair is useless for C++11 features
Chris@16: template<class T>
Chris@101: struct tree_internal_data_type
Chris@16: {
Chris@16:    typedef T type;
Chris@16: };
Chris@16: 
Chris@16: template<class T1, class T2>
Chris@101: struct tree_internal_data_type< std::pair<T1, T2> >
Chris@16: {
Chris@16:    typedef pair<T1, T2> type;
Chris@16: };
Chris@16: 
Chris@16: //The node to be store in the tree
Chris@101: template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
Chris@101: struct tree_node
Chris@101:    :  public intrusive_tree_hook<VoidPointer, tree_type_value, OptimizeSize>::type
Chris@16: {
Chris@16:    private:
Chris@101:    //BOOST_COPYABLE_AND_MOVABLE(tree_node)
Chris@101:    tree_node();
Chris@16: 
Chris@16:    public:
Chris@101:    typedef typename intrusive_tree_hook
Chris@101:       <VoidPointer, tree_type_value, OptimizeSize>::type hook_type;
Chris@101:    typedef T value_type;
Chris@101:    typedef typename tree_internal_data_type<T>::type     internal_type;
Chris@16: 
Chris@101:    typedef tree_node< T, VoidPointer
Chris@101:                     , tree_type_value, OptimizeSize>     node_type;
Chris@16: 
Chris@16:    T &get_data()
Chris@16:    {
Chris@16:       T* ptr = reinterpret_cast<T*>(&this->m_data);
Chris@16:       return *ptr;
Chris@16:    }
Chris@16: 
Chris@16:    const T &get_data() const
Chris@16:    {
Chris@16:       const T* ptr = reinterpret_cast<const T*>(&this->m_data);
Chris@16:       return *ptr;
Chris@16:    }
Chris@16: 
Chris@16:    internal_type m_data;
Chris@16: 
Chris@101:    template<class T1, class T2>
Chris@101:    void do_assign(const std::pair<const T1, T2> &p)
Chris@16:    {
Chris@101:       const_cast<T1&>(m_data.first) = p.first;
Chris@16:       m_data.second  = p.second;
Chris@16:    }
Chris@16: 
Chris@101:    template<class T1, class T2>
Chris@101:    void do_assign(const pair<const T1, T2> &p)
Chris@16:    {
Chris@101:       const_cast<T1&>(m_data.first) = p.first;
Chris@16:       m_data.second  = p.second;
Chris@16:    }
Chris@16: 
Chris@16:    template<class V>
Chris@16:    void do_assign(const V &v)
Chris@16:    {  m_data = v; }
Chris@16: 
Chris@101:    template<class T1, class T2>
Chris@101:    void do_move_assign(std::pair<const T1, T2> &p)
Chris@16:    {
Chris@101:       const_cast<T1&>(m_data.first) = ::boost::move(p.first);
Chris@16:       m_data.second = ::boost::move(p.second);
Chris@16:    }
Chris@16: 
Chris@101:    template<class T1, class T2>
Chris@101:    void do_move_assign(pair<const T1, T2> &p)
Chris@16:    {
Chris@101:       const_cast<T1&>(m_data.first) = ::boost::move(p.first);
Chris@16:       m_data.second  = ::boost::move(p.second);
Chris@16:    }
Chris@16: 
Chris@16:    template<class V>
Chris@16:    void do_move_assign(V &v)
Chris@16:    {  m_data = ::boost::move(v); }
Chris@16: };
Chris@16: 
Chris@101: template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
Chris@101: struct iiterator_node_value_type< tree_node<T, VoidPointer, tree_type_value, OptimizeSize> > {
Chris@101:   typedef T type;
Chris@101: };
Chris@101: 
Chris@16: template<class Node, class Icont>
Chris@16: class insert_equal_end_hint_functor
Chris@16: {
Chris@16:    Icont &icont_;
Chris@16: 
Chris@16:    public:
Chris@16:    insert_equal_end_hint_functor(Icont &icont)
Chris@16:       :  icont_(icont)
Chris@16:    {}
Chris@16: 
Chris@16:    void operator()(Node &n)
Chris@16:    {  this->icont_.insert_equal(this->icont_.cend(), n); }
Chris@16: };
Chris@16: 
Chris@16: template<class Node, class Icont>
Chris@16: class push_back_functor
Chris@16: {
Chris@16:    Icont &icont_;
Chris@16: 
Chris@16:    public:
Chris@16:    push_back_functor(Icont &icont)
Chris@16:       :  icont_(icont)
Chris@16:    {}
Chris@16: 
Chris@16:    void operator()(Node &n)
Chris@16:    {  this->icont_.push_back(n); }
Chris@16: };
Chris@16: 
Chris@16: }//namespace container_detail {
Chris@16: 
Chris@16: namespace container_detail {
Chris@16: 
Chris@101: template< class NodeType, class NodeCompareType
Chris@101:         , class SizeType,  class HookType
Chris@101:         , boost::container::tree_type_enum tree_type_value>
Chris@101: struct intrusive_tree_dispatch;
Chris@101: 
Chris@101: template<class NodeType, class NodeCompareType, class SizeType, class HookType>
Chris@101: struct intrusive_tree_dispatch
Chris@101:    <NodeType, NodeCompareType, SizeType, HookType, boost::container::red_black_tree>
Chris@16: {
Chris@101:    typedef typename container_detail::bi::make_rbtree
Chris@101:       <NodeType
Chris@101:       ,container_detail::bi::compare<NodeCompareType>
Chris@101:       ,container_detail::bi::base_hook<HookType>
Chris@101:       ,container_detail::bi::constant_time_size<true>
Chris@101:       ,container_detail::bi::size_type<SizeType>
Chris@101:       >::type  type;
Chris@101: };
Chris@101: 
Chris@101: template<class NodeType, class NodeCompareType, class SizeType, class HookType>
Chris@101: struct intrusive_tree_dispatch
Chris@101:    <NodeType, NodeCompareType, SizeType, HookType, boost::container::avl_tree>
Chris@101: {
Chris@101:    typedef typename container_detail::bi::make_avltree
Chris@101:       <NodeType
Chris@101:       ,container_detail::bi::compare<NodeCompareType>
Chris@101:       ,container_detail::bi::base_hook<HookType>
Chris@101:       ,container_detail::bi::constant_time_size<true>
Chris@101:       ,container_detail::bi::size_type<SizeType>
Chris@101:       >::type  type;
Chris@101: };
Chris@101: 
Chris@101: template<class NodeType, class NodeCompareType, class SizeType, class HookType>
Chris@101: struct intrusive_tree_dispatch
Chris@101:    <NodeType, NodeCompareType, SizeType, HookType, boost::container::scapegoat_tree>
Chris@101: {
Chris@101:    typedef typename container_detail::bi::make_sgtree
Chris@101:       <NodeType
Chris@101:       ,container_detail::bi::compare<NodeCompareType>
Chris@101:       ,container_detail::bi::base_hook<HookType>
Chris@101:       ,container_detail::bi::floating_point<true>
Chris@101:       ,container_detail::bi::size_type<SizeType>
Chris@101:       >::type  type;
Chris@101: };
Chris@101: 
Chris@101: template<class NodeType, class NodeCompareType, class SizeType, class HookType>
Chris@101: struct intrusive_tree_dispatch
Chris@101:    <NodeType, NodeCompareType, SizeType, HookType, boost::container::splay_tree>
Chris@101: {
Chris@101:    typedef typename container_detail::bi::make_splaytree
Chris@101:       <NodeType
Chris@101:       ,container_detail::bi::compare<NodeCompareType>
Chris@101:       ,container_detail::bi::base_hook<HookType>
Chris@101:       ,container_detail::bi::constant_time_size<true>
Chris@101:       ,container_detail::bi::size_type<SizeType>
Chris@101:       >::type  type;
Chris@101: };
Chris@101: 
Chris@101: template<class Allocator, class ValueCompare, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
Chris@101: struct intrusive_tree_type
Chris@101: {
Chris@101:    private:
Chris@16:    typedef typename boost::container::
Chris@101:       allocator_traits<Allocator>::value_type              value_type;
Chris@16:    typedef typename boost::container::
Chris@101:       allocator_traits<Allocator>::void_pointer            void_pointer;
Chris@16:    typedef typename boost::container::
Chris@101:       allocator_traits<Allocator>::size_type               size_type;
Chris@101:    typedef typename container_detail::tree_node
Chris@101:          < value_type, void_pointer
Chris@101:          , tree_type_value, OptimizeSize>          node_type;
Chris@101:    typedef value_to_node_compare
Chris@101:       <node_type, ValueCompare>                    node_compare_type;
Chris@101:    //Deducing the hook type from node_type (e.g. node_type::hook_type) would
Chris@101:    //provoke an early instantiation of node_type that could ruin recursive
Chris@101:    //tree definitions, so retype the complete type to avoid any problem.
Chris@101:    typedef typename intrusive_tree_hook
Chris@101:       <void_pointer, tree_type_value
Chris@101:       , OptimizeSize>::type                        hook_type;
Chris@101:    public:
Chris@101:    typedef typename intrusive_tree_dispatch
Chris@101:       < node_type, node_compare_type
Chris@101:       , size_type, hook_type
Chris@101:       , tree_type_value>::type                     type;
Chris@101: };
Chris@101: 
Chris@101: //Trait to detect manually rebalanceable tree types
Chris@101: template<boost::container::tree_type_enum tree_type_value>
Chris@101: struct is_manually_balanceable
Chris@101: {  static const bool value = true;  };
Chris@101: 
Chris@101: template<>  struct is_manually_balanceable<red_black_tree>
Chris@101: {  static const bool value = false; };
Chris@101: 
Chris@101: template<>  struct is_manually_balanceable<avl_tree>
Chris@101: {  static const bool value = false; };
Chris@101: 
Chris@101: //Proxy traits to implement different operations depending on the
Chris@101: //is_manually_balanceable<>::value
Chris@101: template< boost::container::tree_type_enum tree_type_value
Chris@101:         , bool IsManuallyRebalanceable = is_manually_balanceable<tree_type_value>::value>
Chris@101: struct intrusive_tree_proxy
Chris@101: {
Chris@101:    template<class Icont>
Chris@101:    static void rebalance(Icont &)   {}
Chris@101: };
Chris@101: 
Chris@101: template<boost::container::tree_type_enum tree_type_value>
Chris@101: struct intrusive_tree_proxy<tree_type_value, true>
Chris@101: {
Chris@101:    template<class Icont>
Chris@101:    static void rebalance(Icont &c)
Chris@101:    {  c.rebalance(); }
Chris@16: };
Chris@16: 
Chris@16: }  //namespace container_detail {
Chris@16: 
Chris@16: namespace container_detail {
Chris@16: 
Chris@101: //This functor will be used with Intrusive clone functions to obtain
Chris@101: //already allocated nodes from a intrusive container instead of
Chris@101: //allocating new ones. When the intrusive container runs out of nodes
Chris@101: //the node holder is used instead.
Chris@101: template<class AllocHolder, bool DoMove>
Chris@101: class RecyclingCloner
Chris@101: {
Chris@101:    typedef typename AllocHolder::intrusive_container  intrusive_container;
Chris@101:    typedef typename AllocHolder::Node                 node_type;
Chris@101:    typedef typename AllocHolder::NodePtr              node_ptr_type;
Chris@101: 
Chris@101:    public:
Chris@101:    RecyclingCloner(AllocHolder &holder, intrusive_container &itree)
Chris@101:       :  m_holder(holder), m_icont(itree)
Chris@101:    {}
Chris@101: 
Chris@101:    static void do_assign(node_ptr_type &p, const node_type &other, bool_<true>)
Chris@101:    {  p->do_move_assign(const_cast<node_type &>(other).m_data);   }
Chris@101: 
Chris@101:    static void do_assign(node_ptr_type &p, const node_type &other, bool_<false>)
Chris@101:    {  p->do_assign(other.m_data);   }
Chris@101: 
Chris@101:    node_ptr_type operator()(const node_type &other) const
Chris@101:    {
Chris@101:       if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){
Chris@101:          //First recycle a node (this can't throw)
Chris@101:          BOOST_TRY{
Chris@101:             //This can throw
Chris@101:             this->do_assign(p, other, bool_<DoMove>());
Chris@101:             return p;
Chris@101:          }
Chris@101:          BOOST_CATCH(...){
Chris@101:             //If there is an exception destroy the whole source
Chris@101:             m_holder.destroy_node(p);
Chris@101:             while((p = m_icont.unlink_leftmost_without_rebalance())){
Chris@101:                m_holder.destroy_node(p);
Chris@101:             }
Chris@101:             BOOST_RETHROW
Chris@101:          }
Chris@101:          BOOST_CATCH_END
Chris@101:       }
Chris@101:       else{
Chris@101:          return m_holder.create_node(other.m_data);
Chris@101:       }
Chris@101:    }
Chris@101: 
Chris@101:    AllocHolder &m_holder;
Chris@101:    intrusive_container &m_icont;
Chris@101: };
Chris@101: 
Chris@101: template<class KeyValueCompare, class Node>
Chris@101: //where KeyValueCompare is tree_value_compare<Key, T, Compare, KeyOfValue>
Chris@101: struct key_node_compare
Chris@101:    :  private KeyValueCompare
Chris@101: {
Chris@101:    explicit key_node_compare(const KeyValueCompare &comp)
Chris@101:       :  KeyValueCompare(comp)
Chris@101:    {}
Chris@101: 
Chris@101:    template<class T>
Chris@101:    struct is_node
Chris@101:    {
Chris@101:       static const bool value = is_same<T, Node>::value;
Chris@101:    };
Chris@101: 
Chris@101:    template<class T>
Chris@101:    typename enable_if_c<is_node<T>::value, const typename KeyValueCompare::value_type &>::type
Chris@101:       key_forward(const T &node) const
Chris@101:    {  return node.get_data();  }
Chris@101: 
Chris@101:    template<class T>
Chris@101:    typename enable_if_c<!is_node<T>::value, const T &>::type
Chris@101:       key_forward(const T &key) const
Chris@101:    {  return key; }
Chris@101: 
Chris@101:    template<class KeyType, class KeyType2>
Chris@101:    bool operator()(const KeyType &key1, const KeyType2 &key2) const
Chris@101:    {  return KeyValueCompare::operator()(this->key_forward(key1), this->key_forward(key2));  }
Chris@101: };
Chris@101: 
Chris@101: template <class Key, class T, class KeyOfValue,
Chris@101:           class Compare, class Allocator,
Chris@101:           class Options = tree_assoc_defaults>
Chris@101: class tree
Chris@16:    : protected container_detail::node_alloc_holder
Chris@101:       < Allocator
Chris@101:       , typename container_detail::intrusive_tree_type
Chris@101:          < Allocator, tree_value_compare<Key, T, Compare, KeyOfValue> //ValComp
Chris@101:          , Options::tree_type, Options::optimize_size>::type
Chris@16:       >
Chris@16: {
Chris@16:    typedef tree_value_compare
Chris@101:             <Key, T, Compare, KeyOfValue>                   ValComp;
Chris@101:    typedef typename container_detail::intrusive_tree_type
Chris@101:          < Allocator, ValComp, Options::tree_type
Chris@101:          , Options::optimize_size>::type                    Icont;
Chris@101:    typedef container_detail::node_alloc_holder
Chris@101:       <Allocator, Icont>                                    AllocHolder;
Chris@16:    typedef typename AllocHolder::NodePtr                    NodePtr;
Chris@101:    typedef tree < Key, T, KeyOfValue
Chris@101:                 , Compare, Allocator, Options>              ThisType;
Chris@16:    typedef typename AllocHolder::NodeAlloc                  NodeAlloc;
Chris@101:    typedef boost::container::
Chris@101:       allocator_traits<NodeAlloc>                           allocator_traits_type;
Chris@16:    typedef typename AllocHolder::ValAlloc                   ValAlloc;
Chris@16:    typedef typename AllocHolder::Node                       Node;
Chris@16:    typedef typename Icont::iterator                         iiterator;
Chris@16:    typedef typename Icont::const_iterator                   iconst_iterator;
Chris@16:    typedef container_detail::allocator_destroyer<NodeAlloc> Destroyer;
Chris@16:    typedef typename AllocHolder::alloc_version              alloc_version;
Chris@101:    typedef intrusive_tree_proxy<Options::tree_type>         intrusive_tree_proxy_t;
Chris@16: 
Chris@101:    BOOST_COPYABLE_AND_MOVABLE(tree)
Chris@16: 
Chris@16:    public:
Chris@16: 
Chris@16:    typedef Key                                        key_type;
Chris@101:    typedef T                                          value_type;
Chris@101:    typedef Allocator                                  allocator_type;
Chris@101:    typedef Compare                                    key_compare;
Chris@16:    typedef ValComp                                    value_compare;
Chris@16:    typedef typename boost::container::
Chris@101:       allocator_traits<Allocator>::pointer            pointer;
Chris@16:    typedef typename boost::container::
Chris@101:       allocator_traits<Allocator>::const_pointer      const_pointer;
Chris@16:    typedef typename boost::container::
Chris@101:       allocator_traits<Allocator>::reference          reference;
Chris@16:    typedef typename boost::container::
Chris@101:       allocator_traits<Allocator>::const_reference    const_reference;
Chris@16:    typedef typename boost::container::
Chris@101:       allocator_traits<Allocator>::size_type          size_type;
Chris@16:    typedef typename boost::container::
Chris@101:       allocator_traits<Allocator>::difference_type    difference_type;
Chris@101:    typedef difference_type                            tree_difference_type;
Chris@101:    typedef pointer                                    tree_pointer;
Chris@101:    typedef const_pointer                              tree_const_pointer;
Chris@101:    typedef reference                                  tree_reference;
Chris@101:    typedef const_reference                            tree_const_reference;
Chris@16:    typedef NodeAlloc                                  stored_allocator_type;
Chris@16: 
Chris@16:    private:
Chris@16: 
Chris@101:    typedef key_node_compare<value_compare, Node>  KeyNodeCompare;
Chris@16: 
Chris@16:    public:
Chris@101:    typedef container_detail::iterator_from_iiterator<iiterator, false>  iterator;
Chris@101:    typedef container_detail::iterator_from_iiterator<iiterator, true >  const_iterator;
Chris@101:    typedef boost::container::reverse_iterator<iterator>                 reverse_iterator;
Chris@101:    typedef boost::container::reverse_iterator<const_iterator>           const_reverse_iterator;
Chris@16: 
Chris@101:    tree()
Chris@101:       : AllocHolder()
Chris@16:    {}
Chris@16: 
Chris@101:    explicit tree(const key_compare& comp, const allocator_type& a = allocator_type())
Chris@101:       : AllocHolder(ValComp(comp), a)
Chris@16:    {}
Chris@16: 
Chris@101:    explicit tree(const allocator_type& a)
Chris@16:       : AllocHolder(a)
Chris@16:    {}
Chris@16: 
Chris@16:    template <class InputIterator>
Chris@101:    tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp,
Chris@16:           const allocator_type& a
Chris@16:       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
Chris@16:       , typename container_detail::enable_if_c
Chris@16:          < container_detail::is_input_iterator<InputIterator>::value
Chris@101:             || container_detail::is_same<alloc_version, version_1>::value
Chris@16:          >::type * = 0
Chris@16:       #endif
Chris@16:          )
Chris@101:       : AllocHolder(value_compare(comp), a)
Chris@16:    {
Chris@16:       //Use cend() as hint to achieve linear time for
Chris@16:       //ordered ranges as required by the standard
Chris@16:       //for the constructor
Chris@16:       const const_iterator end_it(this->cend());
Chris@16:       if(unique_insertion){
Chris@16:          for ( ; first != last; ++first){
Chris@16:             this->insert_unique(end_it, *first);
Chris@16:          }
Chris@16:       }
Chris@16:       else{
Chris@16:          for ( ; first != last; ++first){
Chris@16:             this->insert_equal(end_it, *first);
Chris@16:          }
Chris@16:       }
Chris@16:    }
Chris@16: 
Chris@16:    template <class InputIterator>
Chris@101:    tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp,
Chris@16:           const allocator_type& a
Chris@16:       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
Chris@16:       , typename container_detail::enable_if_c
Chris@16:          < !(container_detail::is_input_iterator<InputIterator>::value
Chris@101:             || container_detail::is_same<alloc_version, version_1>::value)
Chris@16:          >::type * = 0
Chris@16:       #endif
Chris@16:          )
Chris@101:       : AllocHolder(value_compare(comp), a)
Chris@16:    {
Chris@16:       if(unique_insertion){
Chris@16:          //Use cend() as hint to achieve linear time for
Chris@16:          //ordered ranges as required by the standard
Chris@16:          //for the constructor
Chris@16:          const const_iterator end_it(this->cend());
Chris@16:          for ( ; first != last; ++first){
Chris@16:             this->insert_unique(end_it, *first);
Chris@16:          }
Chris@16:       }
Chris@16:       else{
Chris@16:          //Optimized allocation and construction
Chris@16:          this->allocate_many_and_construct
Chris@101:             ( first, boost::container::iterator_distance(first, last)
Chris@16:             , insert_equal_end_hint_functor<Node, Icont>(this->icont()));
Chris@16:       }
Chris@16:    }
Chris@16: 
Chris@16:    template <class InputIterator>
Chris@101:    tree( ordered_range_t, InputIterator first, InputIterator last
Chris@16:          , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type()
Chris@16:          #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
Chris@16:          , typename container_detail::enable_if_c
Chris@16:             < container_detail::is_input_iterator<InputIterator>::value
Chris@101:                || container_detail::is_same<alloc_version, version_1>::value
Chris@16:             >::type * = 0
Chris@16:          #endif
Chris@16:          )
Chris@101:       : AllocHolder(value_compare(comp), a)
Chris@16:    {
Chris@16:       for ( ; first != last; ++first){
Chris@16:          this->push_back_impl(*first);
Chris@16:       }
Chris@16:    }
Chris@16: 
Chris@16:    template <class InputIterator>
Chris@101:    tree( ordered_range_t, InputIterator first, InputIterator last
Chris@16:          , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type()
Chris@16:          #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
Chris@16:          , typename container_detail::enable_if_c
Chris@16:             < !(container_detail::is_input_iterator<InputIterator>::value
Chris@101:                || container_detail::is_same<alloc_version, version_1>::value)
Chris@16:             >::type * = 0
Chris@16:          #endif
Chris@16:          )
Chris@101:       : AllocHolder(value_compare(comp), a)
Chris@16:    {
Chris@16:       //Optimized allocation and construction
Chris@16:       this->allocate_many_and_construct
Chris@101:          ( first, boost::container::iterator_distance(first, last)
Chris@16:          , container_detail::push_back_functor<Node, Icont>(this->icont()));
Chris@16:    }
Chris@16: 
Chris@101:    tree(const tree& x)
Chris@101:       :  AllocHolder(x.value_comp(), x)
Chris@16:    {
Chris@16:       this->icont().clone_from
Chris@16:          (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
Chris@16:    }
Chris@16: 
Chris@101:    tree(BOOST_RV_REF(tree) x)
Chris@101:       :  AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp())
Chris@16:    {}
Chris@16: 
Chris@101:    tree(const tree& x, const allocator_type &a)
Chris@101:       :  AllocHolder(x.value_comp(), a)
Chris@16:    {
Chris@16:       this->icont().clone_from
Chris@16:          (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
Chris@16:    }
Chris@16: 
Chris@101:    tree(BOOST_RV_REF(tree) x, const allocator_type &a)
Chris@101:       :  AllocHolder(x.value_comp(), a)
Chris@16:    {
Chris@16:       if(this->node_alloc() == x.node_alloc()){
Chris@16:          this->icont().swap(x.icont());
Chris@16:       }
Chris@16:       else{
Chris@16:          this->icont().clone_from
Chris@101:             (x.icont(), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc()));
Chris@16:       }
Chris@16:    }
Chris@16: 
Chris@101:    ~tree()
Chris@16:    {} //AllocHolder clears the tree
Chris@16: 
Chris@101:    tree& operator=(BOOST_COPY_ASSIGN_REF(tree) x)
Chris@16:    {
Chris@16:       if (&x != this){
Chris@16:          NodeAlloc &this_alloc     = this->get_stored_allocator();
Chris@16:          const NodeAlloc &x_alloc  = x.get_stored_allocator();
Chris@16:          container_detail::bool_<allocator_traits<NodeAlloc>::
Chris@16:             propagate_on_container_copy_assignment::value> flag;
Chris@16:          if(flag && this_alloc != x_alloc){
Chris@16:             this->clear();
Chris@16:          }
Chris@16:          this->AllocHolder::copy_assign_alloc(x);
Chris@16:          //Transfer all the nodes to a temporary tree
Chris@16:          //If anything goes wrong, all the nodes will be destroyed
Chris@16:          //automatically
Chris@16:          Icont other_tree(::boost::move(this->icont()));
Chris@16: 
Chris@16:          //Now recreate the source tree reusing nodes stored by other_tree
Chris@16:          this->icont().clone_from
Chris@16:             (x.icont()
Chris@101:             , RecyclingCloner<AllocHolder, false>(*this, other_tree)
Chris@16:             , Destroyer(this->node_alloc()));
Chris@16: 
Chris@16:          //If there are remaining nodes, destroy them
Chris@16:          NodePtr p;
Chris@16:          while((p = other_tree.unlink_leftmost_without_rebalance())){
Chris@16:             AllocHolder::destroy_node(p);
Chris@16:          }
Chris@16:       }
Chris@16:       return *this;
Chris@16:    }
Chris@16: 
Chris@101:    tree& operator=(BOOST_RV_REF(tree) x)
Chris@101:       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
Chris@101:                                  && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value )
Chris@16:    {
Chris@101:       BOOST_ASSERT(this != &x);
Chris@101:       NodeAlloc &this_alloc = this->node_alloc();
Chris@101:       NodeAlloc &x_alloc    = x.node_alloc();
Chris@101:       const bool propagate_alloc = allocator_traits<NodeAlloc>::
Chris@101:             propagate_on_container_move_assignment::value;
Chris@101:       const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
Chris@101:       //Resources can be transferred if both allocators are
Chris@101:       //going to be equal after this function (either propagated or already equal)
Chris@101:       if(propagate_alloc || allocators_equal){
Chris@101:          //Destroy
Chris@101:          this->clear();
Chris@101:          //Move allocator if needed
Chris@101:          this->AllocHolder::move_assign_alloc(x);
Chris@101:          //Obtain resources
Chris@101:          this->icont() = boost::move(x.icont());
Chris@101:       }
Chris@101:       //Else do a one by one move
Chris@101:       else{
Chris@101:          //Transfer all the nodes to a temporary tree
Chris@101:          //If anything goes wrong, all the nodes will be destroyed
Chris@101:          //automatically
Chris@101:          Icont other_tree(::boost::move(this->icont()));
Chris@16: 
Chris@101:          //Now recreate the source tree reusing nodes stored by other_tree
Chris@101:          this->icont().clone_from
Chris@101:             (x.icont()
Chris@101:             , RecyclingCloner<AllocHolder, true>(*this, other_tree)
Chris@101:             , Destroyer(this->node_alloc()));
Chris@16: 
Chris@101:          //If there are remaining nodes, destroy them
Chris@101:          NodePtr p;
Chris@101:          while((p = other_tree.unlink_leftmost_without_rebalance())){
Chris@101:             AllocHolder::destroy_node(p);
Chris@16:          }
Chris@16:       }
Chris@16:       return *this;
Chris@16:    }
Chris@16: 
Chris@101:    public:
Chris@16:    // accessors:
Chris@16:    value_compare value_comp() const
Chris@101:    {  return this->icont().value_comp().predicate(); }
Chris@16: 
Chris@16:    key_compare key_comp() const
Chris@101:    {  return this->icont().value_comp().predicate().key_comp(); }
Chris@16: 
Chris@16:    allocator_type get_allocator() const
Chris@16:    {  return allocator_type(this->node_alloc()); }
Chris@16: 
Chris@16:    const stored_allocator_type &get_stored_allocator() const
Chris@16:    {  return this->node_alloc(); }
Chris@16: 
Chris@16:    stored_allocator_type &get_stored_allocator()
Chris@16:    {  return this->node_alloc(); }
Chris@16: 
Chris@16:    iterator begin()
Chris@16:    { return iterator(this->icont().begin()); }
Chris@16: 
Chris@16:    const_iterator begin() const
Chris@16:    {  return this->cbegin();  }
Chris@16: 
Chris@16:    iterator end()
Chris@16:    {  return iterator(this->icont().end());  }
Chris@16: 
Chris@16:    const_iterator end() const
Chris@16:    {  return this->cend();  }
Chris@16: 
Chris@16:    reverse_iterator rbegin()
Chris@16:    {  return reverse_iterator(end());  }
Chris@16: 
Chris@16:    const_reverse_iterator rbegin() const
Chris@16:    {  return this->crbegin();  }
Chris@16: 
Chris@16:    reverse_iterator rend()
Chris@16:    {  return reverse_iterator(begin());   }
Chris@16: 
Chris@16:    const_reverse_iterator rend() const
Chris@16:    {  return this->crend();   }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_iterator cbegin() const
Chris@16:    { return const_iterator(this->non_const_icont().begin()); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_iterator cend() const
Chris@16:    { return const_iterator(this->non_const_icont().end()); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_reverse_iterator crbegin() const
Chris@16:    { return const_reverse_iterator(cend()); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_reverse_iterator crend() const
Chris@16:    { return const_reverse_iterator(cbegin()); }
Chris@16: 
Chris@16:    bool empty() const
Chris@16:    {  return !this->size();  }
Chris@16: 
Chris@16:    size_type size() const
Chris@16:    {  return this->icont().size();   }
Chris@16: 
Chris@16:    size_type max_size() const
Chris@16:    {  return AllocHolder::max_size();  }
Chris@16: 
Chris@16:    void swap(ThisType& x)
Chris@101:       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
Chris@101:                                  && boost::container::container_detail::is_nothrow_swappable<Compare>::value )
Chris@16:    {  AllocHolder::swap(x);   }
Chris@16: 
Chris@16:    public:
Chris@16: 
Chris@16:    typedef typename Icont::insert_commit_data insert_commit_data;
Chris@16: 
Chris@16:    // insert/erase
Chris@16:    std::pair<iterator,bool> insert_unique_check
Chris@16:       (const key_type& key, insert_commit_data &data)
Chris@16:    {
Chris@16:       std::pair<iiterator, bool> ret =
Chris@16:          this->icont().insert_unique_check(key, KeyNodeCompare(value_comp()), data);
Chris@16:       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
Chris@16:    }
Chris@16: 
Chris@16:    std::pair<iterator,bool> insert_unique_check
Chris@16:       (const_iterator hint, const key_type& key, insert_commit_data &data)
Chris@16:    {
Chris@16:       std::pair<iiterator, bool> ret =
Chris@16:          this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(value_comp()), data);
Chris@16:       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
Chris@16:    }
Chris@16: 
Chris@16:    iterator insert_unique_commit(const value_type& v, insert_commit_data &data)
Chris@16:    {
Chris@16:       NodePtr tmp = AllocHolder::create_node(v);
Chris@16:       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
Chris@16:       iterator ret(this->icont().insert_unique_commit(*tmp, data));
Chris@16:       destroy_deallocator.release();
Chris@16:       return ret;
Chris@16:    }
Chris@16: 
Chris@16:    template<class MovableConvertible>
Chris@16:    iterator insert_unique_commit
Chris@101:       (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data)
Chris@16:    {
Chris@101:       NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v));
Chris@16:       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
Chris@16:       iterator ret(this->icont().insert_unique_commit(*tmp, data));
Chris@16:       destroy_deallocator.release();
Chris@16:       return ret;
Chris@16:    }
Chris@16: 
Chris@16:    std::pair<iterator,bool> insert_unique(const value_type& v)
Chris@16:    {
Chris@16:       insert_commit_data data;
Chris@16:       std::pair<iterator,bool> ret =
Chris@16:          this->insert_unique_check(KeyOfValue()(v), data);
Chris@16:       if(ret.second){
Chris@16:          ret.first = this->insert_unique_commit(v, data);
Chris@16:       }
Chris@16:       return ret;
Chris@16:    }
Chris@16: 
Chris@16:    template<class MovableConvertible>
Chris@101:    std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) v)
Chris@16:    {
Chris@16:       insert_commit_data data;
Chris@16:       std::pair<iterator,bool> ret =
Chris@101:          this->insert_unique_check(KeyOfValue()(v), data);
Chris@16:       if(ret.second){
Chris@101:          ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
Chris@16:       }
Chris@16:       return ret;
Chris@16:    }
Chris@16: 
Chris@16:    private:
Chris@16: 
Chris@16:    template<class MovableConvertible>
Chris@101:    void push_back_impl(BOOST_FWD_REF(MovableConvertible) v)
Chris@16:    {
Chris@101:       NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
Chris@16:       //push_back has no-throw guarantee so avoid any deallocator/destroyer
Chris@16:       this->icont().push_back(*tmp);
Chris@16:    }
Chris@16: 
Chris@16:    std::pair<iterator, bool> emplace_unique_impl(NodePtr p)
Chris@16:    {
Chris@16:       value_type &v = p->get_data();
Chris@16:       insert_commit_data data;
Chris@16:       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc());
Chris@16:       std::pair<iterator,bool> ret =
Chris@16:          this->insert_unique_check(KeyOfValue()(v), data);
Chris@16:       if(!ret.second){
Chris@16:          return ret;
Chris@16:       }
Chris@16:       //No throw insertion part, release rollback
Chris@16:       destroy_deallocator.release();
Chris@16:       return std::pair<iterator,bool>
Chris@16:          ( iterator(iiterator(this->icont().insert_unique_commit(*p, data)))
Chris@16:          , true );
Chris@16:    }
Chris@16: 
Chris@16:    iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p)
Chris@16:    {
Chris@16:       value_type &v = p->get_data();
Chris@16:       insert_commit_data data;
Chris@16:       std::pair<iterator,bool> ret =
Chris@16:          this->insert_unique_check(hint, KeyOfValue()(v), data);
Chris@16:       if(!ret.second){
Chris@16:          Destroyer(this->node_alloc())(p);
Chris@16:          return ret.first;
Chris@16:       }
Chris@16:       return iterator(iiterator(this->icont().insert_unique_commit(*p, data)));
Chris@16:    }
Chris@16: 
Chris@16:    public:
Chris@16: 
Chris@101:    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16: 
Chris@16:    template <class... Args>
Chris@101:    std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args)
Chris@16:    {  return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...));   }
Chris@16: 
Chris@16:    template <class... Args>
Chris@101:    iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args)
Chris@16:    {  return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...));   }
Chris@16: 
Chris@16:    template <class... Args>
Chris@101:    iterator emplace_equal(BOOST_FWD_REF(Args)... args)
Chris@16:    {
Chris@16:       NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
Chris@16:       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
Chris@16:       iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
Chris@16:       destroy_deallocator.release();
Chris@16:       return ret;
Chris@16:    }
Chris@16: 
Chris@16:    template <class... Args>
Chris@101:    iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args)
Chris@16:    {
Chris@16:       NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
Chris@16:       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
Chris@16:       iterator ret(this->icont().insert_equal(hint.get(), *tmp));
Chris@16:       destroy_deallocator.release();
Chris@16:       return ret;
Chris@16:    }
Chris@16: 
Chris@101:    #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16: 
Chris@101:    #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \
Chris@101:    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
Chris@101:    std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\
Chris@101:    {  return this->emplace_unique_impl(AllocHolder::create_node(BOOST_MOVE_FWD##N));  }\
Chris@101:    \
Chris@101:    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
Chris@101:    iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
Chris@101:    {  return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\
Chris@101:    \
Chris@101:    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
Chris@101:    iterator emplace_equal(BOOST_MOVE_UREF##N)\
Chris@101:    {\
Chris@101:       NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
Chris@101:       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
Chris@101:       iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\
Chris@101:       destroy_deallocator.release();\
Chris@101:       return ret;\
Chris@101:    }\
Chris@101:    \
Chris@101:    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
Chris@101:    iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
Chris@101:    {\
Chris@101:       NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
Chris@101:       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
Chris@101:       iterator ret(this->icont().insert_equal(hint.get(), *tmp));\
Chris@101:       destroy_deallocator.release();\
Chris@101:       return ret;\
Chris@101:    }\
Chris@101:    //
Chris@101:    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE)
Chris@101:    #undef BOOST_CONTAINER_TREE_EMPLACE_CODE
Chris@16: 
Chris@101:    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16: 
Chris@16:    iterator insert_unique(const_iterator hint, const value_type& v)
Chris@16:    {
Chris@16:       insert_commit_data data;
Chris@16:       std::pair<iterator,bool> ret =
Chris@16:          this->insert_unique_check(hint, KeyOfValue()(v), data);
Chris@16:       if(!ret.second)
Chris@16:          return ret.first;
Chris@16:       return this->insert_unique_commit(v, data);
Chris@16:    }
Chris@16: 
Chris@16:    template<class MovableConvertible>
Chris@101:    iterator insert_unique(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
Chris@16:    {
Chris@16:       insert_commit_data data;
Chris@16:       std::pair<iterator,bool> ret =
Chris@101:          this->insert_unique_check(hint, KeyOfValue()(v), data);
Chris@16:       if(!ret.second)
Chris@16:          return ret.first;
Chris@101:       return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
Chris@16:    }
Chris@16: 
Chris@16:    template <class InputIterator>
Chris@16:    void insert_unique(InputIterator first, InputIterator last)
Chris@16:    {
Chris@16:       for( ; first != last; ++first)
Chris@16:          this->insert_unique(*first);
Chris@16:    }
Chris@16: 
Chris@16:    iterator insert_equal(const value_type& v)
Chris@16:    {
Chris@16:       NodePtr tmp(AllocHolder::create_node(v));
Chris@16:       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
Chris@16:       iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
Chris@16:       destroy_deallocator.release();
Chris@16:       return ret;
Chris@16:    }
Chris@16: 
Chris@16:    template<class MovableConvertible>
Chris@101:    iterator insert_equal(BOOST_FWD_REF(MovableConvertible) v)
Chris@16:    {
Chris@101:       NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
Chris@16:       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
Chris@16:       iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
Chris@16:       destroy_deallocator.release();
Chris@16:       return ret;
Chris@16:    }
Chris@16: 
Chris@16:    iterator insert_equal(const_iterator hint, const value_type& v)
Chris@16:    {
Chris@16:       NodePtr tmp(AllocHolder::create_node(v));
Chris@16:       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
Chris@16:       iterator ret(this->icont().insert_equal(hint.get(), *tmp));
Chris@16:       destroy_deallocator.release();
Chris@16:       return ret;
Chris@16:    }
Chris@16: 
Chris@16:    template<class MovableConvertible>
Chris@101:    iterator insert_equal(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
Chris@16:    {
Chris@101:       NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
Chris@16:       scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
Chris@16:       iterator ret(this->icont().insert_equal(hint.get(), *tmp));
Chris@16:       destroy_deallocator.release();
Chris@16:       return ret;
Chris@16:    }
Chris@16: 
Chris@16:    template <class InputIterator>
Chris@16:    void insert_equal(InputIterator first, InputIterator last)
Chris@16:    {
Chris@16:       for( ; first != last; ++first)
Chris@16:          this->insert_equal(*first);
Chris@16:    }
Chris@16: 
Chris@16:    iterator erase(const_iterator position)
Chris@16:    {  return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); }
Chris@16: 
Chris@16:    size_type erase(const key_type& k)
Chris@16:    {  return AllocHolder::erase_key(k, KeyNodeCompare(value_comp()), alloc_version()); }
Chris@16: 
Chris@16:    iterator erase(const_iterator first, const_iterator last)
Chris@16:    {  return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); }
Chris@16: 
Chris@16:    void clear()
Chris@16:    {  AllocHolder::clear(alloc_version());  }
Chris@16: 
Chris@101:    // search operations. Const and non-const overloads even if no iterator is returned
Chris@101:    // so splay implementations can to their rebalancing when searching in non-const versions
Chris@16:    iterator find(const key_type& k)
Chris@16:    {  return iterator(this->icont().find(k, KeyNodeCompare(value_comp())));  }
Chris@16: 
Chris@16:    const_iterator find(const key_type& k) const
Chris@16:    {  return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(value_comp())));  }
Chris@16: 
Chris@16:    size_type count(const key_type& k) const
Chris@16:    {  return size_type(this->icont().count(k, KeyNodeCompare(value_comp()))); }
Chris@16: 
Chris@16:    iterator lower_bound(const key_type& k)
Chris@16:    {  return iterator(this->icont().lower_bound(k, KeyNodeCompare(value_comp())));  }
Chris@16: 
Chris@16:    const_iterator lower_bound(const key_type& k) const
Chris@16:    {  return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(value_comp())));  }
Chris@16: 
Chris@16:    iterator upper_bound(const key_type& k)
Chris@16:    {  return iterator(this->icont().upper_bound(k, KeyNodeCompare(value_comp())));   }
Chris@16: 
Chris@16:    const_iterator upper_bound(const key_type& k) const
Chris@16:    {  return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(value_comp())));  }
Chris@16: 
Chris@16:    std::pair<iterator,iterator> equal_range(const key_type& k)
Chris@16:    {
Chris@16:       std::pair<iiterator, iiterator> ret =
Chris@16:          this->icont().equal_range(k, KeyNodeCompare(value_comp()));
Chris@16:       return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
Chris@16:    }
Chris@16: 
Chris@16:    std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
Chris@16:    {
Chris@16:       std::pair<iiterator, iiterator> ret =
Chris@16:          this->non_const_icont().equal_range(k, KeyNodeCompare(value_comp()));
Chris@16:       return std::pair<const_iterator,const_iterator>
Chris@16:          (const_iterator(ret.first), const_iterator(ret.second));
Chris@16:    }
Chris@101: 
Chris@101:    std::pair<iterator,iterator> lower_bound_range(const key_type& k)
Chris@101:    {
Chris@101:       std::pair<iiterator, iiterator> ret =
Chris@101:          this->icont().lower_bound_range(k, KeyNodeCompare(value_comp()));
Chris@101:       return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
Chris@101:    }
Chris@101: 
Chris@101:    std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
Chris@101:    {
Chris@101:       std::pair<iiterator, iiterator> ret =
Chris@101:          this->non_const_icont().lower_bound_range(k, KeyNodeCompare(value_comp()));
Chris@101:       return std::pair<const_iterator,const_iterator>
Chris@101:          (const_iterator(ret.first), const_iterator(ret.second));
Chris@101:    }
Chris@101: 
Chris@101:    void rebalance()
Chris@101:    {  intrusive_tree_proxy_t::rebalance(this->icont());   }
Chris@101: 
Chris@101:    friend bool operator==(const tree& x, const tree& y)
Chris@101:    {  return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());  }
Chris@101: 
Chris@101:    friend bool operator<(const tree& x, const tree& y)
Chris@101:    {  return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());  }
Chris@101: 
Chris@101:    friend bool operator!=(const tree& x, const tree& y)
Chris@101:    {  return !(x == y);  }
Chris@101: 
Chris@101:    friend bool operator>(const tree& x, const tree& y)
Chris@101:    {  return y < x;  }
Chris@101: 
Chris@101:    friend bool operator<=(const tree& x, const tree& y)
Chris@101:    {  return !(y < x);  }
Chris@101: 
Chris@101:    friend bool operator>=(const tree& x, const tree& y)
Chris@101:    {  return !(x < y);  }
Chris@101: 
Chris@101:    friend void swap(tree& x, tree& y)
Chris@101:    {  x.swap(y);  }
Chris@16: };
Chris@16: 
Chris@16: } //namespace container_detail {
Chris@16: } //namespace container {
Chris@101: 
Chris@101: template <class T>
Chris@101: struct has_trivial_destructor_after_move;
Chris@101: 
Chris@16: //!has_trivial_destructor_after_move<> == true_type
Chris@16: //!specialization for optimizations
Chris@101: template <class Key, class T, class KeyOfValue, class Compare, class Allocator, class Options>
Chris@16: struct has_trivial_destructor_after_move
Chris@101:    < 
Chris@101:       ::boost::container::container_detail::tree
Chris@101:          <Key, T, KeyOfValue, Compare, Allocator, Options>
Chris@101:    >
Chris@16: {
Chris@101:    typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
Chris@101:    static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
Chris@101:                              ::boost::has_trivial_destructor_after_move<pointer>::value &&
Chris@101:                              ::boost::has_trivial_destructor_after_move<Compare>::value;
Chris@16: };
Chris@101: 
Chris@16: } //namespace boost  {
Chris@16: 
Chris@16: #include <boost/container/detail/config_end.hpp>
Chris@16: 
Chris@16: #endif //BOOST_CONTAINER_TREE_HPP