diff options
Diffstat (limited to 'boost/container/detail/tree.hpp')
-rw-r--r-- | boost/container/detail/tree.hpp | 98 |
1 files changed, 65 insertions, 33 deletions
diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp index 498fc73968..08965e5a6d 100644 --- a/boost/container/detail/tree.hpp +++ b/boost/container/detail/tree.hpp @@ -484,32 +484,65 @@ struct get_tree_opt<void> typedef tree_assoc_defaults type; }; +template<class, class KeyOfValue> +struct real_key_of_value +{ + typedef KeyOfValue type; +}; + +template<class T> +struct real_key_of_value<T, void> +{ + typedef dtl::identity<T> type; +}; + +template<class T1, class T2> +struct real_key_of_value<std::pair<T1, T2>, int> +{ + typedef dtl::select1st<T1> type; +}; + +template<class T1, class T2> +struct real_key_of_value<boost::container::pair<T1, T2>, int> +{ + typedef dtl::select1st<T1> type; +}; + template <class T, class KeyOfValue, class Compare, class Allocator, class Options> class tree : public dtl::node_alloc_holder - < Allocator + < typename real_allocator<T, Allocator>::type , typename dtl::intrusive_tree_type - < Allocator, tree_value_compare - <typename allocator_traits<Allocator>::pointer, Compare, KeyOfValue> + < typename real_allocator<T, Allocator>::type + , tree_value_compare + <typename allocator_traits<typename real_allocator<T, Allocator>::type>::pointer, Compare, typename real_key_of_value<T, KeyOfValue>::type> , get_tree_opt<Options>::type::tree_type , get_tree_opt<Options>::type::optimize_size >::type > { + typedef tree < T, KeyOfValue + , Compare, Allocator, Options> ThisType; + public: + typedef typename real_allocator<T, Allocator>::type allocator_type; + + private: + typedef allocator_traits<allocator_type> allocator_traits_t; + typedef typename real_key_of_value<T, KeyOfValue>::type key_of_value_t; typedef tree_value_compare - < typename allocator_traits<Allocator>::pointer - , Compare, KeyOfValue> ValComp; + < typename allocator_traits_t::pointer + , Compare + , key_of_value_t> ValComp; typedef typename get_tree_opt<Options>::type options_type; typedef typename dtl::intrusive_tree_type - < Allocator, ValComp + < allocator_type, ValComp , options_type::tree_type , options_type::optimize_size >::type Icont; typedef dtl::node_alloc_holder - <Allocator, Icont> AllocHolder; + <allocator_type, Icont> AllocHolder; typedef typename AllocHolder::NodePtr NodePtr; - typedef tree < T, KeyOfValue - , Compare, Allocator, Options> ThisType; + typedef typename AllocHolder::NodeAlloc NodeAlloc; typedef boost::container:: allocator_traits<NodeAlloc> allocator_traits_type; @@ -525,41 +558,40 @@ class tree public: - typedef typename KeyOfValue::type key_type; - typedef T value_type; - typedef Allocator allocator_type; - typedef Compare key_compare; - typedef ValComp value_compare; + typedef typename key_of_value_t::type key_type; + typedef T value_type; + typedef Compare key_compare; + typedef ValComp value_compare; typedef typename boost::container:: - allocator_traits<Allocator>::pointer pointer; + allocator_traits<allocator_type>::pointer pointer; typedef typename boost::container:: - allocator_traits<Allocator>::const_pointer const_pointer; + allocator_traits<allocator_type>::const_pointer const_pointer; typedef typename boost::container:: - allocator_traits<Allocator>::reference reference; + allocator_traits<allocator_type>::reference reference; typedef typename boost::container:: - allocator_traits<Allocator>::const_reference const_reference; + allocator_traits<allocator_type>::const_reference const_reference; typedef typename boost::container:: - allocator_traits<Allocator>::size_type size_type; + allocator_traits<allocator_type>::size_type size_type; typedef typename boost::container:: - allocator_traits<Allocator>::difference_type difference_type; + allocator_traits<allocator_type>::difference_type difference_type; typedef dtl::iterator_from_iiterator - <iiterator, false> iterator; + <iiterator, false> iterator; typedef dtl::iterator_from_iiterator - <iiterator, true > const_iterator; + <iiterator, true > const_iterator; typedef boost::container::reverse_iterator - <iterator> reverse_iterator; + <iterator> reverse_iterator; typedef boost::container::reverse_iterator - <const_iterator> const_reverse_iterator; + <const_iterator> const_reverse_iterator; typedef node_handle - < NodeAlloc, void> node_type; + < NodeAlloc, void> node_type; typedef insert_return_type_base - <iterator, node_type> insert_return_type; + <iterator, node_type> insert_return_type; - typedef NodeAlloc stored_allocator_type; + typedef NodeAlloc stored_allocator_type; private: - typedef key_node_compare<key_compare, KeyOfValue> KeyNodeCompare; + typedef key_node_compare<key_compare, key_of_value_t> KeyNodeCompare; public: @@ -955,7 +987,7 @@ class tree { insert_commit_data data; std::pair<iterator,bool> ret = - this->insert_unique_check(KeyOfValue()(v), data); + this->insert_unique_check(key_of_value_t()(v), data); if(ret.second){ ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); } @@ -998,7 +1030,7 @@ class tree insert_commit_data data; scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc()); std::pair<iterator,bool> ret = - this->insert_unique_check(KeyOfValue()(v), data); + this->insert_unique_check(key_of_value_t()(v), data); if(!ret.second){ return ret; } @@ -1015,7 +1047,7 @@ class tree value_type &v = p->get_data(); insert_commit_data data; std::pair<iterator,bool> ret = - this->insert_unique_check(hint, KeyOfValue()(v), data); + this->insert_unique_check(hint, key_of_value_t()(v), data); if(!ret.second){ Destroyer(this->node_alloc())(p); return ret.first; @@ -1131,7 +1163,7 @@ class tree BOOST_ASSERT((priv_is_linked)(hint)); insert_commit_data data; std::pair<iterator,bool> ret = - this->insert_unique_check(hint, KeyOfValue()(v), data); + this->insert_unique_check(hint, key_of_value_t()(v), data); if(!ret.second) return ret.first; return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); @@ -1246,7 +1278,7 @@ class tree if(!nh.empty()){ insert_commit_data data; std::pair<iterator,bool> ret = - this->insert_unique_check(hint, KeyOfValue()(nh.value()), data); + this->insert_unique_check(hint, key_of_value_t()(nh.value()), data); if(ret.second){ irt.inserted = true; irt.position = iterator(this->icont().insert_unique_commit(*nh.get(), data)); |