Implement full support for non-pointer types in custom allocators. This is for the associative containers only. This work still needs to be done on the unordered and sequence containers. Fixes http://llvm.org/bugs/show_bug.cgi?id=15978
llvm-svn: 184358
Cr-Mirrored-From: sso://chromium.googlesource.com/_direct/external/github.com/llvm/llvm-project
Cr-Mirrored-Commit: 07d3eccd26a600a6cad3bb6807880f46a76f269e
diff --git a/include/__tree b/include/__tree
index cd6d7ef..9ffc38d 100644
--- a/include/__tree
+++ b/include/__tree
@@ -644,7 +644,8 @@
_LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT {}
_LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
- _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &__ptr_->__value_;}
+ _LIBCPP_INLINE_VISIBILITY pointer operator->() const
+ {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
_LIBCPP_INLINE_VISIBILITY
__tree_iterator& operator++()
@@ -686,7 +687,7 @@
{
typedef _ConstNodePtr __node_pointer;
typedef typename pointer_traits<__node_pointer>::element_type __node;
- typedef const typename __node::base __node_base;
+ typedef typename __node::base __node_base;
typedef typename pointer_traits<__node_pointer>::template
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
rebind<__node_base>
@@ -729,7 +730,8 @@
: __ptr_(__p.__ptr_) {}
_LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
- _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &__ptr_->__value_;}
+ _LIBCPP_INLINE_VISIBILITY pointer operator->() const
+ {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
_LIBCPP_INLINE_VISIBILITY
__tree_const_iterator& operator++()
@@ -779,8 +781,10 @@
typedef typename __alloc_traits::size_type size_type;
typedef typename __alloc_traits::difference_type difference_type;
- typedef __tree_node<value_type, typename __alloc_traits::void_pointer> __node;
- typedef __tree_node_base<typename __alloc_traits::void_pointer> __node_base;
+ typedef typename __alloc_traits::void_pointer __void_pointer;
+
+ typedef __tree_node<value_type, __void_pointer> __node;
+ typedef __tree_node_base<__void_pointer> __node_base;
typedef typename __alloc_traits::template
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
rebind_alloc<__node>
@@ -790,9 +794,9 @@
__node_allocator;
typedef allocator_traits<__node_allocator> __node_traits;
typedef typename __node_traits::pointer __node_pointer;
- typedef typename __node_traits::const_pointer __node_const_pointer;
+ typedef typename __node_traits::pointer __node_const_pointer;
typedef typename __node_base::pointer __node_base_pointer;
- typedef typename __node_base::const_pointer __node_base_const_pointer;
+ typedef typename __node_base::pointer __node_base_const_pointer;
private:
typedef typename __node_base::base __end_node_t;
typedef typename pointer_traits<__node_pointer>::template
@@ -804,9 +808,9 @@
__end_node_ptr;
typedef typename pointer_traits<__node_pointer>::template
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
- rebind<const __end_node_t>
+ rebind<__end_node_t>
#else
- rebind<const __end_node_t>::other
+ rebind<__end_node_t>::other
#endif
__end_node_const_ptr;
@@ -828,7 +832,7 @@
{
return static_cast<__node_const_pointer>
(
- pointer_traits<__end_node_const_ptr>::pointer_to(__pair1_.first())
+ pointer_traits<__end_node_const_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first()))
);
}
_LIBCPP_INLINE_VISIBILITY
@@ -865,7 +869,7 @@
{return static_cast<__node_const_pointer>(__end_node()->__left_);}
typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator;
- typedef __tree_const_iterator<value_type, __node_const_pointer, difference_type> const_iterator;
+ typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator;
explicit __tree(const value_compare& __comp)
_NOEXCEPT_(
@@ -1102,6 +1106,9 @@
__node_pointer __detach();
static __node_pointer __detach(__node_pointer);
+
+ template <class, class, class, class> friend class _LIBCPP_TYPE_VIS map;
+ template <class, class, class, class> friend class _LIBCPP_TYPE_VIS multimap;
};
template <class _Tp, class _Compare, class _Allocator>
@@ -1161,7 +1168,7 @@
{
if (__cache->__parent_ == nullptr)
return nullptr;
- if (__tree_is_left_child(__cache))
+ if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache)))
{
__cache->__parent_->__left_ = nullptr;
__cache = static_cast<__node_pointer>(__cache->__parent_);
@@ -1294,7 +1301,7 @@
__begin_node() = __end_node();
else
{
- __end_node()->__left_->__parent_ = __end_node();
+ __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
__t.__begin_node() = __t.__end_node();
__t.__end_node()->__left_ = nullptr;
__t.size() = 0;
@@ -1314,7 +1321,7 @@
{
__begin_node() = __t.__begin_node();
__end_node()->__left_ = __t.__end_node()->__left_;
- __end_node()->__left_->__parent_ = __end_node();
+ __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
size() = __t.size();
__t.__begin_node() = __t.__end_node();
__t.__end_node()->__left_ = nullptr;
@@ -1342,7 +1349,7 @@
__begin_node() = __end_node();
else
{
- __end_node()->__left_->__parent_ = __end_node();
+ __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
__t.__begin_node() = __t.__end_node();
__t.__end_node()->__left_ = nullptr;
__t.size() = 0;
@@ -1447,11 +1454,11 @@
if (size() == 0)
__begin_node() = __end_node();
else
- __end_node()->__left_->__parent_ = __end_node();
+ __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
if (__t.size() == 0)
__t.__begin_node() = __t.__end_node();
else
- __t.__end_node()->__left_->__parent_ = __t.__end_node();
+ __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node());
}
template <class _Tp, class _Compare, class _Allocator>
@@ -1483,7 +1490,7 @@
__nd = static_cast<__node_pointer>(__nd->__right_);
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return __parent->__right_;
}
}
@@ -1493,13 +1500,13 @@
__nd = static_cast<__node_pointer>(__nd->__left_);
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return __parent->__left_;
}
}
}
}
- __parent = __end_node();
+ __parent = static_cast<__node_base_pointer>(__end_node());
return __parent->__left_;
}
@@ -1522,7 +1529,7 @@
__nd = static_cast<__node_pointer>(__nd->__left_);
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return __parent->__left_;
}
}
@@ -1532,13 +1539,13 @@
__nd = static_cast<__node_pointer>(__nd->__right_);
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return __parent->__right_;
}
}
}
}
- __parent = __end_node();
+ __parent = static_cast<__node_base_pointer>(__end_node());
return __parent->__left_;
}
@@ -1563,12 +1570,12 @@
// *prev(__hint) <= __v <= *__hint
if (__hint.__ptr_->__left_ == nullptr)
{
- __parent = const_cast<__node_pointer&>(__hint.__ptr_);
+ __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
return __parent->__left_;
}
else
{
- __parent = const_cast<__node_pointer&>(__prior.__ptr_);
+ __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
return __parent->__right_;
}
}
@@ -1600,7 +1607,7 @@
__nd = static_cast<__node_pointer>(__nd->__left_);
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return __parent->__left_;
}
}
@@ -1610,18 +1617,18 @@
__nd = static_cast<__node_pointer>(__nd->__right_);
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return __parent->__right_;
}
}
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return __parent;
}
}
}
- __parent = __end_node();
+ __parent = static_cast<__node_base_pointer>(__end_node());
return __parent->__left_;
}
@@ -1648,12 +1655,12 @@
// *prev(__hint) < __v < *__hint
if (__hint.__ptr_->__left_ == nullptr)
{
- __parent = const_cast<__node_pointer&>(__hint.__ptr_);
+ __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
return __parent->__left_;
}
else
{
- __parent = const_cast<__node_pointer&>(__prior.__ptr_);
+ __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
return __parent->__right_;
}
}
@@ -1669,12 +1676,12 @@
// *__hint < __v < *_VSTD::next(__hint)
if (__hint.__ptr_->__right_ == nullptr)
{
- __parent = const_cast<__node_pointer&>(__hint.__ptr_);
+ __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
return __parent->__right_;
}
else
{
- __parent = const_cast<__node_pointer&>(__next.__ptr_);
+ __parent = static_cast<__node_base_pointer>(__next.__ptr_);
return __parent->__left_;
}
}
@@ -1682,7 +1689,7 @@
return __find_equal(__parent, __v);
}
// else __v == *__hint
- __parent = const_cast<__node_pointer&>(__hint.__ptr_);
+ __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
return __parent;
}
@@ -1729,7 +1736,7 @@
bool __inserted = false;
if (__child == nullptr)
{
- __insert_node_at(__parent, __child, __h.get());
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
__r = __h.release();
__inserted = true;
}
@@ -1747,7 +1754,7 @@
__node_pointer __r = static_cast<__node_pointer>(__child);
if (__child == nullptr)
{
- __insert_node_at(__parent, __child, __h.get());
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
__r = __h.release();
}
return iterator(__r);
@@ -1761,7 +1768,7 @@
__node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
__node_base_pointer __parent;
__node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_);
- __insert_node_at(__parent, __child, __h.get());
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
return iterator(static_cast<__node_pointer>(__h.release()));
}
@@ -1774,7 +1781,7 @@
__node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
__node_base_pointer __parent;
__node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_);
- __insert_node_at(__parent, __child, __h.get());
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
return iterator(static_cast<__node_pointer>(__h.release()));
}
@@ -1812,7 +1819,7 @@
__node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
__node_base_pointer __parent;
__node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_);
- __insert_node_at(__parent, __child, __h.get());
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
return iterator(__h.release());
}
@@ -1824,7 +1831,7 @@
__node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
__node_base_pointer __parent;
__node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_);
- __insert_node_at(__parent, __child, __h.get());
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
return iterator(__h.release());
}
@@ -1854,7 +1861,7 @@
if (__child == nullptr)
{
__node_holder __h = __construct_node(__v);
- __insert_node_at(__parent, __child, __h.get());
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
__r = __h.release();
__inserted = true;
}
@@ -1871,7 +1878,7 @@
if (__child == nullptr)
{
__node_holder __h = __construct_node(__v);
- __insert_node_at(__parent, __child, __h.get());
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
__r = __h.release();
}
return iterator(__r);
@@ -1884,7 +1891,7 @@
__node_base_pointer __parent;
__node_base_pointer& __child = __find_leaf_high(__parent, __v);
__node_holder __h = __construct_node(__v);
- __insert_node_at(__parent, __child, __h.get());
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
return iterator(__h.release());
}
@@ -1895,7 +1902,7 @@
__node_base_pointer __parent;
__node_base_pointer& __child = __find_leaf(__p, __parent, __v);
__node_holder __h = __construct_node(__v);
- __insert_node_at(__parent, __child, __h.get());
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
return iterator(__h.release());
}
@@ -1909,7 +1916,7 @@
bool __inserted = false;
if (__child == nullptr)
{
- __insert_node_at(__parent, __child, __nd);
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
__r = __nd;
__inserted = true;
}
@@ -1926,7 +1933,7 @@
__node_pointer __r = static_cast<__node_pointer>(__child);
if (__child == nullptr)
{
- __insert_node_at(__parent, __child, __nd);
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
__r = __nd;
}
return iterator(__r);
@@ -1938,7 +1945,7 @@
{
__node_base_pointer __parent;
__node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_);
- __insert_node_at(__parent, __child, __nd);
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
return iterator(__nd);
}
@@ -1949,7 +1956,7 @@
{
__node_base_pointer __parent;
__node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_);
- __insert_node_at(__parent, __child, __nd);
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
return iterator(__nd);
}
@@ -1957,7 +1964,7 @@
typename __tree<_Tp, _Compare, _Allocator>::iterator
__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
{
- __node_pointer __np = const_cast<__node_pointer>(__p.__ptr_);
+ __node_pointer __np = __p.__ptr_;
iterator __r(__np);
++__r;
if (__begin_node() == __np)
@@ -1977,7 +1984,7 @@
{
while (__f != __l)
__f = erase(__f);
- return iterator(const_cast<__node_pointer>(__l.__ptr_));
+ return iterator(__l.__ptr_);
}
template <class _Tp, class _Compare, class _Allocator>
@@ -2264,7 +2271,7 @@
typename __tree<_Tp, _Compare, _Allocator>::__node_holder
__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
{
- __node_pointer __np = const_cast<__node_pointer>(__p.__ptr_);
+ __node_pointer __np = __p.__ptr_;
if (__begin_node() == __np)
{
if (__np->__right_ != nullptr)
diff --git a/include/map b/include/map
index abc07a3..df174da 100644
--- a/include/map
+++ b/include/map
@@ -489,8 +489,8 @@
public:
typedef typename __alloc_traits::pointer pointer;
private:
- typedef typename value_type::first_type first_type;
- typedef typename value_type::second_type second_type;
+ typedef typename value_type::value_type::first_type first_type;
+ typedef typename value_type::value_type::second_type second_type;
allocator_type& __na_;
@@ -522,9 +522,9 @@
void operator()(pointer __p) _NOEXCEPT
{
if (__second_constructed)
- __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
+ __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
if (__first_constructed)
- __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
+ __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
if (__p)
__alloc_traits::deallocate(__na_, __p, 1);
}
@@ -542,8 +542,8 @@
_TreeIterator __i_;
typedef typename _TreeIterator::__pointer_traits __pointer_traits;
- typedef const typename _TreeIterator::value_type::first_type __key_type;
- typedef typename _TreeIterator::value_type::second_type __mapped_type;
+ typedef const typename _TreeIterator::value_type::value_type::first_type __key_type;
+ typedef typename _TreeIterator::value_type::value_type::second_type __mapped_type;
public:
typedef bidirectional_iterator_tag iterator_category;
typedef pair<__key_type, __mapped_type> value_type;
@@ -564,9 +564,9 @@
__map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
_LIBCPP_INLINE_VISIBILITY
- reference operator*() const {return *operator->();}
+ reference operator*() const {return __i_->__cc;}
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return (pointer)__i_.operator->();}
+ pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
_LIBCPP_INLINE_VISIBILITY
__map_iterator& operator++() {++__i_; return *this;}
@@ -607,8 +607,8 @@
_TreeIterator __i_;
typedef typename _TreeIterator::__pointer_traits __pointer_traits;
- typedef const typename _TreeIterator::value_type::first_type __key_type;
- typedef typename _TreeIterator::value_type::second_type __mapped_type;
+ typedef const typename _TreeIterator::value_type::value_type::first_type __key_type;
+ typedef typename _TreeIterator::value_type::value_type::second_type __mapped_type;
public:
typedef bidirectional_iterator_tag iterator_category;
typedef pair<__key_type, __mapped_type> value_type;
@@ -634,9 +634,9 @@
: __i_(__i.__i_) {}
_LIBCPP_INLINE_VISIBILITY
- reference operator*() const {return *operator->();}
+ reference operator*() const {return __i_->__cc;}
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return (pointer)__i_.operator->();}
+ pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
_LIBCPP_INLINE_VISIBILITY
__map_const_iterator& operator++() {++__i_; return *this;}
@@ -679,6 +679,7 @@
typedef _Key key_type;
typedef _Tp mapped_type;
typedef pair<const key_type, mapped_type> value_type;
+ typedef pair<key_type, mapped_type> __nc_value_type;
typedef _Compare key_compare;
typedef _Allocator allocator_type;
typedef value_type& reference;
@@ -699,7 +700,54 @@
};
private:
- typedef pair<key_type, mapped_type> __value_type;
+
+#if __cplusplus >= 201103L
+ union __value_type
+ {
+ typedef typename map::value_type value_type;
+ typedef typename map::__nc_value_type __nc_value_type;
+ value_type __cc;
+ __nc_value_type __nc;
+
+ template <class ..._Args>
+ __value_type(_Args&& ...__args)
+ : __cc(std::forward<_Args>(__args)...) {}
+
+ __value_type(const __value_type& __v)
+ : __cc(std::move(__v.__cc)) {}
+
+ __value_type(__value_type&& __v)
+ : __nc(std::move(__v.__nc)) {}
+
+ __value_type& operator=(const __value_type& __v)
+ {__nc = __v.__cc; return *this;}
+
+ __value_type& operator=(__value_type&& __v)
+ {__nc = std::move(__v.__nc); return *this;}
+
+ ~__value_type() {__cc.~value_type();}
+
+ operator const value_type& () const {return __cc;}
+ };
+#else
+ struct __value_type
+ {
+ typedef typename map::value_type value_type;
+ value_type __cc;
+
+ __value_type() {}
+
+ template <class _A0>
+ __value_type(const _A0& __a0)
+ : __cc(__a0) {}
+
+ template <class _A0, class _A1>
+ __value_type(const _A0& __a0, const _A1& __a1)
+ : __cc(__a0, __a1) {}
+
+ operator const value_type& () const {return __cc;}
+ };
+#endif
typedef __map_value_compare<key_type, mapped_type, key_compare> __vc;
typedef typename allocator_traits<allocator_type>::template
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
@@ -764,7 +812,14 @@
_LIBCPP_INLINE_VISIBILITY
map& operator=(const map& __m)
{
+#if __cplusplus >= 201103L
__tree_ = __m.__tree_;
+#else
+ __tree_.clear();
+ __tree_.value_comp() = __m.__tree_.value_comp();
+ __tree_.__copy_assign_alloc(__m.__tree_);
+ insert(__m.begin(), __m.end());
+#endif
return *this;
}
@@ -1009,9 +1064,6 @@
__node_base_pointer&
__find_equal_key(__node_base_pointer& __parent, const key_type& __k);
- __node_base_pointer&
- __find_equal_key(const_iterator __hint,
- __node_base_pointer& __parent, const key_type& __k);
__node_base_const_pointer
__find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const;
};
@@ -1030,97 +1082,37 @@
{
while (true)
{
- if (__tree_.value_comp().key_comp()(__k, __nd->__value_.first))
+ if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
{
if (__nd->__left_ != nullptr)
__nd = static_cast<__node_pointer>(__nd->__left_);
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return __parent->__left_;
}
}
- else if (__tree_.value_comp().key_comp()(__nd->__value_.first, __k))
+ else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
{
if (__nd->__right_ != nullptr)
__nd = static_cast<__node_pointer>(__nd->__right_);
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return __parent->__right_;
}
}
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return __parent;
}
}
}
- __parent = __tree_.__end_node();
+ __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
return __parent->__left_;
}
-// Find place to insert if __k doesn't exist
-// First check prior to __hint.
-// Next check after __hint.
-// Next do O(log N) search.
-// Set __parent to parent of null leaf
-// Return reference to null leaf
-// If __k exists, set parent to node of __k and return reference to node of __k
-template <class _Key, class _Tp, class _Compare, class _Allocator>
-typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
-map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(const_iterator __hint,
- __node_base_pointer& __parent,
- const key_type& __k)
-{
- if (__hint == end() || __tree_.value_comp().key_comp()(__k, __hint->first)) // check before
- {
- // __k < *__hint
- const_iterator __prior = __hint;
- if (__prior == begin() || __tree_.value_comp().key_comp()((--__prior)->first, __k))
- {
- // *prev(__hint) < __k < *__hint
- if (__hint.__ptr_->__left_ == nullptr)
- {
- __parent = const_cast<__node_pointer&>(__hint.__ptr_);
- return __parent->__left_;
- }
- else
- {
- __parent = const_cast<__node_pointer&>(__prior.__ptr_);
- return __parent->__right_;
- }
- }
- // __k <= *prev(__hint)
- return __find_equal_key(__parent, __k);
- }
- else if (__tree_.value_comp().key_comp()(__hint->first, __k)) // check after
- {
- // *__hint < __k
- const_iterator __next = _VSTD::next(__hint);
- if (__next == end() || __tree_.value_comp().key_comp()(__k, __next->first))
- {
- // *__hint < __k < *next(__hint)
- if (__hint.__ptr_->__right_ == nullptr)
- {
- __parent = const_cast<__node_pointer&>(__hint.__ptr_);
- return __parent->__right_;
- }
- else
- {
- __parent = const_cast<__node_pointer&>(__next.__ptr_);
- return __parent->__left_;
- }
- }
- // *next(__hint) <= __k
- return __find_equal_key(__parent, __k);
- }
- // else __k == *__hint
- __parent = const_cast<__node_pointer&>(__hint.__ptr_);
- return __parent;
-}
-
// Find __k
// Set __parent to parent of null leaf and
// return reference to null leaf iv __k does not exist.
@@ -1135,34 +1127,34 @@
{
while (true)
{
- if (__tree_.value_comp().key_comp()(__k, __nd->__value_.first))
+ if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
{
if (__nd->__left_ != nullptr)
__nd = static_cast<__node_pointer>(__nd->__left_);
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return const_cast<const __node_base_const_pointer&>(__parent->__left_);
}
}
- else if (__tree_.value_comp().key_comp()(__nd->__value_.first, __k))
+ else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
{
if (__nd->__right_ != nullptr)
__nd = static_cast<__node_pointer>(__nd->__right_);
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return const_cast<const __node_base_const_pointer&>(__parent->__right_);
}
}
else
{
- __parent = __nd;
+ __parent = static_cast<__node_base_pointer>(__nd);
return __parent;
}
}
}
- __parent = __tree_.__end_node();
+ __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
return const_cast<const __node_base_const_pointer&>(__parent->__left_);
}
@@ -1187,9 +1179,9 @@
{
__node_allocator& __na = __tree_.__node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
__h.get_deleter().__first_constructed = true;
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
__h.get_deleter().__second_constructed = true;
return __h;
}
@@ -1222,9 +1214,9 @@
{
__node_allocator& __na = __tree_.__node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), _VSTD::forward<_A0>(__a0));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::forward<_A0>(__a0));
__h.get_deleter().__first_constructed = true;
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
__h.get_deleter().__second_constructed = true;
return __h;
}
@@ -1256,9 +1248,9 @@
{
__node_allocator& __na = __tree_.__node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
__h.get_deleter().__first_constructed = true;
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
__h.get_deleter().__second_constructed = true;
return _VSTD::move(__h);
}
@@ -1275,10 +1267,10 @@
if (__child == nullptr)
{
__node_holder __h = __construct_node(__k);
- __tree_.__insert_node_at(__parent, __child, __h.get());
+ __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
__r = __h.release();
}
- return __r->__value_.second;
+ return __r->__value_.__cc.second;
}
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
@@ -1293,10 +1285,10 @@
if (__child == nullptr)
{
__node_holder __h = __construct_node(_VSTD::move(__k));
- __tree_.__insert_node_at(__parent, __child, __h.get());
+ __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
__r = __h.release();
}
- return __r->__value_.second;
+ return __r->__value_.__cc.second;
}
#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
@@ -1311,7 +1303,7 @@
if (__child == nullptr)
throw out_of_range("map::at: key not found");
#endif // _LIBCPP_NO_EXCEPTIONS
- return static_cast<__node_pointer>(__child)->__value_.second;
+ return static_cast<__node_pointer>(__child)->__value_.__cc.second;
}
template <class _Key, class _Tp, class _Compare, class _Allocator>
@@ -1324,7 +1316,7 @@
if (__child == nullptr)
throw out_of_range("map::at: key not found");
#endif // _LIBCPP_NO_EXCEPTIONS
- return static_cast<__node_const_pointer>(__child)->__value_.second;
+ return static_cast<__node_const_pointer>(__child)->__value_.__cc.second;
}
#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
@@ -1429,6 +1421,7 @@
typedef _Key key_type;
typedef _Tp mapped_type;
typedef pair<const key_type, mapped_type> value_type;
+ typedef pair<key_type, mapped_type> __nc_value_type;
typedef _Compare key_compare;
typedef _Allocator allocator_type;
typedef value_type& reference;
@@ -1450,7 +1443,53 @@
};
private:
- typedef pair<key_type, mapped_type> __value_type;
+#if __cplusplus >= 201103L
+ union __value_type
+ {
+ typedef typename multimap::value_type value_type;
+ typedef typename multimap::__nc_value_type __nc_value_type;
+ value_type __cc;
+ __nc_value_type __nc;
+
+ template <class ..._Args>
+ __value_type(_Args&& ...__args)
+ : __cc(std::forward<_Args>(__args)...) {}
+
+ __value_type(const __value_type& __v)
+ : __cc(std::move(__v.__cc)) {}
+
+ __value_type(__value_type&& __v)
+ : __nc(std::move(__v.__nc)) {}
+
+ __value_type& operator=(const __value_type& __v)
+ {__nc = __v.__cc; return *this;}
+
+ __value_type& operator=(__value_type&& __v)
+ {__nc = std::move(__v.__nc); return *this;}
+
+ ~__value_type() {__cc.~value_type();}
+
+ operator const value_type& () const {return __cc;}
+ };
+#else
+ struct __value_type
+ {
+ typedef typename multimap::value_type value_type;
+ value_type __cc;
+
+ __value_type() {}
+
+ template <class _A0>
+ __value_type(const _A0& __a0)
+ : __cc(__a0) {}
+
+ template <class _A0, class _A1>
+ __value_type(const _A0& __a0, const _A1& __a1)
+ : __cc(__a0, __a1) {}
+
+ operator const value_type& () const {return __cc;}
+ };
+#endif
typedef __map_value_compare<key_type, mapped_type, key_compare> __vc;
typedef typename allocator_traits<allocator_type>::template
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
@@ -1516,7 +1555,14 @@
_LIBCPP_INLINE_VISIBILITY
multimap& operator=(const multimap& __m)
{
+#if __cplusplus >= 201103L
__tree_ = __m.__tree_;
+#else
+ __tree_.clear();
+ __tree_.value_comp() = __m.__tree_.value_comp();
+ __tree_.__copy_assign_alloc(__m.__tree_);
+ insert(__m.begin(), __m.end());
+#endif
return *this;
}
@@ -1766,9 +1812,9 @@
{
__node_allocator& __na = __tree_.__node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
__h.get_deleter().__first_constructed = true;
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
__h.get_deleter().__second_constructed = true;
return __h;
}
@@ -1801,9 +1847,9 @@
{
__node_allocator& __na = __tree_.__node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), _VSTD::forward<_A0>(__a0));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::forward<_A0>(__a0));
__h.get_deleter().__first_constructed = true;
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
__h.get_deleter().__second_constructed = true;
return __h;
}