* and returns a bool-like value that is true if the two objects
* are considered equal.
*
- * @tparam _H1 The hash function. A unary function object with
+ * @tparam _Hash The hash function. A unary function object with
* argument type _Key and result type size_t. Return values should
* be distributed over the entire range [0, numeric_limits<size_t>:::max()].
*
- * @tparam _H2 The range-hashing function (in the terminology of
+ * @tparam _RangeHash The range-hashing function (in the terminology of
* Tavori and Dreizin). A binary function object whose argument
* types and result type are all size_t. Given arguments r and N,
* the return value is in the range [0, N).
*
- * @tparam _Hash The ranged hash function (Tavori and Dreizin). A
- * binary function whose argument types are _Key and size_t and
- * whose result type is size_t. Given arguments k and N, the
- * return value is in the range [0, N). Default: hash(k, N) =
- * h2(h1(k), N). If _Hash is anything other than the default, _H1
- * and _H2 are ignored.
+ * @tparam _Unused Not used.
*
* @tparam _RehashPolicy Policy class with three members, all of
* which govern the bucket count. _M_next_bkt(n) returns a bucket
* bucket count appropriate for an element count of n.
* _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the
* current bucket count is n_bkt and the current element count is
- * n_elt, we need to increase the bucket count. If so, returns
- * make_pair(true, n), where n is the new bucket count. If not,
- * returns make_pair(false, <anything>)
+ * n_elt, we need to increase the bucket count for n_ins insertions.
+ * If so, returns make_pair(true, n), where n is the new bucket count. If
+ *
not, returns make_pair(false, <anything>)
*
* @tparam _Traits Compile-time class with three boolean
* std::integral_constant members: __cache_hash_code, __constant_iterators,
*/
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
class _Hashtable
: public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _Traits>,
+ _Hash, _RangeHash, _Unused, _Traits>,
public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>,
+ _Hash, _RangeHash, _Unused,
+ _RehashPolicy, _Traits>,
public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>,
+ _Hash, _RangeHash, _Unused,
+ _RehashPolicy, _Traits>,
public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>,
+ _Hash, _RangeHash, _Unused,
+ _RehashPolicy, _Traits>,
public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>,
+ _Hash, _RangeHash, _Unused,
+ _RehashPolicy, _Traits>,
private __detail::_Hashtable_alloc<
__alloc_rebind<_Alloc,
__detail::_Hash_node<_Value,
using __constant_iterators = typename __traits_type::__constant_iterators;
using __unique_keys = typename __traits_type::__unique_keys;
- using __key_extract = typename std::conditional<
- __constant_iterators::value,
- __detail::_Identity,
- __detail::_Select1st>::type;
-
using __hashtable_base = __detail::
- _Hashtable_base<_Key, _Value, _ExtractKey,
- _Equal, _H1, _H2, _Hash, _Traits>;
+ _Hashtable_base<_Key, _Value, _ExtractKey,
+ _Equal, _Hash, _RangeHash, _Unused, _Traits>;
using __hash_code_base = typename __hashtable_base::__hash_code_base;
using __hash_code = typename __hashtable_base::__hash_code;
using __ireturn_type = typename __hashtable_base::__ireturn_type;
using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey,
- _Equal, _H1, _H2, _Hash,
+ _Equal, _Hash, _RangeHash, _Unused,
_RehashPolicy, _Traits>;
using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc,
_ExtractKey, _Equal,
- _H1, _H2, _Hash,
+ _Hash, _RangeHash, _Unused,
_RehashPolicy, _Traits>;
using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey,
- _Equal, _H1, _H2, _Hash,
+ _Equal, _Hash, _RangeHash, _Unused,
_RehashPolicy, _Traits>;
using __reuse_or_alloc_node_gen_t =
__fwd_value_for(value_type& __val) noexcept
{ return std::move(__val); }
- // Metaprogramming for picking apart hash caching.
- template<typename _Cond>
- using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
-
- template<typename _Cond>
- using __if_hash_not_cached = __or_<__hash_cached, _Cond>;
-
// Compile-time diagnostics.
// _Hash_code_base has everything protected, so use this derived type to
"Cache the hash code or qualify your functors involved"
" in hash code and bucket index computation with noexcept");
- // When hash codes are cached local iterator inherits from H2 functor
- // which must then be default constructible.
- static_assert(__if_hash_cached<is_default_constructible<_H2>>::value,
+ // To get bucket index we need _RangeHash not to throw.
+ static_assert(is_nothrow_default_constructible<_RangeHash>::value,
"Functor used to map hash code to bucket index"
- " must be default constructible");
+ " must be nothrow default constructible");
+ static_assert(noexcept(
+ std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)),
+ "Functor used to map hash code to bucket index must be"
+ " noexcept");
+
+ // To compute bucket index we also need _ExtratKey not to throw.
+ static_assert(is_nothrow_default_constructible<_ExtractKey>::value,
+ "_ExtractKey must be nothrow default constructible");
+ static_assert(noexcept(
+ std::declval<const _ExtractKey&>()(std::declval<_Value>())),
+ "_ExtractKey functor must be noexcept invocable");
template<typename _Keya, typename _Valuea, typename _Alloca,
typename _ExtractKeya, typename _Equala,
- typename _H1a, typename _H2a, typename _Hasha,
+ typename _Hasha, typename _RangeHasha, typename _Unuseda,
typename _RehashPolicya, typename _Traitsa,
bool _Unique_keysa>
friend struct __detail::_Map_base;
template<typename _Keya, typename _Valuea, typename _Alloca,
typename _ExtractKeya, typename _Equala,
- typename _H1a, typename _H2a, typename _Hasha,
+ typename _Hasha, typename _RangeHasha, typename _Unuseda,
typename _RehashPolicya, typename _Traitsa>
friend struct __detail::_Insert_base;
template<typename _Keya, typename _Valuea, typename _Alloca,
typename _ExtractKeya, typename _Equala,
- typename _H1a, typename _H2a, typename _Hasha,
+ typename _Hasha, typename _RangeHasha, typename _Unuseda,
typename _RehashPolicya, typename _Traitsa,
bool _Constant_iteratorsa>
friend struct __detail::_Insert;
template<typename _Keya, typename _Valuea, typename _Alloca,
typename _ExtractKeya, typename _Equala,
- typename _H1a, typename _H2a, typename _Hasha,
+ typename _Hasha, typename _RangeHasha, typename _Unuseda,
typename _RehashPolicya, typename _Traitsa,
bool _Unique_keysa>
friend struct __detail::_Equality;
void
_M_reset() noexcept;
- _Hashtable(const _H1& __h1, const _H2& __h2, const _Hash& __h,
- const _Equal& __eq, const _ExtractKey& __exk,
+ _Hashtable(const _Hash& __h, const _Equal& __eq,
const allocator_type& __a)
- : __hashtable_base(__exk, __h1, __h2, __h, __eq),
+ : __hashtable_base(__h, __eq),
__hashtable_alloc(__node_alloc_type(__a))
{ }
_Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
true_type /* alloc always equal */)
- noexcept(std::is_nothrow_copy_constructible<_H1>::value &&
+ noexcept(std::is_nothrow_copy_constructible<_Hash>::value &&
std::is_nothrow_copy_constructible<_Equal>::value);
_Hashtable(_Hashtable&&, __node_alloc_type&&,
template<typename _InputIterator>
_Hashtable(_InputIterator __first, _InputIterator __last,
size_type __bkt_count_hint,
- const _H1&, const _H2&, const _Hash&,
- const _Equal&, const _ExtractKey&,
- const allocator_type&,
+ const _Hash&, const _Equal&, const allocator_type&,
true_type __uks);
template<typename _InputIterator>
_Hashtable(_InputIterator __first, _InputIterator __last,
size_type __bkt_count_hint,
- const _H1&, const _H2&, const _Hash&,
- const _Equal&, const _ExtractKey&,
- const allocator_type&,
+ const _Hash&, const _Equal&, const allocator_type&,
false_type __uks);
public:
// Constructor, destructor, assignment, swap
_Hashtable() = default;
- _Hashtable(size_type __bkt_count_hint,
- const _H1&, const _H2&, const _Hash&,
- const _Equal&, const _ExtractKey&,
- const allocator_type&);
_Hashtable(const _Hashtable&);
+ _Hashtable(const _Hashtable&, const allocator_type&);
+
+ explicit
+ _Hashtable(size_type __bkt_count_hint,
+ const _Hash& __hf = _Hash(),
+ const key_equal& __eql = key_equal(),
+ const allocator_type& __a = allocator_type());
+
+ // Use delegating constructors.
_Hashtable(_Hashtable&& __ht)
noexcept( noexcept(
_Hashtable(std::declval<_Hashtable>(),
true_type{})
{ }
- _Hashtable(const _Hashtable&, const allocator_type&);
-
_Hashtable(_Hashtable&& __ht, const allocator_type& __a)
noexcept( noexcept(
_Hashtable(std::declval<_Hashtable>(),
typename __node_alloc_traits::is_always_equal{})
{ }
- // Use delegating constructors.
- template<typename _InputIterator>
- _Hashtable(_InputIterator __first, _InputIterator __last,
- size_type __bkt_count_hint,
- const _H1& __h1, const _H2& __h2, const _Hash& __h,
- const _Equal& __eq, const _ExtractKey& __exk,
- const allocator_type& __a)
- : _Hashtable(__first, __last, __bkt_count_hint,
- __h1, __h2, __h, __eq, __exk, __a, __unique_keys{})
- { }
-
explicit
_Hashtable(const allocator_type& __a)
: __hashtable_alloc(__node_alloc_type(__a))
{ }
- explicit
- _Hashtable(size_type __bkt_count_hint,
- const _H1& __hf = _H1(),
- const key_equal& __eql = key_equal(),
- const allocator_type& __a = allocator_type())
- : _Hashtable(__bkt_count_hint, __hf, _H2(), _Hash(), __eql,
- __key_extract(), __a)
- { }
-
template<typename _InputIterator>
_Hashtable(_InputIterator __f, _InputIterator __l,
size_type __bkt_count_hint = 0,
- const _H1& __hf = _H1(),
+ const _Hash& __hf = _Hash(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Hashtable(__f, __l, __bkt_count_hint, __hf, _H2(), _Hash(), __eql,
- __key_extract(), __a)
+ : _Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a,
+ __unique_keys{})
{ }
_Hashtable(initializer_list<value_type> __l,
size_type __bkt_count_hint = 0,
- const _H1& __hf = _H1(),
+ const _Hash& __hf = _Hash(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
: _Hashtable(__l.begin(), __l.end(), __bkt_count_hint,
- __hf, _H2(), _Hash(), __eql,
- __key_extract(), __a)
+ __hf, __eql, __a, __unique_keys{})
{ }
_Hashtable&
_Hashtable&
operator=(_Hashtable&& __ht)
noexcept(__node_alloc_traits::_S_nothrow_move()
- && is_nothrow_move_assignable<_H1>::value
+ && is_nothrow_move_assignable<_Hash>::value
&& is_nothrow_move_assignable<_Equal>::value)
{
- constexpr bool __move_storage =
+ constexpr bool __move_storage =
__node_alloc_traits::_S_propagate_on_move_assign()
|| __node_alloc_traits::_S_always_equal();
_M_move_assign(std::move(__ht), __bool_constant<__move_storage>());
void
swap(_Hashtable&)
- noexcept(__and_<__is_nothrow_swappable<_H1>,
- __is_nothrow_swappable<_Equal>>::value);
+ noexcept(__and_<__is_nothrow_swappable<_Hash>,
+ __is_nothrow_swappable<_Equal>>::value);
// Basic container operations
iterator
size_type
bucket(const key_type& __k) const
- { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
+ { return _M_bucket_index(this->_M_hash_code(__k)); }
local_iterator
begin(size_type __bkt)
{ return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
size_type
- _M_bucket_index(const key_type& __k, __hash_code __c) const
- { return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
+ _M_bucket_index(__hash_code __c) const
+ { return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
// Find and insert helper functions and types
// Find the node before the one matching the criteria.
__node_base*
_M_get_previous_node(size_type __bkt, __node_base* __n);
- // Insert node __n with key __k and hash code __code, in bucket __bkt
- // if no rehash (assumes no element with same key already present).
+ // 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(const key_type& __k, size_type __bkt,
- __hash_code __code, __node_type* __n,
- size_type __n_elt = 1);
+ _M_insert_unique_node(size_type __bkt, __hash_code,
+ __node_type* __n, 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_type* __hint, const key_type& __k,
+ _M_insert_multi_node(__node_type* __hint,
__hash_code __code, __node_type* __n);
template<typename... _Args>
std::pair<iterator, bool>
- _M_emplace(true_type, _Args&&... __args);
+ _M_emplace(true_type __uks, _Args&&... __args);
template<typename... _Args>
iterator
- _M_emplace(false_type __uk, _Args&&... __args)
- { return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); }
+ _M_emplace(false_type __uks, _Args&&... __args)
+ { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); }
// Emplace with hint, useless when keys are unique.
template<typename... _Args>
const _NodeGenerator&, false_type __uks);
size_type
- _M_erase(true_type, const key_type&);
+ _M_erase(true_type __uks, const key_type&);
size_type
- _M_erase(false_type, const key_type&);
+ _M_erase(false_type __uks, const key_type&);
iterator
_M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n);
template<typename... _Args>
__ireturn_type
emplace(_Args&&... __args)
- { return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
+ { return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
template<typename... _Args>
iterator
emplace_hint(const_iterator __hint, _Args&&... __args)
{
- return _M_emplace(__hint, __unique_keys(),
+ return _M_emplace(__hint, __unique_keys{},
std::forward<_Args>(__args)...);
}
size_type
erase(const key_type& __k)
- { return _M_erase(__unique_keys(), __k); }
+ { return _M_erase(__unique_keys{}, __k); }
iterator
erase(const_iterator, const_iterator);
const key_type& __k = __nh._M_key();
__hash_code __code = this->_M_hash_code(__k);
- size_type __bkt = _M_bucket_index(__k, __code);
+ size_type __bkt = _M_bucket_index(__code);
if (__node_type* __n = _M_find_node(__bkt, __k, __code))
{
__ret.node = std::move(__nh);
else
{
__ret.position
- = _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr);
+ = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
__nh._M_ptr = nullptr;
__ret.inserted = true;
}
const key_type& __k = __nh._M_key();
auto __code = this->_M_hash_code(__k);
auto __ret
- = _M_insert_multi_node(__hint._M_cur, __k, __code, __nh._M_ptr);
+ = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
__nh._M_ptr = nullptr;
return __ret;
}
{
node_type __nh;
__hash_code __code = this->_M_hash_code(__k);
- std::size_t __bkt = _M_bucket_index(__k, __code);
+ std::size_t __bkt = _M_bucket_index(__code);
if (__node_base* __prev_node = _M_find_before_node(__bkt, __k, __code))
__nh = _M_extract_node(__bkt, __prev_node);
return __nh;
for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
{
auto __pos = __i++;
- const key_type& __k = this->_M_extract()(*__pos);
+ const key_type& __k = _ExtractKey{}(*__pos);
__hash_code __code = this->_M_hash_code(__k);
- size_type __bkt = _M_bucket_index(__k, __code);
+ size_type __bkt = _M_bucket_index(__code);
if (_M_find_node(__bkt, __k, __code) == nullptr)
{
auto __nh = __src.extract(__pos);
- _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr,
- __n_elt);
+ _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
__nh._M_ptr = nullptr;
__n_elt = 1;
}
private:
// Helper rehash method used when keys are unique.
- void _M_rehash_aux(size_type __bkt_count, true_type);
+ void _M_rehash_aux(size_type __bkt_count, true_type __uks);
// Helper rehash method used when keys can be non-unique.
- void _M_rehash_aux(size_type __bkt_count, false_type);
+ void _M_rehash_aux(size_type __bkt_count, false_type __uks);
// Unconditionally change size of bucket array to n, restore
// hash policy state to __state on exception.
// Definitions of class template _Hashtable's out-of-line member functions.
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_bucket_begin(size_type __bkt) const
-> __node_type*
{
return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_Hashtable(size_type __bkt_count_hint,
- const _H1& __h1, const _H2& __h2, const _Hash& __h,
- const _Equal& __eq, const _ExtractKey& __exk,
- const allocator_type& __a)
- : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
+ const _Hash& __h, const _Equal& __eq, const allocator_type& __a)
+ : _Hashtable(__h, __eq, __a)
{
auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
if (__bkt_count > _M_bucket_count)
}
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
template<typename _InputIterator>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_Hashtable(_InputIterator __f, _InputIterator __l,
size_type __bkt_count_hint,
- const _H1& __h1, const _H2& __h2, const _Hash& __h,
- const _Equal& __eq, const _ExtractKey& __exk,
+ const _Hash& __h, const _Equal& __eq,
const allocator_type& __a, true_type /* __uks */)
- : _Hashtable(__bkt_count_hint, __h1, __h2, __h, __eq, __exk, __a)
+ : _Hashtable(__bkt_count_hint, __h, __eq, __a)
{
for (; __f != __l; ++__f)
this->insert(*__f);
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
template<typename _InputIterator>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_Hashtable(_InputIterator __f, _InputIterator __l,
size_type __bkt_count_hint,
- const _H1& __h1, const _H2& __h2, const _Hash& __h,
- const _Equal& __eq, const _ExtractKey& __exk,
+ const _Hash& __h, const _Equal& __eq,
const allocator_type& __a, false_type /* __uks */)
- : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
+ : _Hashtable(__h, __eq, __a)
{
auto __nb_elems = __detail::__distance_fw(__f, __l);
auto __bkt_count =
this->insert(*__f);
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
operator=(const _Hashtable& __ht)
-> _Hashtable&
{
return *this;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
template<typename _Ht>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_assign_elements(_Ht&& __ht)
{
__bucket_type* __former_buckets = nullptr;
}
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
template<typename _Ht, typename _NodeGenerator>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen)
{
__bucket_type* __buckets = nullptr;
}
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_reset() noexcept
{
_M_rehash_policy._M_reset();
_M_element_count = 0;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_move_assign(_Hashtable&& __ht, true_type)
{
if (__builtin_expect(std::__addressof(__ht) == this, false))
__ht._M_reset();
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_move_assign(_Hashtable&& __ht, false_type)
{
if (__ht._M_node_allocator() == this->_M_node_allocator())
- _M_move_assign(std::move(__ht), true_type());
+ _M_move_assign(std::move(__ht), true_type{});
else
{
// Can't move memory, move elements then.
}
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_Hashtable(const _Hashtable& __ht)
: __hashtable_base(__ht),
__map_base(__ht),
_M_assign(__ht, __alloc_node_gen);
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
true_type /* alloc always equal */)
- noexcept(std::is_nothrow_copy_constructible<_H1>::value &&
+ noexcept(std::is_nothrow_copy_constructible<_Hash>::value &&
std::is_nothrow_copy_constructible<_Equal>::value)
: __hashtable_base(__ht),
__map_base(__ht),
__ht._M_reset();
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_Hashtable(const _Hashtable& __ht, const allocator_type& __a)
: __hashtable_base(__ht),
__map_base(__ht),
_M_assign(__ht, __alloc_node_gen);
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
false_type /* alloc always equal */)
: __hashtable_base(__ht),
}
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
~_Hashtable() noexcept
{
clear();
_M_deallocate_buckets();
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
swap(_Hashtable& __x)
- noexcept(__and_<__is_nothrow_swappable<_H1>,
- __is_nothrow_swappable<_Equal>>::value)
+ noexcept(__and_<__is_nothrow_swappable<_Hash>,
+ __is_nothrow_swappable<_Equal>>::value)
{
// The only base class with member variables is hash_code_base.
// We define _Hash_code_base::_M_swap because different
__x._M_update_bbegin();
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
find(const key_type& __k)
-> iterator
{
__hash_code __code = this->_M_hash_code(__k);
- std::size_t __bkt = _M_bucket_index(__k, __code);
+ std::size_t __bkt = _M_bucket_index(__code);
return iterator(_M_find_node(__bkt, __k, __code));
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
find(const key_type& __k) const
-> const_iterator
{
__hash_code __code = this->_M_hash_code(__k);
- std::size_t __bkt = _M_bucket_index(__k, __code);
+ std::size_t __bkt = _M_bucket_index(__code);
return const_iterator(_M_find_node(__bkt, __k, __code));
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
count(const key_type& __k) const
-> size_type
{
return __result;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
equal_range(const key_type& __k)
-> pair<iterator, iterator>
{
return { __beg, __ite };
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
equal_range(const key_type& __k) const
-> pair<const_iterator, const_iterator>
{
// Find the node before the one whose key compares equal to k in the bucket
// bkt. Return nullptr if no node is found.
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_find_before_node(size_type __bkt, const key_type& __k,
__hash_code __code) const
-> __node_base*
return nullptr;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert_bucket_begin(size_type __bkt, __node_type* __node)
{
if (_M_buckets[__bkt])
}
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_remove_bucket_begin(size_type __bkt, __node_type* __next,
size_type __next_bkt)
{
}
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_get_previous_node(size_type __bkt, __node_base* __n)
-> __node_base*
{
return __prev_n;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
template<typename... _Args>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_emplace(true_type, _Args&&... __args)
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_emplace(true_type /* __uks */, _Args&&... __args)
-> pair<iterator, bool>
{
// First build the node to get access to the hash code
_Scoped_node __node { this, std::forward<_Args>(__args)... };
- const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
+ const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
__hash_code __code = this->_M_hash_code(__k);
- size_type __bkt = _M_bucket_index(__k, __code);
+ size_type __bkt = _M_bucket_index(__code);
if (__node_type* __p = _M_find_node(__bkt, __k, __code))
// There is already an equivalent node, no insertion
return std::make_pair(iterator(__p), false);
// Insert the node
- auto __pos = _M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+ auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
__node._M_node = nullptr;
return { __pos, true };
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
template<typename... _Args>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_emplace(const_iterator __hint, false_type, _Args&&... __args)
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_emplace(const_iterator __hint, false_type /* __uks */,
+ _Args&&... __args)
-> iterator
{
// First build the node to get its hash code.
_Scoped_node __node { this, std::forward<_Args>(__args)... };
- const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
+ const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
__hash_code __code = this->_M_hash_code(__k);
auto __pos
- = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
+ = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
__node._M_node = nullptr;
return __pos;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_insert_unique_node(const key_type& __k, size_type __bkt,
- __hash_code __code, __node_type* __node,
- size_type __n_elt)
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_insert_unique_node(size_type __bkt, __hash_code __code,
+ __node_type* __node, size_type __n_elt)
-> iterator
{
const __rehash_state& __saved_state = _M_rehash_policy._M_state();
if (__do_rehash.first)
{
_M_rehash(__do_rehash.second, __saved_state);
- __bkt = _M_bucket_index(__k, __code);
+ __bkt = _M_bucket_index(__code);
}
this->_M_store_code(__node, __code);
return iterator(__node);
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_insert_multi_node(__node_type* __hint, const key_type& __k,
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_insert_multi_node(__node_type* __hint,
__hash_code __code, __node_type* __node)
-> iterator
{
_M_rehash(__do_rehash.second, __saved_state);
this->_M_store_code(__node, __code);
- size_type __bkt = _M_bucket_index(__k, __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.
}
// Insert v if no element with its key is already present.
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
template<typename _Arg, typename _NodeGenerator>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert(_Arg&& __v, const _NodeGenerator& __node_gen,
true_type /* __uks */)
-> pair<iterator, bool>
{
- const key_type& __k = this->_M_extract()(__v);
+ const key_type& __k = _ExtractKey{}(__v);
__hash_code __code = this->_M_hash_code(__k);
- size_type __bkt = _M_bucket_index(__k, __code);
+ size_type __bkt = _M_bucket_index(__code);
if (__node_type* __node = _M_find_node(__bkt, __k, __code))
return { iterator(__node), false };
_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
auto __pos
- = _M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+ = _M_insert_unique_node(__bkt, __code, __node._M_node);
__node._M_node = nullptr;
return { __pos, true };
}
// Insert v unconditionally.
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
template<typename _Arg, typename _NodeGenerator>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert(const_iterator __hint, _Arg&& __v,
const _NodeGenerator& __node_gen,
false_type /* __uks */)
{
// First compute the hash code so that we don't do anything if it
// throws.
- __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
+ __hash_code __code = this->_M_hash_code(_ExtractKey{}(__v));
// Second allocate new node so that we don't rehash if it throws.
_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
- const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
auto __pos
- = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
+ = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
__node._M_node = nullptr;
return __pos;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
erase(const_iterator __it)
-> iterator
{
return _M_erase(__bkt, __prev_n, __n);
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
-> iterator
{
return __result;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_erase(true_type, const key_type& __k)
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_erase(true_type /* __uks */, const key_type& __k)
-> size_type
{
__hash_code __code = this->_M_hash_code(__k);
- std::size_t __bkt = _M_bucket_index(__k, __code);
+ std::size_t __bkt = _M_bucket_index(__code);
// Look for the node before the first matching node.
__node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
return 1;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_erase(false_type, const key_type& __k)
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_erase(false_type /* __uks */, const key_type& __k)
-> size_type
{
__hash_code __code = this->_M_hash_code(__k);
- std::size_t __bkt = _M_bucket_index(__k, __code);
+ std::size_t __bkt = _M_bucket_index(__code);
// Look for the node before the first matching node.
__node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
return __result;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ 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,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
erase(const_iterator __first, const_iterator __last)
-> iterator
{
return iterator(__n);
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
clear() noexcept
{
this->_M_deallocate_nodes(_M_begin());
_M_before_begin._M_nxt = nullptr;
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
rehash(size_type __bkt_count)
{
const __rehash_state& __saved_state = _M_rehash_policy._M_state();
_M_rehash_policy._M_reset(__saved_state);
}
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_rehash(size_type __bkt_count, const __rehash_state& __state)
{
__try
{
- _M_rehash_aux(__bkt_count, __unique_keys());
+ _M_rehash_aux(__bkt_count, __unique_keys{});
}
__catch(...)
{
}
// Rehash when there is no equivalent elements.
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_rehash_aux(size_type __bkt_count, true_type)
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_rehash_aux(size_type __bkt_count, true_type /* __uks */)
{
__bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
__node_type* __p = _M_begin();
// Rehash when there can be equivalent elements, preserve their relative
// order.
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_rehash_aux(size_type __bkt_count, false_type)
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_rehash_aux(size_type __bkt_count, false_type /* __uks */)
{
__bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
class _Hashtable;
* @ingroup unordered_associative_containers
* @{
*/
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _Traits>
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _Equal, typename _Hash, typename _RangeHash,
+ typename _Unused, typename _Traits>
struct _Hashtable_base;
// Helper function: return distance(first, last) for forward
{
template<typename _Tp>
_Tp&&
- operator()(_Tp&& __x) const
+ operator()(_Tp&& __x) const noexcept
{ return std::forward<_Tp>(__x); }
};
{
template<typename _Tp>
auto
- operator()(_Tp&& __x) const
+ operator()(_Tp&& __x) const noexcept
-> decltype(std::get<0>(std::forward<_Tp>(__x)))
{ return std::get<0>(std::forward<_Tp>(__x)); }
};
*/
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits,
bool _Unique_keys = _Traits::__unique_keys::value>
struct _Map_base { };
/// Partial specialization, __unique_keys set to false.
template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
{
using mapped_type = typename std::tuple_element<1, _Pair>::type;
};
/// Partial specialization, __unique_keys set to true.
template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>
{
private:
- using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair,
- _Select1st,
- _Equal, _H1, _H2, _Hash,
- _Traits>;
+ using __hashtable_base = _Hashtable_base<_Key, _Pair, _Select1st, _Equal,
+ _Hash, _RangeHash, _Unused,
+ _Traits>;
- using __hashtable = _Hashtable<_Key, _Pair, _Alloc,
- _Select1st, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>;
+ using __hashtable = _Hashtable<_Key, _Pair, _Alloc, _Select1st, _Equal,
+ _Hash, _RangeHash,
+ _Unused, _RehashPolicy, _Traits>;
using __hash_code = typename __hashtable_base::__hash_code;
using __node_type = typename __hashtable_base::__node_type;
};
template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
auto
_Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::
operator[](const key_type& __k)
-> mapped_type&
{
__hashtable* __h = static_cast<__hashtable*>(this);
__hash_code __code = __h->_M_hash_code(__k);
- std::size_t __bkt = __h->_M_bucket_index(__k, __code);
+ std::size_t __bkt = __h->_M_bucket_index(__code);
if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
return __node->_M_v().second;
std::tuple<>()
};
auto __pos
- = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+ = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
__node._M_node = nullptr;
return __pos->second;
}
template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
auto
_Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::
operator[](key_type&& __k)
-> mapped_type&
{
__hashtable* __h = static_cast<__hashtable*>(this);
__hash_code __code = __h->_M_hash_code(__k);
- std::size_t __bkt = __h->_M_bucket_index(__k, __code);
+ std::size_t __bkt = __h->_M_bucket_index(__code);
if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
return __node->_M_v().second;
std::tuple<>()
};
auto __pos
- = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+ = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
__node._M_node = nullptr;
return __pos->second;
}
template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
auto
_Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::
at(const key_type& __k)
-> mapped_type&
{
}
template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
auto
_Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::
at(const key_type& __k) const
-> const mapped_type&
{
*/
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
struct _Insert_base
{
protected:
- using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
- _Equal, _H1, _H2, _Hash,
- _RehashPolicy, _Traits>;
-
using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
- _Equal, _H1, _H2, _Hash,
- _Traits>;
+ _Equal, _Hash, _RangeHash,
+ _Unused, _Traits>;
+
+ using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash,
+ _Unused, _RehashPolicy, _Traits>;
using value_type = typename __hashtable_base::value_type;
using iterator = typename __hashtable_base::iterator;
{
__hashtable& __h = _M_conjure_hashtable();
auto __code = __h._M_hash_code(__k);
- std::size_t __bkt = __h._M_bucket_index(__k, __code);
+ std::size_t __bkt = __h._M_bucket_index(__code);
if (__node_type* __node = __h._M_find_node(__bkt, __k, __code))
return { iterator(__node), false };
std::forward_as_tuple(std::forward<_Args>(__args)...)
};
auto __it
- = __h._M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+ = __h._M_insert_unique_node(__bkt, __code, __node._M_node);
__node._M_node = nullptr;
return { __it, true };
}
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
template<typename _InputIterator, typename _NodeGetter>
void
- _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
- _RehashPolicy, _Traits>::
+ _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash, _Unused,
+ _RehashPolicy, _Traits>::
_M_insert_range(_InputIterator __first, _InputIterator __last,
const _NodeGetter& __node_gen, true_type __uks)
{
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
template<typename _InputIterator, typename _NodeGetter>
void
- _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
- _RehashPolicy, _Traits>::
+ _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash, _Unused,
+ _RehashPolicy, _Traits>::
_M_insert_range(_InputIterator __first, _InputIterator __last,
const _NodeGetter& __node_gen, false_type __uks)
{
*/
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits,
bool _Constant_iterators = _Traits::__constant_iterators::value>
struct _Insert;
/// Specialization.
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
- struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
+ struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash, _Unused,
_RehashPolicy, _Traits, true>
: public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
{
using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
- _Equal, _H1, _H2, _Hash,
- _RehashPolicy, _Traits>;
+ _Equal, _Hash, _RangeHash, _Unused,
+ _RehashPolicy, _Traits>;
using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
- _Equal, _H1, _H2, _Hash,
- _Traits>;
+ _Equal, _Hash, _RangeHash,
+ _Unused, _Traits>;
using value_type = typename __base_type::value_type;
using iterator = typename __base_type::iterator;
/// Specialization.
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
- struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
- _RehashPolicy, _Traits, false>
+ struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
: public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
{
using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
- _Equal, _H1, _H2, _Hash,
+ _Equal, _Hash, _RangeHash, _Unused,
_RehashPolicy, _Traits>;
using value_type = typename __base_type::value_type;
using iterator = typename __base_type::iterator;
*/
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits,
typename =
__detected_or_t<false_type, __has_load_factor, _RehashPolicy>>
/// Specialization when rehash policy doesn't provide load factor management.
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits,
- false_type>
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
+ false_type /* Has load factor */>
{
};
/// Specialization when rehash policy provide load factor management.
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits,
- true_type>
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
+ true_type /* Has load factor */>
{
using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
- _Equal, _H1, _H2, _Hash,
+ _Equal, _Hash, _RangeHash, _Unused,
_RehashPolicy, _Traits>;
float
* but not between buckets.
*/
template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
bool __cache_hash_code>
struct _Local_iterator_base;
* Primary template is unused except as a hook for specializations.
*/
template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
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 _H1, typename _H2, typename _Hash>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
- : private _Hashtable_ebo_helper<0, _ExtractKey>,
- private _Hashtable_ebo_helper<1, _Hash>
- {
- private:
- using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
- using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>;
-
- protected:
- typedef void* __hash_code;
- typedef _Hash_node<_Value, false> __node_type;
-
- // We need the default constructor for the local iterators and _Hashtable
- // default constructor.
- _Hash_code_base() = default;
-
- _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
- const _Hash& __h)
- : __ebo_extract_key(__ex), __ebo_hash(__h) { }
-
- __hash_code
- _M_hash_code(const _Key& __key) const
- { return 0; }
-
- std::size_t
- _M_bucket_index(const _Key& __k, __hash_code,
- std::size_t __bkt_count) const
- { return _M_ranged_hash()(__k, __bkt_count); }
-
- std::size_t
- _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
- noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(),
- (std::size_t)0)) )
- { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __bkt_count); }
-
- void
- _M_store_code(__node_type*, __hash_code) const
- { }
-
- void
- _M_copy_code(__node_type*, const __node_type*) const
- { }
-
- void
- _M_swap(_Hash_code_base& __x)
- {
- std::swap(__ebo_extract_key::_M_get(),
- __x.__ebo_extract_key::_M_get());
- std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get());
- }
-
- const _ExtractKey&
- _M_extract() const { return __ebo_extract_key::_M_cget(); }
-
- const _Hash&
- _M_ranged_hash() const { return __ebo_hash::_M_cget(); }
- };
-
- // No specialization for ranged hash function while caching hash codes.
- // That combination is meaningless, and trying to do it is an error.
-
- /// 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 _H1, typename _H2, typename _Hash>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
-
/// Specialization: hash function and range-hashing function, no
/// caching of hash codes.
/// Provides typedef and accessor required by C++ 11.
template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
- _Default_ranged_hash, false>
- : private _Hashtable_ebo_helper<0, _ExtractKey>,
- private _Hashtable_ebo_helper<1, _H1>,
- private _Hashtable_ebo_helper<2, _H2>
+ typename _Hash, typename _RangeHash, typename _Unused>
+ struct _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
+ _Unused, false>
+ : private _Hashtable_ebo_helper<0, _Hash>
{
private:
- using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
- using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
- using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
+ using __ebo_hash = _Hashtable_ebo_helper<0, _Hash>;
// Gives the local iterator implementation access to _M_bucket_index().
- friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
- _Default_ranged_hash, false>;
+ friend struct _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _Hash, _RangeHash, _Unused, false>;
public:
- typedef _H1 hasher;
+ typedef _Hash hasher;
hasher
hash_function() const
- { return _M_h1(); }
+ { return _M_hash(); }
protected:
typedef std::size_t __hash_code;
// We need the default constructor for the local iterators and _Hashtable
// default constructor.
_Hash_code_base() = default;
-
- _Hash_code_base(const _ExtractKey& __ex,
- const _H1& __h1, const _H2& __h2,
- const _Default_ranged_hash&)
- : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
+ _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { }
__hash_code
_M_hash_code(const _Key& __k) const
{
- static_assert(__is_invocable<const _H1&, const _Key&>{},
+ static_assert(__is_invocable<const _Hash&, const _Key&>{},
"hash function must be invocable with an argument of key type");
- return _M_h1()(__k);
+ return _M_hash()(__k);
}
std::size_t
- _M_bucket_index(const _Key&, __hash_code __c,
- std::size_t __bkt_count) const
- { return _M_h2()(__c, __bkt_count); }
+ _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const
+ { return _RangeHash{}(__c, __bkt_count); }
std::size_t
_M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
- noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
- && noexcept(declval<const _H2&>()((__hash_code)0,
- (std::size_t)0)) )
- { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __bkt_count); }
+ noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>()))
+ && noexcept(declval<const _RangeHash&>()((__hash_code)0,
+ (std::size_t)0)) )
+ {
+ return _RangeHash{}(_M_hash()(_ExtractKey{}(__p->_M_v())),
+ __bkt_count);
+ }
void
_M_store_code(__node_type*, __hash_code) const
void
_M_swap(_Hash_code_base& __x)
- {
- std::swap(__ebo_extract_key::_M_get(),
- __x.__ebo_extract_key::_M_get());
- std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get());
- std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get());
- }
-
- const _ExtractKey&
- _M_extract() const { return __ebo_extract_key::_M_cget(); }
+ { std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); }
- const _H1&
- _M_h1() const { return __ebo_h1::_M_cget(); }
-
- const _H2&
- _M_h2() const { return __ebo_h2::_M_cget(); }
+ const _Hash&
+ _M_hash() const { return __ebo_hash::_M_cget(); }
};
/// Specialization: hash function and range-hashing function,
/// caching hash codes. H is provided but ignored. Provides
/// typedef and accessor required by C++ 11.
template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
- _Default_ranged_hash, true>
- : private _Hashtable_ebo_helper<0, _ExtractKey>,
- private _Hashtable_ebo_helper<1, _H1>,
- private _Hashtable_ebo_helper<2, _H2>
+ typename _Hash, typename _RangeHash, typename _Unused>
+ struct _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
+ _Unused, true>
+ : private _Hashtable_ebo_helper<0, _Hash>
{
private:
- // Gives the local iterator implementation access to _M_h2().
- friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
- _Default_ranged_hash, true>;
-
- using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
- using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
- using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
+ using __ebo_hash = _Hashtable_ebo_helper<0, _Hash>;
public:
- typedef _H1 hasher;
+ typedef _Hash hasher;
hasher
hash_function() const
- { return _M_h1(); }
+ { return _M_hash(); }
protected:
typedef std::size_t __hash_code;
// We need the default constructor for _Hashtable default constructor.
_Hash_code_base() = default;
- _Hash_code_base(const _ExtractKey& __ex,
- const _H1& __h1, const _H2& __h2,
- const _Default_ranged_hash&)
- : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
+ _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { }
__hash_code
_M_hash_code(const _Key& __k) const
{
- static_assert(__is_invocable<const _H1&, const _Key&>{},
+ static_assert(__is_invocable<const _Hash&, const _Key&>{},
"hash function must be invocable with an argument of key type");
- return _M_h1()(__k);
+ return _M_hash()(__k);
}
std::size_t
- _M_bucket_index(const _Key&, __hash_code __c,
- std::size_t __bkt_count) const
- { return _M_h2()(__c, __bkt_count); }
+ _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const
+ { return _RangeHash{}(__c, __bkt_count); }
std::size_t
_M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
- noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
- (std::size_t)0)) )
- { return _M_h2()(__p->_M_hash_code, __bkt_count); }
+ noexcept( noexcept(declval<const _RangeHash&>()((__hash_code)0,
+ (std::size_t)0)) )
+ { return _RangeHash{}(__p->_M_hash_code, __bkt_count); }
void
_M_store_code(__node_type* __n, __hash_code __c) const
void
_M_swap(_Hash_code_base& __x)
- {
- std::swap(__ebo_extract_key::_M_get(),
- __x.__ebo_extract_key::_M_get());
- std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get());
- std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get());
- }
-
- const _ExtractKey&
- _M_extract() const { return __ebo_extract_key::_M_cget(); }
+ { std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); }
- const _H1&
- _M_h1() const { return __ebo_h1::_M_cget(); }
-
- const _H2&
- _M_h2() const { return __ebo_h2::_M_cget(); }
+ const _Hash&
+ _M_hash() const { return __ebo_hash::_M_cget(); }
};
/// Partial specialization used when nodes contain a cached hash code.
template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2, typename _Hash>
+ typename _Hash, typename _RangeHash, typename _Unused>
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, true>
- : private _Hashtable_ebo_helper<0, _H2>
- , _Node_iterator_base<_Value, true>
+ _Hash, _RangeHash, _Unused, true>
+ : public _Node_iterator_base<_Value, true>
{
protected:
- using __base_type = _Hashtable_ebo_helper<0, _H2>;
using __base_node_iter = _Node_iterator_base<_Value, true>;
using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, true>;
+ _Hash, _RangeHash, _Unused, true>;
_Local_iterator_base() = default;
- _Local_iterator_base(const __hash_code_base& __base,
+ _Local_iterator_base(const __hash_code_base&,
_Hash_node<_Value, true>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : __base_type(__base._M_h2()), __base_node_iter(__p)
- , _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+ : __base_node_iter(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+ { }
void
_M_incr()
if (this->_M_cur)
{
std::size_t __bkt
- = __base_type::_M_get()(this->_M_cur->_M_hash_code,
- _M_bucket_count);
+ = _RangeHash{}(this->_M_cur->_M_hash_code, _M_bucket_count);
if (__bkt != _M_bucket)
this->_M_cur = nullptr;
}
};
template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2, typename _Hash>
+ typename _Hash, typename _RangeHash, typename _Unused>
using __hash_code_for_local_iter
= _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, false>>;
+ _Hash, _RangeHash, _Unused, false>>;
// Partial specialization used when hash codes are not cached
template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2, typename _Hash>
+ typename _Hash, typename _RangeHash, typename _Unused>
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, false>
- : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
+ _Hash, _RangeHash, _Unused, false>
+ : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
+ _Unused>
, _Node_iterator_base<_Value, false>
{
protected:
using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, false>;
+ _Hash, _RangeHash, _Unused, false>;
using __node_iter_base = _Node_iterator_base<_Value, false>;
_Local_iterator_base() : _M_bucket_count(-1) { }
/// local iterators
template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
bool __constant_iterators, bool __cache>
struct _Local_iterator
: public _Local_iterator_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, __cache>
+ _Hash, _RangeHash, _Unused, __cache>
{
private:
using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, __cache>;
+ _Hash, _RangeHash, _Unused, __cache>;
using __hash_code_base = typename __base_type::__hash_code_base;
public:
typedef _Value value_type;
typedef typename std::conditional<__constant_iterators,
const _Value*, _Value*>::type
- pointer;
+ pointer;
typedef typename std::conditional<__constant_iterators,
const _Value&, _Value&>::type
- reference;
+ reference;
typedef std::ptrdiff_t difference_type;
typedef std::forward_iterator_tag iterator_category;
/// local const_iterators
template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
bool __constant_iterators, bool __cache>
struct _Local_const_iterator
: public _Local_iterator_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, __cache>
+ _Hash, _RangeHash, _Unused, __cache>
{
private:
using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, __cache>;
+ _Hash, _RangeHash, _Unused, __cache>;
using __hash_code_base = typename __base_type::__hash_code_base;
public:
{ }
_Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash,
+ _Hash, _RangeHash, _Unused,
__constant_iterators,
__cache>& __x)
: __base_type(__x)
* - __detail::_Hash_code_base
* - __detail::_Hashtable_ebo_helper
*/
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _Traits>
- struct _Hashtable_base
- : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
- _Traits::__hash_cached::value>,
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _Equal, typename _Hash, typename _RangeHash,
+ typename _Unused, typename _Traits>
+ struct _Hashtable_base
+ : public _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
+ _Unused, _Traits::__hash_cached::value>,
private _Hashtable_ebo_helper<0, _Equal>
{
public:
using __unique_keys = typename __traits_type::__unique_keys;
using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash,
+ _Hash, _RangeHash, _Unused,
__hash_cached::value>;
using __hash_code = typename __hash_code_base::__hash_code;
using __node_type = typename __hash_code_base::__node_type;
- using iterator = __detail::_Node_iterator<value_type,
- __constant_iterators::value,
- __hash_cached::value>;
+ using iterator = _Node_iterator<value_type,
+ __constant_iterators::value,
+ __hash_cached::value>;
- using const_iterator = __detail::_Node_const_iterator<value_type,
- __constant_iterators::value,
- __hash_cached::value>;
+ using const_iterator = _Node_const_iterator<value_type,
+ __constant_iterators::value,
+ __hash_cached::value>;
- using local_iterator = __detail::_Local_iterator<key_type, value_type,
- _ExtractKey, _H1, _H2, _Hash,
- __constant_iterators::value,
- __hash_cached::value>;
+ using local_iterator = _Local_iterator<key_type, value_type,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators::value,
+ __hash_cached::value>;
- using const_local_iterator = __detail::_Local_const_iterator<key_type,
- value_type,
- _ExtractKey, _H1, _H2, _Hash,
+ using const_local_iterator = _Local_const_iterator<key_type, value_type,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
__constant_iterators::value,
- __hash_cached::value>;
+ __hash_cached::value>;
using __ireturn_type = typename std::conditional<__unique_keys::value,
std::pair<iterator, bool>,
protected:
_Hashtable_base() = default;
- _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2,
- const _Hash& __hash, const _Equal& __eq)
- : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
+ _Hashtable_base(const _Hash& __hash, const _Equal& __eq)
+ : __hash_code_base(__hash), _EqualEBO(__eq)
{ }
bool
"key equality predicate must be invocable with two arguments of "
"key type");
return _Equal_hash_code<__node_type>::_S_equals(__c, *__n)
- && _M_eq()(__k, this->_M_extract()(__n->_M_v()));
+ && _M_eq()(__k, _ExtractKey{}(__n->_M_v()));
}
bool
_M_node_equals(const __node_type* __lhn, const __node_type* __rhn) const
{
return _Equal_hash_code<__node_type>::_S_node_equals(*__lhn, *__rhn)
- && _M_eq()(this->_M_extract()(__lhn->_M_v()),
- this->_M_extract()(__rhn->_M_v()));
+ && _M_eq()(_ExtractKey{}(__lhn->_M_v()),
+ _ExtractKey{}(__rhn->_M_v()));
}
void
*/
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits,
bool _Unique_keys = _Traits::__unique_keys::value>
struct _Equality;
/// unordered_map and unordered_set specializations.
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>
{
using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>;
+ _Hash, _RangeHash, _Unused,
+ _RehashPolicy, _Traits>;
bool
_M_equal(const __hashtable&) const;
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
bool
_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::
_M_equal(const __hashtable& __other) const
{
using __node_base = typename __hashtable::__node_base;
/// unordered_multiset and unordered_multimap specializations.
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
{
using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>;
+ _Hash, _RangeHash, _Unused,
+ _RehashPolicy, _Traits>;
bool
_M_equal(const __hashtable&) const;
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
+ typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
bool
_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>::
_M_equal(const __hashtable& __other) const
{
using __node_base = typename __hashtable::__node_base;
std::size_t __x_count = 1;
auto __itx_end = __itx;
for (++__itx_end; __itx_end != __this->end()
- && __this->key_eq()(_ExtractKey()(*__itx),
- _ExtractKey()(*__itx_end));
+ && __this->key_eq()(_ExtractKey{}(*__itx),
+ _ExtractKey{}(*__itx_end));
++__itx_end)
++__x_count;
__node_type* __y_n = static_cast<__node_type*>(__y_prev_n->_M_nxt);
for (;;)
{
- if (__this->key_eq()(_ExtractKey()(__y_n->_M_v()),
- _ExtractKey()(*__itx)))
+ if (__this->key_eq()(_ExtractKey{}(__y_n->_M_v()),
+ _ExtractKey{}(*__itx)))
break;
__node_type* __y_ref_n = __y_n;
projects / thirdparty / gcc.git / commitdiff
