summaryrefslogtreecommitdiff
path: root/boost/intrusive/bstree.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/intrusive/bstree.hpp')
-rw-r--r--boost/intrusive/bstree.hpp648
1 files changed, 291 insertions, 357 deletions
diff --git a/boost/intrusive/bstree.hpp b/boost/intrusive/bstree.hpp
index 39c9d3ed2a..7a67de6e12 100644
--- a/boost/intrusive/bstree.hpp
+++ b/boost/intrusive/bstree.hpp
@@ -35,6 +35,7 @@
#include <boost/intrusive/detail/size_holder.hpp>
#include <boost/intrusive/detail/algo_type.hpp>
#include <boost/intrusive/detail/algorithm.hpp>
+#include <boost/intrusive/detail/tree_value_compare.hpp>
#include <boost/intrusive/detail/get_value_traits.hpp>
#include <boost/intrusive/bstree_algorithms.hpp>
@@ -69,6 +70,7 @@ struct bstree_defaults
static const bool constant_time_size = true;
typedef std::size_t size_type;
typedef void compare;
+ typedef void key_of_value;
static const bool floating_point = true; //For sgtree
typedef void priority; //For treap
typedef void header_holder_type;
@@ -90,7 +92,6 @@ struct bstbase3
typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer;
typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::const_pointer) const_pointer;
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::element_type) value_type;
- typedef BOOST_INTRUSIVE_IMPDEF(value_type) key_type;
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::reference) reference;
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::reference) const_reference;
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::difference_type) difference_type;
@@ -239,28 +240,62 @@ struct get_compare<void, T>
typedef ::std::less<T> type;
};
-template<class ValueTraits, class VoidOrKeyComp, algo_types AlgoType, typename HeaderHolder>
+template<class KeyOfValue, class T>
+struct get_key_of_value
+{
+ typedef KeyOfValue type;
+};
+
+template<class T>
+struct get_key_of_value<void, T>
+{
+ typedef ::boost::intrusive::detail::identity<T> type;
+};
+
+template<class T, class VoidOrKeyOfValue, class VoidOrKeyComp>
+struct bst_key_types
+{
+ typedef typename get_key_of_value
+ < VoidOrKeyOfValue, T>::type key_of_value;
+ typedef typename key_of_value::type key_type;
+ typedef typename get_compare< VoidOrKeyComp
+ , key_type
+ >::type key_compare;
+ typedef tree_value_compare
+ <key_type, T, key_compare, key_of_value> value_compare;
+};
+
+template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, algo_types AlgoType, typename HeaderHolder>
struct bstbase2
//Put the (possibly empty) functor in the first position to get EBO in MSVC
//Use public inheritance to avoid MSVC bugs with closures
- : public detail::ebo_functor_holder<typename get_compare< VoidOrKeyComp
- , typename ValueTraits::value_type
- >::type>
+ : public detail::ebo_functor_holder
+ < typename bst_key_types
+ < typename ValueTraits::value_type
+ , VoidOrKeyOfValue
+ , VoidOrKeyComp
+ >::value_compare
+ >
, public bstbase3<ValueTraits, AlgoType, HeaderHolder>
{
typedef bstbase3<ValueTraits, AlgoType, HeaderHolder> treeheader_t;
+ typedef bst_key_types< typename ValueTraits::value_type
+ , VoidOrKeyOfValue
+ , VoidOrKeyComp> key_types;
typedef typename treeheader_t::value_traits value_traits;
typedef typename treeheader_t::node_algorithms node_algorithms;
- typedef typename get_compare
- < VoidOrKeyComp, typename value_traits::value_type>::type value_compare;
- typedef BOOST_INTRUSIVE_IMPDEF(value_compare) key_compare;
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename key_types::key_type key_type;
+ typedef typename key_types::key_of_value key_of_value;
+ typedef typename key_types::key_compare key_compare;
+ typedef typename key_types::value_compare value_compare;
typedef typename treeheader_t::iterator iterator;
typedef typename treeheader_t::const_iterator const_iterator;
typedef typename treeheader_t::node_ptr node_ptr;
typedef typename treeheader_t::const_node_ptr const_node_ptr;
- bstbase2(const value_compare &comp, const ValueTraits &vtraits)
- : detail::ebo_functor_holder<value_compare>(comp), treeheader_t(vtraits)
+ bstbase2(const key_compare &comp, const ValueTraits &vtraits)
+ : detail::ebo_functor_holder<value_compare>(value_compare(comp)), treeheader_t(vtraits)
{}
const value_compare &comp() const
@@ -271,8 +306,6 @@ struct bstbase2
typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer;
typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::const_pointer) const_pointer;
- typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::element_type) value_type;
- typedef BOOST_INTRUSIVE_IMPDEF(value_type) key_type;
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::reference) reference;
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::reference) const_reference;
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::difference_type) difference_type;
@@ -282,203 +315,181 @@ struct bstbase2
{ return this->comp(); }
key_compare key_comp() const
- { return this->comp(); }
+ { return this->comp().key_comp(); }
//lower_bound
- iterator lower_bound(const_reference value)
- { return this->lower_bound(value, this->comp()); }
+ iterator lower_bound(const key_type &key)
+ { return this->lower_bound(key, this->key_comp()); }
- const_iterator lower_bound(const_reference value) const
- { return this->lower_bound(value, this->comp()); }
+ const_iterator lower_bound(const key_type &key) const
+ { return this->lower_bound(key, this->key_comp()); }
- template<class KeyType, class KeyValueCompare>
- iterator lower_bound(const KeyType &key, KeyValueCompare comp)
+ template<class KeyType, class KeyTypeKeyCompare>
+ iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp)
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
return iterator(node_algorithms::lower_bound
- (this->header_ptr(), key, key_node_comp), this->priv_value_traits_ptr());
+ (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr());
}
- template<class KeyType, class KeyValueCompare>
- const_iterator lower_bound(const KeyType &key, KeyValueCompare comp) const
+ template<class KeyType, class KeyTypeKeyCompare>
+ const_iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) const
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
return const_iterator(node_algorithms::lower_bound
- (this->header_ptr(), key, key_node_comp), this->priv_value_traits_ptr());
+ (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr());
}
//upper_bound
- iterator upper_bound(const_reference value)
- { return this->upper_bound(value, this->comp()); }
+ iterator upper_bound(const key_type &key)
+ { return this->upper_bound(key, this->key_comp()); }
- template<class KeyType, class KeyValueCompare>
- iterator upper_bound(const KeyType &key, KeyValueCompare comp)
+ template<class KeyType, class KeyTypeKeyCompare>
+ iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp)
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
return iterator(node_algorithms::upper_bound
- (this->header_ptr(), key, key_node_comp), this->priv_value_traits_ptr());
+ (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr());
}
- const_iterator upper_bound(const_reference value) const
- { return this->upper_bound(value, this->comp()); }
+ const_iterator upper_bound(const key_type &key) const
+ { return this->upper_bound(key, this->key_comp()); }
- template<class KeyType, class KeyValueCompare>
- const_iterator upper_bound(const KeyType &key, KeyValueCompare comp) const
+ template<class KeyType, class KeyTypeKeyCompare>
+ const_iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) const
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
return const_iterator(node_algorithms::upper_bound
- (this->header_ptr(), key, key_node_comp), this->priv_value_traits_ptr());
+ (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr());
+ }
+
+ template<class KeyTypeKeyCompare>
+ detail::key_nodeptr_comp<KeyTypeKeyCompare, value_traits, key_of_value> key_node_comp(KeyTypeKeyCompare comp) const
+ {
+ return detail::key_nodeptr_comp<KeyTypeKeyCompare, value_traits, key_of_value>(comp, &this->get_value_traits());
}
//find
- iterator find(const_reference value)
- { return this->find(value, this->comp()); }
+ iterator find(const key_type &key)
+ { return this->find(key, this->key_comp()); }
- template<class KeyType, class KeyValueCompare>
- iterator find(const KeyType &key, KeyValueCompare comp)
+ template<class KeyType, class KeyTypeKeyCompare>
+ iterator find(const KeyType &key, KeyTypeKeyCompare comp)
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
return iterator
- (node_algorithms::find(this->header_ptr(), key, key_node_comp), this->priv_value_traits_ptr());
+ (node_algorithms::find(this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr());
}
- const_iterator find(const_reference value) const
- { return this->find(value, this->comp()); }
+ const_iterator find(const key_type &key) const
+ { return this->find(key, this->key_comp()); }
- template<class KeyType, class KeyValueCompare>
- const_iterator find(const KeyType &key, KeyValueCompare comp) const
+ template<class KeyType, class KeyTypeKeyCompare>
+ const_iterator find(const KeyType &key, KeyTypeKeyCompare comp) const
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
return const_iterator
- (node_algorithms::find(this->header_ptr(), key, key_node_comp), this->priv_value_traits_ptr());
+ (node_algorithms::find(this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr());
}
//equal_range
- std::pair<iterator,iterator> equal_range(const_reference value)
- { return this->equal_range(value, this->comp()); }
+ std::pair<iterator,iterator> equal_range(const key_type &key)
+ { return this->equal_range(key, this->key_comp()); }
- template<class KeyType, class KeyValueCompare>
- std::pair<iterator,iterator> equal_range(const KeyType &key, KeyValueCompare comp)
+ template<class KeyType, class KeyTypeKeyCompare>
+ std::pair<iterator,iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp)
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
std::pair<node_ptr, node_ptr> ret
- (node_algorithms::equal_range(this->header_ptr(), key, key_node_comp));
+ (node_algorithms::equal_range(this->header_ptr(), key, this->key_node_comp(comp)));
return std::pair<iterator, iterator>( iterator(ret.first, this->priv_value_traits_ptr())
, iterator(ret.second, this->priv_value_traits_ptr()));
}
std::pair<const_iterator, const_iterator>
- equal_range(const_reference value) const
- { return this->equal_range(value, this->comp()); }
+ equal_range(const key_type &key) const
+ { return this->equal_range(key, this->key_comp()); }
- template<class KeyType, class KeyValueCompare>
+ template<class KeyType, class KeyTypeKeyCompare>
std::pair<const_iterator, const_iterator>
- equal_range(const KeyType &key, KeyValueCompare comp) const
+ equal_range(const KeyType &key, KeyTypeKeyCompare comp) const
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
std::pair<node_ptr, node_ptr> ret
- (node_algorithms::equal_range(this->header_ptr(), key, key_node_comp));
+ (node_algorithms::equal_range(this->header_ptr(), key, this->key_node_comp(comp)));
return std::pair<const_iterator, const_iterator>( const_iterator(ret.first, this->priv_value_traits_ptr())
, const_iterator(ret.second, this->priv_value_traits_ptr()));
}
//lower_bound_range
- std::pair<iterator,iterator> lower_bound_range(const_reference value)
- { return this->lower_bound_range(value, this->comp()); }
+ std::pair<iterator,iterator> lower_bound_range(const key_type &key)
+ { return this->lower_bound_range(key, this->key_comp()); }
- template<class KeyType, class KeyValueCompare>
- std::pair<iterator,iterator> lower_bound_range(const KeyType &key, KeyValueCompare comp)
+ template<class KeyType, class KeyTypeKeyCompare>
+ std::pair<iterator,iterator> lower_bound_range(const KeyType &key, KeyTypeKeyCompare comp)
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
std::pair<node_ptr, node_ptr> ret
- (node_algorithms::lower_bound_range(this->header_ptr(), key, key_node_comp));
+ (node_algorithms::lower_bound_range(this->header_ptr(), key, this->key_node_comp(comp)));
return std::pair<iterator, iterator>( iterator(ret.first, this->priv_value_traits_ptr())
, iterator(ret.second, this->priv_value_traits_ptr()));
}
std::pair<const_iterator, const_iterator>
- lower_bound_range(const_reference value) const
- { return this->lower_bound_range(value, this->comp()); }
+ lower_bound_range(const key_type &key) const
+ { return this->lower_bound_range(key, this->key_comp()); }
- template<class KeyType, class KeyValueCompare>
+ template<class KeyType, class KeyTypeKeyCompare>
std::pair<const_iterator, const_iterator>
- lower_bound_range(const KeyType &key, KeyValueCompare comp) const
+ lower_bound_range(const KeyType &key, KeyTypeKeyCompare comp) const
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
std::pair<node_ptr, node_ptr> ret
- (node_algorithms::lower_bound_range(this->header_ptr(), key, key_node_comp));
+ (node_algorithms::lower_bound_range(this->header_ptr(), key, this->key_node_comp(comp)));
return std::pair<const_iterator, const_iterator>( const_iterator(ret.first, this->priv_value_traits_ptr())
, const_iterator(ret.second, this->priv_value_traits_ptr()));
}
//bounded_range
std::pair<iterator,iterator> bounded_range
- (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
- { return this->bounded_range(lower_value, upper_value, this->comp(), left_closed, right_closed); }
+ (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed)
+ { return this->bounded_range(lower_key, upper_key, this->key_comp(), left_closed, right_closed); }
- template<class KeyType, class KeyValueCompare>
+ template<class KeyType, class KeyTypeKeyCompare>
std::pair<iterator,iterator> bounded_range
- (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed)
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
std::pair<node_ptr, node_ptr> ret
(node_algorithms::bounded_range
- (this->header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed));
+ (this->header_ptr(), lower_key, upper_key, this->key_node_comp(comp), left_closed, right_closed));
return std::pair<iterator, iterator>( iterator(ret.first, this->priv_value_traits_ptr())
, iterator(ret.second, this->priv_value_traits_ptr()));
}
std::pair<const_iterator,const_iterator> bounded_range
- (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
- { return this->bounded_range(lower_value, upper_value, this->comp(), left_closed, right_closed); }
+ (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const
+ { return this->bounded_range(lower_key, upper_key, this->key_comp(), left_closed, right_closed); }
- template<class KeyType, class KeyValueCompare>
+ template<class KeyType, class KeyTypeKeyCompare>
std::pair<const_iterator,const_iterator> bounded_range
- (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- key_node_comp(comp, &this->get_value_traits());
std::pair<node_ptr, node_ptr> ret
(node_algorithms::bounded_range
- (this->header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed));
+ (this->header_ptr(), lower_key, upper_key, this->key_node_comp(comp), left_closed, right_closed));
return std::pair<const_iterator, const_iterator>( const_iterator(ret.first, this->priv_value_traits_ptr())
, const_iterator(ret.second, this->priv_value_traits_ptr()));
}
//insert_unique_check
- template<class KeyType, class KeyValueCompare>
+ template<class KeyType, class KeyTypeKeyCompare>
std::pair<iterator, bool> insert_unique_check
- (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)
+ (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data)
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- ocomp(key_value_comp, &this->get_value_traits());
std::pair<node_ptr, bool> ret =
(node_algorithms::insert_unique_check
- (this->header_ptr(), key, ocomp, commit_data));
+ (this->header_ptr(), key, this->key_node_comp(comp), commit_data));
return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
}
- template<class KeyType, class KeyValueCompare>
+ template<class KeyType, class KeyTypeKeyCompare>
std::pair<iterator, bool> insert_unique_check
(const_iterator hint, const KeyType &key
- ,KeyValueCompare key_value_comp, insert_commit_data &commit_data)
+ ,KeyTypeKeyCompare comp, insert_commit_data &commit_data)
{
- detail::key_nodeptr_comp<KeyValueCompare, value_traits>
- ocomp(key_value_comp, &this->get_value_traits());
std::pair<node_ptr, bool> ret =
(node_algorithms::insert_unique_check
- (this->header_ptr(), hint.pointed_node(), key, ocomp, commit_data));
+ (this->header_ptr(), hint.pointed_node(), key, this->key_node_comp(comp), commit_data));
return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
}
};
@@ -486,19 +497,20 @@ struct bstbase2
//Due to MSVC's EBO implementation, to save space and maintain the ABI, we must put the non-empty size member
//in the first position, but if size is not going to be stored then we'll use an specialization
//that doesn't inherit from size_holder
-template<class ValueTraits, class VoidOrKeyComp, bool ConstantTimeSize, class SizeType, algo_types AlgoType, typename HeaderHolder>
+template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, bool ConstantTimeSize, class SizeType, algo_types AlgoType, typename HeaderHolder>
struct bstbase_hack
: public detail::size_holder<ConstantTimeSize, SizeType>
- , public bstbase2 < ValueTraits, VoidOrKeyComp, AlgoType, HeaderHolder>
+ , public bstbase2 < ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder>
{
- typedef bstbase2< ValueTraits, VoidOrKeyComp, AlgoType, HeaderHolder> base_type;
+ typedef bstbase2< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder> base_type;
+ typedef typename base_type::key_compare key_compare;
typedef typename base_type::value_compare value_compare;
typedef SizeType size_type;
typedef typename base_type::node_traits node_traits;
typedef typename get_algo
<AlgoType, node_traits>::type algo_type;
- bstbase_hack(const value_compare & comp, const ValueTraits &vtraits)
+ bstbase_hack(const key_compare & comp, const ValueTraits &vtraits)
: base_type(comp, vtraits)
{
this->sz_traits().set_size(size_type(0));
@@ -514,17 +526,18 @@ struct bstbase_hack
};
//Specialization for ConstantTimeSize == false
-template<class ValueTraits, class VoidOrKeyComp, class SizeType, algo_types AlgoType, typename HeaderHolder>
-struct bstbase_hack<ValueTraits, VoidOrKeyComp, false, SizeType, AlgoType, HeaderHolder>
- : public bstbase2 < ValueTraits, VoidOrKeyComp, AlgoType, HeaderHolder>
+template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, algo_types AlgoType, typename HeaderHolder>
+struct bstbase_hack<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, false, SizeType, AlgoType, HeaderHolder>
+ : public bstbase2 < ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder>
{
- typedef bstbase2< ValueTraits, VoidOrKeyComp, AlgoType, HeaderHolder> base_type;
+ typedef bstbase2< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder> base_type;
typedef typename base_type::value_compare value_compare;
- bstbase_hack(const value_compare & comp, const ValueTraits &vtraits)
+ typedef typename base_type::key_compare key_compare;
+ bstbase_hack(const key_compare & comp, const ValueTraits &vtraits)
: base_type(comp, vtraits)
{}
- typedef detail::size_holder<true, SizeType> size_traits;
+ typedef detail::size_holder<false, SizeType> size_traits;
size_traits &sz_traits()
{ return s_size_traits; }
@@ -535,18 +548,18 @@ struct bstbase_hack<ValueTraits, VoidOrKeyComp, false, SizeType, AlgoType, Heade
static size_traits s_size_traits;
};
-template<class ValueTraits, class VoidOrKeyComp, class SizeType, algo_types AlgoType, typename HeaderHolder>
-detail::size_holder<true, SizeType> bstbase_hack<ValueTraits, VoidOrKeyComp, false, SizeType, AlgoType, HeaderHolder>::s_size_traits;
+template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, algo_types AlgoType, typename HeaderHolder>
+detail::size_holder<false, SizeType> bstbase_hack<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, false, SizeType, AlgoType, HeaderHolder>::s_size_traits;
//This class will
-template<class ValueTraits, class VoidOrKeyComp, bool ConstantTimeSize, class SizeType, algo_types AlgoType, typename HeaderHolder>
+template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, bool ConstantTimeSize, class SizeType, algo_types AlgoType, typename HeaderHolder>
struct bstbase
- : public bstbase_hack< ValueTraits, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder>
+ : public bstbase_hack< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder>
{
- typedef bstbase_hack< ValueTraits, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> base_type;
+ typedef bstbase_hack< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> base_type;
typedef ValueTraits value_traits;
typedef typename base_type::value_compare value_compare;
- typedef value_compare key_compare;
+ typedef typename base_type::key_compare key_compare;
typedef typename base_type::const_reference const_reference;
typedef typename base_type::reference reference;
typedef typename base_type::iterator iterator;
@@ -556,7 +569,7 @@ struct bstbase
<AlgoType, node_traits>::type node_algorithms;
typedef SizeType size_type;
- bstbase(const value_compare & comp, const ValueTraits &vtraits)
+ bstbase(const key_compare & comp, const ValueTraits &vtraits)
: base_type(comp, vtraits)
{}
@@ -578,7 +591,7 @@ struct bstbase
/// @endcond
//! The class template bstree is an unbalanced intrusive binary search tree
-//! container. The no-throw guarantee holds only, if the value_compare object
+//! container. The no-throw guarantee holds only, if the key_compare object
//! doesn't throw.
//!
//! The complexity guarantees only hold if the tree is balanced, logarithmic
@@ -595,14 +608,14 @@ struct bstbase
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
template<class T, class ...Options>
#else
-template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>
+template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>
#endif
class bstree_impl
- : public bstbase<ValueTraits, VoidKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder>
+ : public bstbase<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder>
{
public:
/// @cond
- typedef bstbase<ValueTraits, VoidKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> data_type;
+ typedef bstbase<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> data_type;
typedef tree_iterator<ValueTraits, false> iterator_type;
typedef tree_iterator<ValueTraits, true> const_iterator_type;
/// @endcond
@@ -611,13 +624,14 @@ class bstree_impl
typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer;
typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::const_pointer) const_pointer;
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::element_type) value_type;
- typedef BOOST_INTRUSIVE_IMPDEF(value_type) key_type;
+ typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::key_type) key_type;
+ typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::key_of_value) key_of_value;
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::reference) reference;
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::reference) const_reference;
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::difference_type) difference_type;
typedef BOOST_INTRUSIVE_IMPDEF(SizeType) size_type;
typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::value_compare) value_compare;
- typedef BOOST_INTRUSIVE_IMPDEF(value_compare) key_compare;
+ typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::key_compare) key_compare;
typedef BOOST_INTRUSIVE_IMPDEF(iterator_type) iterator;
typedef BOOST_INTRUSIVE_IMPDEF(const_iterator_type) const_iterator;
typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::reverse_iterator<iterator>) reverse_iterator;
@@ -660,8 +674,8 @@ class bstree_impl
//!
//! <b>Throws</b>: If value_traits::node_traits::node
//! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
- //! or the copy constructor of the value_compare object throws. Basic guarantee.
- explicit bstree_impl( const value_compare &cmp = value_compare()
+ //! or the copy constructor of the key_compare object throws. Basic guarantee.
+ explicit bstree_impl( const key_compare &cmp = key_compare()
, const value_traits &v_traits = value_traits())
: data_type(cmp, v_traits)
{}
@@ -677,10 +691,10 @@ class bstree_impl
//!
//! <b>Throws</b>: If value_traits::node_traits::node
//! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
- //! or the copy constructor/operator() of the value_compare object throws. Basic guarantee.
+ //! or the copy constructor/operator() of the key_compare object throws. Basic guarantee.
template<class Iterator>
bstree_impl( bool unique, Iterator b, Iterator e
- , const value_compare &cmp = value_compare()
+ , const key_compare &cmp = key_compare()
, const value_traits &v_traits = value_traits())
: data_type(cmp, v_traits)
{
@@ -863,7 +877,7 @@ class bstree_impl
//!
//! <b>Complexity</b>: Constant.
//!
- //! <b>Throws</b>: If value_compare copy-constructor throws.
+ //! <b>Throws</b>: If key_compare copy-constructor throws.
key_compare key_comp() const;
//! <b>Effects</b>: Returns the value_compare object used by the container.
@@ -960,7 +974,7 @@ class bstree_impl
//!
//! <b>Effects</b>: Erases all the elements from *this
//! calling Disposer::operator()(pointer), clones all the
- //! elements from src calling Cloner::operator()(const_reference )
+ //! elements from src calling Cloner::operator()(reference)
//! and inserts them on *this. Copies the predicate from the source container.
//!
//! If cloner throws, all cloned elements are unlinked and disposed
@@ -973,7 +987,7 @@ class bstree_impl
//! <b>Note</b>: This version can modify the source container, useful to implement
//! move semantics.
template <class Cloner, class Disposer>
- void clone_from(bstree_impl &src, Cloner cloner, Disposer disposer)
+ void clone_from(BOOST_RV_REF(bstree_impl) src, Cloner cloner, Disposer disposer)
{
this->clear_and_dispose(disposer);
if(!src.empty()){
@@ -997,19 +1011,17 @@ class bstree_impl
//! <b>Complexity</b>: Average complexity for insert element is at
//! most logarithmic.
//!
- //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
+ //! <b>Throws</b>: If the internal key_compare ordering function throws. Strong guarantee.
//!
//! <b>Note</b>: Does not affect the validity of iterators and references.
//! No copy-constructors are called.
iterator insert_equal(reference value)
{
- detail::key_nodeptr_comp<value_compare, value_traits>
- key_node_comp(this->comp(), &this->get_value_traits());
node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
if(safemode_or_autounlink)
BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
iterator ret(node_algorithms::insert_equal_upper_bound
- (this->header_ptr(), to_insert, key_node_comp), this->priv_value_traits_ptr());
+ (this->header_ptr(), to_insert, this->key_node_comp(this->key_comp())), this->priv_value_traits_ptr());
this->sz_traits().increment();
return ret;
}
@@ -1024,19 +1036,17 @@ class bstree_impl
//! <b>Complexity</b>: Logarithmic in general, but it is amortized
//! constant time if t is inserted immediately before hint.
//!
- //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
+ //! <b>Throws</b>: If the internal key_compare ordering function throws. Strong guarantee.
//!
//! <b>Note</b>: Does not affect the validity of iterators and references.
//! No copy-constructors are called.
iterator insert_equal(const_iterator hint, reference value)
{
- detail::key_nodeptr_comp<value_compare, value_traits>
- key_node_comp(this->comp(), &this->get_value_traits());
node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
if(safemode_or_autounlink)
BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
iterator ret(node_algorithms::insert_equal
- (this->header_ptr(), hint.pointed_node(), to_insert, key_node_comp), this->priv_value_traits_ptr());
+ (this->header_ptr(), hint.pointed_node(), to_insert, this->key_node_comp(this->key_comp())), this->priv_value_traits_ptr());
this->sz_traits().increment();
return ret;
}
@@ -1078,10 +1088,13 @@ class bstree_impl
std::pair<iterator, bool> insert_unique(reference value)
{
insert_commit_data commit_data;
- std::pair<iterator, bool> ret = this->insert_unique_check(value, this->comp(), commit_data);
- if(!ret.second)
- return ret;
- return std::pair<iterator, bool> (this->insert_unique_commit(value, commit_data), true);
+ std::pair<node_ptr, bool> ret =
+ (node_algorithms::insert_unique_check
+ (this->header_ptr(), key_of_value()(value), this->key_node_comp(this->key_comp()), commit_data));
+ return std::pair<iterator, bool>
+ ( ret.second ? this->insert_unique_commit(value, commit_data)
+ : iterator(ret.first, this->priv_value_traits_ptr())
+ , ret.second);
}
//! <b>Requires</b>: value must be an lvalue, and "hint" must be
@@ -1101,10 +1114,11 @@ class bstree_impl
iterator insert_unique(const_iterator hint, reference value)
{
insert_commit_data commit_data;
- std::pair<iterator, bool> ret = this->insert_unique_check(hint, value, this->comp(), commit_data);
- if(!ret.second)
- return ret.first;
- return this->insert_unique_commit(value, commit_data);
+ std::pair<node_ptr, bool> ret =
+ (node_algorithms::insert_unique_check
+ (this->header_ptr(), hint.pointed_node(), key_of_value()(value), this->key_node_comp(this->key_comp()), commit_data));
+ return ret.second ? this->insert_unique_commit(value, commit_data)
+ : iterator(ret.first, this->priv_value_traits_ptr());
}
//! <b>Requires</b>: Dereferencing iterator must yield an lvalue
@@ -1136,9 +1150,9 @@ class bstree_impl
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- //! <b>Requires</b>: key_value_comp must be a comparison function that induces
- //! the same strict weak ordering as value_compare. The difference is that
- //! key_value_comp compares an arbitrary key with the contained values.
+ //! <b>Requires</b>: comp must be a comparison function that induces
+ //! the same strict weak ordering as key_compare. The difference is that
+ //! comp compares an arbitrary key with the contained values.
//!
//! <b>Effects</b>: Checks if a value can be inserted in the container, using
//! a user provided key instead of the value itself.
@@ -1151,7 +1165,7 @@ class bstree_impl
//!
//! <b>Complexity</b>: Average complexity is at most logarithmic.
//!
- //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
+ //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee.
//!
//! <b>Notes</b>: This function is used to improve performance when constructing
//! a value_type is expensive: if there is an equivalent value
@@ -1166,13 +1180,13 @@ class bstree_impl
//!
//! "commit_data" remains valid for a subsequent "insert_commit" only if no more
//! objects are inserted or erased from the container.
- template<class KeyType, class KeyValueCompare>
+ template<class KeyType, class KeyTypeKeyCompare>
std::pair<iterator, bool> insert_unique_check
- (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data);
+ (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data);
- //! <b>Requires</b>: key_value_comp must be a comparison function that induces
- //! the same strict weak ordering as value_compare. The difference is that
- //! key_value_comp compares an arbitrary key with the contained values.
+ //! <b>Requires</b>: comp must be a comparison function that induces
+ //! the same strict weak ordering as key_compare. The difference is that
+ //! comp compares an arbitrary key with the contained values.
//!
//! <b>Effects</b>: Checks if a value can be inserted in the container, using
//! a user provided key instead of the value itself, using "hint"
@@ -1187,7 +1201,7 @@ class bstree_impl
//! <b>Complexity</b>: Logarithmic in general, but it's amortized
//! constant time if t is inserted immediately before hint.
//!
- //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
+ //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee.
//!
//! <b>Notes</b>: This function is used to improve performance when constructing
//! a value_type is expensive: if there is an equivalent value
@@ -1202,10 +1216,10 @@ class bstree_impl
//!
//! "commit_data" remains valid for a subsequent "insert_commit" only if no more
//! objects are inserted or erased from the container.
- template<class KeyType, class KeyValueCompare>
+ template<class KeyType, class KeyTypeKeyCompare>
std::pair<iterator, bool> insert_unique_check
(const_iterator hint, const KeyType &key
- ,KeyValueCompare key_value_comp, insert_commit_data &commit_data);
+ ,KeyTypeKeyCompare comp, insert_commit_data &commit_data);
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
@@ -1351,8 +1365,8 @@ class bstree_impl
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
- size_type erase(const_reference value)
- { return this->erase(value, this->comp()); }
+ size_type erase(const key_type &key)
+ { return this->erase(key, this->key_comp()); }
//! <b>Effects</b>: Erases all the elements with the given key.
//! according to the comparison functor "comp".
@@ -1365,12 +1379,10 @@ class bstree_impl
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
- template<class KeyType, class KeyValueCompare>
- size_type erase(const KeyType& key, KeyValueCompare comp
- /// @cond
- , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
- /// @endcond
- )
+ template<class KeyType, class KeyTypeKeyCompare>
+ BOOST_INTRUSIVE_DOC1ST(size_type
+ , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)
+ erase(const KeyType& key, KeyTypeKeyCompare comp)
{
std::pair<iterator,iterator> p = this->equal_range(key, comp);
size_type n;
@@ -1398,12 +1410,6 @@ class bstree_impl
return ret;
}
- #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
- template<class Disposer>
- iterator erase_and_dispose(iterator i, Disposer disposer)
- { return this->erase_and_dispose(const_iterator(i), disposer); }
- #endif
-
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
//! <b>Effects</b>: Erases all the elements with the given value.
@@ -1418,9 +1424,9 @@ class bstree_impl
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
template<class Disposer>
- size_type erase_and_dispose(const_reference value, Disposer disposer)
+ size_type erase_and_dispose(const key_type &key, Disposer disposer)
{
- std::pair<iterator,iterator> p = this->equal_range(value);
+ std::pair<iterator,iterator> p = this->equal_range(key);
size_type n;
this->private_erase(p.first, p.second, n, disposer);
return n;
@@ -1456,12 +1462,10 @@ class bstree_impl
//!
//! <b>Note</b>: Invalidates the iterators
//! to the erased elements.
- template<class KeyType, class KeyValueCompare, class Disposer>
- size_type erase_and_dispose(const KeyType& key, KeyValueCompare comp, Disposer disposer
- /// @cond
- , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
- /// @endcond
- )
+ template<class KeyType, class KeyTypeKeyCompare, class Disposer>
+ BOOST_INTRUSIVE_DOC1ST(size_type
+ , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)
+ erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer)
{
std::pair<iterator,iterator> p = this->equal_range(key, comp);
size_type n;
@@ -1512,9 +1516,9 @@ class bstree_impl
//! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
//! to number of objects with the given value.
//!
- //! <b>Throws</b>: If `value_compare` throws.
- size_type count(const_reference value) const
- { return size_type(this->count(value, this->comp())); }
+ //! <b>Throws</b>: If `key_compare` throws.
+ size_type count(const key_type &key) const
+ { return size_type(this->count(key, this->key_comp())); }
//! <b>Effects</b>: Returns the number of contained elements with the given key
//!
@@ -1522,8 +1526,8 @@ class bstree_impl
//! to number of objects with the given key.
//!
//! <b>Throws</b>: If `comp` throws.
- template<class KeyType, class KeyValueCompare>
- size_type count(const KeyType &key, KeyValueCompare comp) const
+ template<class KeyType, class KeyTypeKeyCompare>
+ size_type count(const KeyType &key, KeyTypeKeyCompare comp) const
{
std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp);
size_type n = 0;
@@ -1535,11 +1539,11 @@ class bstree_impl
//Add non-const overloads to theoretically const members
//as some algorithms have different behavior when non-const versions are used (like splay trees).
- size_type count(const_reference value)
- { return size_type(this->count(value, this->comp())); }
+ size_type count(const key_type &key)
+ { return size_type(this->count(key, this->key_comp())); }
- template<class KeyType, class KeyValueCompare>
- size_type count(const KeyType &key, KeyValueCompare comp)
+ template<class KeyType, class KeyTypeKeyCompare>
+ size_type count(const KeyType &key, KeyTypeKeyCompare comp)
{
std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp);
size_type n = 0;
@@ -1554,16 +1558,16 @@ class bstree_impl
//!
//! <b>Complexity</b>: Logarithmic.
//!
- //! <b>Throws</b>: If `value_compare` throws.
- iterator lower_bound(const_reference value);
+ //! <b>Throws</b>: If `key_compare` throws.
+ iterator lower_bound(const key_type &key);
//! <b>Effects</b>: Returns an iterator to the first element whose
//! key is not less than k or end() if that element does not exist.
//!
//! <b>Complexity</b>: Logarithmic.
//!
- //! <b>Throws</b>: If `value_compare` throws.
- const_iterator lower_bound(const_reference value) const;
+ //! <b>Throws</b>: If `key_compare` throws.
+ const_iterator lower_bound(const key_type &key) const;
//! <b>Effects</b>: Returns an iterator to the first element whose
//! key is not less than k or end() if that element does not exist.
@@ -1571,8 +1575,8 @@ class bstree_impl
//! <b>Complexity</b>: Logarithmic.
//!
//! <b>Throws</b>: If `comp` throws.
- template<class KeyType, class KeyValueCompare>
- iterator lower_bound(const KeyType &key, KeyValueCompare comp);
+ template<class KeyType, class KeyTypeKeyCompare>
+ iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp);
//! <b>Effects</b>: Returns a const iterator to the first element whose
//! key is not less than k or end() if that element does not exist.
@@ -1580,16 +1584,16 @@ class bstree_impl
//! <b>Complexity</b>: Logarithmic.
//!
//! <b>Throws</b>: If `comp` throws.
- template<class KeyType, class KeyValueCompare>
- const_iterator lower_bound(const KeyType &key, KeyValueCompare comp) const;
+ template<class KeyType, class KeyTypeKeyCompare>
+ const_iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) const;
//! <b>Effects</b>: Returns an iterator to the first element whose
//! key is greater than k or end() if that element does not exist.
//!
//! <b>Complexity</b>: Logarithmic.
//!
- //! <b>Throws</b>: If `value_compare` throws.
- iterator upper_bound(const_reference value);
+ //! <b>Throws</b>: If `key_compare` throws.
+ iterator upper_bound(const key_type &key);
//! <b>Effects</b>: Returns an iterator to the first element whose
//! key is greater than k according to comp or end() if that element
@@ -1598,16 +1602,16 @@ class bstree_impl
//! <b>Complexity</b>: Logarithmic.
//!
//! <b>Throws</b>: If `comp` throws.
- template<class KeyType, class KeyValueCompare>
- iterator upper_bound(const KeyType &key, KeyValueCompare comp);
+ template<class KeyType, class KeyTypeKeyCompare>
+ iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp);
//! <b>Effects</b>: Returns an iterator to the first element whose
//! key is greater than k or end() if that element does not exist.
//!
//! <b>Complexity</b>: Logarithmic.
//!
- //! <b>Throws</b>: If `value_compare` throws.
- const_iterator upper_bound(const_reference value) const;
+ //! <b>Throws</b>: If `key_compare` throws.
+ const_iterator upper_bound(const key_type &key) const;
//! <b>Effects</b>: Returns an iterator to the first element whose
//! key is greater than k according to comp or end() if that element
@@ -1616,16 +1620,16 @@ class bstree_impl
//! <b>Complexity</b>: Logarithmic.
//!
//! <b>Throws</b>: If `comp` throws.
- template<class KeyType, class KeyValueCompare>
- const_iterator upper_bound(const KeyType &key, KeyValueCompare comp) const;
+ template<class KeyType, class KeyTypeKeyCompare>
+ const_iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) const;
//! <b>Effects</b>: Finds an iterator to the first element whose key is
//! k or end() if that element does not exist.
//!
//! <b>Complexity</b>: Logarithmic.
//!
- //! <b>Throws</b>: If `value_compare` throws.
- iterator find(const_reference value);
+ //! <b>Throws</b>: If `key_compare` throws.
+ iterator find(const key_type &key);
//! <b>Effects</b>: Finds an iterator to the first element whose key is
//! k or end() if that element does not exist.
@@ -1633,16 +1637,16 @@ class bstree_impl
//! <b>Complexity</b>: Logarithmic.
//!
//! <b>Throws</b>: If `comp` throws.
- template<class KeyType, class KeyValueCompare>
- iterator find(const KeyType &key, KeyValueCompare comp);
+ template<class KeyType, class KeyTypeKeyCompare>
+ iterator find(const KeyType &key, KeyTypeKeyCompare comp);
//! <b>Effects</b>: Finds a const_iterator to the first element whose key is
//! k or end() if that element does not exist.
//!
//! <b>Complexity</b>: Logarithmic.
//!
- //! <b>Throws</b>: If `value_compare` throws.
- const_iterator find(const_reference value) const;
+ //! <b>Throws</b>: If `key_compare` throws.
+ const_iterator find(const key_type &key) const;
//! <b>Effects</b>: Finds a const_iterator to the first element whose key is
//! k or end() if that element does not exist.
@@ -1650,8 +1654,8 @@ class bstree_impl
//! <b>Complexity</b>: Logarithmic.
//!
//! <b>Throws</b>: If `comp` throws.
- template<class KeyType, class KeyValueCompare>
- const_iterator find(const KeyType &key, KeyValueCompare comp) const;
+ template<class KeyType, class KeyTypeKeyCompare>
+ const_iterator find(const KeyType &key, KeyTypeKeyCompare comp) const;
//! <b>Effects</b>: Finds a range containing all elements whose key is k or
//! an empty range that indicates the position where those elements would be
@@ -1659,8 +1663,8 @@ class bstree_impl
//!
//! <b>Complexity</b>: Logarithmic.
//!
- //! <b>Throws</b>: If `value_compare` throws.
- std::pair<iterator,iterator> equal_range(const_reference value);
+ //! <b>Throws</b>: If `key_compare` throws.
+ std::pair<iterator,iterator> equal_range(const key_type &key);
//! <b>Effects</b>: Finds a range containing all elements whose key is k or
//! an empty range that indicates the position where those elements would be
@@ -1669,8 +1673,8 @@ class bstree_impl
//! <b>Complexity</b>: Logarithmic.
//!
//! <b>Throws</b>: If `comp` throws.
- template<class KeyType, class KeyValueCompare>
- std::pair<iterator,iterator> equal_range(const KeyType &key, KeyValueCompare comp);
+ template<class KeyType, class KeyTypeKeyCompare>
+ std::pair<iterator,iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp);
//! <b>Effects</b>: Finds a range containing all elements whose key is k or
//! an empty range that indicates the position where those elements would be
@@ -1678,9 +1682,9 @@ class bstree_impl
//!
//! <b>Complexity</b>: Logarithmic.
//!
- //! <b>Throws</b>: If `value_compare` throws.
+ //! <b>Throws</b>: If `key_compare` throws.
std::pair<const_iterator, const_iterator>
- equal_range(const_reference value) const;
+ equal_range(const key_type &key) const;
//! <b>Effects</b>: Finds a range containing all elements whose key is k or
//! an empty range that indicates the position where those elements would be
@@ -1689,12 +1693,12 @@ class bstree_impl
//! <b>Complexity</b>: Logarithmic.
//!
//! <b>Throws</b>: If `comp` throws.
- template<class KeyType, class KeyValueCompare>
+ template<class KeyType, class KeyTypeKeyCompare>
std::pair<const_iterator, const_iterator>
- equal_range(const KeyType &key, KeyValueCompare comp) const;
+ equal_range(const KeyType &key, KeyTypeKeyCompare comp) const;
- //! <b>Requires</b>: 'lower_value' must not be greater than 'upper_value'. If
- //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //! <b>Requires</b>: 'lower_key' must not be greater than 'upper_key'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
//!
//! <b>Effects</b>: Returns an a pair with the following criteria:
//!
@@ -1704,16 +1708,16 @@ class bstree_impl
//!
//! <b>Complexity</b>: Logarithmic.
//!
- //! <b>Throws</b>: If `value_compare` throws.
+ //! <b>Throws</b>: If `key_compare` throws.
//!
//! <b>Note</b>: This function can be more efficient than calling upper_bound
//! and lower_bound for lower_value and upper_value.
//!
//! <b>Note</b>: Experimental function, the interface might change in future releases.
std::pair<iterator,iterator> bounded_range
- (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed);
+ (const key_type &lower_key, const key_type &upper_value, bool left_closed, bool right_closed);
- //! <b>Requires</b>: KeyValueCompare is a function object that induces a strict weak
+ //! <b>Requires</b>: KeyTypeKeyCompare is a function object that induces a strict weak
//! ordering compatible with the strict weak ordering used to create the
//! the container.
//! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
@@ -1733,12 +1737,12 @@ class bstree_impl
//! and lower_bound for lower_key and upper_key.
//!
//! <b>Note</b>: Experimental function, the interface might change in future releases.
- template<class KeyType, class KeyValueCompare>
+ template<class KeyType, class KeyTypeKeyCompare>
std::pair<iterator,iterator> bounded_range
- (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed);
+ (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
- //! <b>Requires</b>: 'lower_value' must not be greater than 'upper_value'. If
- //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //! <b>Requires</b>: 'lower_key' must not be greater than 'upper_key'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
//!
//! <b>Effects</b>: Returns an a pair with the following criteria:
//!
@@ -1748,16 +1752,16 @@ class bstree_impl
//!
//! <b>Complexity</b>: Logarithmic.
//!
- //! <b>Throws</b>: If `value_compare` throws.
+ //! <b>Throws</b>: If `key_compare` throws.
//!
//! <b>Note</b>: This function can be more efficient than calling upper_bound
//! and lower_bound for lower_value and upper_value.
//!
//! <b>Note</b>: Experimental function, the interface might change in future releases.
std::pair<const_iterator,const_iterator> bounded_range
- (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const;
+ (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
- //! <b>Requires</b>: KeyValueCompare is a function object that induces a strict weak
+ //! <b>Requires</b>: KeyTypeKeyCompare is a function object that induces a strict weak
//! ordering compatible with the strict weak ordering used to create the
//! the container.
//! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
@@ -1777,9 +1781,9 @@ class bstree_impl
//! and lower_bound for lower_key and upper_key.
//!
//! <b>Note</b>: Experimental function, the interface might change in future releases.
- template<class KeyType, class KeyValueCompare>
+ template<class KeyType, class KeyTypeKeyCompare>
std::pair<const_iterator,const_iterator> bounded_range
- (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const;
+ (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
//! <b>Requires</b>: value must be an lvalue and shall be in a set of
//! appropriate type. Otherwise the behavior is undefined.
@@ -1936,8 +1940,8 @@ class bstree_impl
template <class ExtraChecker>
void check(ExtraChecker extra_checker) const
{
- typedef detail::key_nodeptr_comp<value_compare, value_traits> nodeptr_comp_t;
- nodeptr_comp_t nodeptr_comp(this->comp(), &this->get_value_traits());
+ typedef detail::key_nodeptr_comp<key_compare, value_traits, key_of_value> nodeptr_comp_t;
+ nodeptr_comp_t nodeptr_comp(this->key_comp(), &this->get_value_traits());
typedef typename get_node_checker<AlgoType, ValueTraits, nodeptr_comp_t, ExtraChecker>::type node_checker_t;
typename node_checker_t::return_type checker_return;
node_algorithms::check(this->header_ptr(), node_checker_t(nodeptr_comp, extra_checker), checker_return);
@@ -1956,6 +1960,32 @@ class bstree_impl
check(detail::empty_node_checker<ValueTraits>());
}
+ friend bool operator==(const bstree_impl &x, const bstree_impl &y)
+ {
+ if(constant_time_size && x.size() != y.size()){
+ return false;
+ }
+ return boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend());
+ }
+
+ friend bool operator!=(const bstree_impl &x, const bstree_impl &y)
+ { return !(x == y); }
+
+ friend bool operator<(const bstree_impl &x, const bstree_impl &y)
+ { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
+
+ friend bool operator>(const bstree_impl &x, const bstree_impl &y)
+ { return y < x; }
+
+ friend bool operator<=(const bstree_impl &x, const bstree_impl &y)
+ { return !(x > y); }
+
+ friend bool operator>=(const bstree_impl &x, const bstree_impl &y)
+ { return !(x < y); }
+
+ friend void swap(bstree_impl &x, bstree_impl &y)
+ { x.swap(y); }
+
/// @cond
private:
template<class Disposer>
@@ -1975,111 +2005,6 @@ class bstree_impl
/// @endcond
};
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-template<class T, class ...Options>
-#else
-template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>
-#endif
-inline bool operator<
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-(const bstree_impl<T, Options...> &x, const bstree_impl<T, Options...> &y)
-#else
-( const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &x
-, const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &y)
-#endif
-{ return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
-
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-template<class T, class ...Options>
-#else
-template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>
-#endif
-bool operator==
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-(const bstree_impl<T, Options...> &x, const bstree_impl<T, Options...> &y)
-#else
-( const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &x
-, const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &y)
-#endif
-{
- typedef bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> tree_type;
-
- if(tree_type::constant_time_size && x.size() != y.size()){
- return false;
- }
- return boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend());
-}
-
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-template<class T, class ...Options>
-#else
-template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>
-#endif
-inline bool operator!=
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-(const bstree_impl<T, Options...> &x, const bstree_impl<T, Options...> &y)
-#else
-( const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &x
-, const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &y)
-#endif
-{ return !(x == y); }
-
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-template<class T, class ...Options>
-#else
-template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>
-#endif
-inline bool operator>
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-(const bstree_impl<T, Options...> &x, const bstree_impl<T, Options...> &y)
-#else
-( const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &x
-, const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &y)
-#endif
-{ return y < x; }
-
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-template<class T, class ...Options>
-#else
-template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>
-#endif
-inline bool operator<=
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-(const bstree_impl<T, Options...> &x, const bstree_impl<T, Options...> &y)
-#else
-( const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &x
-, const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &y)
-#endif
-{ return !(y < x); }
-
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-template<class T, class ...Options>
-#else
-template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>
-#endif
-inline bool operator>=
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-(const bstree_impl<T, Options...> &x, const bstree_impl<T, Options...> &y)
-#else
-( const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &x
-, const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &y)
-#endif
-{ return !(x < y); }
-
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-template<class T, class ...Options>
-#else
-template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>
-#endif
-inline void swap
-#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-(bstree_impl<T, Options...> &x, bstree_impl<T, Options...> &y)
-#else
-( bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &x
-, bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &y)
-#endif
-{ x.swap(y); }
-
//! Helper metafunction to define a \c bstree that yields to the same type when the
//! same options (either explicitly or implicitly) are used.
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
@@ -2087,7 +2012,7 @@ template<class T, class ...Options>
#else
template<class T, class O1 = void, class O2 = void
, class O3 = void, class O4 = void
- , class O5 = void>
+ , class O5 = void, class O6 = void>
#endif
struct make_bstree
{
@@ -2095,7 +2020,7 @@ struct make_bstree
typedef typename pack_options
< bstree_defaults,
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- O1, O2, O3, O4, O5
+ O1, O2, O3, O4, O5, O6
#else
Options...
#endif
@@ -2106,6 +2031,7 @@ struct make_bstree
typedef bstree_impl
< value_traits
+ , typename packed_options::key_of_value
, typename packed_options::compare
, typename packed_options::size_type
, packed_options::constant_time_size
@@ -2120,14 +2046,14 @@ struct make_bstree
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
-template<class T, class O1, class O2, class O3, class O4, class O5>
+template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
#else
template<class T, class ...Options>
#endif
class bstree
: public make_bstree<T,
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- O1, O2, O3, O4, O5
+ O1, O2, O3, O4, O5, O6
#else
Options...
#endif
@@ -2136,7 +2062,7 @@ class bstree
typedef typename make_bstree
<T,
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- O1, O2, O3, O4, O5
+ O1, O2, O3, O4, O5, O6
#else
Options...
#endif
@@ -2144,7 +2070,7 @@ class bstree
BOOST_MOVABLE_BUT_NOT_COPYABLE(bstree)
public:
- typedef typename Base::value_compare value_compare;
+ typedef typename Base::key_compare key_compare;
typedef typename Base::value_traits value_traits;
typedef typename Base::iterator iterator;
typedef typename Base::const_iterator const_iterator;
@@ -2152,14 +2078,14 @@ class bstree
//Assert if passed value traits are compatible with the type
BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
- bstree( const value_compare &cmp = value_compare()
+ bstree( const key_compare &cmp = key_compare()
, const value_traits &v_traits = value_traits())
: Base(cmp, v_traits)
{}
template<class Iterator>
bstree( bool unique, Iterator b, Iterator e
- , const value_compare &cmp = value_compare()
+ , const key_compare &cmp = key_compare()
, const value_traits &v_traits = value_traits())
: Base(unique, b, e, cmp, v_traits)
{}
@@ -2171,6 +2097,14 @@ class bstree
bstree& operator=(BOOST_RV_REF(bstree) x)
{ return static_cast<bstree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
+ template <class Cloner, class Disposer>
+ void clone_from(const bstree &src, Cloner cloner, Disposer disposer)
+ { Base::clone_from(src, cloner, disposer); }
+
+ template <class Cloner, class Disposer>
+ void clone_from(BOOST_RV_REF(bstree) src, Cloner cloner, Disposer disposer)
+ { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
+
static bstree &container_from_end_iterator(iterator end_iterator)
{ return static_cast<bstree &>(Base::container_from_end_iterator(end_iterator)); }