| ////////////////////////////////////////////////////////////////////////////// |
| // |
| // (C) Copyright Ion Gaztanaga 2005-2009. 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_CONTAINERS_TREE_HPP |
| #define BOOST_CONTAINERS_TREE_HPP |
| |
| #include "config_begin.hpp" |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_WORKAROUND_HPP |
| #include INCLUDE_BOOST_CONTAINER_CONTAINER_FWD_HPP |
| |
| #include INCLUDE_BOOST_CONTAINER_MOVE_HPP |
| #include <boost/pointer_to_other.hpp> |
| #include <boost/type_traits/has_trivial_destructor.hpp> |
| #include <boost/detail/no_exceptions_support.hpp> |
| #include <boost/intrusive/rbtree.hpp> |
| |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_UTILITIES_HPP |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_ALGORITHMS_HPP |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_NODE_ALLOC_HOLDER_HPP |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_DESTROYERS_HPP |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_PAIR_HPP |
| #ifndef BOOST_CONTAINERS_PERFECT_FORWARDING |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_PREPROCESSOR_HPP |
| #endif |
| |
| #include <utility> //std::pair |
| #include <iterator> |
| #include <algorithm> |
| |
| namespace boost { |
| namespace container { |
| namespace containers_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(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 A, class B> |
| bool operator()(const A &a, const B &b) const |
| { return key_compare::operator()(KeyOfValue()(a), KeyOfValue()(b)); } |
| }; |
| |
| template<class VoidPointer> |
| struct rbtree_hook |
| { |
| typedef typename containers_detail::bi::make_set_base_hook |
| < containers_detail::bi::void_pointer<VoidPointer> |
| , containers_detail::bi::link_mode<containers_detail::bi::normal_link> |
| , containers_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 |
| { |
| 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; |
| |
| #ifndef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| rbtree_node() |
| : m_data() |
| {} |
| |
| rbtree_node(const rbtree_node &other) |
| : m_data(other.m_data) |
| {} |
| |
| #define BOOST_PP_LOCAL_MACRO(n) \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| rbtree_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| : m_data(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)) \ |
| {} \ |
| //! |
| #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) |
| #include BOOST_PP_LOCAL_ITERATE() |
| |
| #else //#ifndef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| rbtree_node() |
| : m_data() |
| {} |
| |
| template<class ...Args> |
| rbtree_node(Args &&...args) |
| : m_data(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...) |
| {} |
| #endif//#ifndef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| rbtree_node &operator=(const rbtree_node &other) |
| { do_assign(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; } |
| |
| public: |
| template<class Convertible> |
| static void construct(node_type *ptr, BOOST_MOVE_MACRO_FWD_REF(Convertible) convertible) |
| { new(ptr) node_type(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Convertible>(convertible)); } |
| }; |
| |
| }//namespace containers_detail { |
| #if defined(BOOST_NO_RVALUE_REFERENCES) |
| template<class T, class VoidPointer> |
| struct has_own_construct_from_it |
| < boost::container::containers_detail::rbtree_node<T, VoidPointer> > |
| { |
| static const bool value = true; |
| }; |
| #endif |
| namespace containers_detail { |
| |
| template<class A, class ValueCompare> |
| struct intrusive_rbtree_type |
| { |
| typedef typename A::value_type value_type; |
| typedef typename boost::pointer_to_other |
| <typename A::pointer, void>::type void_pointer; |
| typedef typename containers_detail::rbtree_node |
| <value_type, void_pointer> node_type; |
| typedef node_compare<ValueCompare, node_type> node_compare_type; |
| typedef typename containers_detail::bi::make_rbtree |
| <node_type |
| ,containers_detail::bi::compare<node_compare_type> |
| ,containers_detail::bi::base_hook<typename rbtree_hook<void_pointer>::type> |
| ,containers_detail::bi::constant_time_size<true> |
| ,containers_detail::bi::size_type<typename A::size_type> |
| >::type container_type; |
| typedef container_type type ; |
| }; |
| |
| } //namespace containers_detail { |
| |
| namespace containers_detail { |
| |
| template <class Key, class Value, class KeyOfValue, |
| class KeyCompare, class A> |
| class rbtree |
| : protected containers_detail::node_alloc_holder |
| <A, typename containers_detail::intrusive_rbtree_type |
| <A, value_compare_impl<Key, Value, KeyCompare, KeyOfValue> |
| >::type |
| > |
| { |
| typedef typename containers_detail::intrusive_rbtree_type |
| <A, value_compare_impl |
| <Key, Value, KeyCompare, KeyOfValue> |
| >::type Icont; |
| typedef containers_detail::node_alloc_holder<A, Icont> 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 containers_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(!m_icont.empty()){ |
| if(NodePtr p = m_icont.unlink_leftmost_without_rebalance()){ |
| //First recycle a node (this can't throw) |
| //NodePtr p = m_icont.unlink_leftmost_without_rebalance(); |
| 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; |
| }; |
| BOOST_MOVE_MACRO_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 A::pointer pointer; |
| typedef typename A::const_pointer const_pointer; |
| typedef typename A::reference reference; |
| typedef typename A::const_reference const_reference; |
| typedef typename A::size_type size_type; |
| typedef typename 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(KeyValueCompare comp) |
| : KeyValueCompare(comp) |
| {} |
| |
| template<class KeyType> |
| bool operator()(const Node &n, const KeyType &k) const |
| { return KeyValueCompare::operator()(n.get_data(), k); } |
| |
| template<class KeyType> |
| bool operator()(const KeyType &k, const Node &n) const |
| { return KeyValueCompare::operator()(k, n.get_data()); } |
| }; |
| |
| 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(const key_compare& comp = key_compare(), |
| 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_MOVE_MACRO_RV_REF(rbtree) x) |
| : AllocHolder(x, x.key_comp()) |
| { this->swap(x); } |
| |
| ~rbtree() |
| {} //AllocHolder clears the tree |
| |
| rbtree& operator=(BOOST_MOVE_MACRO_COPY_ASSIGN_REF(rbtree) x) |
| { |
| if (this != &x) { |
| //Transfer all the nodes to a temporary tree |
| //If anything goes wrong, all the nodes will be destroyed |
| //automatically |
| Icont other_tree(this->icont().value_comp()); |
| other_tree.swap(this->icont()); |
| |
| //Now recreate the source tree reusing nodes stored by other_tree |
| this->icont().clone_from |
| (x.icont() |
| , RecyclingCloner(*this, other_tree) |
| //, AllocHolder::cloner(*this) |
| , 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_MOVE_MACRO_RV_REF(rbtree) mx) |
| { this->clear(); this->swap(mx); 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_MOVE_MACRO_FWD_REF(MovableConvertible) mv, insert_commit_data &data) |
| { |
| NodePtr tmp = AllocHolder::create_node(BOOST_CONTAINER_MOVE_NAMESPACE::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_MOVE_MACRO_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_CONTAINER_MOVE_NAMESPACE::forward<MovableConvertible>(mv), data), true); |
| } |
| |
| private: |
| iterator 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.first; |
| } |
| return iterator(iiterator(this->icont().insert_unique_commit(*p, data))); |
| } |
| |
| 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_CONTAINERS_PERFECT_FORWARDING |
| |
| template <class... Args> |
| iterator emplace_unique(Args&&... args) |
| { return this->emplace_unique_impl(AllocHolder::create_node(BOOST_CONTAINER_MOVE_NAMESPACE::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_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...)); } |
| |
| template <class... Args> |
| iterator emplace_equal(Args&&... args) |
| { |
| NodePtr p(AllocHolder::create_node(BOOST_CONTAINER_MOVE_NAMESPACE::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_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...)); |
| return iterator(this->icont().insert_equal(hint.get(), *p)); |
| } |
| |
| #else //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| iterator emplace_unique() |
| { return this->emplace_unique_impl(AllocHolder::create_node()); } |
| |
| iterator emplace_hint_unique(const_iterator hint) |
| { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node()); } |
| |
| iterator emplace_equal() |
| { |
| NodePtr p(AllocHolder::create_node()); |
| return iterator(this->icont().insert_equal(this->icont().end(), *p)); |
| } |
| |
| iterator emplace_hint_equal(const_iterator hint) |
| { |
| NodePtr p(AllocHolder::create_node()); |
| return iterator(this->icont().insert_equal(hint.get(), *p)); |
| } |
| |
| #define BOOST_PP_LOCAL_MACRO(n) \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| iterator emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| { \ |
| return this->emplace_unique_impl \ |
| (AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _))); \ |
| } \ |
| \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| iterator emplace_hint_unique(const_iterator hint, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| { \ |
| return this->emplace_unique_hint_impl \ |
| (hint, AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _))); \ |
| } \ |
| \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| { \ |
| NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _))); \ |
| return iterator(this->icont().insert_equal(this->icont().end(), *p)); \ |
| } \ |
| \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| iterator emplace_hint_equal(const_iterator hint, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| { \ |
| NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _))); \ |
| return iterator(this->icont().insert_equal(hint.get(), *p)); \ |
| } \ |
| //! |
| #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) |
| #include BOOST_PP_LOCAL_ITERATE() |
| |
| #endif //#ifdef BOOST_CONTAINERS_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_MOVE_MACRO_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_CONTAINER_MOVE_NAMESPACE::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_MOVE_MACRO_FWD_REF(MovableConvertible) mv) |
| { |
| NodePtr p(AllocHolder::create_node(BOOST_CONTAINER_MOVE_NAMESPACE::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_MOVE_MACRO_FWD_REF(MovableConvertible) mv) |
| { |
| NodePtr p(AllocHolder::create_node(BOOST_CONTAINER_MOVE_NAMESPACE::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 containers_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::containers_detail::rbtree<K, V, KOV, C, A> > |
| { |
| static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value; |
| }; |
| */ |
| } //namespace boost { |
| |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_CONFIG_END_HPP |
| |
| #endif //BOOST_CONTAINERS_TREE_HPP |