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.hpp375
1 files changed, 124 insertions, 251 deletions
diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp
index 14a1f150c5..843ad3cb78 100644
--- a/boost/container/detail/tree.hpp
+++ b/boost/container/detail/tree.hpp
@@ -52,8 +52,7 @@
#include <boost/move/detail/fwd_macros.hpp>
#endif
#include <boost/move/detail/move_helpers.hpp>
-// other
-#include <boost/core/no_exceptions_support.hpp>
+#include <boost/move/detail/force_ptr.hpp>
@@ -120,104 +119,9 @@ struct tree_internal_data_type< std::pair<T1, T2> >
typedef pair<typename boost::move_detail::remove_const<T1>::type, T2> type;
};
-//The node to be store in the tree
template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
-struct tree_node
- : public intrusive_tree_hook<VoidPointer, tree_type_value, OptimizeSize>::type
+struct iiterator_node_value_type< base_node<T, intrusive_tree_hook<VoidPointer, tree_type_value, OptimizeSize>, true > >
{
- public:
- typedef typename intrusive_tree_hook
- <VoidPointer, tree_type_value, OptimizeSize>::type hook_type;
- typedef T value_type;
- typedef typename tree_internal_data_type<T>::type internal_type;
-
- typedef tree_node< T, VoidPointer
- , tree_type_value, OptimizeSize> node_t;
-
- typedef typename boost::container::dtl::aligned_storage
- <sizeof(T), boost::container::dtl::alignment_of<T>::value>::type storage_t;
- storage_t m_storage;
-
- #if defined(BOOST_GCC) && (BOOST_GCC >= 40600) && (BOOST_GCC < 80000)
- #pragma GCC diagnostic push
- #pragma GCC diagnostic ignored "-Wstrict-aliasing"
- #define BOOST_CONTAINER_DISABLE_ALIASING_WARNING
- # endif
-
- BOOST_CONTAINER_FORCEINLINE T &get_data()
- { return *reinterpret_cast<T*>(this->m_storage.data); }
-
- BOOST_CONTAINER_FORCEINLINE const T &get_data() const
- { return *reinterpret_cast<const T*>(this->m_storage.data); }
-
- BOOST_CONTAINER_FORCEINLINE T *get_data_ptr()
- { return reinterpret_cast<T*>(this->m_storage.data); }
-
- BOOST_CONTAINER_FORCEINLINE const T *get_data_ptr() const
- { return reinterpret_cast<T*>(this->m_storage.data); }
-
- BOOST_CONTAINER_FORCEINLINE internal_type &get_real_data()
- { return *reinterpret_cast<internal_type*>(this->m_storage.data); }
-
- BOOST_CONTAINER_FORCEINLINE const internal_type &get_real_data() const
- { return *reinterpret_cast<const internal_type*>(this->m_storage.data); }
-
- BOOST_CONTAINER_FORCEINLINE internal_type *get_real_data_ptr()
- { return reinterpret_cast<internal_type*>(this->m_storage.data); }
-
- BOOST_CONTAINER_FORCEINLINE const internal_type *get_real_data_ptr() const
- { return reinterpret_cast<internal_type*>(this->m_storage.data); }
-
- BOOST_CONTAINER_FORCEINLINE ~tree_node()
- { reinterpret_cast<internal_type*>(this->m_storage.data)->~internal_type(); }
-
- #if defined(BOOST_CONTAINER_DISABLE_ALIASING_WARNING)
- #pragma GCC diagnostic pop
- #undef BOOST_CONTAINER_DISABLE_ALIASING_WARNING
- # endif
-
- BOOST_CONTAINER_FORCEINLINE void destroy_header()
- { static_cast<hook_type*>(this)->~hook_type(); }
-
- template<class T1, class T2>
- BOOST_CONTAINER_FORCEINLINE void do_assign(const std::pair<const T1, T2> &p)
- {
- const_cast<T1&>(this->get_real_data().first) = p.first;
- this->get_real_data().second = p.second;
- }
-
- template<class T1, class T2>
- BOOST_CONTAINER_FORCEINLINE void do_assign(const pair<const T1, T2> &p)
- {
- const_cast<T1&>(this->get_real_data().first) = p.first;
- this->get_real_data().second = p.second;
- }
-
- template<class V>
- BOOST_CONTAINER_FORCEINLINE void do_assign(const V &v)
- { this->get_real_data() = v; }
-
- template<class T1, class T2>
- BOOST_CONTAINER_FORCEINLINE void do_move_assign(std::pair<const T1, T2> &p)
- {
- const_cast<T1&>(this->get_real_data().first) = ::boost::move(p.first);
- this->get_real_data().second = ::boost::move(p.second);
- }
-
- template<class T1, class T2>
- BOOST_CONTAINER_FORCEINLINE void do_move_assign(pair<const T1, T2> &p)
- {
- const_cast<T1&>(this->get_real_data().first) = ::boost::move(p.first);
- this->get_real_data().second = ::boost::move(p.second);
- }
-
- template<class V>
- BOOST_CONTAINER_FORCEINLINE void do_move_assign(V &v)
- { this->get_real_data() = ::boost::move(v); }
-};
-
-template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
-struct iiterator_node_value_type< tree_node<T, VoidPointer, tree_type_value, OptimizeSize> > {
typedef T type;
};
@@ -253,88 +157,95 @@ class push_back_functor
namespace dtl {
-template< class NodeType, class NodeCompareType
- , class SizeType, class HookType
+template< class NodeType
+ , class KeyOfNode
+ , class KeyCompare
+ , class HookType
, boost::container::tree_type_enum tree_type_value>
struct intrusive_tree_dispatch;
-template<class NodeType, class NodeCompareType, class SizeType, class HookType>
+template<class NodeType, class KeyOfNode, class KeyCompare, class HookType>
struct intrusive_tree_dispatch
- <NodeType, NodeCompareType, SizeType, HookType, boost::container::red_black_tree>
+ <NodeType, KeyOfNode, KeyCompare, HookType, boost::container::red_black_tree>
{
typedef typename dtl::bi::make_rbtree
<NodeType
- ,dtl::bi::compare<NodeCompareType>
+ ,dtl::bi::key_of_value<KeyOfNode>
+ ,dtl::bi::compare<KeyCompare>
,dtl::bi::base_hook<HookType>
,dtl::bi::constant_time_size<true>
- ,dtl::bi::size_type<SizeType>
>::type type;
};
-template<class NodeType, class NodeCompareType, class SizeType, class HookType>
+template<class NodeType, class KeyOfNode, class KeyCompare, class HookType>
struct intrusive_tree_dispatch
- <NodeType, NodeCompareType, SizeType, HookType, boost::container::avl_tree>
+ <NodeType, KeyOfNode, KeyCompare, HookType, boost::container::avl_tree>
{
typedef typename dtl::bi::make_avltree
<NodeType
- ,dtl::bi::compare<NodeCompareType>
+ ,dtl::bi::key_of_value<KeyOfNode>
+ ,dtl::bi::compare<KeyCompare>
,dtl::bi::base_hook<HookType>
,dtl::bi::constant_time_size<true>
- ,dtl::bi::size_type<SizeType>
>::type type;
};
-template<class NodeType, class NodeCompareType, class SizeType, class HookType>
+template<class NodeType, class KeyOfNode, class KeyCompare, class HookType>
struct intrusive_tree_dispatch
- <NodeType, NodeCompareType, SizeType, HookType, boost::container::scapegoat_tree>
+ <NodeType, KeyOfNode, KeyCompare, HookType, boost::container::scapegoat_tree>
{
typedef typename dtl::bi::make_sgtree
<NodeType
- ,dtl::bi::compare<NodeCompareType>
+ ,dtl::bi::key_of_value<KeyOfNode>
+ ,dtl::bi::compare<KeyCompare>
,dtl::bi::base_hook<HookType>
,dtl::bi::floating_point<true>
- ,dtl::bi::size_type<SizeType>
>::type type;
};
-template<class NodeType, class NodeCompareType, class SizeType, class HookType>
+template<class NodeType, class KeyOfNode, class KeyCompare, class HookType>
struct intrusive_tree_dispatch
- <NodeType, NodeCompareType, SizeType, HookType, boost::container::splay_tree>
+ <NodeType, KeyOfNode, KeyCompare, HookType, boost::container::splay_tree>
{
typedef typename dtl::bi::make_splaytree
<NodeType
- ,dtl::bi::compare<NodeCompareType>
+ ,dtl::bi::key_of_value<KeyOfNode>
+ ,dtl::bi::compare<KeyCompare>
,dtl::bi::base_hook<HookType>
,dtl::bi::constant_time_size<true>
- ,dtl::bi::size_type<SizeType>
>::type type;
};
-template<class Allocator, class ValueCompare, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
+template < class Allocator
+ , class KeyOfValue
+ , class KeyCompare
+ , boost::container::tree_type_enum tree_type_value
+ , bool OptimizeSize>
struct intrusive_tree_type
{
private:
typedef typename boost::container::
- allocator_traits<Allocator>::value_type value_type;
+ allocator_traits<Allocator>::value_type value_type;
typedef typename boost::container::
- allocator_traits<Allocator>::void_pointer void_pointer;
- typedef typename boost::container::
- allocator_traits<Allocator>::size_type size_type;
- typedef typename dtl::tree_node
- < value_type, void_pointer
- , tree_type_value, OptimizeSize> node_t;
- typedef value_to_node_compare
- <node_t, ValueCompare> node_compare_type;
+ allocator_traits<Allocator>::void_pointer void_pointer;
+ typedef base_node<value_type, intrusive_tree_hook
+ <void_pointer, tree_type_value, OptimizeSize>, true > node_t;
//Deducing the hook type from node_t (e.g. node_t::hook_type) would
//provoke an early instantiation of node_t that could ruin recursive
//tree definitions, so retype the complete type to avoid any problem.
typedef typename intrusive_tree_hook
<void_pointer, tree_type_value
- , OptimizeSize>::type hook_type;
+ , OptimizeSize>::type hook_type;
+
+ typedef key_of_node
+ <node_t, KeyOfValue> key_of_node_t;
+
public:
typedef typename intrusive_tree_dispatch
- < node_t, node_compare_type
- , size_type, hook_type
+ < node_t
+ , key_of_node_t
+ , KeyCompare
+ , hook_type
, tree_type_value>::type type;
};
@@ -387,10 +298,10 @@ class RecyclingCloner
: m_holder(holder), m_icont(itree)
{}
- BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, node_t &other, bool_<true>)
+ BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type p, node_t &other, bool_<true>)
{ p->do_move_assign(other.get_real_data()); }
- BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<false>)
+ BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type p, const node_t &other, bool_<false>)
{ p->do_assign(other.get_real_data()); }
node_ptr_type operator()
@@ -398,20 +309,20 @@ class RecyclingCloner
{
if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){
//First recycle a node (this can't throw)
- BOOST_TRY{
+ BOOST_CONTAINER_TRY{
//This can throw
this->do_assign(p, other, bool_<DoMove>());
return p;
}
- BOOST_CATCH(...){
+ BOOST_CONTAINER_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);
}
- BOOST_RETHROW
+ BOOST_CONTAINER_RETHROW
}
- BOOST_CATCH_END
+ BOOST_CONTAINER_CATCH_END
}
else{
return m_holder.create_node(boost::move(other.get_real_data()));
@@ -422,57 +333,6 @@ class RecyclingCloner
intrusive_container &m_icont;
};
-
-template<class KeyCompare, class KeyOfValue>
-struct key_node_compare
- : public boost::intrusive::detail::ebo_functor_holder<KeyCompare>
-{
- BOOST_CONTAINER_FORCEINLINE explicit key_node_compare(const KeyCompare &comp)
- : base_t(comp)
- {}
-
- typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t;
- typedef KeyCompare key_compare;
- typedef KeyOfValue key_of_value;
- typedef typename KeyOfValue::type key_type;
-
-
- template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
- BOOST_CONTAINER_FORCEINLINE static const key_type &
- key_from(const tree_node<T, VoidPointer, tree_type_value, OptimizeSize> &n)
- {
- return key_of_value()(n.get_data());
- }
-
- template <class T>
- BOOST_CONTAINER_FORCEINLINE static const T &
- key_from(const T &t)
- {
- return t;
- }
-
- BOOST_CONTAINER_FORCEINLINE const key_compare &key_comp() const
- { return static_cast<const key_compare &>(*this); }
-
- BOOST_CONTAINER_FORCEINLINE key_compare &key_comp()
- { return static_cast<key_compare &>(*this); }
-
- BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const
- { return this->key_comp()(key1, key2); }
-
- template<class U>
- BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const U &nonkey2) const
- { return this->key_comp()(key1, this->key_from(nonkey2)); }
-
- template<class U>
- BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2) const
- { return this->key_comp()(this->key_from(nonkey1), key2); }
-
- template<class U, class V>
- BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const V &nonkey2) const
- { return this->key_comp()(this->key_from(nonkey1), this->key_from(nonkey2)); }
-};
-
template<class Options>
struct get_tree_opt
{
@@ -486,40 +346,47 @@ struct get_tree_opt<void>
};
template<class, class KeyOfValue>
-struct real_key_of_value
+struct tree_key_of_value
{
typedef KeyOfValue type;
};
template<class T>
-struct real_key_of_value<T, void>
+struct tree_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>
+struct tree_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>
+struct tree_key_of_value<boost::container::dtl::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
- < typename real_allocator<T, Allocator>::type
- , typename dtl::intrusive_tree_type
+struct make_intrusive_tree_type
+ : dtl::intrusive_tree_type
< 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>
+ , typename tree_key_of_value<T, KeyOfValue>::type
+ , Compare
, get_tree_opt<Options>::type::tree_type
, get_tree_opt<Options>::type::optimize_size
- >::type
+ >
+{};
+
+
+template <class T, class KeyOfValue, class Compare, class Allocator, class Options>
+class tree
+ : public dtl::node_alloc_holder
+ < typename real_allocator<T, Allocator>::type
+ , typename make_intrusive_tree_type<T, KeyOfValue, Compare, Allocator, Options>::type
>
{
typedef tree < T, KeyOfValue
@@ -529,17 +396,14 @@ class tree
private:
typedef allocator_traits<allocator_type> allocator_traits_t;
- typedef typename real_key_of_value<T, KeyOfValue>::type key_of_value_t;
+ typedef typename tree_key_of_value<T, KeyOfValue>::type key_of_value_t;
typedef tree_value_compare
< 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_type, ValComp
- , options_type::tree_type
- , options_type::optimize_size
- >::type Icont;
+ typedef typename make_intrusive_tree_type
+ <T, KeyOfValue, Compare, Allocator, Options>::type Icont;
typedef dtl::node_alloc_holder
<allocator_type, Icont> AllocHolder;
typedef typename AllocHolder::NodePtr NodePtr;
@@ -551,7 +415,7 @@ class tree
typedef typename AllocHolder::Node Node;
typedef typename Icont::iterator iiterator;
typedef typename Icont::const_iterator iconst_iterator;
- typedef dtl::allocator_destroyer<NodeAlloc> Destroyer;
+ typedef dtl::allocator_node_destroyer<NodeAlloc> Destroyer;
typedef typename AllocHolder::alloc_version alloc_version;
typedef intrusive_tree_proxy<options_type::tree_type> intrusive_tree_proxy_t;
@@ -559,7 +423,8 @@ class tree
public:
- typedef typename key_of_value_t::type key_type;
+ typedef typename dtl::remove_const
+ <typename key_of_value_t::type>::type key_type;
typedef T value_type;
typedef Compare key_compare;
typedef ValComp value_compare;
@@ -592,7 +457,7 @@ class tree
private:
- typedef key_node_compare<key_compare, key_of_value_t> KeyNodeCompare;
+ typedef key_node_pred<key_compare, key_of_value_t, Node> KeyNodeCompare;
public:
@@ -711,7 +576,7 @@ class tree
{
//Optimized allocation and construction
this->allocate_many_and_construct
- ( first, boost::container::iterator_distance(first, last)
+ ( first, boost::container::iterator_udistance(first, last)
, insert_equal_end_hint_functor<Node, Icont>(this->icont()));
}
@@ -728,7 +593,7 @@ class tree
{
//Optimized allocation and construction
this->allocate_many_and_construct
- ( first, boost::container::iterator_distance(first, last)
+ ( first, boost::container::iterator_udistance(first, last)
, dtl::push_back_functor<Node, Icont>(this->icont()));
//AllocHolder clears in case of exception
}
@@ -866,11 +731,11 @@ class tree
// accessors:
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
value_compare value_comp() const
- { return this->icont().value_comp().predicate(); }
+ { return value_compare(this->key_comp()); }
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
key_compare key_comp() const
- { return this->icont().value_comp().predicate().key_comp(); }
+ { return this->icont().key_comp(); }
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
allocator_type get_allocator() const
@@ -981,7 +846,7 @@ class tree
(const key_type& key, insert_commit_data &data)
{
std::pair<iiterator, bool> ret =
- this->icont().insert_unique_check(key, KeyNodeCompare(key_comp()), data);
+ this->icont().insert_unique_check(key, data);
return std::pair<iterator, bool>(iterator(ret.first), ret.second);
}
@@ -990,7 +855,7 @@ class tree
{
BOOST_ASSERT((priv_is_linked)(hint));
std::pair<iiterator, bool> ret =
- this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(key_comp()), data);
+ this->icont().insert_unique_check(hint.get(), key, data);
return std::pair<iterator, bool>(iterator(ret.first), ret.second);
}
@@ -999,7 +864,7 @@ class tree
(BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data)
{
NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v));
- scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
iterator ret(this->icont().insert_unique_commit(*tmp, data));
destroy_deallocator.release();
return ret;
@@ -1037,7 +902,7 @@ class tree
(BOOST_FWD_REF(KeyConvertible) key, BOOST_FWD_REF(M) obj, insert_commit_data &data)
{
NodePtr tmp = AllocHolder::create_node(boost::forward<KeyConvertible>(key), boost::forward<M>(obj));
- scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
iiterator ret(this->icont().insert_unique_commit(*tmp, data));
destroy_deallocator.release();
return ret;
@@ -1064,7 +929,7 @@ class tree
{
value_type &v = p->get_data();
insert_commit_data data;
- scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc());
+ scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc());
std::pair<iterator,bool> ret =
this->insert_unique_check(key_of_value_t()(v), data);
if(!ret.second){
@@ -1108,7 +973,7 @@ class tree
iterator emplace_equal(BOOST_FWD_REF(Args)... args)
{
NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
- scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
destroy_deallocator.release();
return ret;
@@ -1119,7 +984,7 @@ class tree
{
BOOST_ASSERT((priv_is_linked)(hint));
NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
- scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
iterator ret(this->icont().insert_equal(hint.get(), *tmp));
destroy_deallocator.release();
return ret;
@@ -1132,8 +997,8 @@ class tree
insert_commit_data data;
const key_type & k = key; //Support emulated rvalue references
std::pair<iiterator, bool> ret =
- hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)
- : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);
+ hint == const_iterator() ? this->icont().insert_unique_check( k, data)
+ : this->icont().insert_unique_check(hint.get(), k, data);
if(ret.second){
ret.first = this->icont().insert_unique_commit
(*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key), boost::forward<Args>(args)...), data);
@@ -1156,7 +1021,7 @@ class tree
iterator emplace_equal(BOOST_MOVE_UREF##N)\
{\
NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
- scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
+ scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\
destroy_deallocator.release();\
return ret;\
@@ -1167,7 +1032,7 @@ class tree
{\
BOOST_ASSERT((priv_is_linked)(hint));\
NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
- scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
+ scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
iterator ret(this->icont().insert_equal(hint.get(), *tmp));\
destroy_deallocator.release();\
return ret;\
@@ -1180,8 +1045,8 @@ class tree
insert_commit_data data;\
const key_type & k = key;\
std::pair<iiterator, bool> ret =\
- hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)\
- : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);\
+ hint == const_iterator() ? this->icont().insert_unique_check( k, data)\
+ : this->icont().insert_unique_check(hint.get(), k, data);\
if(ret.second){\
ret.first = this->icont().insert_unique_commit\
(*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N), data);\
@@ -1207,7 +1072,7 @@ class tree
iterator insert_equal_convertible(BOOST_FWD_REF(MovableConvertible) v)
{
NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
- scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
destroy_deallocator.release();
return ret;
@@ -1218,7 +1083,7 @@ class tree
{
BOOST_ASSERT((priv_is_linked)(hint));
NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
- scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ scoped_node_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
iterator ret(this->icont().insert_equal(hint.get(), *tmp));
destroy_deallocator.release();
return ret;
@@ -1240,8 +1105,8 @@ class tree
insert_commit_data data;
const key_type & k = key; //Support emulated rvalue references
std::pair<iiterator, bool> ret =
- hint == const_iterator() ? this->icont().insert_unique_check(k, KeyNodeCompare(key_comp()), data)
- : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);
+ hint == const_iterator() ? this->icont().insert_unique_check(k, data)
+ : this->icont().insert_unique_check(hint.get(), k, data);
if(ret.second){
ret.first = this->priv_insert_or_assign_commit(boost::forward<KeyType>(key), boost::forward<M>(obj), data);
}
@@ -1258,7 +1123,16 @@ class tree
}
BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& k)
- { return AllocHolder::erase_key(k, KeyNodeCompare(key_comp()), alloc_version()); }
+ { return AllocHolder::erase_key(k, alloc_version()); }
+
+ size_type erase_unique(const key_type& k)
+ {
+ iterator i = this->find(k);
+ size_type ret = static_cast<size_type>(i != this->end());
+ if (ret)
+ this->erase(i);
+ return ret;
+ }
iterator erase(const_iterator first, const_iterator last)
{
@@ -1348,33 +1222,33 @@ class tree
// so splay implementations can to their rebalancing when searching in non-const versions
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
iterator find(const key_type& k)
- { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); }
+ { return iterator(this->icont().find(k)); }
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
const_iterator find(const key_type& k) const
- { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); }
+ { return const_iterator(this->non_const_icont().find(k)); }
template <class K>
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
typename dtl::enable_if_transparent<key_compare, K, iterator>::type
find(const K& k)
- { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); }
+ { return iterator(this->icont().find(k, KeyNodeCompare())); }
template <class K>
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
find(const K& k) const
- { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); }
+ { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare())); }
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
size_type count(const key_type& k) const
- { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); }
+ { return size_type(this->icont().count(k)); }
template <class K>
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
typename dtl::enable_if_transparent<key_compare, K, size_type>::type
count(const K& k) const
- { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); }
+ { return size_type(this->icont().count(k, KeyNodeCompare())); }
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
bool contains(const key_type& x) const
@@ -1388,49 +1262,48 @@ class tree
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
iterator lower_bound(const key_type& k)
- { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
+ { return iterator(this->icont().lower_bound(k)); }
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
const_iterator lower_bound(const key_type& k) const
- { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
+ { return const_iterator(this->non_const_icont().lower_bound(k)); }
template <class K>
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
typename dtl::enable_if_transparent<key_compare, K, iterator>::type
lower_bound(const K& k)
- { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
+ { return iterator(this->icont().lower_bound(k, KeyNodeCompare())); }
template <class K>
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
lower_bound(const K& k) const
- { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); }
+ { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare())); }
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
iterator upper_bound(const key_type& k)
- { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
+ { return iterator(this->icont().upper_bound(k)); }
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
const_iterator upper_bound(const key_type& k) const
- { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
+ { return const_iterator(this->non_const_icont().upper_bound(k)); }
template <class K>
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
typename dtl::enable_if_transparent<key_compare, K, iterator>::type
upper_bound(const K& k)
- { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
+ { return iterator(this->icont().upper_bound(k, KeyNodeCompare())); }
template <class K>
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
upper_bound(const K& k) const
- { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); }
+ { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare())); }
BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
std::pair<iterator,iterator> equal_range(const key_type& k)
{
- std::pair<iiterator, iiterator> ret =
- this->icont().equal_range(k, KeyNodeCompare(key_comp()));
+ std::pair<iiterator, iiterator> ret = this->icont().equal_range(k);
return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
}
@@ -1438,7 +1311,7 @@ class tree
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(key_comp()));
+ this->non_const_icont().equal_range(k);
return std::pair<const_iterator,const_iterator>
(const_iterator(ret.first), const_iterator(ret.second));
}
@@ -1449,7 +1322,7 @@ class tree
equal_range(const K& k)
{
std::pair<iiterator, iiterator> ret =
- this->icont().equal_range(k, KeyNodeCompare(key_comp()));
+ this->icont().equal_range(k, KeyNodeCompare());
return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
}
@@ -1459,7 +1332,7 @@ class tree
equal_range(const K& k) const
{
std::pair<iiterator, iiterator> ret =
- this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp()));
+ this->non_const_icont().equal_range(k, KeyNodeCompare());
return std::pair<const_iterator,const_iterator>
(const_iterator(ret.first), const_iterator(ret.second));
}
@@ -1468,7 +1341,7 @@ class tree
std::pair<iterator,iterator> lower_bound_range(const key_type& k)
{
std::pair<iiterator, iiterator> ret =
- this->icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
+ this->icont().lower_bound_range(k);
return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
}
@@ -1476,7 +1349,7 @@ class tree
std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
{
std::pair<iiterator, iiterator> ret =
- this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
+ this->non_const_icont().lower_bound_range(k);
return std::pair<const_iterator,const_iterator>
(const_iterator(ret.first), const_iterator(ret.second));
}
@@ -1487,7 +1360,7 @@ class tree
lower_bound_range(const K& k)
{
std::pair<iiterator, iiterator> ret =
- this->icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
+ this->icont().lower_bound_range(k, KeyNodeCompare());
return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
}
@@ -1497,7 +1370,7 @@ class tree
lower_bound_range(const K& k) const
{
std::pair<iiterator, iiterator> ret =
- this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp()));
+ this->non_const_icont().lower_bound_range(k, KeyNodeCompare());
return std::pair<const_iterator,const_iterator>
(const_iterator(ret.first), const_iterator(ret.second));
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-23 18:53:34 +0000