This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: hashtable local iterator
Hi
Here is a new proposition to fix the unordered containers
local_iterator Standard non-conforming regression.
I finally introduce no modification in hashtable data model, a
bucket is still a simple node pointer. I simply embed the necessary
functors in local_iterator instances. However I had to put some
constraints on functor types used to instantiate _Hashtable. If hash
code are cached only the type used to map hash codes to bucket indexes
needs to be empty, otherwise the extract key, h1, h2 and hash functors
must all be empty. The consequence is that cache hash code flag default
value in unordered_XXX types now depends on hash functor emptiness, if
hash functor is not an empty type hash code will be put in cache so that
local iterators are not invalidated when hashtable instances are swapped.
I have however a remark regarding this patch. For the moment, on my
64bits platform, sizeof(local_iterator) is 32 while it should normally
be 24 for the 2 size_t and the node pointer. I thought about using
inheritance in _Hash_code_base type in replacement of _M_extract, _M_h1,
_M_h2, _M_hash fields to benefit from EBO, would it be ok ? This way I
could replace the static assertion:
static_assert(__or_<integral_constant<bool, __cache_hash_code>,
__and_<is_empty<_H1>, is_empty<_H2>,
is_empty<_Hash>, is_empty<_ExtractKey>>>::value,
"Cache the hash code or make _ExtractKey, _H1 and _Hash
functors"
" empty");
with the more accurate:
static_assert(__or_<integral_constant<bool, __cache_hash_code>,
is_empty<_HCBase>>::value,
"Cache the hash code or make _ExtractKey, _H1 and _Hash
functors"
" empty");
because H1, H2 and Hash are never used all together.
I already noticed that I couldn't inherit from both _Hash and _Equal
because those 2 types might be identical resulting in an ambiguity. But
between _ExtractKey, _H1, _H2 and _Hash there is no chance of ambiguity.
2011-12-19 François Dumont <fdumont@gcc.gnu.org>
* include/bits/hashtable_policy.h (_Equal_helper<>) New.
(_Hash_code_base): Move _Equal functor management...
(_Hashtable_base)
...here, new, use _Equal_helper. (_Local_iterator_base<>,
_Locale_iterator<>, _Locale_const_iterator<>): New, use
_Hash_code_base,
implementation of...
* include/bits/hashtable.h (_Hashtable<>::local_iterator,
_Hashtable<>::const_local_iterator): ...those. Add static
assertions
checking that some functors are empty depending on whether hash
code
is cache or not. (_Hashtable<>::_M_bucket_index): New overloads
using
current bucket count, use through out the _Hastable<>
implementation.
* include/bits/unordered_set.h (__unordered_set<>,
__unordered_multiset<>): Cache hash code if hash functor is not
empty.
* include/bits/unordere_map.H (__unordered_map<>,
__unordered_multimap<>): Likewise.
* include/debug/unordered_map
(unordered_map<>::_S_to_local, unordered_multimap<>::_S_to_local):
Adapt to match new local iterator implementation.
* include/debug/unordered_set (unordered_set<>::_S_to_local,
unordered_multiset<>::_S_to_local): Likewise.
* include/profile/unordered_map
(unordered_map<>::_M_profile_destruct,
unordered_multimap<>::_M_profile_destruct): Enhance thanks to
usage of
local iterators.
* include/profile/unordered_set
(unordered_set<>::_M_profile_destruct,
unordered_multiset<>::_M_profile_destruct): Likewise.
François
Index: include/debug/unordered_map
===================================================================
--- include/debug/unordered_map (revision 182411)
+++ include/debug/unordered_map (working copy)
@@ -418,11 +418,19 @@
static _Base_local_iterator
_S_to_local(_Base_iterator __it)
- { return _Base_local_iterator(__it._M_cur); }
+ {
+ // The return local iterator is not going to be incremented so we don't
+ // need to compute __it node bucket
+ return _Base_local_iterator(__it._M_cur, 0, 0);
+ }
static _Base_const_local_iterator
_S_to_local(_Base_const_iterator __it)
- { return _Base_const_local_iterator(__it._M_cur); }
+ {
+ // The return local iterator is not going to be incremented so we don't
+ // need to compute __it node bucket
+ return _Base_const_local_iterator(__it._M_cur, 0, 0);
+ }
};
template<typename _Key, typename _Tp, typename _Hash,
@@ -820,11 +828,19 @@
static _Base_local_iterator
_S_to_local(_Base_iterator __it)
- { return _Base_local_iterator(__it._M_cur); }
+ {
+ // The return local iterator is not going to be incremented so we don't
+ // need to compute __it node bucket
+ return _Base_local_iterator(__it._M_cur, 0, 0);
+ }
static _Base_const_local_iterator
_S_to_local(_Base_const_iterator __it)
- { return _Base_const_local_iterator(__it._M_cur); }
+ {
+ // The return local iterator is not going to be incremented so we don't
+ // need to compute __it node bucket
+ return _Base_const_local_iterator(__it._M_cur, 0, 0);
+ }
};
template<typename _Key, typename _Tp, typename _Hash,
Index: include/debug/unordered_set
===================================================================
--- include/debug/unordered_set (revision 182411)
+++ include/debug/unordered_set (working copy)
@@ -417,11 +417,19 @@
static _Base_local_iterator
_S_to_local(_Base_iterator __it)
- { return _Base_local_iterator(__it._M_cur); }
+ {
+ // The return local iterator is not going to be incremented so we don't
+ // need to compute __it node bucket
+ return _Base_local_iterator(__it._M_cur, 0, 0);
+ }
static _Base_const_local_iterator
_S_to_local(_Base_const_iterator __it)
- { return _Base_const_local_iterator(__it._M_cur); }
+ {
+ // The return local iterator is not going to be incremented so we don't
+ // need to compute __it node bucket
+ return _Base_const_local_iterator(__it._M_cur, 0, 0);
+ }
};
template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
@@ -805,11 +813,19 @@
static _Base_local_iterator
_S_to_local(_Base_iterator __it)
- { return _Base_local_iterator(__it._M_cur); }
+ {
+ // The return local iterator is not going to be incremented so we don't
+ // need to compute __it node bucket
+ return _Base_local_iterator(__it._M_cur, 0, 0);
+ }
static _Base_const_local_iterator
_S_to_local(_Base_const_iterator __it)
- { return _Base_const_local_iterator(__it._M_cur); }
+ {
+ // The return local iterator is not going to be incremented so we don't
+ // need to compute __it node bucket
+ return _Base_const_local_iterator(__it._M_cur, 0, 0);
+ }
};
template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
Index: include/profile/unordered_map
===================================================================
--- include/profile/unordered_map (revision 182411)
+++ include/profile/unordered_map (working copy)
@@ -308,9 +308,9 @@
while (__it != this->end())
{
size_type __bkt = this->bucket(__it->first);
- for (++__it; __it != this->end()
- && this->bucket(__it->first) == __bkt;
- ++__it)
+ auto __lit = this->begin(__bkt);
+ auto __lend = this->end(__bkt);
+ for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
++__chain;
if (__chain)
{
@@ -577,9 +577,9 @@
while (__it != this->end())
{
size_type __bkt = this->bucket(__it->first);
- for (++__it; __it != this->end()
- && this->bucket(__it->first) == __bkt;
- ++__it)
+ auto __lit = this->begin(__bkt);
+ auto __lend = this->end(__bkt);
+ for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
++__chain;
if (__chain)
{
Index: include/profile/unordered_set
===================================================================
--- include/profile/unordered_set (revision 182411)
+++ include/profile/unordered_set (working copy)
@@ -277,10 +277,10 @@
while (__it != this->end())
{
size_type __bkt = this->bucket(*__it);
- for (++__it; __it != this->end() && this->bucket(*__it) == __bkt;
- ++__it)
+ auto __lit = this->begin(__bkt);
+ auto __lend = this->end(__bkt);
+ for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
++__chain;
-
if (__chain)
{
++__chain;
@@ -539,10 +539,10 @@
while (__it != this->end())
{
size_type __bkt = this->bucket(*__it);
- for (++__it; __it != this->end() && this->bucket(*__it) == __bkt;
- ++__it)
+ auto __lit = this->begin(__bkt);
+ auto __lend = this->end(__bkt);
+ for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
++__chain;
-
if (__chain)
{
++__chain;
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 182411)
+++ include/bits/hashtable.h (working copy)
@@ -155,7 +155,7 @@
__cache_hash_code,
__constant_iterators,
__unique_keys> >,
- public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+ public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
_H1, _H2, _Hash, __cache_hash_code>,
public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
_Hashtable<_Key, _Value, _Allocator,
@@ -177,6 +177,27 @@
static_assert(__or_<integral_constant<bool, __cache_hash_code>,
__detail::__is_noexcept_hash<_Key, _H1>>::value,
"Cache the hash code or qualify your hash functor with noexcept");
+ // Following two static assertions are necessary to guaranty that swapping
+ // two hashtable instances won't invalidate associated local iterators.
+
+ // When hash codes are cached local iterator only use H2 that then have to
+ // be empty.
+ static_assert(__or_<__not_<integral_constant<bool, __cache_hash_code>>,
+ is_empty<_H2>>::value,
+ "Functor used to map hash code on bucket index must be empty");
+
+ typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash,
+ __cache_hash_code> _HCBase;
+
+ // When hash codes are not cached local iterator is going to use _HCBase
+ // above to compute node bucket index so it has to be empty.
+ static_assert(__or_<integral_constant<bool, __cache_hash_code>,
+ __and_<is_empty<_H1>, is_empty<_H2>,
+ is_empty<_Hash>, is_empty<_ExtractKey>>>::value,
+ "Cache the hash code or make _ExtractKey, _H1 and _Hash functors"
+ " empty");
+
public:
typedef _Allocator allocator_type;
typedef _Value value_type;
@@ -191,17 +212,24 @@
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
+ typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
+ _H1, _H2, _Hash,
+ __constant_iterators,
+ __cache_hash_code>
+ local_iterator;
+ typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
+ _H1, _H2, _Hash,
+ __constant_iterators,
+ __cache_hash_code>
+ const_local_iterator;
typedef __detail::_Node_iterator<value_type, __constant_iterators,
__cache_hash_code>
- local_iterator;
+ iterator;
typedef __detail::_Node_const_iterator<value_type,
__constant_iterators,
__cache_hash_code>
- const_local_iterator;
+ const_iterator;
- typedef local_iterator iterator;
- typedef const_local_iterator const_iterator;
-
template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
typename _Hashtable2>
friend struct __detail::_Map_base;
@@ -212,7 +240,6 @@
typedef typename _Allocator::template rebind<_Node>::other
_Node_allocator_type;
typedef _Node* _Bucket;
- //typedef __detail::_Bucket<_Value, __cache_hash_code> _Bucket;
typedef typename _Allocator::template rebind<_Bucket>::other
_Bucket_allocator_type;
@@ -253,14 +280,6 @@
_Node*
_M_bucket_end(size_type __bkt) const;
- // Gets the bucket node after the last if any
- _Node*
- _M_bucket_past_the_end(size_type __bkt) const
- {
- _Node* __end = _M_bucket_end(__bkt);
- return __end ? __end->_M_next : nullptr;
- }
-
public:
// Constructor, destructor, assignment, swap
_Hashtable(size_type __bucket_hint,
@@ -364,35 +383,35 @@
size_type
bucket(const key_type& __k) const
- {
- return this->_M_bucket_index(__k, this->_M_hash_code(__k),
- bucket_count());
- }
+ { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
local_iterator
begin(size_type __n)
- { return local_iterator(_M_bucket_begin(__n)); }
+ { return local_iterator(_M_bucket_begin(__n), __n,
+ _M_bucket_count); }
local_iterator
end(size_type __n)
- { return local_iterator(_M_bucket_past_the_end(__n)); }
+ { return local_iterator(); }
const_local_iterator
begin(size_type __n) const
- { return const_local_iterator(_M_bucket_begin(__n)); }
+ { return const_local_iterator(_M_bucket_begin(__n), __n,
+ _M_bucket_count); }
const_local_iterator
end(size_type __n) const
- { return const_local_iterator(_M_bucket_past_the_end(__n)); }
+ { return const_local_iterator(); }
// DR 691.
const_local_iterator
cbegin(size_type __n) const
- { return const_local_iterator(_M_bucket_begin(__n)); }
+ { return const_local_iterator(_M_bucket_begin(__n), __n,
+ _M_bucket_count); }
const_local_iterator
cend(size_type __n) const
- { return const_local_iterator(_M_bucket_past_the_end(__n)); }
+ { return const_local_iterator(); }
float
load_factor() const noexcept
@@ -428,6 +447,15 @@
equal_range(const key_type& __k) const;
private:
+ size_type
+ _M_bucket_index(_Node* __n) const
+ { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
+
+ size_type
+ _M_bucket_index(const key_type& __k,
+ typename _Hashtable::_Hash_code_type __c) const
+ { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
+
// Find and insert helper functions and types
_Node*
_M_find_node(size_type, const key_type&,
@@ -679,9 +707,7 @@
_Node* __n = _M_bucket_begin(__bkt);
if (__n)
for (;; __n = __n->_M_next)
- if (!__n->_M_next
- || this->_M_bucket_index(__n->_M_next, _M_bucket_count)
- != __bkt)
+ if (!__n->_M_next || _M_bucket_index(__n->_M_next) != __bkt)
break;
return __n;
}
@@ -697,9 +723,9 @@
const _Equal& __eq, const _ExtractKey& __exk,
const allocator_type& __a)
: __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
- __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
- _H1, _H2, _Hash, __chc>(__exk, __eq,
- __h1, __h2, __h),
+ __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
+ __eq),
__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
_M_node_allocator(__a),
_M_bucket_count(0),
@@ -727,9 +753,9 @@
const _Equal& __eq, const _ExtractKey& __exk,
const allocator_type& __a)
: __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
- __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
- _H1, _H2, _Hash, __chc>(__exk, __eq,
- __h1, __h2, __h),
+ __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
+ __eq),
__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
_M_node_allocator(__a),
_M_bucket_count(0),
@@ -768,7 +794,7 @@
_H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
_Hashtable(const _Hashtable& __ht)
: __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
- __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+ __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
_H1, _H2, _Hash, __chc>(__ht),
__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
_M_node_allocator(__ht._M_node_allocator),
@@ -833,7 +859,7 @@
_H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
_Hashtable(_Hashtable&& __ht)
: __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
- __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+ __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
_H1, _H2, _Hash, __chc>(__ht),
__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
_M_node_allocator(std::move(__ht._M_node_allocator)),
@@ -874,8 +900,7 @@
// The only base class with member variables is hash_code_base. We
// define _Hash_code_base::_M_swap because different specializations
// have different members.
- __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
- _H1, _H2, _Hash, __chc>::_M_swap(__x);
+ _HCBase::_M_swap(__x);
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 431. Swapping containers with unequal allocators.
@@ -916,7 +941,7 @@
find(const key_type& __k)
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __n = _M_bucket_index(__k, __code);
_Node* __p = _M_find_node(__n, __k, __code);
return __p ? iterator(__p) : this->end();
}
@@ -933,7 +958,7 @@
find(const key_type& __k) const
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __n = _M_bucket_index(__k, __code);
_Node* __p = _M_find_node(__n, __k, __code);
return __p ? const_iterator(__p) : this->end();
}
@@ -950,7 +975,7 @@
count(const key_type& __k) const
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __n = _M_bucket_index(__k, __code);
_Node* __p = _M_bucket_begin(__n);
if (!__p)
return 0;
@@ -958,16 +983,14 @@
std::size_t __result = 0;
for (;; __p = __p->_M_next)
{
- if (this->_M_compare(__k, __code, __p))
+ if (this->_M_equals(__k, __code, __p))
++__result;
else if (__result)
// All equivalent values are next to each other, if we found a not
// equivalent value after an equivalent one it means that we won't
// find anymore an equivalent value.
break;
- if (!__p->_M_next
- || this->_M_bucket_index(__p->_M_next, _M_bucket_count)
- != __n)
+ if (!__p->_M_next || _M_bucket_index(__p->_M_next) != __n)
break;
}
return __result;
@@ -990,15 +1013,14 @@
equal_range(const key_type& __k)
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __n = _M_bucket_index(__k, __code);
_Node* __p = _M_find_node(__n, __k, __code);
if (__p)
{
_Node* __p1 = __p->_M_next;
- while (__p1
- && this->_M_bucket_index(__p1, _M_bucket_count) == __n
- && this->_M_compare(__k, __code, __p1))
+ while (__p1 && _M_bucket_index(__p1) == __n
+ && this->_M_equals(__k, __code, __p1))
__p1 = __p1->_M_next;
return std::make_pair(iterator(__p), iterator(__p1));
@@ -1024,15 +1046,14 @@
equal_range(const key_type& __k) const
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __n = _M_bucket_index(__k, __code);
_Node* __p = _M_find_node(__n, __k, __code);
if (__p)
{
_Node* __p1 = __p->_M_next;
- while (__p1
- && this->_M_bucket_index(__p1, _M_bucket_count) == __n
- && this->_M_compare(__k, __code, __p1))
+ while (__p1 && _M_bucket_index(__p1) == __n
+ && this->_M_equals(__k, __code, __p1))
__p1 = __p1->_M_next;
return std::make_pair(const_iterator(__p), const_iterator(__p1));
@@ -1060,10 +1081,9 @@
return nullptr;
for (;; __p = __p->_M_next)
{
- if (this->_M_compare(__k, __code, __p))
+ if (this->_M_equals(__k, __code, __p))
return __p;
- if (!(__p->_M_next)
- || this->_M_bucket_index(__p->_M_next, _M_bucket_count) != __n)
+ if (!(__p->_M_next) || _M_bucket_index(__p->_M_next) != __n)
break;
}
return nullptr;
@@ -1119,8 +1139,7 @@
{
if (__prev_n->_M_next)
{
- size_type __next_bkt =
- this->_M_bucket_index(__prev_n->_M_next, _M_bucket_count);
+ size_type __next_bkt = _M_bucket_index(__prev_n->_M_next);
if (__next_bkt != __bkt)
_M_buckets[__next_bkt] = __new_n;
}
@@ -1199,8 +1218,7 @@
const key_type& __k = this->_M_extract(__new_node->_M_v);
typename _Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k);
- size_type __bkt
- = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ size_type __bkt = _M_bucket_index(__k, __code);
if (_Node* __p = _M_find_node(__bkt, __k, __code))
{
@@ -1220,7 +1238,7 @@
if (__do_rehash.first)
{
_M_rehash(__do_rehash.second, __saved_state);
- __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ __bkt = _M_bucket_index(__k, __code);
}
if (_M_buckets[__bkt])
@@ -1262,8 +1280,7 @@
typename _Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k);
this->_M_store_code(__new_node, __code);
- size_type __bkt
- = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ size_type __bkt = _M_bucket_index(__k, __code);
// Second find the node, avoid rehash if compare throws.
_Node* __prev = _M_find_node(__bkt, __k, __code);
@@ -1271,7 +1288,7 @@
if (__do_rehash.first)
{
_M_rehash(__do_rehash.second, __saved_state);
- __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ __bkt = _M_bucket_index(__k, __code);
// __prev is still valid because rehash do not invalidate nodes
}
@@ -1323,7 +1340,7 @@
if (__do_rehash.first)
{
const key_type& __k = this->_M_extract(__v);
- __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
+ __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
}
_Node* __new_node = nullptr;
@@ -1369,7 +1386,7 @@
{
const key_type& __k = this->_M_extract(__v);
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ size_type __n = _M_bucket_index(__k, __code);
if (_Node* __p = _M_find_node(__n, __k, __code))
return std::make_pair(iterator(__p), false);
@@ -1397,7 +1414,7 @@
const key_type& __k = this->_M_extract(__v);
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ size_type __n = _M_bucket_index(__k, __code);
// First find the node, avoid leaking new_node if compare throws.
_Node* __prev = _M_find_node(__n, __k, __code);
@@ -1410,7 +1427,7 @@
if (__do_rehash.first)
{
_M_rehash(__do_rehash.second, __saved_state);
- __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ __n = _M_bucket_index(__k, __code);
// __prev is still valid because rehash do not invalidate nodes
}
@@ -1477,7 +1494,7 @@
erase(const_iterator __it)
{
_Node* __n = __it._M_cur;
- std::size_t __bkt = this->_M_bucket_index(__n, _M_bucket_count);
+ std::size_t __bkt = _M_bucket_index(__n);
// Look for previous node to unlink it from the erased one, this is why
// we need buckets to contain the before begin node of the bucket to make
@@ -1485,12 +1502,10 @@
_Node* __prev_n = _M_get_previous_node(__bkt, __n);
if (__n == _M_bucket_begin(__bkt))
_M_remove_bucket_begin(__bkt, __n->_M_next,
- __n->_M_next ? this->_M_bucket_index(__n->_M_next, _M_bucket_count)
- : 0);
+ __n->_M_next ? _M_bucket_index(__n->_M_next) : 0);
else if (__n->_M_next)
{
- size_type __next_bkt =
- this->_M_bucket_index(__n->_M_next, _M_bucket_count);
+ size_type __next_bkt = _M_bucket_index(__n->_M_next);
if (__next_bkt != __bkt)
_M_buckets[__next_bkt] = __prev_n;
}
@@ -1516,7 +1531,7 @@
erase(const key_type& __k)
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __bkt = _M_bucket_index(__k, __code);
// Look for the first matching node with its previous node at the same
// time
_Node* __n = _M_buckets[__bkt];
@@ -1531,10 +1546,9 @@
bool __is_bucket_begin = true;
for (;; __prev_n = __n, __n = __n->_M_next)
{
- if (this->_M_compare(__k, __code, __n))
+ if (this->_M_equals(__k, __code, __n))
break;
- if (!(__n->_M_next)
- || this->_M_bucket_index(__n->_M_next, _M_bucket_count) != __bkt)
+ if (!(__n->_M_next) || _M_bucket_index(__n->_M_next) != __bkt)
return 0;
__is_bucket_begin = false;
}
@@ -1560,9 +1574,9 @@
++__result;
if (!__next_n)
break;
- __next_bkt = this->_M_bucket_index(__next_n, _M_bucket_count);
+ __next_bkt = _M_bucket_index(__next_n);
}
- while (__next_bkt == __bkt && this->_M_compare(__k, __code, __next_n));
+ while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
if (__saved_n)
_M_deallocate_node(__saved_n);
@@ -1591,7 +1605,7 @@
if (__n == __last_n)
return iterator(__n);
- std::size_t __bkt = this->_M_bucket_index(__n, _M_bucket_count);
+ std::size_t __bkt = _M_bucket_index(__n);
_Node* __prev_n = _M_get_previous_node(__bkt, __n);
bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
@@ -1606,7 +1620,7 @@
--_M_element_count;
if (!__n)
break;
- __n_bkt = this->_M_bucket_index(__n, _M_bucket_count);
+ __n_bkt = _M_bucket_index(__n);
}
while (__n != __last_n && __n_bkt == __bkt);
if (__is_bucket_begin)
@@ -1672,7 +1686,7 @@
while (__p)
{
_Node* __next = __p->_M_next;
- std::size_t __new_index = this->_M_bucket_index(__p, __n);
+ std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
if (!__new_buckets[__new_index])
// Store temporarily bucket end node in _M_buckets if possible.
// This will boost second loop where we need to access bucket
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (revision 182411)
+++ include/bits/hashtable_policy.h (working copy)
@@ -101,8 +101,7 @@
_M_next() { }
};
- // Local iterators, used to iterate within a bucket but not between
- // buckets.
+ // Node iterators, used to iterate through all the hashtable.
template<typename _Value, bool __cache>
struct _Node_iterator_base
{
@@ -425,8 +424,7 @@
{
_Hashtable* __h = static_cast<_Hashtable*>(this);
typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
- std::size_t __n = __h->_M_bucket_index(__k, __code,
- __h->_M_bucket_count);
+ std::size_t __n = __h->_M_bucket_index(__k, __code);
typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
if (!__p)
@@ -443,8 +441,7 @@
{
_Hashtable* __h = static_cast<_Hashtable*>(this);
typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
- std::size_t __n = __h->_M_bucket_index(__k, __code,
- __h->_M_bucket_count);
+ std::size_t __n = __h->_M_bucket_index(__k, __code);
typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
if (!__p)
@@ -462,8 +459,7 @@
{
_Hashtable* __h = static_cast<_Hashtable*>(this);
typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
- std::size_t __n = __h->_M_bucket_index(__k, __code,
- __h->_M_bucket_count);
+ std::size_t __n = __h->_M_bucket_index(__k, __code);
typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
if (!__p)
@@ -479,8 +475,7 @@
{
const _Hashtable* __h = static_cast<const _Hashtable*>(this);
typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
- std::size_t __n = __h->_M_bucket_index(__k, __code,
- __h->_M_bucket_count);
+ std::size_t __n = __h->_M_bucket_index(__k, __code);
typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
if (!__p)
@@ -526,28 +521,26 @@
// we have a dummy type as placeholder.
// (2) Whether or not we cache hash codes. Caching hash codes is
// meaningless if we have a ranged hash function.
- // We also put the key extraction and equality comparison function
- // objects here, for convenience.
+ // We also put the key extraction objects here, for convenience.
// Primary template: unused except as a hook for specializations.
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
+ template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash,
bool __cache_hash_code>
struct _Hash_code_base;
// Specialization: ranged hash function, no caching hash codes. H1
// and H2 are provided but ignored. We define a dummy hash code type.
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
+ template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
- _Hash, false>
+ struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
{
protected:
- _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+ // We need the default constructor for the local iterators.
+ _Hash_code_base() = default;
+ _Hash_code_base(const _ExtractKey& __ex,
const _H1&, const _H2&, const _Hash& __h)
- : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
+ : _M_extract(__ex), _M_ranged_hash(__h) { }
typedef void* _Hash_code_type;
@@ -565,11 +558,6 @@
std::size_t __n) const
{ return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
- bool
- _M_compare(const _Key& __k, _Hash_code_type,
- _Hash_node<_Value, false>* __n) const
- { return _M_eq(__k, _M_extract(__n->_M_v)); }
-
void
_M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
{ }
@@ -583,13 +571,11 @@
_M_swap(_Hash_code_base& __x)
{
std::swap(_M_extract, __x._M_extract);
- std::swap(_M_eq, __x._M_eq);
std::swap(_M_ranged_hash, __x._M_ranged_hash);
}
protected:
_ExtractKey _M_extract;
- _Equal _M_eq;
_Hash _M_ranged_hash;
};
@@ -601,19 +587,16 @@
// Specialization: ranged hash function, cache hash codes. This
// combination is meaningless, so we provide only a declaration
// and no definition.
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
+ template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
- _Hash, true>;
+ struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
// Specialization: hash function and range-hashing function, no
// caching of hash codes. H is provided but ignored. Provides
// typedef and accessor required by TR1.
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
+ template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
+ struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
_Default_ranged_hash, false>
{
typedef _H1 hasher;
@@ -623,10 +606,12 @@
{ return _M_h1; }
protected:
- _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+ // We need the default constructor for the local iterators.
+ _Hash_code_base() = default;
+ _Hash_code_base(const _ExtractKey& __ex,
const _H1& __h1, const _H2& __h2,
const _Default_ranged_hash&)
- : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
+ : _M_extract(__ex), _M_h1(__h1), _M_h2(__h2) { }
typedef std::size_t _Hash_code_type;
@@ -644,11 +629,6 @@
std::size_t __n) const
{ return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
- bool
- _M_compare(const _Key& __k, _Hash_code_type,
- _Hash_node<_Value, false>* __n) const
- { return _M_eq(__k, _M_extract(__n->_M_v)); }
-
void
_M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
{ }
@@ -662,14 +642,12 @@
_M_swap(_Hash_code_base& __x)
{
std::swap(_M_extract, __x._M_extract);
- std::swap(_M_eq, __x._M_eq);
std::swap(_M_h1, __x._M_h1);
std::swap(_M_h2, __x._M_h2);
}
protected:
_ExtractKey _M_extract;
- _Equal _M_eq;
_H1 _M_h1;
_H2 _M_h2;
};
@@ -677,10 +655,9 @@
// Specialization: hash function and range-hashing function,
// caching hash codes. H is provided but ignored. Provides
// typedef and accessor required by TR1.
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
+ template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
+ struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
_Default_ranged_hash, true>
{
typedef _H1 hasher;
@@ -690,10 +667,10 @@
{ return _M_h1; }
protected:
- _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+ _Hash_code_base(const _ExtractKey& __ex,
const _H1& __h1, const _H2& __h2,
const _Default_ranged_hash&)
- : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
+ : _M_extract(__ex), _M_h1(__h1), _M_h2(__h2) { }
typedef std::size_t _Hash_code_type;
@@ -711,11 +688,6 @@
std::size_t __n) const
{ return _M_h2(__p->_M_hash_code, __n); }
- bool
- _M_compare(const _Key& __k, _Hash_code_type __c,
- _Hash_node<_Value, true>* __n) const
- { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
-
void
_M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
{ __n->_M_hash_code = __c; }
@@ -729,19 +701,274 @@
_M_swap(_Hash_code_base& __x)
{
std::swap(_M_extract, __x._M_extract);
- std::swap(_M_eq, __x._M_eq);
std::swap(_M_h1, __x._M_h1);
std::swap(_M_h2, __x._M_h2);
}
protected:
_ExtractKey _M_extract;
- _Equal _M_eq;
_H1 _M_h1;
_H2 _M_h2;
};
+ template <typename _Key, typename _Value, typename _ExtractKey,
+ typename _Equal, typename _HashCodeType,
+ bool __cache_hash_code>
+ struct _Equal_helper;
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _Equal, typename _HashCodeType>
+ struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
+ {
+ bool static _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
+ const _Key& __k, _HashCodeType __c,
+ _Hash_node<_Value, true>* __n)
+ { return __c == __n->_M_hash_code
+ && __eq(__k, __extract(__n->_M_v)); }
+ };
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _Equal, typename _HashCodeType>
+ struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
+ {
+ bool static _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
+ const _Key& __k, _HashCodeType,
+ _Hash_node<_Value, false>* __n)
+ { return __eq(__k, __extract(__n->_M_v)); }
+ };
+
+ // Helper class adding management of _Equal functor to _Hash_code_base
+ // type.
+ template<typename _Key, typename _Value,
+ typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash,
+ bool __cache_hash_code>
+ struct _Hashtable_base
+ : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+ __cache_hash_code>
+ {
+ protected:
+ typedef _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache_hash_code> _Base;
+ typedef typename _Base::_Hash_code_type _Hash_code_type;
+
+ _Hashtable_base(const _ExtractKey& __ex,
+ const _H1& __h1, const _H2& __h2,
+ const _Hash& __hash, const _Equal& __eq)
+ : _Base(__ex, __h1, __h2, __hash), _M_eq(__eq) { }
+
+ bool
+ _M_equals(const _Key& __k, _Hash_code_type __c,
+ _Hash_node<_Value, __cache_hash_code>* __n) const
+ {
+ typedef _Equal_helper<_Key, _Value, _ExtractKey,
+ _Equal, _Hash_code_type,
+ __cache_hash_code> _EqualHelper;
+ return _EqualHelper::_S_equals(_M_eq, this->_M_extract, __k, __c, __n);
+ }
+
+ void
+ _M_swap(_Hashtable_base& __x)
+ {
+ _Base::_M_swap(__x);
+ std::swap(_M_eq, __x._M_eq);
+ }
+
+ private:
+ _Equal _M_eq;
+ };
+
+ // Local iterators, used to iterate within a bucket but not between
+ // buckets.
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash,
+ bool __cache_hash_code>
+ struct _Local_iterator_base;
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash>
+ struct _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, true>
+ : public _H2
+ {
+ _Local_iterator_base() = default;
+ _Local_iterator_base(_Hash_node<_Value, true>* __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+
+ void
+ _M_incr()
+ {
+ _M_cur = _M_cur->_M_next;
+ if (_M_cur)
+ {
+ std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
+ if (__bkt != _M_bucket)
+ _M_cur = nullptr;
+ }
+ }
+
+ const _H2& _M_h2() const
+ { return *this; }
+
+ _Hash_node<_Value, true>* _M_cur;
+ std::size_t _M_bucket;
+ std::size_t _M_bucket_count;
+ };
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash>
+ struct _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, false>
+ : public _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, false>
+ {
+ _Local_iterator_base() = default;
+ _Local_iterator_base(_Hash_node<_Value, false>* __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+
+ void
+ _M_incr()
+ {
+ _M_cur = _M_cur->_M_next;
+ if (_M_cur)
+ {
+ std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
+ if (__bkt != _M_bucket)
+ _M_cur = nullptr;
+ }
+ }
+
+ _Hash_node<_Value, false>* _M_cur;
+ std::size_t _M_bucket;
+ std::size_t _M_bucket_count;
+ };
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash, bool __cache>
+ inline bool
+ operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>& __x,
+ const _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>& __y)
+ { return __x._M_cur == __y._M_cur; }
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash, bool __cache>
+ inline bool
+ operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>& __x,
+ const _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>& __y)
+ { return __x._M_cur != __y._M_cur; }
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash,
+ bool __constant_iterators, bool __cache>
+ struct _Local_iterator
+ : public _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>
+ {
+ typedef _Value value_type;
+ typedef typename std::conditional<__constant_iterators,
+ const _Value*, _Value*>::type
+ pointer;
+ typedef typename std::conditional<__constant_iterators,
+ const _Value&, _Value&>::type
+ reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ _Local_iterator() = default;
+
+ explicit
+ _Local_iterator(_Hash_node<_Value, __cache>* __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+ __cache>(__p, __bkt, __bkt_count)
+ { }
+
+ reference
+ operator*() const
+ { return this->_M_cur->_M_v; }
+
+ pointer
+ operator->() const
+ { return std::__addressof(this->_M_cur->_M_v); }
+
+ _Local_iterator&
+ operator++()
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Local_iterator
+ operator++(int)
+ {
+ _Local_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash,
+ bool __constant_iterators, bool __cache>
+ struct _Local_const_iterator
+ : public _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>
+ {
+ typedef _Value value_type;
+ typedef const _Value* pointer;
+ typedef const _Value& reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ _Local_const_iterator() = default;
+
+ explicit
+ _Local_const_iterator(_Hash_node<_Value, __cache>* __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+ __cache>(__p, __bkt, __bkt_count)
+ { }
+
+ _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash,
+ __constant_iterators,
+ __cache>& __x)
+ : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+ __cache>(__x._M_cur, __x._M_bucket,
+ __x._M_bucket_count)
+ { }
+
+ reference
+ operator*() const
+ { return this->_M_cur->_M_v; }
+
+ pointer
+ operator->() const
+ { return std::__addressof(this->_M_cur->_M_v); }
+
+ _Local_const_iterator&
+ operator++()
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Local_const_iterator
+ operator++(int)
+ {
+ _Local_const_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+
// Class template _Equality_base. This is for implementing equality
// comparison for unordered containers, per N3068, by John Lakos and
// Pablo Halpern. Algorithmically, we follow closely the reference
Index: include/bits/unordered_map.h
===================================================================
--- include/bits/unordered_map.h (revision 182411)
+++ include/bits/unordered_map.h (working copy)
@@ -41,7 +41,7 @@
class _Pred = std::equal_to<_Key>,
class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
bool __cache_hash_code =
- __not_<__and_<is_integral<_Key>,
+ __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
__detail::__is_noexcept_hash<_Key, _Hash>>>::value>
class __unordered_map
: public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
@@ -112,7 +112,7 @@
class _Pred = std::equal_to<_Key>,
class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
bool __cache_hash_code =
- __not_<__and_<is_integral<_Key>,
+ __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
__detail::__is_noexcept_hash<_Key, _Hash>>>::value>
class __unordered_multimap
: public _Hashtable<_Key, std::pair<const _Key, _Tp>,
Index: include/bits/unordered_set.h
===================================================================
--- include/bits/unordered_set.h (revision 182411)
+++ include/bits/unordered_set.h (working copy)
@@ -41,7 +41,7 @@
class _Pred = std::equal_to<_Value>,
class _Alloc = std::allocator<_Value>,
bool __cache_hash_code =
- __not_<__and_<is_integral<_Value>,
+ __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
__detail::__is_noexcept_hash<_Value, _Hash>>>::value>
class __unordered_set
: public _Hashtable<_Value, _Value, _Alloc,
@@ -124,7 +124,7 @@
class _Pred = std::equal_to<_Value>,
class _Alloc = std::allocator<_Value>,
bool __cache_hash_code =
- __not_<__and_<is_integral<_Value>,
+ __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
__detail::__is_noexcept_hash<_Value, _Hash>>>::value>
class __unordered_multiset
: public _Hashtable<_Value, _Value, _Alloc,