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.hpp343
1 files changed, 178 insertions, 165 deletions
diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp
index e59bca0887..0f90b5a4e2 100644
--- a/boost/container/detail/tree.hpp
+++ b/boost/container/detail/tree.hpp
@@ -11,62 +11,66 @@
#ifndef BOOST_CONTAINER_TREE_HPP
#define BOOST_CONTAINER_TREE_HPP
-#if defined(_MSC_VER)
+#ifndef BOOST_CONFIG_HPP
+# include <boost/config.hpp>
+#endif
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
# pragma once
#endif
#include <boost/container/detail/config_begin.hpp>
#include <boost/container/detail/workaround.hpp>
+// container
+#include <boost/container/allocator_traits.hpp>
#include <boost/container/container_fwd.hpp>
+#include <boost/container/options.hpp>
-#include <boost/container/detail/utilities.hpp>
+// container/detail
+#include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
+#include <boost/container/detail/compare_functors.hpp>
+#include <boost/container/detail/destroyers.hpp>
+#include <boost/container/detail/iterator.hpp>
#include <boost/container/detail/iterators.hpp>
-#include <boost/container/detail/algorithms.hpp>
#include <boost/container/detail/node_alloc_holder.hpp>
-#include <boost/container/detail/destroyers.hpp>
#include <boost/container/detail/pair.hpp>
#include <boost/container/detail/type_traits.hpp>
-#include <boost/container/allocator_traits.hpp>
-#include <boost/container/options.hpp>
-
-//
+// intrusive
#include <boost/intrusive/pointer_traits.hpp>
#include <boost/intrusive/rbtree.hpp>
#include <boost/intrusive/avltree.hpp>
#include <boost/intrusive/splaytree.hpp>
#include <boost/intrusive/sgtree.hpp>
-//
+// intrusive/detail
+#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
+// move
#include <boost/move/utility_core.hpp>
-#include <boost/type_traits/has_trivial_destructor.hpp>
-#include <boost/core/no_exceptions_support.hpp>
-//
-#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
-#include <boost/container/detail/preprocessor.hpp>
+// move/detail
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+#include <boost/move/detail/fwd_macros.hpp>
#endif
-
-#include <utility> //std::pair
-#include <iterator>
-#include <algorithm>
+// other
+#include <boost/core/no_exceptions_support.hpp>
namespace boost {
namespace container {
namespace container_detail {
-template<class Key, class Value, class KeyCompare, class KeyOfValue>
+template<class Key, class T, class Compare, class KeyOfValue>
struct tree_value_compare
- : public KeyCompare
+ : public Compare
{
- typedef Value value_type;
- typedef KeyCompare key_compare;
+ typedef T value_type;
+ typedef Compare key_compare;
typedef KeyOfValue key_of_value;
typedef Key key_type;
explicit tree_value_compare(const key_compare &kcomp)
- : KeyCompare(kcomp)
+ : Compare(kcomp)
{}
tree_value_compare()
- : KeyCompare()
+ : Compare()
{}
const key_compare &key_comp() const
@@ -75,25 +79,29 @@ struct tree_value_compare
key_compare &key_comp()
{ return static_cast<key_compare &>(*this); }
- template<class T>
+ template<class U>
struct is_key
{
- static const bool value = is_same<const T, const key_type>::value;
+ static const bool value = is_same<const U, const key_type>::value;
};
- template<class T>
- typename enable_if_c<is_key<T>::value, const key_type &>::type
- key_forward(const T &key) const
+ template<class U>
+ typename enable_if_c<is_key<U>::value, const key_type &>::type
+ key_forward(const U &key) const
{ return key; }
- template<class T>
- typename enable_if_c<!is_key<T>::value, const key_type &>::type
- key_forward(const T &key) const
+ template<class U>
+ typename enable_if_c<!is_key<U>::value, const key_type &>::type
+ key_forward(const U &key) const
{ return KeyOfValue()(key); }
template<class KeyType, class KeyType2>
bool operator()(const KeyType &key1, const KeyType2 &key2) const
{ return key_compare::operator()(this->key_forward(key1), this->key_forward(key2)); }
+
+ template<class KeyType, class KeyType2>
+ bool operator()(const KeyType &key1, const KeyType2 &key2)
+ { return key_compare::operator()(this->key_forward(key1), this->key_forward(key2)); }
};
template<class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
@@ -183,17 +191,17 @@ struct tree_node
internal_type m_data;
- template<class A, class B>
- void do_assign(const std::pair<const A, B> &p)
+ template<class T1, class T2>
+ void do_assign(const std::pair<const T1, T2> &p)
{
- const_cast<A&>(m_data.first) = p.first;
+ const_cast<T1&>(m_data.first) = p.first;
m_data.second = p.second;
}
- template<class A, class B>
- void do_assign(const pair<const A, B> &p)
+ template<class T1, class T2>
+ void do_assign(const pair<const T1, T2> &p)
{
- const_cast<A&>(m_data.first) = p.first;
+ const_cast<T1&>(m_data.first) = p.first;
m_data.second = p.second;
}
@@ -201,17 +209,17 @@ struct tree_node
void do_assign(const V &v)
{ m_data = v; }
- template<class A, class B>
- void do_move_assign(std::pair<const A, B> &p)
+ template<class T1, class T2>
+ void do_move_assign(std::pair<const T1, T2> &p)
{
- const_cast<A&>(m_data.first) = ::boost::move(p.first);
+ const_cast<T1&>(m_data.first) = ::boost::move(p.first);
m_data.second = ::boost::move(p.second);
}
- template<class A, class B>
- void do_move_assign(pair<const A, B> &p)
+ template<class T1, class T2>
+ void do_move_assign(pair<const T1, T2> &p)
{
- const_cast<A&>(m_data.first) = ::boost::move(p.first);
+ const_cast<T1&>(m_data.first) = ::boost::move(p.first);
m_data.second = ::boost::move(p.second);
}
@@ -314,20 +322,21 @@ struct intrusive_tree_dispatch
>::type type;
};
-template<class A, class ValueCompare, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
+template<class Allocator, class ValueCompare, boost::container::tree_type_enum tree_type_value, bool OptimizeSize>
struct intrusive_tree_type
{
private:
typedef typename boost::container::
- allocator_traits<A>::value_type value_type;
+ allocator_traits<Allocator>::value_type value_type;
typedef typename boost::container::
- allocator_traits<A>::void_pointer void_pointer;
+ allocator_traits<Allocator>::void_pointer void_pointer;
typedef typename boost::container::
- allocator_traits<A>::size_type size_type;
+ allocator_traits<Allocator>::size_type size_type;
typedef typename container_detail::tree_node
< value_type, void_pointer
, tree_type_value, OptimizeSize> node_type;
- typedef node_compare<ValueCompare, node_type> node_compare_type;
+ typedef value_to_node_compare
+ <node_type, ValueCompare> node_compare_type;
//Deducing the hook type from node_type (e.g. node_type::hook_type) would
//provoke an early instantiation of node_type that could ruin recursive
//tree definitions, so retype the complete type to avoid any problem.
@@ -391,10 +400,10 @@ class RecyclingCloner
{}
static void do_assign(node_ptr_type &p, const node_type &other, bool_<true>)
- { p->do_assign(other.m_data); }
+ { p->do_move_assign(const_cast<node_type &>(other).m_data); }
static void do_assign(node_ptr_type &p, const node_type &other, bool_<false>)
- { p->do_move_assign(const_cast<node_type &>(other).m_data); }
+ { p->do_assign(other.m_data); }
node_ptr_type operator()(const node_type &other) const
{
@@ -425,7 +434,7 @@ class RecyclingCloner
};
template<class KeyValueCompare, class Node>
-//where KeyValueCompare is tree_value_compare<Key, Value, KeyCompare, KeyOfValue>
+//where KeyValueCompare is tree_value_compare<Key, T, Compare, KeyOfValue>
struct key_node_compare
: private KeyValueCompare
{
@@ -454,35 +463,35 @@ struct key_node_compare
{ return KeyValueCompare::operator()(this->key_forward(key1), this->key_forward(key2)); }
};
-template <class Key, class Value, class KeyOfValue,
- class KeyCompare, class A,
+template <class Key, class T, class KeyOfValue,
+ class Compare, class Allocator,
class Options = tree_assoc_defaults>
class tree
: protected container_detail::node_alloc_holder
- < A
+ < Allocator
, typename container_detail::intrusive_tree_type
- < A, tree_value_compare<Key, Value, KeyCompare, KeyOfValue> //ValComp
+ < Allocator, tree_value_compare<Key, T, Compare, KeyOfValue> //ValComp
, Options::tree_type, Options::optimize_size>::type
>
{
typedef tree_value_compare
- <Key, Value, KeyCompare, KeyOfValue> ValComp;
+ <Key, T, Compare, KeyOfValue> ValComp;
typedef typename container_detail::intrusive_tree_type
- < A, ValComp, Options::tree_type
+ < Allocator, ValComp, Options::tree_type
, Options::optimize_size>::type Icont;
typedef container_detail::node_alloc_holder
- <A, Icont> AllocHolder;
+ <Allocator, Icont> AllocHolder;
typedef typename AllocHolder::NodePtr NodePtr;
- typedef tree < Key, Value, KeyOfValue
- , KeyCompare, A, Options> ThisType;
+ typedef tree < Key, T, KeyOfValue
+ , Compare, Allocator, Options> ThisType;
typedef typename AllocHolder::NodeAlloc NodeAlloc;
+ typedef boost::container::
+ allocator_traits<NodeAlloc> allocator_traits_type;
typedef typename AllocHolder::ValAlloc ValAlloc;
typedef typename AllocHolder::Node Node;
typedef typename Icont::iterator iiterator;
typedef typename Icont::const_iterator iconst_iterator;
typedef container_detail::allocator_destroyer<NodeAlloc> Destroyer;
- typedef typename AllocHolder::allocator_v1 allocator_v1;
- typedef typename AllocHolder::allocator_v2 allocator_v2;
typedef typename AllocHolder::alloc_version alloc_version;
typedef intrusive_tree_proxy<Options::tree_type> intrusive_tree_proxy_t;
@@ -491,22 +500,22 @@ class tree
public:
typedef Key key_type;
- typedef Value value_type;
- typedef A allocator_type;
- typedef KeyCompare key_compare;
+ typedef T value_type;
+ typedef Allocator allocator_type;
+ typedef Compare key_compare;
typedef ValComp value_compare;
typedef typename boost::container::
- allocator_traits<A>::pointer pointer;
+ allocator_traits<Allocator>::pointer pointer;
typedef typename boost::container::
- allocator_traits<A>::const_pointer const_pointer;
+ allocator_traits<Allocator>::const_pointer const_pointer;
typedef typename boost::container::
- allocator_traits<A>::reference reference;
+ allocator_traits<Allocator>::reference reference;
typedef typename boost::container::
- allocator_traits<A>::const_reference const_reference;
+ allocator_traits<Allocator>::const_reference const_reference;
typedef typename boost::container::
- allocator_traits<A>::size_type size_type;
+ allocator_traits<Allocator>::size_type size_type;
typedef typename boost::container::
- allocator_traits<A>::difference_type difference_type;
+ allocator_traits<Allocator>::difference_type difference_type;
typedef difference_type tree_difference_type;
typedef pointer tree_pointer;
typedef const_pointer tree_const_pointer;
@@ -519,17 +528,17 @@ class tree
typedef key_node_compare<value_compare, Node> KeyNodeCompare;
public:
- typedef container_detail::iterator<iiterator, false> iterator;
- typedef container_detail::iterator<iiterator, true > const_iterator;
- typedef container_detail::reverse_iterator<iterator> reverse_iterator;
- typedef container_detail::reverse_iterator<const_iterator> const_reverse_iterator;
+ typedef container_detail::iterator_from_iiterator<iiterator, false> iterator;
+ typedef container_detail::iterator_from_iiterator<iiterator, true > const_iterator;
+ typedef boost::container::reverse_iterator<iterator> reverse_iterator;
+ typedef boost::container::reverse_iterator<const_iterator> const_reverse_iterator;
tree()
- : AllocHolder(ValComp(key_compare()))
+ : AllocHolder()
{}
explicit tree(const key_compare& comp, const allocator_type& a = allocator_type())
- : AllocHolder(a, ValComp(comp))
+ : AllocHolder(ValComp(comp), a)
{}
explicit tree(const allocator_type& a)
@@ -542,11 +551,11 @@ class tree
#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
, typename container_detail::enable_if_c
< container_detail::is_input_iterator<InputIterator>::value
- || container_detail::is_same<alloc_version, allocator_v1>::value
+ || container_detail::is_same<alloc_version, version_1>::value
>::type * = 0
#endif
)
- : AllocHolder(a, value_compare(comp))
+ : AllocHolder(value_compare(comp), a)
{
//Use cend() as hint to achieve linear time for
//ordered ranges as required by the standard
@@ -570,11 +579,11 @@ class tree
#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
, typename container_detail::enable_if_c
< !(container_detail::is_input_iterator<InputIterator>::value
- || container_detail::is_same<alloc_version, allocator_v1>::value)
+ || container_detail::is_same<alloc_version, version_1>::value)
>::type * = 0
#endif
)
- : AllocHolder(a, value_compare(comp))
+ : AllocHolder(value_compare(comp), a)
{
if(unique_insertion){
//Use cend() as hint to achieve linear time for
@@ -588,7 +597,7 @@ class tree
else{
//Optimized allocation and construction
this->allocate_many_and_construct
- ( first, std::distance(first, last)
+ ( first, boost::container::iterator_distance(first, last)
, insert_equal_end_hint_functor<Node, Icont>(this->icont()));
}
}
@@ -599,11 +608,11 @@ class tree
#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
, typename container_detail::enable_if_c
< container_detail::is_input_iterator<InputIterator>::value
- || container_detail::is_same<alloc_version, allocator_v1>::value
+ || container_detail::is_same<alloc_version, version_1>::value
>::type * = 0
#endif
)
- : AllocHolder(a, value_compare(comp))
+ : AllocHolder(value_compare(comp), a)
{
for ( ; first != last; ++first){
this->push_back_impl(*first);
@@ -616,45 +625,45 @@ class tree
#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
, typename container_detail::enable_if_c
< !(container_detail::is_input_iterator<InputIterator>::value
- || container_detail::is_same<alloc_version, allocator_v1>::value)
+ || container_detail::is_same<alloc_version, version_1>::value)
>::type * = 0
#endif
)
- : AllocHolder(a, value_compare(comp))
+ : AllocHolder(value_compare(comp), a)
{
//Optimized allocation and construction
this->allocate_many_and_construct
- ( first, std::distance(first, last)
+ ( first, boost::container::iterator_distance(first, last)
, container_detail::push_back_functor<Node, Icont>(this->icont()));
}
tree(const tree& x)
- : AllocHolder(x, x.value_comp())
+ : AllocHolder(x.value_comp(), x)
{
this->icont().clone_from
(x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
}
tree(BOOST_RV_REF(tree) x)
- : AllocHolder(::boost::move(static_cast<AllocHolder&>(x)), x.value_comp())
+ : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp())
{}
tree(const tree& x, const allocator_type &a)
- : AllocHolder(a, x.value_comp())
+ : AllocHolder(x.value_comp(), a)
{
this->icont().clone_from
(x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
}
tree(BOOST_RV_REF(tree) x, const allocator_type &a)
- : AllocHolder(a, x.value_comp())
+ : AllocHolder(x.value_comp(), a)
{
if(this->node_alloc() == x.node_alloc()){
this->icont().swap(x.icont());
}
else{
this->icont().clone_from
- (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
+ (x.icont(), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc()));
}
}
@@ -693,6 +702,8 @@ class tree
}
tree& operator=(BOOST_RV_REF(tree) x)
+ BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
+ && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value )
{
BOOST_ASSERT(this != &x);
NodeAlloc &this_alloc = this->node_alloc();
@@ -735,10 +746,10 @@ class tree
public:
// accessors:
value_compare value_comp() const
- { return this->icont().value_comp().value_comp(); }
+ { return this->icont().value_comp().predicate(); }
key_compare key_comp() const
- { return this->icont().value_comp().value_comp().key_comp(); }
+ { return this->icont().value_comp().predicate().key_comp(); }
allocator_type get_allocator() const
{ return allocator_type(this->node_alloc()); }
@@ -817,6 +828,8 @@ class tree
{ return AllocHolder::max_size(); }
void swap(ThisType& x)
+ BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
+ && boost::container::container_detail::is_nothrow_swappable<Compare>::value )
{ AllocHolder::swap(x); }
public:
@@ -851,9 +864,9 @@ class tree
template<class MovableConvertible>
iterator insert_unique_commit
- (BOOST_FWD_REF(MovableConvertible) mv, insert_commit_data &data)
+ (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data)
{
- NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(mv));
+ NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v));
scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
iterator ret(this->icont().insert_unique_commit(*tmp, data));
destroy_deallocator.release();
@@ -872,13 +885,13 @@ class tree
}
template<class MovableConvertible>
- std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) mv)
+ std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) v)
{
insert_commit_data data;
std::pair<iterator,bool> ret =
- this->insert_unique_check(KeyOfValue()(mv), data);
+ this->insert_unique_check(KeyOfValue()(v), data);
if(ret.second){
- ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(mv), data);
+ ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
}
return ret;
}
@@ -886,9 +899,9 @@ class tree
private:
template<class MovableConvertible>
- void push_back_impl(BOOST_FWD_REF(MovableConvertible) mv)
+ void push_back_impl(BOOST_FWD_REF(MovableConvertible) v)
{
- NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(mv)));
+ NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
//push_back has no-throw guarantee so avoid any deallocator/destroyer
this->icont().push_back(*tmp);
}
@@ -925,18 +938,18 @@ class tree
public:
- #ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+ #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
template <class... Args>
- std::pair<iterator, bool> emplace_unique(Args&&... args)
+ std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args)
{ return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...)); }
template <class... Args>
- iterator emplace_hint_unique(const_iterator hint, Args&&... args)
+ iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args)
{ return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); }
template <class... Args>
- iterator emplace_equal(Args&&... args)
+ 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());
@@ -946,7 +959,7 @@ class tree
}
template <class... Args>
- iterator emplace_hint_equal(const_iterator hint, Args&&... args)
+ iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args)
{
NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
@@ -955,49 +968,41 @@ class tree
return ret;
}
- #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
-
- #define BOOST_PP_LOCAL_MACRO(n) \
- BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
- std::pair<iterator, bool> emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
- { \
- return this->emplace_unique_impl \
- (AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
- } \
- \
- BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
- iterator emplace_hint_unique(const_iterator hint \
- BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
- { \
- return this->emplace_unique_hint_impl \
- (hint, AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
- } \
- \
- BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
- iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
- { \
- NodePtr tmp(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
- scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); \
- iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); \
- destroy_deallocator.release(); \
- return ret; \
- } \
- \
- BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
- iterator emplace_hint_equal(const_iterator hint \
- BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
- { \
- NodePtr tmp(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
- scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); \
- iterator ret(this->icont().insert_equal(hint.get(), *tmp)); \
- destroy_deallocator.release(); \
- return ret; \
- } \
- //!
- #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
- #include BOOST_PP_LOCAL_ITERATE()
-
- #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+ #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+ #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \
+ BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
+ std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\
+ { return this->emplace_unique_impl(AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\
+ \
+ BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
+ iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
+ { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\
+ \
+ BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
+ 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());\
+ iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\
+ destroy_deallocator.release();\
+ return ret;\
+ }\
+ \
+ BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
+ iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
+ {\
+ NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\
+ iterator ret(this->icont().insert_equal(hint.get(), *tmp));\
+ destroy_deallocator.release();\
+ return ret;\
+ }\
+ //
+ BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE)
+ #undef BOOST_CONTAINER_TREE_EMPLACE_CODE
+
+ #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
iterator insert_unique(const_iterator hint, const value_type& v)
{
@@ -1010,14 +1015,14 @@ class tree
}
template<class MovableConvertible>
- iterator insert_unique(const_iterator hint, BOOST_FWD_REF(MovableConvertible) mv)
+ iterator insert_unique(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
{
insert_commit_data data;
std::pair<iterator,bool> ret =
- this->insert_unique_check(hint, KeyOfValue()(mv), data);
+ this->insert_unique_check(hint, KeyOfValue()(v), data);
if(!ret.second)
return ret.first;
- return this->insert_unique_commit(boost::forward<MovableConvertible>(mv), data);
+ return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data);
}
template <class InputIterator>
@@ -1037,9 +1042,9 @@ class tree
}
template<class MovableConvertible>
- iterator insert_equal(BOOST_FWD_REF(MovableConvertible) mv)
+ iterator insert_equal(BOOST_FWD_REF(MovableConvertible) v)
{
- NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(mv)));
+ NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
destroy_deallocator.release();
@@ -1056,9 +1061,9 @@ class tree
}
template<class MovableConvertible>
- iterator insert_equal(const_iterator hint, BOOST_FWD_REF(MovableConvertible) mv)
+ iterator insert_equal(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v)
{
- NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(mv)));
+ NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v)));
scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
iterator ret(this->icont().insert_equal(hint.get(), *tmp));
destroy_deallocator.release();
@@ -1141,10 +1146,10 @@ class tree
{ intrusive_tree_proxy_t::rebalance(this->icont()); }
friend bool operator==(const tree& x, const tree& y)
- { return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin()); }
+ { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
friend bool operator<(const tree& x, const tree& y)
- { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
+ { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
friend bool operator!=(const tree& x, const tree& y)
{ return !(x == y); }
@@ -1164,17 +1169,25 @@ class tree
} //namespace container_detail {
} //namespace container {
-/*
+
+template <class T>
+struct has_trivial_destructor_after_move;
+
//!has_trivial_destructor_after_move<> == true_type
//!specialization for optimizations
-template <class K, class V, class KOV,
-class C, class A>
+template <class Key, class T, class KeyOfValue, class Compare, class Allocator, class Options>
struct has_trivial_destructor_after_move
- <boost::container::container_detail::tree<K, V, KOV, C, A> >
+ <
+ ::boost::container::container_detail::tree
+ <Key, T, KeyOfValue, Compare, Allocator, Options>
+ >
{
- static const bool value = has_trivial_destructor_after_move<A>::value && has_trivial_destructor_after_move<C>::value;
+ typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
+ static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
+ ::boost::has_trivial_destructor_after_move<pointer>::value &&
+ ::boost::has_trivial_destructor_after_move<Compare>::value;
};
-*/
+
} //namespace boost {
#include <boost/container/detail/config_end.hpp>