libstdc++: [_Hashtable] Prefer to insert after last node
When inserting an element into an empty bucket we currently insert
the new node
after the before-begin node so in first position. The drawback of
doing this is
that we are forced to update the bucket that was containing this
before-begin
node to point to the newly inserted node. To do so we need at best
to do a modulo
to find this bucket and at worst, when hash code is not cached,
also compute it.
To avoid this side effect it is better to insert after the last
node. To do so
we are introducing a helper type _HintPolicy that have 3
resposibilities.
1. When the gnu versioned namespace is used we add a _M_last member
to _Hashtable,
_HintPolicy is then in charge of maintaining it. For this purpose
_HintPolicy is
using the RAII pattern, it resets the _M_last at destruction level.
It also maintain
its own _M_last, all mutable operations are updating it when needed.
2. When the gnu versioned namespace is not used _HintPolicy will
still maintain its
_M_last member using initially the user provided hint if any and if
it is actually
the container last node that is to say a dereferenceable node with
its next node being
null. All mutable operations can also update the contextual
_HintPolicy instance
whenever they detect the last node during their process.
3. As long as we haven't been able to detect the container last
node _HintPolicy
is used to keep a cache of the before-begin bucket index so that we
do not need to
compute it afterward for example in the context of range insertion.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h
[_GLIBCXX_INLINE_VERSION](_Hashtable<>::_M_last): New, the container
last node.
(_Hashtable<>::_HintPolicy): New.
(_Hashtable<>::_M_get_hint(__node_ptr)): New.
(_Hashtable<>::_M_get_hint_policy(__node_ptr)): New.
(_Hashtable<>::_M_check_for_last(__node_base_ptr)): New.
(_Hashtable<>::_M_set_last(__node_ptr)): New.
(_Hashtable<>::_M_get_last()): New.
(_Hashtable<>::_M_compute_hash_code(__node_ptr, const
key_type&)): Remove.
(_Hashtable<>::_InsertInfo): New struct.
(_Hashtable<>::_M_get_insert_info): New, return latter.
(_Hashtable<>::operator=(initializer_list<>)): Adapt to instantiate a
_HintPolicy.
(_Hashtable<>::_M_insert_bucket_begin): Add _HintPolicy&
parameter and use it
to optimize insertion in an empty bucket.
(_Hashtable<>::_M_insert_unique_node): Add _HintPolicy&
parameter.
(_Hashtable<>::_M_insert_multi_node): Likewise and add
_InsertInfo parameter.
(_Hashtable<>::_M_emplace_unique(_HintPolicy&, _Args&&...)): New.
(_Hashtable<>::_M_emplace_multi(_HintPolicy&, _Args&&...)): New.
(_Hashtable<>::_M_emplace): Adapt to use latters.
(_Hashtable<>::_M_insert_unique): Add _HintPolicy& parameter.
(_Hashtable<>::_M_insert_unique_aux): Add _HintPolicy&
parameter.
(_Hashtable<>::_M_insert): Adapt to use latter.
(_Hashtable<>::emplace_hint(const_iterator, _Args&&...)):
Adapt.
(_hashtable<>::rehash(size_type)): Adapt.
(_Hashtable<>::_M_reinsert_node(const_iterator, node_type&&)):
Add hint parameter, adapt to use it for _HintPolicy
instantiation.
(_Hashtable<>::_M_reinsert_node_multi): Likewise.
(_Hashtable<>::_M_merge_unique): Adapt.
(_Hashtable<>::_M_rehash): Add _HintPolicy& parameter.
(_Hashtable<>::_Hashtable<_InputIte>()): Adapt.
(_Hashtable<>::_M_assign): Call _M_set_last.
(_Hashtable<>::_M_reset()): Reset _M_last.
(_Hashtable<>::_M_move_assign(_Hashtable&&, true_type)): Move _M_last.
(_Hashtable<>(_Hashtable&&, __node_alloc_type&&,
true_type)): Copy _M_last.
(_Hashtable<>(_Hashtable&&, __node_alloc_type&&,
false_type)): Copy _M_last.
(_Hashtable<>::_M_insert_range): Adapt.
(_Hashtable<>::_M_erase): Call _M_check_for_last.
(_Hashtable<>::erase): Likewise.
* include/bits/hashtable_policy.h:
(_Map_base<>::operator[](const key_type&)): Use hint policy.
(_Map_base<>::operator[](key_type&&)): Likewise.
(_Insert_base<>::insert(const_iterator, const
value_type&)): Likewise using hint.
(_Insert_base<>::try_emplace): Likewise.
(_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, true_type)):
Use hint policy.
(_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, false_type)):
Use hint policy.
(_Insert<>::insert(const_iterator, value_type&&)): Likewise.
* include/bits/unordered_map.h
(unordered_map<>::insert(node_type&&)): Pass cend as
hint.
(unordered_map<>::insert(const_iterator, node_type&&)):
Adapt to use hint.
* include/bits/unordered_set.h
(unordered_set<>::insert(node_type&&)): Pass cend as
hint.
(unordered_set<>::insert(const_iterator, node_type&&)):
Adapt to use hint.
*
testsuite/23_containers/unordered_multimap/insert/hint.cc: Adapt
implementation
specific tests.
Tested under Linux x64
Ok to commit ?
François
diff --git a/libstdc++-v3/include/bits/hashtable.h
b/libstdc++-v3/include/bits/hashtable.h
index aec77c34a58..d758b054b00 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -403,6 +403,59 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// numerous checks in the code to avoid 0 modulus.
__node_base_ptr _M_single_bucket = nullptr;
+#if _GLIBCXX_INLINE_VERSION
+ // The last container node to optimize insertion in empty buckets.
+ __node_ptr _M_last = nullptr;
+#endif
+
+ class _HintPolicy
+ {
+ _Hashtable& _M_htb;
+ __node_ptr _M_last;
+ std::size_t _M_bbegin_index;
+ bool _M_initialized = false;
+
+ public:
+ _HintPolicy(_Hashtable& __htbl, __node_ptr __last)
+ : _M_htb(__htbl), _M_last(__last)
+ { }
+
+#if _GLIBCXX_INLINE_VERSION
+ ~_HintPolicy()
+ { _M_htb._M_last = _M_last; }
+#endif
+
+ std::size_t
+ _M_get_bbegin_bkt(__node_ptr __n) const
+ {
+ if (!_M_initialized)
+ return _M_htb._M_bucket_index(*__n);
+ return _M_bbegin_index;
+ }
+
+ void
+ _M_store_bbegin_bkt(std::size_t __bkt)
+ {
+ _M_bbegin_index = __bkt;
+ _M_initialized = true;
+ }
+
+ constexpr __node_ptr
+ _M_get_hint()
+ { return _M_last; }
+
+ void
+ _M_set_last(__node_ptr __n)
+ { _M_last = __n; }
+
+ void
+ _M_checked_set(__node_ptr __n)
+ {
+ if (!__n || !__n->_M_nxt)
+ _M_last = __n;
+ }
+ };
+
void
_M_update_bbegin()
{
@@ -425,6 +478,51 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_uses_single_bucket() const
{ return _M_uses_single_bucket(_M_buckets); }
+ __node_ptr
+ _M_get_hint([[maybe_unused]] __node_ptr __usr_hint = nullptr) const
+ {
+#if _GLIBCXX_INLINE_VERSION
+ return _M_last;
+#else
+ return __usr_hint && !__usr_hint->_M_nxt ? __usr_hint : nullptr;
+#endif
+ }
+
+ _HintPolicy
+ _M_get_hint_policy(__node_ptr __usr_hint = nullptr)
+ { return _HintPolicy(*this, _M_get_hint(__usr_hint)); }
+
+ void
+ _M_check_for_last([[maybe_unused]] __node_base_ptr __prev_n)
+ {
+#if _GLIBCXX_INLINE_VERSION
+ if (!__prev_n->_M_nxt)
+ {
+ _M_last = __prev_n == &_M_before_begin
+ ? nullptr
+ : static_cast<__node_ptr>(__prev_n);
+ }
+#endif
+ }
+
+ void
+ _M_set_last([[maybe_unused]] __node_ptr __n)
+ {
+#if _GLIBCXX_INLINE_VERSION
+ _M_last = __n;
+#endif
+ }
+
+ constexpr __node_ptr
+ _M_get_last()
+ {
+#if _GLIBCXX_INLINE_VERSION
+ return _M_last;
+#else
+ return nullptr;
+#endif
+ }
+
static constexpr size_t
__small_size_threshold() noexcept
{
@@ -612,11 +710,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// We consider that all elements of __l are going to be inserted.
auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
+ auto __hint_policy = _M_get_hint_policy();
+
// Do not shrink to keep potential user reservation.
if (_M_bucket_count < __l_bkt_count)
- rehash(__l_bkt_count);
+ _M_rehash(__hint_policy, __l_bkt_count);
- _M_insert_range(__l.begin(), __l.end(), __roan);
+ _M_insert_range(__l.begin(), __l.end(), __hint_policy, __roan);
return *this;
}
@@ -838,30 +938,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Insert a node at the beginning of a bucket.
void
- _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
+ _M_insert_bucket_begin(_HintPolicy& __hint_policy,
+ size_type __bkt, __node_ptr __node)
{
+ __node_base_ptr __prev;
if (_M_buckets[__bkt])
{
// Bucket is not empty, we just need to insert the new node
// after the bucket before begin.
- __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
- _M_buckets[__bkt]->_M_nxt = __node;
+ __prev = _M_buckets[__bkt];
+ if (!__prev->_M_nxt)
+ __hint_policy._M_set_last(__node);
}
else
{
- // The bucket is empty, the new node is inserted at the
- // beginning of the singly-linked list and the bucket will
- // contain _M_before_begin pointer.
- __node->_M_nxt = _M_before_begin._M_nxt;
- _M_before_begin._M_nxt = __node;
-
- if (__node->_M_nxt)
- // We must update former begin bucket that is pointing to
- // _M_before_begin.
- _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
-
- _M_buckets[__bkt] = &_M_before_begin;
+ // If we have a hint, the last container node, insert after.
+ __node_ptr __hint = __hint_policy._M_get_hint();
+ if (__hint)
+ {
+ __prev = __hint;
+ __hint_policy._M_set_last(__node);
+ }
+ else
+ {
+ // The bucket is empty, the new node is inserted at the
+ // beginning of the singly-linked list and the bucket will
+ // contain _M_before_begin pointer.
+ __prev = &_M_before_begin;
+
+ if (__prev->_M_nxt)
+ {
+ // We must update former begin bucket that is pointing to
+ // _M_before_begin.
+ size_type __bb_bkt = __hint_policy._M_get_bbegin_bkt(
+ static_cast<__node_ptr>(__prev->_M_nxt));
+ _M_buckets[__bb_bkt] = __node;
+ }
+ else
+ __hint_policy._M_set_last(__node);
+
+ __hint_policy._M_store_bbegin_bkt(__bkt);
+ }
+
+ _M_buckets[__bkt] = __prev;
}
+
+ __node->_M_nxt = __prev->_M_nxt;
+ __prev->_M_nxt = __node;
}
// Remove the bucket first node
@@ -887,44 +1010,76 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__node_base_ptr
_M_get_previous_node(size_type __bkt, __node_ptr __n);
- pair<__node_ptr, __hash_code>
- _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const;
+ struct _InsertInfo
+ {
+ __node_base_ptr _M_prev;
+ __node_ptr _M_equi_n;
+ __hash_code _M_code;
+ };
+
+ _InsertInfo
+ _M_get_insert_info(_HintPolicy& __hint_policy, const key_type& __k,
+ __node_ptr __n = nullptr) const;
// Insert node __n with hash code __code, in bucket __bkt if no
// rehash (assumes no element with same key already present).
// Takes ownership of __n if insertion succeeds, throws otherwise.
iterator
- _M_insert_unique_node(size_type __bkt, __hash_code,
+ _M_insert_unique_node(_HintPolicy& __hint_policy,
+ size_type __bkt, __hash_code,
__node_ptr __n, size_type __n_elt = 1);
- // Insert node __n with key __k and hash code __code.
+ // Insert node __n after __prev if any.
// Takes ownership of __n if insertion succeeds, throws otherwise.
iterator
- _M_insert_multi_node(__node_ptr __hint,
- __hash_code __code, __node_ptr __n);
+ _M_insert_multi_node(_HintPolicy& __hint_policy,
+ const _InsertInfo& __info, __node_ptr __n);
+
+ template<typename... _Args>
+ std::pair<iterator, bool>
+ _M_emplace_unique(_HintPolicy&, _Args&&... __args);
+
+ template<typename... _Args>
+ iterator
+ _M_emplace_multi(_HintPolicy&, _Args&&... __args);
template<typename... _Args>
std::pair<iterator, bool>
- _M_emplace(true_type __uks, _Args&&... __args);
+ _M_emplace(true_type /*__uks*/, _Args&&... __args)
+ {
+ auto __hint_policy = _M_get_hint_policy();
+ return _M_emplace_unique(__hint_policy,
+ std::forward<_Args>(__args)...);
+ }
template<typename... _Args>
iterator
- _M_emplace(false_type __uks, _Args&&... __args)
- { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); }
+ _M_emplace(false_type /*__uks*/, _Args&&... __args)
+ {
+ auto __hint_policy = _M_get_hint_policy();
+ return _M_emplace_multi(__hint_policy,
+ std::forward<_Args>(__args)...);
+ }
- // Emplace with hint, useless when keys are unique.
template<typename... _Args>
iterator
- _M_emplace(const_iterator, true_type __uks, _Args&&... __args)
- { return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
+ _M_emplace(_HintPolicy& __hint_policy,
+ true_type /*__uks*/, _Args&&... __args)
+ {
+ return _M_emplace_unique(__hint_policy,
+ std::forward<_Args>(__args)...).first;
+ }
template<typename... _Args>
iterator
- _M_emplace(const_iterator, false_type __uks, _Args&&... __args);
+ _M_emplace(_HintPolicy& __hint_policy,
+ false_type /*__uks*/, _Args&&... __args)
+ { return _M_emplace_multi(__hint_policy,
std::forward<_Args>(__args)...); }
template<typename _Kt, typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
+ _M_insert_unique(_HintPolicy& __hint_policy,
+ _Kt&&, _Arg&&, _NodeGenerator&);
template<typename _Kt>
static __conditional_t<
@@ -944,9 +1099,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen)
+ _M_insert_unique_aux(_HintPolicy& __hint_policy,
+ _Arg&& __arg, _NodeGenerator& __node_gen)
{
- return _M_insert_unique(
+ return _M_insert_unique(__hint_policy,
_S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
std::forward<_Arg>(__arg), __node_gen);
}
@@ -956,9 +1112,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
true_type /* __uks */)
{
+ auto __hint_policy = _M_get_hint_policy();
using __to_value
= __detail::_ConvertToValueType<_ExtractKey, value_type>;
- return _M_insert_unique_aux(
+ return _M_insert_unique_aux(__hint_policy,
__to_value{}(std::forward<_Arg>(__arg)), __node_gen);
}
@@ -967,32 +1124,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
false_type __uks)
{
+ auto __hint_policy = _M_get_hint_policy();
using __to_value
= __detail::_ConvertToValueType<_ExtractKey, value_type>;
- return _M_insert(cend(),
+ return _M_insert(__hint_policy,
__to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks);
}
- // Insert with hint, not used when keys are unique.
+ // Insert with hint when keys are unique.
template<typename _Arg, typename _NodeGenerator>
iterator
- _M_insert(const_iterator, _Arg&& __arg,
- _NodeGenerator& __node_gen, true_type __uks)
+ _M_insert(_HintPolicy& __hint_policy, _Arg&& __arg,
+ _NodeGenerator& __node_gen, true_type /* __uks */)
{
- return
- _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
+ using __to_value
+ = __detail::_ConvertToValueType<_ExtractKey, value_type>;
+ return _M_insert_unique_aux(__hint_policy,
+ __to_value{}(std::forward<_Arg>(__arg)), __node_gen).first;
}
// Insert with hint when keys are not unique.
template<typename _Arg, typename _NodeGenerator>
iterator
- _M_insert(const_iterator, _Arg&&,
+ _M_insert(_HintPolicy& __hint_policy, _Arg&& __arg,
_NodeGenerator&, false_type __uks);
template<typename _InputIterator, typename _NodeGenerator>
void
_M_insert_range(_InputIterator __first, _InputIterator __last,
- _NodeGenerator&);
+ _HintPolicy&, _NodeGenerator&);
size_type
_M_erase(true_type __uks, const key_type&);
@@ -1014,7 +1174,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
emplace_hint(const_iterator __hint, _Args&&... __args)
{
- return _M_emplace(__hint, __unique_keys{},
+ auto __hint_policy = _M_get_hint_policy(__hint._M_cur);
+ return _M_emplace(__hint_policy, __unique_keys{},
std::forward<_Args>(__args)...);
}
@@ -1041,7 +1202,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Set number of buckets keeping it appropriate for container's number
// of elements.
- void rehash(size_type __bkt_count);
+ void rehash(size_type __bkt_count)
+ {
+ auto __hint_policy = _M_get_hint_policy();
+ _M_rehash(__hint_policy, __bkt_count);
+ }
// DR 1189.
// reserve, if present, comes from _Rehash_base.
@@ -1049,7 +1214,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#if __cplusplus > 201402L
/// Re-insert an extracted node into a container with unique keys.
insert_return_type
- _M_reinsert_node(node_type&& __nh)
+ _M_reinsert_node(const_iterator __hint, node_type&& __nh)
{
insert_return_type __ret;
if (__nh.empty())
@@ -1058,14 +1223,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__glibcxx_assert(get_allocator() == __nh.get_allocator());
+ auto __hint_policy = _M_get_hint_policy(__hint._M_cur);
__node_ptr __n = nullptr;
const key_type& __k = __nh._M_key();
const size_type __size = size();
if (__size <= __small_size_threshold())
{
- for (__n = _M_begin(); __n; __n = __n->_M_next())
- if (this->_M_key_equals(__k, *__n))
- break;
+ __node_ptr __last_n = nullptr;
+ for (__n = _M_begin(); __n;
+ __last_n = __n, __n = __n->_M_next())
+ {
+ if (this->_M_key_equals(__k, *__n))
+ break;
+ }
+
+ if (!__n)
+ __hint_policy._M_set_last(__last_n);
}
__hash_code __code;
@@ -1086,8 +1259,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
{
- __ret.position
- = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
+ __ret.position = _M_insert_unique_node(
+ __hint_policy, __bkt, __code, __nh._M_ptr);
__nh._M_ptr = nullptr;
__ret.inserted = true;
}
@@ -1104,10 +1277,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_assert(get_allocator() == __nh.get_allocator());
+ auto __hint_policy = _M_get_hint_policy(__hint._M_cur);
const key_type& __k = __nh._M_key();
- auto __code = this->_M_hash_code(__k);
- auto __ret
- = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
+ auto __info = _M_get_insert_info(__hint_policy, __k);
+ auto __ret = _M_insert_multi_node(__hint_policy, __info, __nh._M_ptr);
__nh._M_ptr = nullptr;
return __ret;
}
@@ -1147,6 +1320,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return this->_M_hash_code(__k);
}
+ template<typename _H2>
+ _InsertInfo
+ _M_get_insert_info(const _H2&, _HintPolicy& __hint_policy,
+ __node_ptr __n, const key_type& __k)
+ {
+ if constexpr (std::is_same_v<_H2, _Hash>)
+ if constexpr (std::is_empty_v<_Hash>)
+ return _M_get_insert_info(__hint_policy, __k, __n);
+
+ return _M_get_insert_info(__hint_policy, __k);
+ }
+
public:
// Extract a node.
node_type
@@ -1178,6 +1363,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type>, "Node types are compatible");
__glibcxx_assert(get_allocator() == __src.get_allocator());
+ auto __hint_policy = _M_get_hint_policy();
auto __n_elt = __src.size();
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
{
@@ -1186,8 +1372,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const key_type& __k = _ExtractKey{}(*__pos);
if (__size <= __small_size_threshold())
{
+ __node_ptr __last_n = nullptr;
bool __found = false;
- for (auto __n = _M_begin(); __n; __n = __n->_M_next())
+ for (auto __n = _M_begin(); __n;
+ __last_n = __n, __n = __n->_M_next())
if (this->_M_key_equals(__k, *__n))
{
__found = true;
@@ -1200,6 +1388,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
--__n_elt;
continue;
}
+ else
+ __hint_policy._M_set_last(__last_n);
}
__hash_code __code
@@ -1209,7 +1399,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
|| _M_find_node(__bkt, __k, __code) == nullptr)
{
auto __nh = __src.extract(__pos);
- _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
+ _M_insert_unique_node(
+ __hint_policy, __bkt, __code, __nh._M_ptr, __n_elt);
__nh._M_ptr = nullptr;
__n_elt = 1;
}
@@ -1227,27 +1418,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type>, "Node types are compatible");
__glibcxx_assert(get_allocator() == __src.get_allocator());
- __node_ptr __hint = nullptr;
+ auto __hint_policy = _M_get_hint_policy();
this->reserve(size() + __src.size());
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
{
auto __pos = __i++;
const key_type& __k = _ExtractKey{}(*__pos);
- __hash_code __code
- = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
+ auto __info = _M_get_insert_info(__src.hash_function(),
+ __hint_policy, __pos._M_cur, __k);
auto __nh = __src.extract(__pos);
- __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
+ _M_insert_multi_node(__hint_policy, __info, __nh._M_ptr);
__nh._M_ptr = nullptr;
}
}
#endif // C++17
private:
+ void _M_rehash(_HintPolicy&, size_type __bkt_count);
+
// Helper rehash method used when keys are unique.
- void _M_rehash(size_type __bkt_count, true_type __uks);
+ void _M_rehash(_HintPolicy&, size_type __bkt_count, true_type __uks);
// Helper rehash method used when keys can be non-unique.
- void _M_rehash(size_type __bkt_count, false_type __uks);
+ void _M_rehash(_HintPolicy&, size_type __bkt_count, false_type __uks);
};
// Definitions of class template _Hashtable's out-of-line member functions.
@@ -1308,8 +1501,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_bucket_count = __bkt_count;
}
+ auto __hint_policy = _M_get_hint_policy();
__alloc_node_gen_t __node_gen(*this);
- _M_insert_range(__f, __l, __node_gen);
+ _M_insert_range(__f, __l, __hint_policy, __node_gen);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -1454,6 +1648,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_buckets[__bkt] = __prev_n;
__prev_n = __this_n;
}
+
+ _M_set_last(__prev_n);
}
__catch(...)
{
@@ -1479,6 +1675,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_buckets = &_M_single_bucket;
_M_before_begin._M_nxt = nullptr;
_M_element_count = 0;
+ _M_set_last(nullptr);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -1509,9 +1706,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
_M_element_count = __ht._M_element_count;
std::__alloc_on_move(this->_M_node_allocator(),
__ht._M_node_allocator());
+ _M_set_last(__ht._M_get_last());
// Fix bucket containing the _M_before_begin pointer that can't be moved.
_M_update_bbegin();
+
__ht._M_reset();
}
@@ -1575,6 +1774,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_before_begin(__ht._M_before_begin._M_nxt),
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
+#if _GLIBCXX_INLINE_VERSION
+ , _M_last(__ht._M_last)
+#endif
{
// Update buckets if __ht is using its single bucket.
if (__ht._M_uses_single_bucket())
@@ -1638,6 +1840,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else
_M_buckets = __ht._M_buckets;
+ _M_set_last(__ht._M_get_last());
+
// Fix bucket containing the _M_before_begin pointer that can't be
// moved.
_M_update_bbegin(__ht._M_begin());
@@ -2147,7 +2351,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_emplace(true_type /* __uks */, _Args&&... __args)
+ _M_emplace_unique(_HintPolicy& __hint_policy, _Args&&... __args)
-> pair<iterator, bool>
{
// First build the node to get access to the hash code
@@ -2156,10 +2360,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const size_type __size = size();
if (__size <= __small_size_threshold())
{
- for (auto __it = _M_begin(); __it; __it = __it->_M_next())
- if (this->_M_key_equals(__k, *__it))
+ __node_ptr __last_n = nullptr;
+ for (auto __n = _M_begin(); __n;
+ __last_n = __n, __n = __n->_M_next())
+ if (this->_M_key_equals(__k, *__n))
// There is already an equivalent node, no insertion
- return { iterator(__it), false };
+ return { iterator(__n), false };
+
+ __hint_policy._M_set_last(__last_n);
}
__hash_code __code = this->_M_hash_code(__k);
@@ -2170,7 +2378,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return { iterator(__p), false };
// Insert the node
- auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
+ auto __pos = _M_insert_unique_node(__hint_policy, __bkt, __code,
+ __node._M_node);
__node._M_node = nullptr;
return { __pos, true };
}
@@ -2183,17 +2392,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_emplace(const_iterator __hint, false_type /* __uks */,
- _Args&&... __args)
+ _M_emplace_multi(_HintPolicy& __hint_policy, _Args&&... __args)
-> iterator
{
// First build the node to get its hash code.
_Scoped_node __node { this, std::forward<_Args>(__args)... };
const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
- auto __res = this->_M_compute_hash_code(__hint._M_cur, __k);
- auto __pos
- = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
+ auto __info = _M_get_insert_info(__hint_policy, __k);
+ auto __pos = _M_insert_multi_node(__hint_policy, __info,
__node._M_node);
__node._M_node = nullptr;
return __pos;
}
@@ -2205,26 +2412,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const
- -> pair<__node_ptr, __hash_code>
+ _M_get_insert_info(_HintPolicy& __hint_policy, const key_type& __k,
+ __node_ptr __equi_n) const
+ -> _InsertInfo
{
if (size() <= __small_size_threshold())
{
- if (__hint)
- {
- for (auto __it = __hint; __it; __it = __it->_M_next())
- if (this->_M_key_equals(__k, *__it))
- return { __it, this->_M_hash_code(*__it) };
- }
-
- for (auto __it = _M_begin(); __it != __hint; __it = __it->_M_next())
- if (this->_M_key_equals(__k, *__it))
- return { __it, this->_M_hash_code(*__it) };
+ __node_ptr __last_n = nullptr;
+ __node_base_ptr __prev
+ = const_cast<__node_base_ptr>(&_M_before_begin);
+ for (auto __n = static_cast<__node_ptr>(__prev->_M_nxt); __n;
+ __prev = __last_n = __n, __n = __n->_M_next())
+ if (this->_M_key_equals(__k, *__n))
+ return
+ {
+ __prev, __n,
+ __hash_cached::value ? this->_M_hash_code(*__n) : 0
+ };
- __hint = nullptr;
+ __hint_policy._M_set_last(__last_n);
}
- return { __hint, this->_M_hash_code(__k) };
+ return
+ {
+ nullptr, nullptr,
+ __equi_n ? this->_M_hash_code(*__equi_n) : this->_M_hash_code(__k)
+ };
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2234,7 +2447,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert_unique_node(size_type __bkt, __hash_code __code,
+ _M_insert_unique_node(_HintPolicy& __hint_policy,
+ size_type __bkt, __hash_code __code,
__node_ptr __node, size_type __n_elt)
-> iterator
{
@@ -2245,7 +2459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__do_rehash.first)
{
- _M_rehash(__do_rehash.second, true_type{});
+ _M_rehash(__hint_policy, __do_rehash.second, true_type{});
__bkt = _M_bucket_index(__code);
}
@@ -2253,7 +2467,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
this->_M_store_code(*__node, __code);
// Always insert at the beginning of the bucket.
- _M_insert_bucket_begin(__bkt, __node);
+ _M_insert_bucket_begin(__hint_policy, __bkt, __node);
++_M_element_count;
return iterator(__node);
}
@@ -2265,8 +2479,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert_multi_node(__node_ptr __hint,
- __hash_code __code, __node_ptr __node)
+ _M_insert_multi_node(_HintPolicy& __hint_policy,
+ const _InsertInfo& __info, __node_ptr __node)
-> iterator
{
__rehash_guard_t __rehash_guard(_M_rehash_policy);
@@ -2274,42 +2488,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
= _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
if (__do_rehash.first)
- _M_rehash(__do_rehash.second, false_type{});
+ _M_rehash(__hint_policy, __do_rehash.second, false_type{});
__rehash_guard._M_guarded_obj = nullptr;
+ auto __code = __info._M_code;
this->_M_store_code(*__node, __code);
const key_type& __k = _ExtractKey{}(__node->_M_v());
- size_type __bkt = _M_bucket_index(__code);
+ auto __prev = __info._M_prev;
+ const bool __has_prev = __prev != nullptr;
+ size_type __bkt;
// Find the node before an equivalent one or use hint if it exists and
// if it is equivalent.
- __node_base_ptr __prev
- = __builtin_expect(__hint != nullptr, false)
- && this->_M_equals(__k, __code, *__hint)
- ? __hint
- : _M_find_before_node(__bkt, __k, __code);
+ if (!__has_prev)
+ {
+ __bkt = _M_bucket_index(__code);
+ __prev = _M_find_before_node(__bkt, __k, __code);
+ }
if (__prev)
{
// Insert after the node before the equivalent one.
__node->_M_nxt = __prev->_M_nxt;
__prev->_M_nxt = __node;
- if (__builtin_expect(__prev == __hint, false))
- // hint might be the last bucket node, in this case we need to
- // update next bucket.
- if (__node->_M_nxt
- && !this->_M_equals(__k, __code, *__node->_M_next()))
- {
- size_type __next_bkt = _M_bucket_index(*__node->_M_next());
- if (__next_bkt != __bkt)
- _M_buckets[__next_bkt] = __node;
- }
+
+ // __hint might be the last bucket node, in this case we need to
+ // update next bucket.
+ if (__has_prev && __node->_M_nxt != __info._M_equi_n)
+ {
+ const auto __nxt = __node->_M_next();
+ if (!this->_M_equals(__k, __code, *__nxt))
+ {
+ size_type __next_bkt = _M_bucket_index(*__nxt);
+ if (__next_bkt != _M_bucket_index(__code))
+ _M_buckets[__next_bkt] = __node;
+ }
+ }
+
+ __hint_policy._M_checked_set(__node);
}
else
- // The inserted node has no equivalent in the hashtable. We must
- // insert the new node at the beginning of the bucket to preserve
- // equivalent elements' relative positions.
- _M_insert_bucket_begin(__bkt, __node);
+ {
+ // The inserted node has no equivalent in the hashtable. We must
+ // insert the new node at the beginning of the bucket to preserve
+ // equivalent elements' relative positions.
+ _M_insert_bucket_begin(__hint_policy, __bkt, __node);
+ }
+
++_M_element_count;
return iterator(__node);
}
@@ -2323,15 +2548,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert_unique(_Kt&& __k, _Arg&& __v,
+ _M_insert_unique(_HintPolicy& __hint_policy, _Kt&& __k, _Arg&& __v,
_NodeGenerator& __node_gen)
-> pair<iterator, bool>
{
const size_type __size = size();
if (__size <= __small_size_threshold())
- for (auto __it = _M_begin(); __it; __it = __it->_M_next())
- if (this->_M_key_equals_tr(__k, *__it))
- return { iterator(__it), false };
+ {
+ __node_ptr __last_n = nullptr;
+ for (auto __n = _M_begin(); __n;
+ __last_n = __n, __n = __n->_M_next())
+ if (this->_M_key_equals_tr(__k, *__n))
+ return { iterator(__n), false };
+
+ __hint_policy._M_set_last(__last_n);
+ }
__hash_code __code = this->_M_hash_code_tr(__k);
size_type __bkt = _M_bucket_index(__code);
@@ -2346,8 +2577,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__node_gen),
this
};
+
auto __pos
- = _M_insert_unique_node(__bkt, __code, __node._M_node);
+ = _M_insert_unique_node(__hint_policy, __bkt, __code, __node._M_node);
__node._M_node = nullptr;
return { __pos, true };
}
@@ -2361,20 +2593,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert(const_iterator __hint, _Arg&& __v,
- _NodeGenerator& __node_gen,
- false_type /* __uks */)
+ _M_insert(_HintPolicy& __hint_policy, _Arg&& __v,
+ _NodeGenerator& __node_gen, false_type /* __uks */)
-> iterator
{
// First allocate new node so that we don't do anything if it throws.
- _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
+ _Scoped_node __node { __node_gen(std::forward<_Arg>(__v)), this };
// Second compute the hash code so that we don't rehash if it throws.
- auto __res = this->_M_compute_hash_code(
- __hint._M_cur, _ExtractKey{}(__node._M_node->_M_v()));
-
- auto __pos
- = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
+ auto __info =
+ _M_get_insert_info(__hint_policy,
+ _ExtractKey{}(__node._M_node->_M_v()));
+ auto __pos = _M_insert_multi_node(__hint_policy,
+ __info, __node._M_node);
__node._M_node = nullptr;
return __pos;
}
@@ -2388,10 +2619,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert_range(_InputIterator __first, _InputIterator __last,
- _NodeGenerator& __node_gen)
+ _HintPolicy& __hint_policy, _NodeGenerator& __node_gen)
{
for (; __first != __last; ++__first)
- _M_insert(*__first, __node_gen, __unique_keys{});
+ _M_insert(__hint_policy, *__first, __node_gen, __unique_keys{});
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2438,7 +2669,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator __result(__n->_M_next());
this->_M_deallocate_node(__n);
--_M_element_count;
-
+ _M_check_for_last(__prev_n);
return __result;
}
@@ -2547,7 +2778,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
else if (__n_last_bkt != __bkt)
_M_buckets[__n_last_bkt] = __prev_n;
+
__prev_n->_M_nxt = __n_last;
+ _M_check_for_last(__prev_n);
return __result;
}
@@ -2595,6 +2828,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__n && (__n_bkt != __bkt || __is_bucket_begin))
_M_buckets[__n_bkt] = __prev_n;
__prev_n->_M_nxt = __n;
+ _M_check_for_last(__prev_n);
return iterator(__n);
}
@@ -2612,6 +2846,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_bucket_count * sizeof(__node_base_ptr));
_M_element_count = 0;
_M_before_begin._M_nxt = nullptr;
+ _M_set_last(nullptr);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2621,7 +2856,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- rehash(size_type __bkt_count)
+ _M_rehash(_HintPolicy& __hint_policy, size_type __bkt_count)
{
__rehash_guard_t __rehash_guard(_M_rehash_policy);
__bkt_count
@@ -2631,7 +2866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__bkt_count != _M_bucket_count)
{
- _M_rehash(__bkt_count, __unique_keys{});
+ _M_rehash(__hint_policy, __bkt_count, __unique_keys{});
__rehash_guard._M_guarded_obj = nullptr;
}
}
@@ -2644,9 +2879,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_rehash(size_type __bkt_count, true_type /* __uks */)
+ _M_rehash(_HintPolicy& __hint_policy,
+ size_type __bkt_count, true_type /* __uks */)
{
__buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
+ __node_ptr __prev_p = nullptr;
__node_ptr __p = _M_begin();
_M_before_begin._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
@@ -2670,12 +2907,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__new_buckets[__bkt]->_M_nxt = __p;
}
+ __prev_p = __p;
__p = __next;
}
_M_deallocate_buckets();
_M_bucket_count = __bkt_count;
_M_buckets = __new_buckets;
+ __hint_policy._M_set_last(__prev_p);
}
// Rehash when there can be equivalent elements, preserve their relative
@@ -2687,7 +2926,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_rehash(size_type __bkt_count, false_type /* __uks */)
+ _M_rehash(_HintPolicy& __hint_policy,
+ size_type __bkt_count, false_type /* __uks */)
{
__buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
__node_ptr __p = _M_begin();
@@ -2750,6 +2990,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__new_buckets[__bkt]->_M_nxt = __p;
}
}
+
__prev_p = __p;
__prev_bkt = __bkt;
__p = __next;
@@ -2767,6 +3008,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_deallocate_buckets();
_M_bucket_count = __bkt_count;
_M_buckets = __new_buckets;
+ __hint_policy._M_set_last(__prev_p);
}
#if __cplusplus > 201402L
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
b/libstdc++-v3/include/bits/hashtable_policy.h
index 9f775522cff..c8905f59289 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -848,8 +848,9 @@ namespace __detail
std::tuple<const key_type&>(__k),
std::tuple<>()
};
- auto __pos
- = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
+ auto __hint_policy = __h->_M_get_hint_policy();
+ auto __pos = __h->_M_insert_unique_node(__hint_policy, __bkt, __code,
+ __node._M_node);
__node._M_node = nullptr;
return __pos->second;
}
@@ -875,8 +876,9 @@ namespace __detail
std::forward_as_tuple(std::move(__k)),
std::tuple<>()
};
- auto __pos
- = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
+ auto __hint_policy = __h->_M_get_hint_policy();
+ auto __pos = __h->_M_insert_unique_node(__hint_policy, __bkt, __code,
+ __node._M_node);
__node._M_node = nullptr;
return __pos->second;
}
@@ -964,13 +966,14 @@ namespace __detail
insert(const_iterator __hint, const value_type& __v)
{
__hashtable& __h = _M_conjure_hashtable();
- __node_gen_type __node_gen(__h);
- return __h._M_insert(__hint, __v, __node_gen, __unique_keys{});
+ auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur);
+ __node_gen_type __node_gen(__h);
+ return __h._M_insert(__hint_policy, __v, __node_gen, __unique_keys{});
}
template<typename _KType, typename... _Args>
std::pair<iterator, bool>
- try_emplace(const_iterator, _KType&& __k, _Args&&... __args)
+ try_emplace(const_iterator __hint, _KType&& __k, _Args&&... __args)
{
__hashtable& __h = _M_conjure_hashtable();
auto __code = __h._M_hash_code(__k);
@@ -984,8 +987,9 @@ namespace __detail
std::forward_as_tuple(std::forward<_KType>(__k)),
std::forward_as_tuple(std::forward<_Args>(__args)...)
};
- auto __it
- = __h._M_insert_unique_node(__bkt, __code, __node._M_node);
+ auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur);
+ auto __it = __h._M_insert_unique_node(__hint_policy, __bkt, __code,
+ __node._M_node);
__node._M_node = nullptr;
return { __it, true };
}
@@ -1013,8 +1017,9 @@ namespace __detail
true_type /* __uks */)
{
__hashtable& __h = _M_conjure_hashtable();
+ auto __hint_policy = __h._M_get_hint_policy();
__node_gen_type __node_gen(__h);
- __h._M_insert_range(__first, __last, __node_gen);
+ __h._M_insert_range(__first, __last, __hint_policy, __node_gen);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -1037,6 +1042,7 @@ namespace __detail
return;
__hashtable& __h = _M_conjure_hashtable();
+ auto __hint_policy = __h._M_get_hint_policy();
__rehash_guard_t __rehash_guard(__h._M_rehash_policy);
__pair_type __do_rehash
= __h._M_rehash_policy._M_need_rehash(__h._M_bucket_count,
@@ -1044,11 +1050,11 @@ namespace __detail
__n_elt);
if (__do_rehash.first)
- __h._M_rehash(__do_rehash.second, __uks);
+ __h._M_rehash(__hint_policy, __do_rehash.second, __uks);
__rehash_guard._M_guarded_obj = nullptr;
__node_gen_type __node_gen(__h);
- __h._M_insert_range(__first, __last, __node_gen);
+ __h._M_insert_range(__first, __last, __hint_policy, __node_gen);
}
/**
@@ -1102,8 +1108,9 @@ namespace __detail
insert(const_iterator __hint, value_type&& __v)
{
__hashtable& __h = this->_M_conjure_hashtable();
+ auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur);
__node_gen_type __node_gen(__h);
- return __h._M_insert(__hint, std::move(__v), __node_gen,
+ return __h._M_insert(__hint_policy, std::move(__v), __node_gen,
__unique_keys{});
}
};
@@ -1153,7 +1160,8 @@ namespace __detail
insert(const_iterator __hint, _Pair&& __v)
{
__hashtable& __h = this->_M_conjure_hashtable();
- return __h._M_emplace(__hint, __unique_keys{},
+ auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur);
+ return __h._M_emplace(__hint_policy, __unique_keys{},
std::forward<_Pair>(__v));
}
};
diff --git a/libstdc++-v3/include/bits/unordered_map.h
b/libstdc++-v3/include/bits/unordered_map.h
index 1c99a83bc1e..e5df97c9229 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -443,12 +443,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)); }
+ { return _M_h._M_reinsert_node(cend(), std::move(__nh)); }
/// Re-insert an extracted node.
iterator
- insert(const_iterator, node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+ insert(const_iterator __hint, node_type&& __nh)
+ { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
#endif // C++17
#ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
diff --git a/libstdc++-v3/include/bits/unordered_set.h
b/libstdc++-v3/include/bits/unordered_set.h
index f3b0c078baa..915cd4fb700 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -504,12 +504,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)); }
+ { return _M_h._M_reinsert_node(cend(), std::move(__nh)); }
/// Re-insert an extracted node.
iterator
- insert(const_iterator, node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+ insert(const_iterator __hint, node_type&& __nh)
+ { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
#endif // C++17
///@{
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
index d0ed60c6799..1db71b8f30b 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
@@ -40,11 +40,12 @@ void test01()
VERIFY( it2 != m.end() );
VERIFY( it2 != it1 );
VERIFY( it2->second == 2 );
- VERIFY( it2 == std::next(it1) );
+ VERIFY( std::next(it2) == it1 );
+ it1 = it2;
Pair p(0, 1);
it2 = m.insert(it1, p);
- VERIFY( it2 == std::next(it1) );
+ VERIFY( std::next(it2) == it1 );
}
struct hasher
@@ -71,13 +72,13 @@ void test02()
VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 );
auto it4 = m.insert(it1, Pair(0, 1));
- VERIFY( it4 == std::next(it1) );
+ VERIFY( std::next(it4) == it1 );
VERIFY( m.bucket_size(m.bucket(it1->first)) == 3 );
VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 );
Pair p(1, 1);
it4 = m.insert(it2, p);
- VERIFY( it4 == std::next(it2) );
+ VERIFY( std::next(it4) == it2 );
VERIFY( m.bucket_size(m.bucket(it1->first)) == 4 );
auto range = m.equal_range(0);
VERIFY( std::distance(range.first, range.second) == 2 );
@@ -104,11 +105,12 @@ void test03()
VERIFY( it2 != m.end() );
VERIFY( it2 != it1 );
VERIFY( it2->second == 2 );
- VERIFY( it2 == std::next(it1) );
+ VERIFY( std::next(it2) == it1 );
+ it1 = it2;
Pair p(0, 1);
it2 = m.emplace_hint(it1, p);
- VERIFY( it2 == std::next(it1) );
+ VERIFY( std::next(it2) == it1 );
}
int main()
