diff options
Diffstat (limited to 'src/third_party/boost/boost/container/detail/tree.hpp')
| -rw-r--r-- | src/third_party/boost/boost/container/detail/tree.hpp | 1154 |
1 files changed, 0 insertions, 1154 deletions
diff --git a/src/third_party/boost/boost/container/detail/tree.hpp b/src/third_party/boost/boost/container/detail/tree.hpp deleted file mode 100644 index 6cd91ed2a69..00000000000 --- a/src/third_party/boost/boost/container/detail/tree.hpp +++ /dev/null @@ -1,1154 +0,0 @@ -////////////////////////////////////////////////////////////////////////////// -// -// (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 |