vamp-build-and-test: DEPENDENCIES/generic/include/boost/container/detail/tree.hpp comparison

comparison DEPENDENCIES/generic/include/boost/container/detail/tree.hpp @ 101:c530137014c0

Update Boost headers (1.58.0)

author	Chris Cannam
date	Mon, 07 Sep 2015 11:12:49 +0100
parents	2665513ce2d3
children

comparison

equal deleted inserted replaced

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

Mercurial > hg > vamp-build-and-test

comparison DEPENDENCIES/generic/include/boost/container/detail/tree.hpp @ 101:c530137014c0