Squashed 'third_party/boostorg/container/' content from commit 1ad6431
Change-Id: I7d095db3455264c03446268e5675b926bebedb0a
git-subtree-dir: third_party/boostorg/container
git-subtree-split: 1ad64316a432a7f021b4956acf88abc6aaa8a77e
diff --git a/include/boost/container/detail/tree.hpp b/include/boost/container/detail/tree.hpp
new file mode 100644
index 0000000..c32e992
--- /dev/null
+++ b/include/boost/container/detail/tree.hpp
@@ -0,0 +1,1458 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2015. 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
+
+#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/container/node_handle.hpp>
+
+// container/detail
+#include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
+#include <boost/container/detail/compare_functors.hpp>
+#include <boost/container/detail/destroyers.hpp>
+#include <boost/container/detail/iterator.hpp>
+#include <boost/container/detail/iterators.hpp>
+#include <boost/container/detail/node_alloc_holder.hpp>
+#include <boost/container/detail/pair.hpp>
+#include <boost/container/detail/type_traits.hpp>
+// intrusive
+#include <boost/intrusive/pointer_traits.hpp>
+#include <boost/intrusive/rbtree.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
+#include <boost/intrusive/detail/tree_value_compare.hpp> //tree_value_compare
+// move
+#include <boost/move/utility_core.hpp>
+// move/detail
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+#include <boost/move/detail/fwd_macros.hpp>
+#endif
+#include <boost/move/detail/move_helpers.hpp>
+// other
+#include <boost/core/no_exceptions_support.hpp>
+
+
+
+#include <boost/container/detail/std_fwd.hpp>
+
+namespace boost {
+namespace container {
+namespace dtl {
+
+using boost::intrusive::tree_value_compare;
+
+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 dtl::bi::make_set_base_hook
+ < dtl::bi::void_pointer<VoidPointer>
+ , dtl::bi::link_mode<dtl::bi::normal_link>
+ , dtl::bi::optimize_size<OptimizeSize>
+ >::type type;
+};
+
+template<class VoidPointer, bool OptimizeSize>
+struct intrusive_tree_hook<VoidPointer, boost::container::avl_tree, OptimizeSize>
+{
+ typedef typename dtl::bi::make_avl_set_base_hook
+ < dtl::bi::void_pointer<VoidPointer>
+ , dtl::bi::link_mode<dtl::bi::normal_link>
+ , dtl::bi::optimize_size<OptimizeSize>
+ >::type type;
+};
+
+template<class VoidPointer, bool OptimizeSize>
+struct intrusive_tree_hook<VoidPointer, boost::container::scapegoat_tree, OptimizeSize>
+{
+ typedef typename dtl::bi::make_bs_set_base_hook
+ < dtl::bi::void_pointer<VoidPointer>
+ , dtl::bi::link_mode<dtl::bi::normal_link>
+ >::type type;
+};
+
+template<class VoidPointer, bool OptimizeSize>
+struct intrusive_tree_hook<VoidPointer, boost::container::splay_tree, OptimizeSize>
+{
+ typedef typename dtl::bi::make_bs_set_base_hook
+ < dtl::bi::void_pointer<VoidPointer>
+ , dtl::bi::link_mode<dtl::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 tree_internal_data_type
+{
+ typedef T type;
+};
+
+template<class T1, class T2>
+struct tree_internal_data_type< std::pair<T1, T2> >
+{
+ typedef pair<typename boost::move_detail::remove_const<T1>::type, T2> type;
+};
+
+//The node to be store in the tree
+template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
+struct tree_node
+ : public intrusive_tree_hook<VoidPointer, tree_type_value, OptimizeSize>::type
+{
+ private:
+ //BOOST_COPYABLE_AND_MOVABLE(tree_node)
+ tree_node();
+
+ public:
+ typedef typename intrusive_tree_hook
+ <VoidPointer, tree_type_value, OptimizeSize>::type hook_type;
+ typedef T value_type;
+ typedef typename tree_internal_data_type<T>::type internal_type;
+
+ typedef tree_node< T, VoidPointer
+ , tree_type_value, OptimizeSize> node_t;
+
+ BOOST_CONTAINER_FORCEINLINE T &get_data()
+ {
+ T* ptr = reinterpret_cast<T*>(&this->m_data);
+ return *ptr;
+ }
+
+ BOOST_CONTAINER_FORCEINLINE const T &get_data() const
+ {
+ const T* ptr = reinterpret_cast<const T*>(&this->m_data);
+ return *ptr;
+ }
+
+ internal_type m_data;
+
+ template<class T1, class T2>
+ BOOST_CONTAINER_FORCEINLINE void do_assign(const std::pair<const T1, T2> &p)
+ {
+ const_cast<T1&>(m_data.first) = p.first;
+ m_data.second = p.second;
+ }
+
+ template<class T1, class T2>
+ BOOST_CONTAINER_FORCEINLINE void do_assign(const pair<const T1, T2> &p)
+ {
+ const_cast<T1&>(m_data.first) = p.first;
+ m_data.second = p.second;
+ }
+
+ template<class V>
+ BOOST_CONTAINER_FORCEINLINE void do_assign(const V &v)
+ { m_data = v; }
+
+ template<class T1, class T2>
+ BOOST_CONTAINER_FORCEINLINE void do_move_assign(std::pair<const T1, T2> &p)
+ {
+ const_cast<T1&>(m_data.first) = ::boost::move(p.first);
+ m_data.second = ::boost::move(p.second);
+ }
+
+ template<class T1, class T2>
+ BOOST_CONTAINER_FORCEINLINE void do_move_assign(pair<const T1, T2> &p)
+ {
+ const_cast<T1&>(m_data.first) = ::boost::move(p.first);
+ m_data.second = ::boost::move(p.second);
+ }
+
+ template<class V>
+ BOOST_CONTAINER_FORCEINLINE 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
+{
+ Icont &icont_;
+
+ public:
+ BOOST_CONTAINER_FORCEINLINE insert_equal_end_hint_functor(Icont &icont)
+ : icont_(icont)
+ {}
+
+ BOOST_CONTAINER_FORCEINLINE void operator()(Node &n)
+ { this->icont_.insert_equal(this->icont_.cend(), n); }
+};
+
+template<class Node, class Icont>
+class push_back_functor
+{
+ Icont &icont_;
+
+ public:
+ BOOST_CONTAINER_FORCEINLINE push_back_functor(Icont &icont)
+ : icont_(icont)
+ {}
+
+ BOOST_CONTAINER_FORCEINLINE void operator()(Node &n)
+ { this->icont_.push_back(n); }
+};
+
+}//namespace dtl {
+
+namespace dtl {
+
+template< class NodeType, class NodeCompareType
+ , 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 dtl::bi::make_rbtree
+ <NodeType
+ ,dtl::bi::compare<NodeCompareType>
+ ,dtl::bi::base_hook<HookType>
+ ,dtl::bi::constant_time_size<true>
+ ,dtl::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 dtl::bi::make_avltree
+ <NodeType
+ ,dtl::bi::compare<NodeCompareType>
+ ,dtl::bi::base_hook<HookType>
+ ,dtl::bi::constant_time_size<true>
+ ,dtl::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 dtl::bi::make_sgtree
+ <NodeType
+ ,dtl::bi::compare<NodeCompareType>
+ ,dtl::bi::base_hook<HookType>
+ ,dtl::bi::floating_point<true>
+ ,dtl::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 dtl::bi::make_splaytree
+ <NodeType
+ ,dtl::bi::compare<NodeCompareType>
+ ,dtl::bi::base_hook<HookType>
+ ,dtl::bi::constant_time_size<true>
+ ,dtl::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<Allocator>::value_type value_type;
+ typedef typename boost::container::
+ allocator_traits<Allocator>::void_pointer void_pointer;
+ typedef typename boost::container::
+ allocator_traits<Allocator>::size_type size_type;
+ typedef typename dtl::tree_node
+ < value_type, void_pointer
+ , tree_type_value, OptimizeSize> node_t;
+ typedef value_to_node_compare
+ <node_t, ValueCompare> node_compare_type;
+ //Deducing the hook type from node_t (e.g. node_t::hook_type) would
+ //provoke an early instantiation of node_t that could ruin recursive
+ //tree definitions, so retype the complete type to avoid any problem.
+ typedef typename intrusive_tree_hook
+ <void_pointer, tree_type_value
+ , OptimizeSize>::type hook_type;
+ public:
+ typedef typename intrusive_tree_dispatch
+ < node_t, 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>
+ BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &) {}
+};
+
+template<boost::container::tree_type_enum tree_type_value>
+struct intrusive_tree_proxy<tree_type_value, true>
+{
+ template<class Icont>
+ BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &c)
+ { c.rebalance(); }
+};
+
+} //namespace dtl {
+
+namespace dtl {
+
+//This functor will be used with Intrusive clone functions to obtain
+//already allocated nodes from a intrusive container instead of
+//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_t;
+ typedef typename AllocHolder::NodePtr node_ptr_type;
+
+ public:
+ RecyclingCloner(AllocHolder &holder, intrusive_container &itree)
+ : m_holder(holder), m_icont(itree)
+ {}
+
+ BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<true>)
+ { p->do_move_assign(const_cast<node_t &>(other).m_data); }
+
+ BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<false>)
+ { p->do_assign(other.m_data); }
+
+ node_ptr_type operator()(const node_t &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 KeyCompare, class KeyOfValue>
+struct key_node_compare
+ : public boost::intrusive::detail::ebo_functor_holder<KeyCompare>
+{
+ BOOST_CONTAINER_FORCEINLINE explicit key_node_compare(const KeyCompare &comp)
+ : base_t(comp)
+ {}
+
+ typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t;
+ typedef KeyCompare key_compare;
+ typedef KeyOfValue key_of_value;
+ typedef typename KeyOfValue::type key_type;
+
+
+ template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
+ BOOST_CONTAINER_FORCEINLINE static const key_type &
+ key_from(const tree_node<T, VoidPointer, tree_type_value, OptimizeSize> &n)
+ {
+ return key_of_value()(n.get_data());
+ }
+
+ template <class T>
+ BOOST_CONTAINER_FORCEINLINE static const T &
+ key_from(const T &t)
+ {
+ return t;
+ }
+
+ BOOST_CONTAINER_FORCEINLINE const key_compare &key_comp() const
+ { return static_cast<const key_compare &>(*this); }
+
+ BOOST_CONTAINER_FORCEINLINE key_compare &key_comp()
+ { return static_cast<key_compare &>(*this); }
+
+ BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const
+ { return this->key_comp()(key1, key2); }
+
+ template<class U>
+ BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const U &nonkey2) const
+ { return this->key_comp()(key1, this->key_from(nonkey2)); }
+
+ template<class U>
+ BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2) const
+ { return this->key_comp()(this->key_from(nonkey1), key2); }
+
+ template<class U, class V>
+ BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const V &nonkey2) const
+ { return this->key_comp()(this->key_from(nonkey1), this->key_from(nonkey2)); }
+};
+
+template<class Options>
+struct get_tree_opt
+{
+ typedef Options type;
+};
+
+template<>
+struct get_tree_opt<void>
+{
+ typedef tree_assoc_defaults type;
+};
+
+template <class T, class KeyOfValue, class Compare, class Allocator, class Options>
+class tree
+ : public dtl::node_alloc_holder
+ < Allocator
+ , typename dtl::intrusive_tree_type
+ < Allocator, tree_value_compare
+ <typename allocator_traits<Allocator>::pointer, Compare, KeyOfValue>
+ , get_tree_opt<Options>::type::tree_type
+ , get_tree_opt<Options>::type::optimize_size
+ >::type
+ >
+{
+ typedef tree_value_compare
+ < typename allocator_traits<Allocator>::pointer
+ , Compare, KeyOfValue> ValComp;
+ typedef typename get_tree_opt<Options>::type options_type;
+ typedef typename dtl::intrusive_tree_type
+ < Allocator, ValComp
+ , options_type::tree_type
+ , options_type::optimize_size
+ >::type Icont;
+ typedef dtl::node_alloc_holder
+ <Allocator, Icont> AllocHolder;
+ typedef typename AllocHolder::NodePtr NodePtr;
+ typedef tree < T, KeyOfValue
+ , 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 dtl::allocator_destroyer<NodeAlloc> Destroyer;
+ typedef typename AllocHolder::alloc_version alloc_version;
+ typedef intrusive_tree_proxy<options_type::tree_type> intrusive_tree_proxy_t;
+
+ BOOST_COPYABLE_AND_MOVABLE(tree)
+
+ public:
+
+ typedef typename KeyOfValue::type key_type;
+ typedef T value_type;
+ typedef Allocator allocator_type;
+ typedef Compare key_compare;
+ typedef ValComp value_compare;
+ typedef typename boost::container::
+ allocator_traits<Allocator>::pointer pointer;
+ typedef typename boost::container::
+ allocator_traits<Allocator>::const_pointer const_pointer;
+ typedef typename boost::container::
+ allocator_traits<Allocator>::reference reference;
+ typedef typename boost::container::
+ allocator_traits<Allocator>::const_reference const_reference;
+ typedef typename boost::container::
+ allocator_traits<Allocator>::size_type size_type;
+ typedef typename boost::container::
+ allocator_traits<Allocator>::difference_type difference_type;
+ typedef dtl::iterator_from_iiterator
+ <iiterator, false> iterator;
+ typedef dtl::iterator_from_iiterator
+ <iiterator, true > const_iterator;
+ typedef boost::container::reverse_iterator
+ <iterator> reverse_iterator;
+ typedef boost::container::reverse_iterator
+ <const_iterator> const_reverse_iterator;
+ typedef node_handle
+ < NodeAlloc, void> node_type;
+ typedef insert_return_type_base
+ <iterator, node_type> insert_return_type;
+
+ typedef NodeAlloc stored_allocator_type;
+
+ private:
+
+ typedef key_node_compare<key_compare, KeyOfValue> KeyNodeCompare;
+
+ public:
+
+ BOOST_CONTAINER_FORCEINLINE tree()
+ : AllocHolder()
+ {}
+
+ BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp)
+ : AllocHolder(ValComp(comp))
+ {}
+
+ BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a)
+ : AllocHolder(ValComp(comp), a)
+ {}
+
+ BOOST_CONTAINER_FORCEINLINE explicit tree(const allocator_type& a)
+ : AllocHolder(a)
+ {}
+
+ template <class InputIterator>
+ tree(bool unique_insertion, InputIterator first, InputIterator last)
+ : AllocHolder(value_compare(key_compare()))
+ {
+ this->tree_construct(unique_insertion, first, last);
+ //AllocHolder clears in case of exception
+ }
+
+ template <class InputIterator>
+ tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp)
+ : AllocHolder(value_compare(comp))
+ {
+ this->tree_construct(unique_insertion, first, last);
+ //AllocHolder clears in case of exception
+ }
+
+ template <class InputIterator>
+ tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a)
+ : AllocHolder(value_compare(comp), a)
+ {
+ this->tree_construct(unique_insertion, first, last);
+ //AllocHolder clears in case of exception
+ }
+
+ //construct with ordered range
+ template <class InputIterator>
+ tree( ordered_range_t, InputIterator first, InputIterator last)
+ : AllocHolder(value_compare(key_compare()))
+ {
+ this->tree_construct(ordered_range_t(), first, last);
+ }
+
+ template <class InputIterator>
+ tree( ordered_range_t, InputIterator first, InputIterator last, const key_compare& comp)
+ : AllocHolder(value_compare(comp))
+ {
+ this->tree_construct(ordered_range_t(), first, last);
+ }
+
+ template <class InputIterator>
+ tree( ordered_range_t, InputIterator first, InputIterator last
+ , const key_compare& comp, const allocator_type& a)
+ : AllocHolder(value_compare(comp), a)
+ {
+ this->tree_construct(ordered_range_t(), first, last);
+ }
+
+ private:
+
+ template <class InputIterator>
+ void tree_construct(bool unique_insertion, InputIterator first, InputIterator last)
+ {
+ //Use cend() as hint to achieve linear time for
+ //ordered ranges as required by the standard
+ //for the constructor
+ if(unique_insertion){
+ const const_iterator end_it(this->cend());
+ for ( ; first != last; ++first){
+ this->insert_unique_convertible(end_it, *first);
+ }
+ }
+ else{
+ this->tree_construct_non_unique(first, last);
+ }
+ }
+
+ template <class InputIterator>
+ void tree_construct_non_unique(InputIterator first, InputIterator last
+ #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+ , typename dtl::enable_if_or
+ < void
+ , dtl::is_same<alloc_version, version_1>
+ , dtl::is_input_iterator<InputIterator>
+ >::type * = 0
+ #endif
+ )
+ {
+ //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());
+ for ( ; first != last; ++first){
+ this->insert_equal_convertible(end_it, *first);
+ }
+ }
+
+ template <class InputIterator>
+ void tree_construct_non_unique(InputIterator first, InputIterator last
+ #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+ , typename dtl::disable_if_or
+ < void
+ , dtl::is_same<alloc_version, version_1>
+ , dtl::is_input_iterator<InputIterator>
+ >::type * = 0
+ #endif
+ )
+ {
+ //Optimized allocation and construction
+ this->allocate_many_and_construct
+ ( first, boost::container::iterator_distance(first, last)
+ , insert_equal_end_hint_functor<Node, Icont>(this->icont()));
+ }
+
+ template <class InputIterator>
+ void tree_construct( ordered_range_t, InputIterator first, InputIterator last
+ #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+ , typename dtl::disable_if_or
+ < void
+ , dtl::is_same<alloc_version, version_1>
+ , dtl::is_input_iterator<InputIterator>
+ >::type * = 0
+ #endif
+ )
+ {
+ //Optimized allocation and construction
+ this->allocate_many_and_construct
+ ( first, boost::container::iterator_distance(first, last)
+ , dtl::push_back_functor<Node, Icont>(this->icont()));
+ //AllocHolder clears in case of exception
+ }
+
+ template <class InputIterator>
+ void tree_construct( ordered_range_t, InputIterator first, InputIterator last
+ #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+ , typename dtl::enable_if_or
+ < void
+ , dtl::is_same<alloc_version, version_1>
+ , dtl::is_input_iterator<InputIterator>
+ >::type * = 0
+ #endif
+ )
+ {
+ for ( ; first != last; ++first){
+ this->push_back_impl(*first);
+ }
+ }
+
+ public:
+
+ BOOST_CONTAINER_FORCEINLINE tree(const tree& x)
+ : AllocHolder(x, x.value_comp())
+ {
+ this->icont().clone_from
+ (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
+ }
+
+ BOOST_CONTAINER_FORCEINLINE tree(BOOST_RV_REF(tree) x)
+ BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
+ : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp())
+ {}
+
+ BOOST_CONTAINER_FORCEINLINE tree(const tree& x, const allocator_type &a)
+ : AllocHolder(x.value_comp(), a)
+ {
+ this->icont().clone_from
+ (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
+ //AllocHolder clears in case of exception
+ }
+
+ tree(BOOST_RV_REF(tree) x, const allocator_type &a)
+ : AllocHolder(x.value_comp(), a)
+ {
+ if(this->node_alloc() == x.node_alloc()){
+ this->icont().swap(x.icont());
+ }
+ else{
+ this->icont().clone_from
+ (boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc()));
+ }
+ //AllocHolder clears in case of exception
+ }
+
+ BOOST_CONTAINER_FORCEINLINE ~tree()
+ {} //AllocHolder clears the tree
+
+ 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();
+ dtl::bool_<allocator_traits<NodeAlloc>::
+ propagate_on_container_copy_assignment::value> flag;
+ if(flag && this_alloc != x_alloc){
+ this->clear();
+ }
+ this->AllocHolder::copy_assign_alloc(x);
+ //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, 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())){
+ AllocHolder::destroy_node(p);
+ }
+ }
+ return *this;
+ }
+
+ tree& operator=(BOOST_RV_REF(tree) x)
+ BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
+ allocator_traits_type::is_always_equal::value) &&
+ boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
+ {
+ BOOST_ASSERT(this != &x);
+ NodeAlloc &this_alloc = this->node_alloc();
+ NodeAlloc &x_alloc = x.node_alloc();
+ const bool propagate_alloc = allocator_traits<NodeAlloc>::
+ propagate_on_container_move_assignment::value;
+ const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
+ //Resources can be transferred if both allocators are
+ //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
+ (::boost::move(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);
+ }
+ }
+ return *this;
+ }
+
+ public:
+ // accessors:
+ BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const
+ { return this->icont().value_comp().predicate(); }
+
+ BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const
+ { return this->icont().value_comp().predicate().key_comp(); }
+
+ BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const
+ { return allocator_type(this->node_alloc()); }
+
+ BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const
+ { return this->node_alloc(); }
+
+ BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator()
+ { return this->node_alloc(); }
+
+ BOOST_CONTAINER_FORCEINLINE iterator begin()
+ { return iterator(this->icont().begin()); }
+
+ BOOST_CONTAINER_FORCEINLINE const_iterator begin() const
+ { return this->cbegin(); }
+
+ BOOST_CONTAINER_FORCEINLINE iterator end()
+ { return iterator(this->icont().end()); }
+
+ BOOST_CONTAINER_FORCEINLINE const_iterator end() const
+ { return this->cend(); }
+
+ BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin()
+ { return reverse_iterator(end()); }
+
+ BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const
+ { return this->crbegin(); }
+
+ BOOST_CONTAINER_FORCEINLINE reverse_iterator rend()
+ { return reverse_iterator(begin()); }
+
+ BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const
+ { return this->crend(); }
+
+ //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: Constant.
+ BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const
+ { return const_iterator(this->non_const_icont().begin()); }
+
+ //! <b>Effects</b>: Returns a const_iterator to the end of the container.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: Constant.
+ BOOST_CONTAINER_FORCEINLINE const_iterator cend() const
+ { return const_iterator(this->non_const_icont().end()); }
+
+ //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
+ //! of the reversed container.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: Constant.
+ BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const
+ { return const_reverse_iterator(cend()); }
+
+ //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
+ //! of the reversed container.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: Constant.
+ BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const
+ { return const_reverse_iterator(cbegin()); }
+
+ BOOST_CONTAINER_FORCEINLINE bool empty() const
+ { return !this->size(); }
+
+ BOOST_CONTAINER_FORCEINLINE size_type size() const
+ { return this->icont().size(); }
+
+ BOOST_CONTAINER_FORCEINLINE size_type max_size() const
+ { return AllocHolder::max_size(); }
+
+ BOOST_CONTAINER_FORCEINLINE void swap(ThisType& x)
+ BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
+ && boost::container::dtl::is_nothrow_swappable<Compare>::value )
+ { AllocHolder::swap(x); }
+
+ public:
+
+ typedef typename Icont::insert_commit_data insert_commit_data;
+
+ // insert/erase
+ std::pair<iterator,bool> insert_unique_check
+ (const key_type& key, insert_commit_data &data)
+ {
+ std::pair<iiterator, bool> ret =
+ this->icont().insert_unique_check(key, KeyNodeCompare(key_comp()), data);
+ return std::pair<iterator, bool>(iterator(ret.first), ret.second);
+ }
+
+ std::pair<iterator,bool> insert_unique_check
+ (const_iterator hint, const key_type& key, insert_commit_data &data)
+ {
+ BOOST_ASSERT((priv_is_linked)(hint));
+ std::pair<iiterator, bool> ret =
+ this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(key_comp()), data);
+ return std::pair<iterator, bool>(iterator(ret.first), ret.second);
+ }
+
+ template<class MovableConvertible>
+ iterator insert_unique_commit
+ (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data)
+ {
+ 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;
+ }
+
+ template<class MovableConvertible>
+ 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()(v), data);
+ if(ret.second){
+ ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
+ }
+ return ret;
+ }
+
+ private:
+
+ template<class KeyConvertible, class M>
+ iiterator priv_insert_or_assign_commit
+ (BOOST_FWD_REF(KeyConvertible) key, BOOST_FWD_REF(M) obj, insert_commit_data &data)
+ {
+ NodePtr tmp = AllocHolder::create_node(boost::forward<KeyConvertible>(key), boost::forward<M>(obj));
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ iiterator ret(this->icont().insert_unique_commit(*tmp, data));
+ destroy_deallocator.release();
+ return ret;
+ }
+
+ bool priv_is_linked(const_iterator const position) const
+ {
+ iiterator const cur(position.get());
+ return cur == this->icont().end() ||
+ cur == this->icont().root() ||
+ iiterator(cur).go_parent().go_left() == cur ||
+ iiterator(cur).go_parent().go_right() == cur;
+ }
+
+ template<class MovableConvertible>
+ void push_back_impl(BOOST_FWD_REF(MovableConvertible) v)
+ {
+ 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)
+ {
+ value_type &v = p->get_data();
+ insert_commit_data data;
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc());
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(KeyOfValue()(v), data);
+ if(!ret.second){
+ return ret;
+ }
+ //No throw insertion part, release rollback
+ destroy_deallocator.release();
+ return std::pair<iterator,bool>
+ ( iterator(this->icont().insert_unique_commit(*p, data))
+ , true );
+ }
+
+ iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p)
+ {
+ BOOST_ASSERT((priv_is_linked)(hint));
+ value_type &v = p->get_data();
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(hint, KeyOfValue()(v), data);
+ if(!ret.second){
+ Destroyer(this->node_alloc())(p);
+ return ret.first;
+ }
+ return iterator(this->icont().insert_unique_commit(*p, data));
+ }
+
+ public:
+
+ #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+ template <class... Args>
+ BOOST_CONTAINER_FORCEINLINE 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>
+ BOOST_CONTAINER_FORCEINLINE 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(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, BOOST_FWD_REF(Args)... args)
+ {
+ BOOST_ASSERT((priv_is_linked)(hint));
+ 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;
+ }
+
+ template <class KeyType, class... Args>
+ BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace
+ (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args)
+ {
+ insert_commit_data data;
+ const key_type & k = key; //Support emulated rvalue references
+ std::pair<iiterator, bool> ret =
+ hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)
+ : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);
+ if(ret.second){
+ ret.first = this->icont().insert_unique_commit
+ (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key), boost::forward<Args>(args)...), data);
+ }
+ return std::pair<iterator, bool>(iterator(ret.first), ret.second);
+ }
+
+ #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+ #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \
+ BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
+ std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\
+ { return this->emplace_unique_impl(AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\
+ \
+ 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_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
+ iterator emplace_equal(BOOST_MOVE_UREF##N)\
+ {\
+ NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
+ 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;\
+ }\
+ \
+ BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
+ iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
+ {\
+ BOOST_ASSERT((priv_is_linked)(hint));\
+ NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
+ iterator ret(this->icont().insert_equal(hint.get(), *tmp));\
+ destroy_deallocator.release();\
+ return ret;\
+ }\
+ \
+ template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\
+ BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\
+ try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
+ {\
+ insert_commit_data data;\
+ const key_type & k = key;\
+ std::pair<iiterator, bool> ret =\
+ hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)\
+ : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);\
+ if(ret.second){\
+ ret.first = this->icont().insert_unique_commit\
+ (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N), data);\
+ }\
+ return std::pair<iterator, bool>(iterator(ret.first), ret.second);\
+ }\
+ //
+ BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE)
+ #undef BOOST_CONTAINER_TREE_EMPLACE_CODE
+
+ #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+ template<class MovableConvertible>
+ iterator insert_unique_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
+ {
+ BOOST_ASSERT((priv_is_linked)(hint));
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(hint, KeyOfValue()(v), data);
+ if(!ret.second)
+ return ret.first;
+ return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
+ }
+
+ BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_unique, value_type, iterator, this->insert_unique_convertible, const_iterator, const_iterator)
+
+ template <class InputIterator>
+ void insert_unique(InputIterator first, InputIterator last)
+ {
+ for( ; first != last; ++first)
+ this->insert_unique(*first);
+ }
+
+ iterator insert_equal(const value_type& v)
+ {
+ NodePtr tmp(AllocHolder::create_node(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;
+ }
+
+ template<class MovableConvertible>
+ iterator insert_equal(BOOST_FWD_REF(MovableConvertible) v)
+ {
+ 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;
+ }
+
+ template<class MovableConvertible>
+ iterator insert_equal_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
+ {
+ BOOST_ASSERT((priv_is_linked)(hint));
+ 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;
+ }
+
+ BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_equal, value_type, iterator, this->insert_equal_convertible, const_iterator, const_iterator)
+
+ template <class InputIterator>
+ void insert_equal(InputIterator first, InputIterator last)
+ {
+ for( ; first != last; ++first)
+ this->insert_equal(*first);
+ }
+
+ template<class KeyType, class M>
+ std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj)
+ {
+ insert_commit_data data;
+ const key_type & k = key; //Support emulated rvalue references
+ std::pair<iiterator, bool> ret =
+ hint == const_iterator() ? this->icont().insert_unique_check(k, KeyNodeCompare(key_comp()), data)
+ : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);
+ if(ret.second){
+ ret.first = this->priv_insert_or_assign_commit(boost::forward<KeyType>(key), boost::forward<M>(obj), data);
+ }
+ else{
+ ret.first->get_data().second = boost::forward<M>(obj);
+ }
+ return std::pair<iterator, bool>(iterator(ret.first), ret.second);
+ }
+
+ iterator erase(const_iterator position)
+ {
+ BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position));
+ return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc())));
+ }
+
+ BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& k)
+ { return AllocHolder::erase_key(k, KeyNodeCompare(key_comp()), alloc_version()); }
+
+ iterator erase(const_iterator first, const_iterator last)
+ {
+ BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first)));
+ BOOST_ASSERT(first == last || (priv_is_linked)(last));
+ return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version()));
+ }
+
+ node_type extract(const key_type& k)
+ {
+ iterator const it = this->find(k);
+ if(this->end() != it){
+ return this->extract(it);
+ }
+ return node_type();
+ }
+
+ node_type extract(const_iterator position)
+ {
+ BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position));
+ iiterator const iit(position.get());
+ this->icont().erase(iit);
+ return node_type(iit.operator->(), this->node_alloc());
+ }
+
+ insert_return_type insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
+ {
+ return this->insert_unique_node(this->end(), boost::move(nh));
+ }
+
+ insert_return_type insert_unique_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
+ {
+ insert_return_type irt; //inserted == false, node.empty()
+ if(!nh.empty()){
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(hint, KeyOfValue()(nh.value()), data);
+ if(ret.second){
+ irt.inserted = true;
+ irt.position = iterator(this->icont().insert_unique_commit(*nh.get(), data));
+ nh.release();
+ }
+ else{
+ irt.position = ret.first;
+ irt.node = boost::move(nh);
+ }
+ }
+ else{
+ irt.position = this->end();
+ }
+ return BOOST_MOVE_RET(insert_return_type, irt);
+ }
+
+ iterator insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
+ {
+ if(nh.empty()){
+ return this->end();
+ }
+ else{
+ NodePtr const p(nh.release());
+ return iterator(this->icont().insert_equal(*p));
+ }
+ }
+
+ iterator insert_equal_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
+ {
+ if(nh.empty()){
+ return this->end();
+ }
+ else{
+ NodePtr const p(nh.release());
+ return iterator(this->icont().insert_equal(hint.get(), *p));
+ }
+ }
+
+ template<class C2>
+ BOOST_CONTAINER_FORCEINLINE void merge_unique(tree<T, KeyOfValue, C2, Allocator, Options>& source)
+ { return this->icont().merge_unique(source.icont()); }
+
+ template<class C2>
+ BOOST_CONTAINER_FORCEINLINE void merge_equal(tree<T, KeyOfValue, C2, Allocator, Options>& source)
+ { return this->icont().merge_equal(source.icont()); }
+ BOOST_CONTAINER_FORCEINLINE void clear()
+ { AllocHolder::clear(alloc_version()); }
+
+ // 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
+ BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& k)
+ { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); }
+
+ BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& k) const
+ { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); }
+
+ template <class K>
+ BOOST_CONTAINER_FORCEINLINE
+ typename dtl::enable_if_transparent<key_compare, K, iterator>::type
+ find(const K& k)
+ { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); }
+
+ template <class K>
+ BOOST_CONTAINER_FORCEINLINE
+ typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
+ find(const K& k) const
+ { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); }
+
+ BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& k) const
+ { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); }
+
+ template <class K>
+ BOOST_CONTAINER_FORCEINLINE
+ typename dtl::enable_if_transparent<key_compare, K, size_type>::type
+ count(const K& k) const
+ { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); }
+
+ BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k)
+ { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
+
+ BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& k) const
+ { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
+
+ template <class K>
+ BOOST_CONTAINER_FORCEINLINE
+ typename dtl::enable_if_transparent<key_compare, K, iterator>::type
+ lower_bound(const K& k)
+ { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
+
+ template <class K>
+ BOOST_CONTAINER_FORCEINLINE
+ typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
+ lower_bound(const K& k) const
+ { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
+
+ BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& k)
+ { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
+
+ BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& k) const
+ { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
+
+ template <class K>
+ BOOST_CONTAINER_FORCEINLINE
+ typename dtl::enable_if_transparent<key_compare, K, iterator>::type
+ upper_bound(const K& k)
+ { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
+
+ template <class K>
+ BOOST_CONTAINER_FORCEINLINE
+ typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
+ upper_bound(const K& k) const
+ { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
+
+ std::pair<iterator,iterator> equal_range(const key_type& k)
+ {
+ std::pair<iiterator, iiterator> ret =
+ this->icont().equal_range(k, KeyNodeCompare(key_comp()));
+ return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
+ }
+
+ std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
+ {
+ std::pair<iiterator, iiterator> ret =
+ this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp()));
+ return std::pair<const_iterator,const_iterator>
+ (const_iterator(ret.first), const_iterator(ret.second));
+ }
+
+ template <class K>
+ BOOST_CONTAINER_FORCEINLINE
+ typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type
+ equal_range(const K& k)
+ {
+ std::pair<iiterator, iiterator> ret =
+ this->icont().equal_range(k, KeyNodeCompare(key_comp()));
+ return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
+ }
+
+ template <class K>
+ BOOST_CONTAINER_FORCEINLINE
+ typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type
+ equal_range(const K& k) const
+ {
+ std::pair<iiterator, iiterator> ret =
+ this->non_const_icont().equal_range(k, KeyNodeCompare(key_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)
+ {
+ std::pair<iiterator, iiterator> ret =
+ this->icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
+ return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
+ }
+
+ std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
+ {
+ std::pair<iiterator, iiterator> ret =
+ this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
+ return std::pair<const_iterator,const_iterator>
+ (const_iterator(ret.first), const_iterator(ret.second));
+ }
+
+ template <class K>
+ BOOST_CONTAINER_FORCEINLINE
+ typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type
+ lower_bound_range(const K& k)
+ {
+ std::pair<iiterator, iiterator> ret =
+ this->icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
+ return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
+ }
+
+ template <class K>
+ BOOST_CONTAINER_FORCEINLINE
+ typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type
+ lower_bound_range(const K& k) const
+ {
+ std::pair<iiterator, iiterator> ret =
+ this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
+ return std::pair<const_iterator,const_iterator>
+ (const_iterator(ret.first), const_iterator(ret.second));
+ }
+
+ BOOST_CONTAINER_FORCEINLINE void rebalance()
+ { intrusive_tree_proxy_t::rebalance(this->icont()); }
+
+ BOOST_CONTAINER_FORCEINLINE friend bool operator==(const tree& x, const tree& y)
+ { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
+
+ BOOST_CONTAINER_FORCEINLINE friend bool operator<(const tree& x, const tree& y)
+ { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
+
+ BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const tree& x, const tree& y)
+ { return !(x == y); }
+
+ BOOST_CONTAINER_FORCEINLINE friend bool operator>(const tree& x, const tree& y)
+ { return y < x; }
+
+ BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const tree& x, const tree& y)
+ { return !(y < x); }
+
+ BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const tree& x, const tree& y)
+ { return !(x < y); }
+
+ BOOST_CONTAINER_FORCEINLINE friend void swap(tree& x, tree& y)
+ { x.swap(y); }
+};
+
+} //namespace dtl {
+} //namespace container {
+
+template <class T>
+struct has_trivial_destructor_after_move;
+
+//!has_trivial_destructor_after_move<> == true_type
+//!specialization for optimizations
+template <class T, class KeyOfValue, class Compare, class Allocator, class Options>
+struct has_trivial_destructor_after_move
+ <
+ ::boost::container::dtl::tree
+ <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