summaryrefslogtreecommitdiff
path: root/boost/container/detail/tree.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/container/detail/tree.hpp')
-rw-r--r--boost/container/detail/tree.hpp98
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));