diff options
Diffstat (limited to 'boost/container/detail/tree.hpp')
-rw-r--r-- | boost/container/detail/tree.hpp | 1154 |
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 |