summaryrefslogtreecommitdiff
path: root/boost/container/detail/tree.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/container/detail/tree.hpp')
-rw-r--r--boost/container/detail/tree.hpp1154
1 files changed, 1154 insertions, 0 deletions
diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp
new file mode 100644
index 0000000000..6cd91ed2a6
--- /dev/null
+++ b/boost/container/detail/tree.hpp
@@ -0,0 +1,1154 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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"
+#include <boost/container/detail/workaround.hpp>
+#include <boost/container/container_fwd.hpp>
+
+#include <boost/move/move.hpp>
+#include <boost/intrusive/pointer_traits.hpp>
+#include <boost/type_traits/has_trivial_destructor.hpp>
+#include <boost/detail/no_exceptions_support.hpp>
+#include <boost/intrusive/rbtree.hpp>
+
+#include <boost/container/detail/utilities.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/allocator_traits.hpp>
+#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/container/detail/preprocessor.hpp>
+#endif
+
+#include <utility> //std::pair
+#include <iterator>
+#include <algorithm>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template<class Key, class Value, class KeyCompare, class KeyOfValue>
+struct value_compare_impl
+ : public KeyCompare
+{
+ typedef Value value_type;
+ typedef KeyCompare key_compare;
+ typedef KeyOfValue key_of_value;
+ typedef Key key_type;
+
+ value_compare_impl(const key_compare &kcomp)
+ : key_compare(kcomp)
+ {}
+
+ 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>
+ struct is_key
+ {
+ static const bool value = is_same<const T, const key_type>::value;
+ };
+
+ template<class T>
+ typename enable_if_c<is_key<T>::value, const key_type &>::type
+ key_forward(const T &key) const
+ { return key; }
+
+ template<class T>
+ typename enable_if_c<!is_key<T>::value, const key_type &>::type
+ key_forward(const T &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 VoidPointer>
+struct rbtree_hook
+{
+ 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>
+ >::type type;
+};
+
+template<class T>
+struct rbtree_type
+{
+ typedef T type;
+};
+
+template<class T1, class T2>
+struct rbtree_type< std::pair<T1, T2> >
+{
+ typedef pair<T1, T2> type;
+};
+
+template <class T, class VoidPointer>
+struct rbtree_node
+ : public rbtree_hook<VoidPointer>::type
+{
+ private:
+ BOOST_COPYABLE_AND_MOVABLE(rbtree_node)
+
+ public:
+ typedef typename rbtree_hook<VoidPointer>::type hook_type;
+
+ typedef T value_type;
+ typedef typename rbtree_type<T>::type internal_type;
+
+ typedef rbtree_node<T, VoidPointer> node_type;
+
+ rbtree_node()
+ : m_data()
+ {}
+
+ rbtree_node(const rbtree_node &other)
+ : m_data(other.m_data)
+ {}
+
+ rbtree_node(BOOST_RV_REF(rbtree_node) other)
+ : m_data(boost::move(other.m_data))
+ {}
+
+ #ifndef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ #define BOOST_PP_LOCAL_MACRO(n) \
+ template<BOOST_PP_ENUM_PARAMS(n, class P)> \
+ rbtree_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ : m_data(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)) \
+ {} \
+ //!
+ #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ #include BOOST_PP_LOCAL_ITERATE()
+
+ #else //#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template<class ...Args>
+ rbtree_node(Args &&...args)
+ : m_data(boost::forward<Args>(args)...)
+ {}
+ #endif//#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ rbtree_node &operator=(const rbtree_node &other)
+ { do_assign(other.m_data); return *this; }
+
+ rbtree_node &operator=(BOOST_RV_REF(rbtree_node) other)
+ { do_move(other.m_data); return *this; }
+
+ T &get_data()
+ {
+ T* ptr = reinterpret_cast<T*>(&this->m_data);
+ return *ptr;
+ }
+
+ const T &get_data() const
+ {
+ const T* ptr = reinterpret_cast<const T*>(&this->m_data);
+ return *ptr;
+ }
+
+ private:
+ internal_type m_data;
+
+ template<class A, class B>
+ void do_assign(const std::pair<const A, B> &p)
+ {
+ const_cast<A&>(m_data.first) = p.first;
+ m_data.second = p.second;
+ }
+
+ template<class A, class B>
+ void do_assign(const pair<const A, B> &p)
+ {
+ const_cast<A&>(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>
+ void do_move(std::pair<const A, B> &p)
+ {
+ const_cast<A&>(m_data.first) = boost::move(p.first);
+ m_data.second = boost::move(p.second);
+ }
+
+ template<class A, class B>
+ void do_move(pair<const A, B> &p)
+ {
+ const_cast<A&>(m_data.first) = boost::move(p.first);
+ m_data.second = boost::move(p.second);
+ }
+
+ template<class V>
+ void do_move(V &v)
+ { m_data = boost::move(v); }
+};
+
+}//namespace container_detail {
+
+namespace container_detail {
+
+template<class A, class ValueCompare>
+struct intrusive_rbtree_type
+{
+ typedef typename boost::container::
+ allocator_traits<A>::value_type value_type;
+ typedef typename boost::container::
+ allocator_traits<A>::void_pointer void_pointer;
+ typedef typename boost::container::
+ allocator_traits<A>::size_type size_type;
+ typedef typename container_detail::rbtree_node
+ <value_type, void_pointer> node_type;
+ typedef node_compare<ValueCompare, node_type> node_compare_type;
+ typedef typename container_detail::bi::make_rbtree
+ <node_type
+ ,container_detail::bi::compare<node_compare_type>
+ ,container_detail::bi::base_hook<typename rbtree_hook<void_pointer>::type>
+ ,container_detail::bi::constant_time_size<true>
+ ,container_detail::bi::size_type<size_type>
+ >::type container_type;
+ typedef container_type type ;
+};
+
+} //namespace container_detail {
+
+namespace container_detail {
+
+template <class Key, class Value, class KeyOfValue,
+ class KeyCompare, class A>
+class rbtree
+ : protected container_detail::node_alloc_holder
+ < A
+ , typename container_detail::intrusive_rbtree_type
+ <A, value_compare_impl<Key, Value, KeyCompare, KeyOfValue>
+ >::type
+ , KeyCompare
+ >
+{
+ typedef typename container_detail::intrusive_rbtree_type
+ < A, value_compare_impl
+ <Key, Value, KeyCompare, KeyOfValue>
+ >::type Icont;
+ typedef container_detail::node_alloc_holder
+ <A, Icont, KeyCompare> AllocHolder;
+ typedef typename AllocHolder::NodePtr NodePtr;
+ typedef rbtree < Key, Value, KeyOfValue
+ , KeyCompare, A> ThisType;
+ typedef typename AllocHolder::NodeAlloc NodeAlloc;
+ 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;
+
+ class RecyclingCloner;
+ friend class RecyclingCloner;
+
+ 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)
+ try{
+ //This can throw
+ *p = other;
+ return p;
+ }
+ 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);
+ }
+ throw;
+ }
+ }
+ else{
+ return m_holder.create_node(other);
+ }
+ }
+
+ 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)
+ try{
+ //This can throw
+ *p = boost::move(other);
+ return p;
+ }
+ 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);
+ }
+ throw;
+ }
+ }
+ else{
+ return m_holder.create_node(other);
+ }
+ }
+
+ AllocHolder &m_holder;
+ Icont &m_icont;
+ };
+
+ BOOST_COPYABLE_AND_MOVABLE(rbtree)
+
+ public:
+
+ typedef Key key_type;
+ typedef Value value_type;
+ typedef A allocator_type;
+ typedef KeyCompare key_compare;
+ typedef value_compare_impl< Key, Value
+ , KeyCompare, KeyOfValue> value_compare;
+ typedef typename boost::container::
+ allocator_traits<A>::pointer pointer;
+ typedef typename boost::container::
+ allocator_traits<A>::const_pointer const_pointer;
+ typedef typename boost::container::
+ allocator_traits<A>::reference reference;
+ typedef typename boost::container::
+ allocator_traits<A>::const_reference const_reference;
+ typedef typename boost::container::
+ allocator_traits<A>::size_type size_type;
+ typedef typename boost::container::
+ allocator_traits<A>::difference_type difference_type;
+ typedef difference_type rbtree_difference_type;
+ typedef pointer rbtree_pointer;
+ typedef const_pointer rbtree_const_pointer;
+ typedef reference rbtree_reference;
+ typedef const_reference rbtree_const_reference;
+ typedef NodeAlloc stored_allocator_type;
+
+ private:
+
+ template<class KeyValueCompare>
+ 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:
+ //rbtree const_iterator
+ class const_iterator
+ : public std::iterator
+ < std::bidirectional_iterator_tag
+ , value_type , rbtree_difference_type
+ , rbtree_const_pointer , rbtree_const_reference>
+ {
+ protected:
+ typedef typename Icont::iterator iiterator;
+ iiterator m_it;
+ explicit const_iterator(iiterator it) : m_it(it){}
+ void prot_incr() { ++m_it; }
+ void prot_decr() { --m_it; }
+
+ private:
+ iiterator get()
+ { return this->m_it; }
+
+ public:
+ friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>;
+ typedef rbtree_difference_type difference_type;
+
+ //Constructors
+ const_iterator()
+ : m_it()
+ {}
+
+ //Pointer like operators
+ const_reference operator*() const
+ { return m_it->get_data(); }
+
+ const_pointer operator->() const
+ { return const_pointer(&m_it->get_data()); }
+
+ //Increment / Decrement
+ const_iterator& operator++()
+ { prot_incr(); return *this; }
+
+ const_iterator operator++(int)
+ { iiterator tmp = m_it; ++*this; return const_iterator(tmp); }
+
+ const_iterator& operator--()
+ { prot_decr(); return *this; }
+
+ const_iterator operator--(int)
+ { iiterator tmp = m_it; --*this; return const_iterator(tmp); }
+
+ //Comparison operators
+ bool operator== (const const_iterator& r) const
+ { return m_it == r.m_it; }
+
+ bool operator!= (const const_iterator& r) const
+ { return m_it != r.m_it; }
+ };
+
+ //rbtree iterator
+ class iterator : public const_iterator
+ {
+ private:
+ explicit iterator(iiterator it)
+ : const_iterator(it)
+ {}
+
+ iiterator get()
+ { return this->m_it; }
+
+ public:
+ friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>;
+ typedef rbtree_pointer pointer;
+ typedef rbtree_reference reference;
+
+ //Constructors
+ iterator(){}
+
+ //Pointer like operators
+ reference operator*() const { return this->m_it->get_data(); }
+ pointer operator->() const { return pointer(&this->m_it->get_data()); }
+
+ //Increment / Decrement
+ iterator& operator++()
+ { this->prot_incr(); return *this; }
+
+ iterator operator++(int)
+ { iiterator tmp = this->m_it; ++*this; return iterator(tmp); }
+
+ iterator& operator--()
+ { this->prot_decr(); return *this; }
+
+ iterator operator--(int)
+ { iterator tmp = *this; --*this; return tmp; }
+ };
+
+ typedef std::reverse_iterator<iterator> reverse_iterator;
+ typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
+ rbtree()
+ : AllocHolder(key_compare())
+ {}
+
+ rbtree(const key_compare& comp, const allocator_type& a = allocator_type())
+ : AllocHolder(a, comp)
+ {}
+
+ template <class InputIterator>
+ rbtree(InputIterator first, InputIterator last, const key_compare& comp,
+ const allocator_type& a, bool unique_insertion)
+ : AllocHolder(a, comp)
+ {
+ typedef typename std::iterator_traits<InputIterator>::iterator_category ItCat;
+ priv_create_and_insert_nodes(first, last, unique_insertion, alloc_version(), ItCat());
+ }
+
+ template <class InputIterator>
+ rbtree( ordered_range_t, InputIterator first, InputIterator last
+ , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type())
+ : AllocHolder(a, comp)
+ {
+ typedef typename std::iterator_traits<InputIterator>::iterator_category ItCat;
+ priv_create_and_insert_ordered_nodes(first, last, alloc_version(), ItCat());
+ }
+
+ rbtree(const rbtree& x)
+ : AllocHolder(x, x.key_comp())
+ {
+ this->icont().clone_from
+ (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
+ }
+
+ rbtree(BOOST_RV_REF(rbtree) x)
+ : AllocHolder(boost::move(static_cast<AllocHolder&>(x)), x.key_comp())
+ {}
+
+ ~rbtree()
+ {} //AllocHolder clears the tree
+
+ rbtree& operator=(BOOST_COPY_ASSIGN_REF(rbtree) 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>::
+ 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(*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;
+ }
+
+ rbtree& operator=(BOOST_RV_REF(rbtree) x)
+ {
+ if (&x != this){
+ NodeAlloc &this_alloc = this->node_alloc();
+ NodeAlloc &x_alloc = x.node_alloc();
+ //If allocators are equal we can just swap pointers
+ if(this_alloc == x_alloc){
+ //Destroy and swap pointers
+ this->clear();
+ this->icont() = boost::move(x.icont());
+ //Move allocator if needed
+ this->AllocHolder::move_assign_alloc(x);
+ }
+ //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(); }
+
+ key_compare key_comp() const
+ { return this->icont().value_comp().value_comp().key_comp(); }
+
+ allocator_type get_allocator() const
+ { return allocator_type(this->node_alloc()); }
+
+ const stored_allocator_type &get_stored_allocator() const
+ { return this->node_alloc(); }
+
+ stored_allocator_type &get_stored_allocator()
+ { return this->node_alloc(); }
+
+ iterator begin()
+ { return iterator(this->icont().begin()); }
+
+ const_iterator begin() const
+ { return this->cbegin(); }
+
+ iterator end()
+ { return iterator(this->icont().end()); }
+
+ const_iterator end() const
+ { return this->cend(); }
+
+ reverse_iterator rbegin()
+ { return reverse_iterator(end()); }
+
+ const_reverse_iterator rbegin() const
+ { return this->crbegin(); }
+
+ reverse_iterator rend()
+ { return reverse_iterator(begin()); }
+
+ 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.
+ 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.
+ 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.
+ 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.
+ const_reverse_iterator crend() const
+ { return const_reverse_iterator(cbegin()); }
+
+ bool empty() const
+ { return !this->size(); }
+
+ size_type size() const
+ { return this->icont().size(); }
+
+ size_type max_size() const
+ { return AllocHolder::max_size(); }
+
+ void swap(ThisType& x)
+ { 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(value_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)
+ {
+ std::pair<iiterator, bool> ret =
+ this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(value_comp()), data);
+ return std::pair<iterator, bool>(iterator(ret.first), ret.second);
+ }
+
+ iterator insert_unique_commit(const value_type& v, insert_commit_data &data)
+ {
+ NodePtr tmp = AllocHolder::create_node(v);
+ iiterator it(this->icont().insert_unique_commit(*tmp, data));
+ return iterator(it);
+ }
+
+ template<class MovableConvertible>
+ iterator insert_unique_commit
+ (BOOST_FWD_REF(MovableConvertible) mv, insert_commit_data &data)
+ {
+ NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(mv));
+ iiterator it(this->icont().insert_unique_commit(*tmp, data));
+ return iterator(it);
+ }
+
+ std::pair<iterator,bool> insert_unique(const value_type& v)
+ {
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(KeyOfValue()(v), data);
+ if(!ret.second)
+ return ret;
+ return std::pair<iterator,bool>
+ (this->insert_unique_commit(v, data), true);
+ }
+
+ template<class MovableConvertible>
+ std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) mv)
+ {
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(KeyOfValue()(mv), data);
+ if(!ret.second)
+ return ret;
+ return std::pair<iterator,bool>
+ (this->insert_unique_commit(boost::forward<MovableConvertible>(mv), data), true);
+ }
+
+ private:
+ std::pair<iterator, bool> emplace_unique_impl(NodePtr p)
+ {
+ value_type &v = p->get_data();
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(KeyOfValue()(v), data);
+ if(!ret.second){
+ Destroyer(this->node_alloc())(p);
+ return ret;
+ }
+ return std::pair<iterator,bool>
+ ( iterator(iiterator(this->icont().insert_unique_commit(*p, data)))
+ , true );
+ }
+
+ iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p)
+ {
+ 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(iiterator(this->icont().insert_unique_commit(*p, data)));
+ }
+
+ public:
+
+ #ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template <class... Args>
+ std::pair<iterator, bool> emplace_unique(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)
+ { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); }
+
+ template <class... Args>
+ iterator emplace_equal(Args&&... args)
+ {
+ NodePtr p(AllocHolder::create_node(boost::forward<Args>(args)...));
+ return iterator(this->icont().insert_equal(this->icont().end(), *p));
+ }
+
+ template <class... Args>
+ iterator emplace_hint_equal(const_iterator hint, Args&&... args)
+ {
+ NodePtr p(AllocHolder::create_node(boost::forward<Args>(args)...));
+ return iterator(this->icont().insert_equal(hint.get(), *p));
+ }
+
+ #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ #define BOOST_PP_LOCAL_MACRO(n) \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ std::pair<iterator, bool> emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ return this->emplace_unique_impl \
+ (AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
+ } \
+ \
+ 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_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ return this->emplace_unique_hint_impl \
+ (hint, AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
+ } \
+ \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
+ return iterator(this->icont().insert_equal(this->icont().end(), *p)); \
+ } \
+ \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace_hint_equal(const_iterator hint \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
+ return iterator(this->icont().insert_equal(hint.get(), *p)); \
+ } \
+ //!
+ #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 =
+ this->insert_unique_check(hint, KeyOfValue()(v), data);
+ if(!ret.second)
+ return ret.first;
+ return this->insert_unique_commit(v, data);
+ }
+
+ template<class MovableConvertible>
+ iterator insert_unique(const_iterator hint, BOOST_FWD_REF(MovableConvertible) mv)
+ {
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(hint, KeyOfValue()(mv), data);
+ if(!ret.second)
+ return ret.first;
+ return this->insert_unique_commit(boost::forward<MovableConvertible>(mv), data);
+ }
+
+ template <class InputIterator>
+ void insert_unique(InputIterator first, InputIterator last)
+ {
+ if(this->empty()){
+ //Insert with end hint, to achieve linear
+ //complexity if [first, last) is ordered
+ const_iterator end(this->end());
+ for( ; first != last; ++first)
+ this->insert_unique(end, *first);
+ }
+ else{
+ for( ; first != last; ++first)
+ this->insert_unique(*first);
+ }
+ }
+
+ iterator insert_equal(const value_type& v)
+ {
+ NodePtr p(AllocHolder::create_node(v));
+ return iterator(this->icont().insert_equal(this->icont().end(), *p));
+ }
+
+ template<class MovableConvertible>
+ iterator insert_equal(BOOST_FWD_REF(MovableConvertible) mv)
+ {
+ NodePtr p(AllocHolder::create_node(boost::forward<MovableConvertible>(mv)));
+ return iterator(this->icont().insert_equal(this->icont().end(), *p));
+ }
+
+ iterator insert_equal(const_iterator hint, const value_type& v)
+ {
+ NodePtr p(AllocHolder::create_node(v));
+ return iterator(this->icont().insert_equal(hint.get(), *p));
+ }
+
+ template<class MovableConvertible>
+ iterator insert_equal(const_iterator hint, BOOST_FWD_REF(MovableConvertible) mv)
+ {
+ NodePtr p(AllocHolder::create_node(boost::forward<MovableConvertible>(mv)));
+ return iterator(this->icont().insert_equal(hint.get(), *p));
+ }
+
+ template <class InputIterator>
+ void insert_equal(InputIterator first, InputIterator last)
+ {
+ //Insert with end hint, to achieve linear
+ //complexity if [first, last) is ordered
+ const_iterator end(this->cend());
+ for( ; first != last; ++first)
+ this->insert_equal(end, *first);
+ }
+
+ iterator erase(const_iterator position)
+ { return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); }
+
+ size_type erase(const key_type& k)
+ { return AllocHolder::erase_key(k, KeyNodeCompare(value_comp()), alloc_version()); }
+
+ iterator erase(const_iterator first, const_iterator last)
+ { return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); }
+
+ void clear()
+ { AllocHolder::clear(alloc_version()); }
+
+ // set operations:
+ 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()))); }
+
+ size_type count(const key_type& k) const
+ { return size_type(this->icont().count(k, KeyNodeCompare(value_comp()))); }
+
+ iterator lower_bound(const key_type& k)
+ { return iterator(this->icont().lower_bound(k, KeyNodeCompare(value_comp()))); }
+
+ const_iterator lower_bound(const key_type& k) const
+ { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(value_comp()))); }
+
+ iterator upper_bound(const key_type& k)
+ { return iterator(this->icont().upper_bound(k, KeyNodeCompare(value_comp()))); }
+
+ const_iterator upper_bound(const key_type& k) const
+ { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(value_comp()))); }
+
+ std::pair<iterator,iterator> equal_range(const key_type& k)
+ {
+ std::pair<iiterator, iiterator> ret =
+ this->icont().equal_range(k, KeyNodeCompare(value_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(value_comp()));
+ return std::pair<const_iterator,const_iterator>
+ (const_iterator(ret.first), const_iterator(ret.second));
+ }
+
+ private:
+ //Iterator range version
+ template<class InpIterator>
+ void priv_create_and_insert_nodes
+ (InpIterator beg, InpIterator end, bool unique, allocator_v1, std::input_iterator_tag)
+ {
+ if(unique){
+ for (; beg != end; ++beg){
+ this->insert_unique(*beg);
+ }
+ }
+ else{
+ for (; beg != end; ++beg){
+ this->insert_equal(*beg);
+ }
+ }
+ }
+
+ template<class InpIterator>
+ void priv_create_and_insert_nodes
+ (InpIterator beg, InpIterator end, bool unique, allocator_v2, std::input_iterator_tag)
+ { //Just forward to the default one
+ priv_create_and_insert_nodes(beg, end, unique, allocator_v1(), std::input_iterator_tag());
+ }
+
+ class insertion_functor;
+ friend class insertion_functor;
+
+ class insertion_functor
+ {
+ Icont &icont_;
+
+ public:
+ insertion_functor(Icont &icont)
+ : icont_(icont)
+ {}
+
+ void operator()(Node &n)
+ { this->icont_.insert_equal(this->icont_.cend(), n); }
+ };
+
+
+ template<class FwdIterator>
+ void priv_create_and_insert_nodes
+ (FwdIterator beg, FwdIterator end, bool unique, allocator_v2, std::forward_iterator_tag)
+ {
+ if(beg != end){
+ if(unique){
+ priv_create_and_insert_nodes(beg, end, unique, allocator_v2(), std::input_iterator_tag());
+ }
+ else{
+ //Optimized allocation and construction
+ this->allocate_many_and_construct
+ (beg, std::distance(beg, end), insertion_functor(this->icont()));
+ }
+ }
+ }
+
+ //Iterator range version
+ template<class InpIterator>
+ void priv_create_and_insert_ordered_nodes
+ (InpIterator beg, InpIterator end, allocator_v1, std::input_iterator_tag)
+ {
+ const_iterator cend_n(this->cend());
+ for (; beg != end; ++beg){
+ this->insert_before(cend_n, *beg);
+ }
+ }
+
+ template<class InpIterator>
+ void priv_create_and_insert_ordered_nodes
+ (InpIterator beg, InpIterator end, allocator_v2, std::input_iterator_tag)
+ { //Just forward to the default one
+ priv_create_and_insert_ordered_nodes(beg, end, allocator_v1(), std::input_iterator_tag());
+ }
+
+ class back_insertion_functor;
+ friend class back_insertion_functor;
+
+ class back_insertion_functor
+ {
+ Icont &icont_;
+
+ public:
+ back_insertion_functor(Icont &icont)
+ : icont_(icont)
+ {}
+
+ void operator()(Node &n)
+ { this->icont_.push_back(n); }
+ };
+
+
+ template<class FwdIterator>
+ void priv_create_and_insert_ordered_nodes
+ (FwdIterator beg, FwdIterator end, allocator_v2, std::forward_iterator_tag)
+ {
+ if(beg != end){
+ //Optimized allocation and construction
+ this->allocate_many_and_construct
+ (beg, std::distance(beg, end), back_insertion_functor(this->icont()));
+ }
+ }
+};
+
+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.size() == y.size() &&
+ std::equal(x.begin(), x.end(), y.begin());
+}
+
+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 std::lexicographical_compare(x.begin(), x.end(),
+ y.begin(), y.end());
+}
+
+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 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 !(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 {
+/*
+//!has_trivial_destructor_after_move<> == true_type
+//!specialization for optimizations
+template <class K, class V, class KOV,
+class C, class A>
+struct has_trivial_destructor_after_move
+ <boost::container::container_detail::rbtree<K, V, KOV, C, A> >
+{
+ static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value;
+};
+*/
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //BOOST_CONTAINER_TREE_HPP