@@ -288,10 +288,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using __reuse_or_alloc_node_gen_t =
__detail::_ReuseOrAllocNode<__node_alloc_type>;
- using __alloc_node_gen_t =
- __detail::_AllocNode<__node_alloc_type>;
+ using __alloc_node_gen_cache_bbegin_t =
+ __detail::_AllocNode<__node_alloc_type, __detail::_CacheBBeginPolicy>;
using __node_builder_t =
__detail::_NodeBuilder<_ExtractKey>;
+ using __no_cache_bbegin_policy_t =
+ __detail::_NoCacheBBeginPolicy;
+ using __cache_bbegin_policy_t =
+ __detail::_CacheBBeginPolicy;
// Simple RAII type for managing a node containing an element
struct _Scoped_node
@@ -376,6 +380,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool _Unique_keysa>
friend struct __detail::_Equality;
+ friend struct __detail::_CacheBBeginPolicy;
+ friend struct __detail::_NoCacheBBeginPolicy;
+
public:
using size_type = typename __hashtable_base::size_type;
using difference_type = typename __hashtable_base::difference_type;
@@ -872,8 +879,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
// Insert a node at the beginning of a bucket.
- void
- _M_insert_bucket_begin(size_type, __node_ptr);
+ template<typename _BBeginPolicy>
+ void
+ _M_insert_bucket_begin(size_type, __node_ptr, const _BBeginPolicy&);
// Remove the bucket first node
void
@@ -890,15 +898,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// 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,
- __node_ptr __n, size_type __n_elt = 1);
+ template<typename _BBeginPolicy>
+ iterator
+ _M_insert_unique_node(size_type __bkt, __hash_code,
+ __node_ptr __n, const _BBeginPolicy&,
+ size_type __n_elt = 1);
// Insert node __n with key __k and hash code __code.
// Takes ownership of __n if insertion succeeds, throws otherwise.
- iterator
- _M_insert_multi_node(__node_ptr __hint,
- __hash_code __code, __node_ptr __n);
+ template<typename _BBeginPolicy>
+ iterator
+ _M_insert_multi_node(__node_ptr __hint, __hash_code,
+ __node_ptr __n, const _BBeginPolicy&);
template<typename... _Args>
std::pair<iterator, bool>
@@ -1087,8 +1098,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
{
+ __no_cache_bbegin_policy_t __bbegin_policy;
__ret.position
- = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
+ = _M_insert_unique_node(__bkt, __code, __nh._M_ptr,
+ __bbegin_policy);
__nh._M_ptr = nullptr;
__ret.inserted = true;
}
@@ -1117,8 +1130,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__hint = cend();
}
+ __no_cache_bbegin_policy_t __bbegin_policy;
auto __ret
- = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
+ = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr,
+ __bbegin_policy);
__nh._M_ptr = nullptr;
return __ret;
}
@@ -1175,6 +1190,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type>, "Node types are compatible");
__glibcxx_assert(get_allocator() == __src.get_allocator());
+ __cache_bbegin_policy_t __bbegin_policy;
auto __n_elt = __src.size();
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
{
@@ -1186,7 +1202,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (_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(__bkt, __code, __nh._M_ptr,
+ __bbegin_policy, __n_elt);
__nh._M_ptr = nullptr;
__n_elt = 1;
}
@@ -1204,6 +1221,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type>, "Node types are compatible");
__glibcxx_assert(get_allocator() == __src.get_allocator());
+ __cache_bbegin_policy_t __bbegin_policy;
__node_ptr __hint = nullptr;
this->reserve(size() + __src.size());
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
@@ -1220,7 +1238,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
auto __nh = __src.extract(__pos);
- __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
+ __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr,
+ __bbegin_policy)._M_cur;
__nh._M_ptr = nullptr;
}
}
@@ -1310,7 +1329,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_bucket_count = __bkt_count;
}
- __alloc_node_gen_t __node_gen(*this);
+ __alloc_node_gen_cache_bbegin_t __node_gen(*this);
for (; __f != __l; ++__f)
_M_insert(*__f, __node_gen, __uks);
}
@@ -1345,10 +1364,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_bucket_count = __ht._M_bucket_count;
_M_element_count = __ht._M_element_count;
_M_rehash_policy = __ht._M_rehash_policy;
- __alloc_node_gen_t __alloc_node_gen(*this);
+ __alloc_node_gen_cache_bbegin_t __node_gen(*this);
__try
{
- _M_assign(__ht, __alloc_node_gen);
+ _M_assign(__ht, __node_gen);
}
__catch(...)
{
@@ -1556,8 +1575,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
- __alloc_node_gen_t __alloc_node_gen(*this);
- _M_assign(__ht, __alloc_node_gen);
+ __alloc_node_gen_cache_bbegin_t __node_gen(*this);
+ _M_assign(__ht, __node_gen);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -1610,8 +1629,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
- __alloc_node_gen_t __alloc_node_gen(*this);
- _M_assign(__ht, __alloc_node_gen);
+ __alloc_node_gen_cache_bbegin_t __node_gen(*this);
+ _M_assign(__ht, __node_gen);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -1650,12 +1669,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
{
- __alloc_node_gen_t __alloc_gen(*this);
-
+ __alloc_node_gen_cache_bbegin_t __node_gen(*this);
using _Fwd_Ht = __conditional_t<
__move_if_noexcept_cond<value_type>::value,
const _Hashtable&, _Hashtable&&>;
- _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
+ _M_assign(std::forward<_Fwd_Ht>(__ht), __node_gen);
__ht.clear();
}
}
@@ -2079,34 +2097,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
- void
- _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
- {
- 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;
- }
- 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;
- }
- }
+ template<typename _BBeginPolicy>
+ void
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_insert_bucket_begin(size_type __bkt, __node_ptr __node,
+ const _BBeginPolicy& __bb_policy)
+ {
+ 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;
+ }
+ 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[__bb_policy._M_get_bbegin_bkt(*this, __node->_M_next())]
+ = __node;
+
+ __bb_policy._M_store_bbegin_bkt(__bkt);
+ _M_buckets[__bkt] = &_M_before_begin;
+ }
+ }
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
@@ -2190,8 +2212,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__bkt = _M_bucket_index(__code);
}
+ __no_cache_bbegin_policy_t __bbegin_policy;
// Insert the node
- auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
+ auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node,
+ __bbegin_policy);
__node._M_node = nullptr;
return { __pos, true };
}
@@ -2213,9 +2237,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
auto __res = this->_M_compute_hash_code(__hint, __k);
+ __no_cache_bbegin_policy_t __bbegin_policy;
auto __pos
= _M_insert_multi_node(__res.first._M_cur, __res.second,
- __node._M_node);
+ __node._M_node, __bbegin_policy);
__node._M_node = nullptr;
return __pos;
}
@@ -2255,86 +2280,93 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
- auto
- _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert_unique_node(size_type __bkt, __hash_code __code,
- __node_ptr __node, size_type __n_elt)
- -> iterator
- {
- const __rehash_state& __saved_state = _M_rehash_policy._M_state();
- std::pair<bool, std::size_t> __do_rehash
- = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
- __n_elt);
+ template<typename _BBeginPolicy>
+ auto
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_insert_unique_node(size_type __bkt, __hash_code __code,
+ __node_ptr __node,
+ const _BBeginPolicy& __bbegin_policy,
+ size_type __n_elt)
+ -> iterator
+ {
+ const __rehash_state& __saved_state = _M_rehash_policy._M_state();
+ std::pair<bool, std::size_t> __do_rehash
+ = _M_rehash_policy._M_need_rehash(_M_bucket_count,
+ _M_element_count,
+ __n_elt);
- if (__do_rehash.first)
- {
- _M_rehash(__do_rehash.second, __saved_state);
- __bkt = _M_bucket_index(__code);
- }
+ if (__do_rehash.first)
+ {
+ _M_rehash(__do_rehash.second, __saved_state);
+ __bkt = _M_bucket_index(__code);
+ }
- this->_M_store_code(*__node, __code);
+ this->_M_store_code(*__node, __code);
- // Always insert at the beginning of the bucket.
- _M_insert_bucket_begin(__bkt, __node);
- ++_M_element_count;
- return iterator(__node);
- }
+ // Always insert at the beginning of the bucket.
+ _M_insert_bucket_begin(__bkt, __node, __bbegin_policy);
+ ++_M_element_count;
+ return iterator(__node);
+ }
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
- 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)
- -> iterator
- {
- const __rehash_state& __saved_state = _M_rehash_policy._M_state();
- std::pair<bool, std::size_t> __do_rehash
- = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
+ template<typename _BBeginPolicy>
+ 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,
+ const _BBeginPolicy& __bbegin_policy)
+ -> iterator
+ {
+ const __rehash_state& __saved_state = _M_rehash_policy._M_state();
+ std::pair<bool, std::size_t> __do_rehash
+ = _M_rehash_policy._M_need_rehash(_M_bucket_count,
+ _M_element_count, 1);
- if (__do_rehash.first)
- _M_rehash(__do_rehash.second, __saved_state);
+ if (__do_rehash.first)
+ _M_rehash(__do_rehash.second, __saved_state);
- this->_M_store_code(*__node, __code);
- const key_type& __k = _ExtractKey{}(__node->_M_v());
- size_type __bkt = _M_bucket_index(__code);
+ this->_M_store_code(*__node, __code);
+ const key_type& __k = _ExtractKey{}(__node->_M_v());
+ size_type __bkt = _M_bucket_index(__code);
- // 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 &&
- this->_M_equals(__k, __code, *__hint), false)
- ? __hint
- : _M_find_before_node(__bkt, __k, __code);
+ // 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 &&
+ this->_M_equals(__k, __code, *__hint), false)
+ ? __hint
+ : _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 (__prev == __hint) [[__unlikely__]]
- // 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;
- }
- }
- 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);
- ++_M_element_count;
- return iterator(__node);
- }
+ if (__prev)
+ {
+ // Insert after the node before the equivalent one.
+ __node->_M_nxt = __prev->_M_nxt;
+ __prev->_M_nxt = __node;
+ if (__prev == __hint) [[__unlikely__]]
+ // 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;
+ }
+ }
+ 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, __bbegin_policy);
+ ++_M_element_count;
+ return iterator(__node);
+ }
// Insert v if no element with its key is already present.
template<typename _Key, typename _Value, typename _Alloc,
@@ -2374,8 +2406,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
this
};
- auto __pos
- = _M_insert_unique_node(__bkt, __code, __node._M_node);
+ auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node,
+ __node_gen);
__node._M_node = nullptr;
return { __pos, true };
}
@@ -2403,7 +2435,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__hint, _ExtractKey{}(__node._M_node->_M_v()));
auto __pos
= _M_insert_multi_node(__res.first._M_cur, __res.second,
- __node._M_node);
+ __node._M_node, __node_gen);
__node._M_node = nullptr;
return __pos;
}
@@ -176,13 +176,47 @@ namespace __detail
{ return __node_gen(__hint, std::forward<_Kt>(__k)); }
};
+ struct _CacheBBeginPolicy
+ {
+ template<typename _Ht, typename _NodePtr>
+ std::size_t
+ _M_get_bbegin_bkt(const _Ht& __ht, _NodePtr __n) const
+ {
+ if (!_M_initialized)
+ return __ht._M_bucket_index(*__n);
+ return _M_bbegin_index;
+ }
+
+ void
+ _M_store_bbegin_bkt(std::size_t __bkt) const
+ {
+ _M_bbegin_index = __bkt;
+ _M_initialized = true;
+ }
+
+ mutable bool _M_initialized = false;
+ mutable std::size_t _M_bbegin_index;
+ };
+
+ struct _NoCacheBBeginPolicy
+ {
+ template<typename _Ht, typename _NodePtr>
+ std::size_t
+ _M_get_bbegin_bkt(const _Ht& __ht, _NodePtr __n) const
+ { return __ht._M_bucket_index(*__n); }
+
+ void
+ _M_store_bbegin_bkt(std::size_t) const
+ { }
+ };
+
template<typename _NodeAlloc>
struct _Hashtable_alloc;
// Functor recycling a pool of nodes and using allocation once the pool is
// empty.
template<typename _NodeAlloc>
- struct _ReuseOrAllocNode
+ struct _ReuseOrAllocNode : _CacheBBeginPolicy
{
private:
using __node_alloc_type = _NodeAlloc;
@@ -236,8 +270,8 @@ namespace __detail
// Functor similar to the previous one but without any pool of nodes to
// recycle.
- template<typename _NodeAlloc>
- struct _AllocNode
+ template<typename _NodeAlloc, typename _BBeginPolicy>
+ struct _AllocNode : _BBeginPolicy
{
private:
using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
@@ -824,8 +858,10 @@ namespace __detail
std::tuple<const key_type&>(__k),
std::tuple<>()
};
+ _NoCacheBBeginPolicy __bbegin_policy;
auto __pos
- = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
+ = __h->_M_insert_unique_node(__bkt, __code, __node._M_node,
+ __bbegin_policy);
__node._M_node = nullptr;
return __pos->second;
}
@@ -852,8 +888,10 @@ namespace __detail
std::forward_as_tuple(std::move(__k)),
std::tuple<>()
};
+ _NoCacheBBeginPolicy __bbegin_policy;
auto __pos
- = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
+ = __h->_M_insert_unique_node(__bkt, __code, __node._M_node,
+ __bbegin_policy);
__node._M_node = nullptr;
return __pos->second;
}
@@ -901,7 +939,8 @@ namespace __detail
using __unique_keys = typename _Traits::__unique_keys;
using __node_alloc_type = typename __hashtable_alloc::__node_alloc_type;
- using __node_gen_type = _AllocNode<__node_alloc_type>;
+ template<typename _BBeginPolicy>
+ using __alloc_node_gen_t = _AllocNode<__node_alloc_type, _BBeginPolicy>;
__hashtable&
_M_conjure_hashtable()
@@ -933,7 +972,7 @@ namespace __detail
insert(const value_type& __v)
{
__hashtable& __h = _M_conjure_hashtable();
- __node_gen_type __node_gen(__h);
+ __alloc_node_gen_t<_NoCacheBBeginPolicy> __node_gen(__h);
return __h._M_insert(__v, __node_gen, __unique_keys{});
}
@@ -941,7 +980,7 @@ namespace __detail
insert(const_iterator __hint, const value_type& __v)
{
__hashtable& __h = _M_conjure_hashtable();
- __node_gen_type __node_gen(__h);
+ __alloc_node_gen_t<_NoCacheBBeginPolicy> __node_gen(__h);
return __h._M_insert(__hint, __v, __node_gen, __unique_keys{});
}
@@ -961,8 +1000,10 @@ namespace __detail
std::forward_as_tuple(std::forward<_KType>(__k)),
std::forward_as_tuple(std::forward<_Args>(__args)...)
};
+ _NoCacheBBeginPolicy __bbegin_policy;
auto __it
- = __h._M_insert_unique_node(__bkt, __code, __node._M_node);
+ = __h._M_insert_unique_node(__bkt, __code, __node._M_node,
+ __bbegin_policy);
__node._M_node = nullptr;
return { __it, true };
}
@@ -985,7 +1026,7 @@ namespace __detail
insert(_InputIterator __first, _InputIterator __last)
{
__hashtable& __h = _M_conjure_hashtable();
- __node_gen_type __node_gen(__h);
+ __alloc_node_gen_t<_CacheBBeginPolicy> __node_gen(__h);
return _M_insert_range(__first, __last, __node_gen, __unique_keys{});
}
};
@@ -1076,15 +1117,15 @@ namespace __detail
using __unique_keys = typename __base_type::__unique_keys;
using __hashtable = typename __base_type::__hashtable;
- using __node_gen_type = typename __base_type::__node_gen_type;
-
+ using __alloc_node_gen_t
+ = typename __base_type::__alloc_node_gen_t<_NoCacheBBeginPolicy>;
using __base_type::insert;
__ireturn_type
insert(value_type&& __v)
{
__hashtable& __h = this->_M_conjure_hashtable();
- __node_gen_type __node_gen(__h);
+ __alloc_node_gen_t __node_gen(__h);
return __h._M_insert(std::move(__v), __node_gen, __unique_keys{});
}
@@ -1092,7 +1133,7 @@ namespace __detail
insert(const_iterator __hint, value_type&& __v)
{
__hashtable& __h = this->_M_conjure_hashtable();
- __node_gen_type __node_gen(__h);
+ __alloc_node_gen_t __node_gen(__h);
return __h._M_insert(__hint, std::move(__v), __node_gen,
__unique_keys{});
}