This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: hashtable local iterator
On 12/21/2011 04:53 PM, Jonathan Wakely wrote:
On 21 December 2011 01:27, Paolo Carlini wrote:
.. by the way, when working on this issue, make sure to have 'PR
libstdc++/51608' on the ChangeLog, and please also double check the latter
for typos (I see an 'unordere_map.H')
And "whether hash code is cache or not" should be "cached" not "cache"
There should be a new line after that, before "(_Hash_code_base):"
Thanks for commenting the code thoroughly, the code is quite
complicated, so good comments are very important. I haven't studied
the code closely enough to understand it all but there are several
grammatical issues in the comments that made it harder for me.
I compiled you and Paolo feedback normally and here is the result.
I saw your feedback regarding usage of tuple, do you prefer a solution
based on it ? Note that even if it works it will imply inclusion of
tuple header each time unordered containers are used, is it ok ? I know
Paolo is rather sensible on this subject :-)
2011-12-21 François Dumont <fdumont@gcc.gnu.org>
PR libstdc++/51608
* include/bits/hashtable_policy.h (_Equal_helper<>): New,
change the
way the _Equal functor is used depending on whether hash code is
cached or not.
(_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 returned local iterator will not be incremented so we don't
+ // need to compute __it's 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 returned local iterator will not be incremented so we don't
+ // need to compute __it's 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 returned local iterator will not be incremented so we don't
+ // need to compute __it's 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 returned local iterator will not be incremented so we don't
+ // need to compute __it's 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 returned local iterator will not be incremented so we don't
+ // need to compute __it's 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 returned local iterator will not be incremented so we don't
+ // need to compute __it's 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 returned local iterator will not be incremented so we don't
+ // need to compute __it's 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 returned local iterator will not be incremented so we don't
+ // need to compute __it's 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,33 @@
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 guarantee that
+ // swapping two hashtable instances won't invalidate associated local
+ // iterators.
+
+ template<typename _Cond>
+ using __if_hash_code_cached
+ = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
+
+ template<typename _Cond>
+ using __if_hash_code_not_cached
+ = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
+
+ // When hash codes are cached local iterator only uses H2 which must then
+ // be empty.
+ static_assert(__if_hash_code_cached<is_empty<_H2>>::value,
+ "Functor used to map hash code to 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(__if_hash_code_not_cached<is_empty<_HCBase>>::value,
+ "Cache the hash code or make functors involved in hash code"
+ " and bucket index computation empty");
+
public:
typedef _Allocator allocator_type;
typedef _Value value_type;
@@ -191,17 +218,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 +246,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 +286,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 +389,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(nullptr, __n, _M_bucket_count); }
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(nullptr, __n, _M_bucket_count); }
// 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(nullptr, __n, _M_bucket_count); }
float
load_factor() const noexcept
@@ -428,6 +453,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 +713,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 +729,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 +759,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 +800,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 +865,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 +906,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);
+ this->_M_swap(__x);
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 431. Swapping containers with unequal allocators.
@@ -916,7 +947,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 +964,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 +981,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 +989,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 +1019,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 +1052,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 +1087,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 +1145,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;
}
@@ -1196,11 +1221,10 @@
_Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
__try
{
- const key_type& __k = this->_M_extract(__new_node->_M_v);
+ 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 +1244,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])
@@ -1258,12 +1282,11 @@
_Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
__try
{
- const key_type& __k = this->_M_extract(__new_node->_M_v);
+ const key_type& __k = this->_M_extract()(__new_node->_M_v);
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 +1294,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
}
@@ -1322,8 +1345,8 @@
if (__do_rehash.first)
{
- const key_type& __k = this->_M_extract(__v);
- __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
+ const key_type& __k = this->_M_extract()(__v);
+ __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
}
_Node* __new_node = nullptr;
@@ -1367,9 +1390,9 @@
_H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
_M_insert(_Arg&& __v, std::true_type)
{
- const key_type& __k = this->_M_extract(__v);
+ 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);
@@ -1395,9 +1418,9 @@
= _M_rehash_policy._M_need_rehash(_M_bucket_count,
_M_element_count, 1);
- const key_type& __k = this->_M_extract(__v);
+ 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 +1433,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 +1500,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 +1508,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 +1537,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 +1552,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;
}
@@ -1551,7 +1571,7 @@
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 526. Is it undefined if a function in the standard changes
// in parameters?
- if (std::__addressof(this->_M_extract(__p->_M_v))
+ if (std::__addressof(this->_M_extract()(__p->_M_v))
!= std::__addressof(__k))
_M_deallocate_node(__p);
else
@@ -1560,9 +1580,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 +1611,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 +1626,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 +1692,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,33 @@
// 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.
+ //
+ // Each specialization derives from one or more of the template parameters to
+ // benefit from EBO. This is important as this type is inherited in some cases
+ // by the _Local_iterator_base type used to implement local_iterator and
+ // const_local_iterator. As with any iterator type we prefer to make it as
+ // small as possible.
// 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>
+ : _ExtractKey, _Hash
{
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) { }
+ : _ExtractKey(__ex), _Hash(__h) { }
typedef void* _Hash_code_type;
@@ -558,18 +558,13 @@
std::size_t
_M_bucket_index(const _Key& __k, _Hash_code_type,
std::size_t __n) const
- { return _M_ranged_hash(__k, __n); }
+ { return _M_ranged_hash()(__k, __n); }
std::size_t
_M_bucket_index(const _Hash_node<_Value, false>* __p,
std::size_t __n) const
- { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
+ { 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
{ }
@@ -582,15 +577,19 @@
void
_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);
+ std::swap(_M_extract(), __x._M_extract());
+ std::swap(_M_ranged_hash(), __x._M_ranged_hash());
}
protected:
- _ExtractKey _M_extract;
- _Equal _M_eq;
- _Hash _M_ranged_hash;
+ const _ExtractKey&
+ _M_extract() const { return *this; }
+ _ExtractKey&
+ _M_extract() { return *this; }
+ const _Hash&
+ _M_ranged_hash() const { return *this; }
+ _Hash&
+ _M_ranged_hash() { return *this; }
};
@@ -601,54 +600,49 @@
// 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,
+ // caching of hash codes.
+ // Provides typedef and accessor required by TR1.
+ 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>
+ : _ExtractKey, _H1, _H2
{
typedef _H1 hasher;
hasher
hash_function() const
- { return _M_h1; }
+ { return *this; }
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) { }
+ : _ExtractKey(__ex), _H1(__h1), _H2(__h2) { }
typedef std::size_t _Hash_code_type;
_Hash_code_type
_M_hash_code(const _Key& __k) const
- { return _M_h1(__k); }
+ { return _M_h1()(__k); }
std::size_t
_M_bucket_index(const _Key&, _Hash_code_type __c,
std::size_t __n) const
- { return _M_h2(__c, __n); }
+ { return _M_h2()(__c, __n); }
std::size_t
_M_bucket_index(const _Hash_node<_Value, false>* __p,
std::size_t __n) const
- { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
+ { 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
{ }
@@ -661,61 +655,63 @@
void
_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);
+ std::swap(_M_extract(), __x._M_extract());
+ 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;
+ const _ExtractKey&
+ _M_extract() const { return *this; }
+ _ExtractKey&
+ _M_extract() { return *this; }
+ const _H1&
+ _M_h1() const { return *this; }
+ _H1&
+ _M_h1() { return *this; }
+ const _H2&
+ _M_h2() const { return *this; }
+ _H2&
+ _M_h2() { return *this; }
};
// 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>
+ : _ExtractKey, _H1, _H2
{
typedef _H1 hasher;
hasher
hash_function() const
- { return _M_h1; }
+ { return *this; }
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) { }
+ : _ExtractKey(__ex), _H1(__h1), _H2(__h2) { }
typedef std::size_t _Hash_code_type;
_Hash_code_type
_M_hash_code(const _Key& __k) const
- { return _M_h1(__k); }
+ { return _M_h1()(__k); }
std::size_t
_M_bucket_index(const _Key&, _Hash_code_type __c,
std::size_t __n) const
- { return _M_h2(__c, __n); }
+ { return _M_h2()(__c, __n); }
std::size_t
_M_bucket_index(const _Hash_node<_Value, true>* __p,
std::size_t __n) const
- { return _M_h2(__p->_M_hash_code, __n); }
+ { 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; }
@@ -728,20 +724,284 @@
void
_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);
+ std::swap(_M_extract(), __x._M_extract());
+ 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;
+ const _ExtractKey&
+ _M_extract() const { return *this; }
+ _ExtractKey&
+ _M_extract() { return *this; }
+ const _H1&
+ _M_h1() const { return *this; }
+ _H1&
+ _M_h1() { return *this; }
+ const _H2&
+ _M_h2() const { return *this; }
+ _H2&
+ _M_h2() { return *this; }
};
+ 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,