+ const _ExtractKey&
+ _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+ _ExtractKey&
+ _M_extract() { return _EboExtractKey::_S_get(*this); }
+ const _H1&
+ _M_h1() const { return _EboH1::_S_cget(*this); }
+ _H1&
+ _M_h1() { return _EboH1::_S_get(*this); }
+ const _H2&
+ _M_h2() const { return _EboH2::_S_cget(*this); }
+ _H2&
+ _M_h2() { return _EboH2::_S_get(*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>
+ {
+ static bool
+ _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>
+ {
+ static bool
+ _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
+ : _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+ __cache_hash_code>,
+ _Ebo_helper<0, _Equal>
+ {
+ private:
+ typedef _Ebo_helper<0, _Equal> _EboEqual;
+
+ protected:
+ typedef _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache_hash_code> _HCBase;
+ typedef typename _HCBase::_Hash_code_type _Hash_code_type;
+
+ _Hashtable_base(const _ExtractKey& __ex,
+ const _H1& __h1, const _H2& __h2,
+ const _Hash& __hash, const _Equal& __eq)
+ : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__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)
+ {
+ _HCBase::_M_swap(__x);
+ std::swap(_M_eq(), __x._M_eq());
+ }
+
+ private:
+ const _Equal&
+ _M_eq() const { return _EboEqual::_S_cget(*this); }
+ _Equal&
+ _M_eq() { return _EboEqual::_S_get(*this); }
+ };
+
+ // 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>
+ : _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>
+ : _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;
+ }