Subversion Repositories openrisc

// hashtable.h header -*- C++ -*-

// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// <http://www.gnu.org/licenses/>.

/** @file bits/hashtable.h

 *  This is an internal header file, included by other library headers.

 *  Do not attempt to use it directly. @headername{unordered_map, unordered_set}

 */

#ifndef _HASHTABLE_H

#define _HASHTABLE_H 1

#pragma GCC system_header

#include <bits/hashtable_policy.h>

namespace std _GLIBCXX_VISIBILITY(default)

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

  // Class template _Hashtable, class definition.

  // Meaning of class template _Hashtable's template parameters

  // _Key and _Value: arbitrary CopyConstructible types.

  // _Allocator: an allocator type ([lib.allocator.requirements]) whose

  // value type is Value.  As a conforming extension, we allow for

  // value type != Value.

  // _ExtractKey: function object that takes an object of type Value

  // and returns a value of type _Key.

  // _Equal: function object that takes two objects of type k and returns

  // a bool-like value that is true if the two objects are considered equal.

  // _H1: 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()].

  // _H2: 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).

  // _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.

  // _RehashPolicy: Policy class with three members, all of which govern

  // the bucket count. _M_next_bkt(n) returns a bucket count no smaller

  // than n.  _M_bkt_for_elements(n) returns a 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>).

  // __cache_hash_code: bool.  true if we store the value of the hash

  // function along with the value.  This is a time-space tradeoff.

  // Storing it may improve lookup speed by reducing the number of times

  // we need to call the Equal function.

  // __constant_iterators: bool.  true if iterator and const_iterator are

  // both constant iterator types.  This is true for unordered_set and

  // unordered_multiset, false for unordered_map and unordered_multimap.

  // __unique_keys: bool.  true if the return value of _Hashtable::count(k)

  // is always at most one, false if it may be an arbitrary number.  This

  // true for unordered_set and unordered_map, false for unordered_multiset

  // and unordered_multimap.

  /**

   * Here's _Hashtable data structure, each _Hashtable has:

   * - _Bucket[]       _M_buckets

   * - _Hash_node_base _M_before_begin

   * - size_type       _M_bucket_count

   * - size_type       _M_element_count

   *

   * with _Bucket being _Hash_node* and _Hash_node constaining:

   * - _Hash_node*   _M_next

   * - Tp            _M_value

   * - size_t        _M_code if cache_hash_code is true

   *

   * In terms of Standard containers the hastable is like the aggregation of:

   * - std::forward_list<_Node> containing the elements

   * - std::vector<std::forward_list<_Node>::iterator> representing the buckets

   *

   * The non-empty buckets contain the node before the first bucket node. This

   * design allow to implement something like a std::forward_list::insert_after

   * on container insertion and std::forward_list::erase_after on container

   * erase calls. _M_before_begin is equivalent to

   * std::foward_list::before_begin. Empty buckets are containing nullptr.

   * Note that one of the non-empty bucket contains &_M_before_begin which is

   * not a derefenrenceable node so the node pointers in buckets shall never be

   * derefenrenced, only its next node can be.

   *

   * Walk through a bucket nodes require a check on the hash code to see if the

   * node is still in the bucket. Such a design impose a quite efficient hash

   * functor and is one of the reasons it is highly advise to set

   * __cache_hash_code to true.

   *

   * The container iterators are simply built from nodes. This way incrementing

   * the iterator is perfectly efficient independent of how many empty buckets

   * there are in the container.

   *

   * On insert we compute element hash code and thanks to it find the bucket

   * index. If the element must be inserted on an empty bucket we add it at the

   * beginning of the singly linked list and make the bucket point to

   * _M_before_begin. The bucket that used to point to _M_before_begin, if any,

   * is updated to point to its new before begin node.

   *

   * On erase, the simple iterator design impose to use the hash functor to get

   * the index of the bucket to update. For this reason, when __cache_hash_code

   * is set to false, there is a static assertion that the hash functor cannot

   * throw.

   */

  template<typename _Key, typename _Value, typename _Allocator,

           typename _ExtractKey, typename _Equal,

           typename _H1, typename _H2, typename _Hash,

           typename _RehashPolicy,

           bool __cache_hash_code,

           bool __constant_iterators,

           bool __unique_keys>

    class _Hashtable

    : public __detail::_Rehash_base<_RehashPolicy,

                                    _Hashtable<_Key, _Value, _Allocator,

                                               _ExtractKey,

                                               _Equal, _H1, _H2, _Hash,

                                               _RehashPolicy,

                                               __cache_hash_code,

                                               __constant_iterators,

                                               __unique_keys> >,

      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,

                                            _ExtractKey,

                                            _Equal, _H1, _H2, _Hash,

                                            _RehashPolicy,

                                            __cache_hash_code,

                                            __constant_iterators,

                                            __unique_keys> >,

      public __detail::_Equality_base<_ExtractKey, __unique_keys,

                                      _Hashtable<_Key, _Value, _Allocator,

                                                 _ExtractKey,

                                                 _Equal, _H1, _H2, _Hash,

                                                 _RehashPolicy,

                                                 __cache_hash_code,

                                                 __constant_iterators,

                                                 __unique_keys> >

    {

      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 not cached the hash functor shall not throw

      // because it is used in methods (erase, swap...) that shall not throw.

      static_assert(__if_hash_code_not_cached<__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.

      // 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;

      typedef _Key                                        key_type;

      typedef _Equal                                      key_equal;

      // mapped_type, if present, comes from _Map_base.

      // hasher, if present, comes from _Hash_code_base.

      typedef typename _Allocator::pointer                pointer;

      typedef typename _Allocator::const_pointer          const_pointer;

      typedef typename _Allocator::reference              reference;

      typedef typename _Allocator::const_reference        const_reference;

      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>

                                                          iterator;

      typedef __detail::_Node_const_iterator<value_type,

                                             __constant_iterators,

                                             __cache_hash_code>

                                                          const_iterator;

      template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,

               typename _Hashtable2>

        friend struct __detail::_Map_base;

    private:

      typedef typename _RehashPolicy::_State _RehashPolicyState;

      typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;

      typedef typename _Allocator::template rebind<_Node>::other

                                                        _Node_allocator_type;

      typedef __detail::_Hash_node_base _BaseNode;

      typedef _BaseNode* _Bucket;

      typedef typename _Allocator::template rebind<_Bucket>::other

                                                        _Bucket_allocator_type;

      typedef typename _Allocator::template rebind<_Value>::other

                                                        _Value_allocator_type;

      _Node_allocator_type      _M_node_allocator;

      _Bucket*                  _M_buckets;

      size_type                 _M_bucket_count;

      _BaseNode                 _M_before_begin;

      size_type                 _M_element_count;

      _RehashPolicy             _M_rehash_policy;

      template<typename... _Args>

        _Node*

        _M_allocate_node(_Args&&... __args);

      void

      _M_deallocate_node(_Node* __n);

      // Deallocate the linked list of nodes pointed to by __n

      void

      _M_deallocate_nodes(_Node* __n);

      _Bucket*

      _M_allocate_buckets(size_type __n);

      void

      _M_deallocate_buckets(_Bucket*, size_type __n);

      // Gets bucket begin, deals with the fact that non-empty buckets contain

      // their before begin node.

      _Node*

      _M_bucket_begin(size_type __bkt) const;

      _Node*

      _M_begin() const

      { return static_cast<_Node*>(_M_before_begin._M_nxt); }

    public:

      // Constructor, destructor, assignment, swap

      _Hashtable(size_type __bucket_hint,

                 const _H1&, const _H2&, const _Hash&,

                 const _Equal&, const _ExtractKey&,

                 const allocator_type&);

      template<typename _InputIterator>

        _Hashtable(_InputIterator __first, _InputIterator __last,

                   size_type __bucket_hint,

                   const _H1&, const _H2&, const _Hash&,

                   const _Equal&, const _ExtractKey&,

                   const allocator_type&);

      _Hashtable(const _Hashtable&);

      _Hashtable(_Hashtable&&);

      _Hashtable&

      operator=(const _Hashtable& __ht)

      {

        _Hashtable __tmp(__ht);

        this->swap(__tmp);

        return *this;

      }

      _Hashtable&

      operator=(_Hashtable&& __ht)

      {

        // NB: DR 1204.

        // NB: DR 675.

        this->clear();

        this->swap(__ht);

        return *this;

      }

      ~_Hashtable() noexcept;

      void swap(_Hashtable&);

      // Basic container operations

      iterator

      begin() noexcept

      { return iterator(_M_begin()); }

      const_iterator

      begin() const noexcept

      { return const_iterator(_M_begin()); }

      iterator

      end() noexcept

      { return iterator(nullptr); }

      const_iterator

      end() const noexcept

      { return const_iterator(nullptr); }

      const_iterator

      cbegin() const noexcept

      { return const_iterator(_M_begin()); }

      const_iterator

      cend() const noexcept

      { return const_iterator(nullptr); }

      size_type

      size() const noexcept

      { return _M_element_count; }

      bool

      empty() const noexcept

      { return size() == 0; }

      allocator_type

      get_allocator() const noexcept

      { return allocator_type(_M_node_allocator); }

      size_type

      max_size() const noexcept

      { return _M_node_allocator.max_size(); }

      // Observers

      key_equal

      key_eq() const

      { return this->_M_eq(); }

      // hash_function, if present, comes from _Hash_code_base.

      // Bucket operations

      size_type

      bucket_count() const noexcept

      { return _M_bucket_count; }

      size_type

      max_bucket_count() const noexcept

      { return max_size(); }

      size_type

      bucket_size(size_type __n) const

      { return std::distance(begin(__n), end(__n)); }

      size_type

      bucket(const key_type& __k) const

      { return _M_bucket_index(__k, this->_M_hash_code(__k)); }

      local_iterator

      begin(size_type __n)

      { return local_iterator(_M_bucket_begin(__n), __n,

                              _M_bucket_count); }

      local_iterator

      end(size_type __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), __n,

                                    _M_bucket_count); }

      const_local_iterator

      end(size_type __n) const

      { 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), __n,

                                    _M_bucket_count); }

      const_local_iterator

      cend(size_type __n) const

      { return const_local_iterator(nullptr, __n, _M_bucket_count); }

      float

      load_factor() const noexcept

      {

        return static_cast<float>(size()) / static_cast<float>(bucket_count());

      }

      // max_load_factor, if present, comes from _Rehash_base.

      // Generalization of max_load_factor.  Extension, not found in TR1.  Only

      // useful if _RehashPolicy is something other than the default.

      const _RehashPolicy&

      __rehash_policy() const

      { return _M_rehash_policy; }

      void

      __rehash_policy(const _RehashPolicy&);

      // Lookup.

      iterator

      find(const key_type& __k);

      const_iterator

      find(const key_type& __k) const;

      size_type

      count(const key_type& __k) const;

      std::pair<iterator, iterator>

      equal_range(const key_type& __k);

      std::pair<const_iterator, const_iterator>

      equal_range(const key_type& __k) const;

    private:

      // Bucket index computation helpers.

      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

      // Find the node before the one matching the criteria.

      _BaseNode*

      _M_find_before_node(size_type, const key_type&,

                          typename _Hashtable::_Hash_code_type) const;

      _Node*

      _M_find_node(size_type __bkt, const key_type& __key,

                   typename _Hashtable::_Hash_code_type __c) const

      {

        _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c);

        if (__before_n)

          return static_cast<_Node*>(__before_n->_M_nxt);

        return nullptr;

      }

      // Insert a node at the beginning of a bucket.

      void

      _M_insert_bucket_begin(size_type, _Node*);

      // Remove the bucket first node

      void

      _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,

                             size_type __next_bkt);

      // Get the node before __n in the bucket __bkt

      _BaseNode*

      _M_get_previous_node(size_type __bkt, _BaseNode* __n);

      template<typename _Arg>

        iterator

        _M_insert_bucket(_Arg&&, size_type,

                         typename _Hashtable::_Hash_code_type);

      typedef typename std::conditional<__unique_keys,

                                        std::pair<iterator, bool>,

                                        iterator>::type

        _Insert_Return_Type;

      typedef typename std::conditional<__unique_keys,

                                        std::_Select1st<_Insert_Return_Type>,

                                        std::_Identity<_Insert_Return_Type>

                                   >::type

        _Insert_Conv_Type;

    protected:

      template<typename... _Args>

        std::pair<iterator, bool>

        _M_emplace(std::true_type, _Args&&... __args);

      template<typename... _Args>

        iterator

        _M_emplace(std::false_type, _Args&&... __args);

      template<typename _Arg>

        std::pair<iterator, bool>

        _M_insert(_Arg&&, std::true_type);

      template<typename _Arg>

        iterator

        _M_insert(_Arg&&, std::false_type);

    public:

      // Emplace, insert and erase

      template<typename... _Args>

        _Insert_Return_Type

        emplace(_Args&&... __args)

        { return _M_emplace(integral_constant<bool, __unique_keys>(),

                            std::forward<_Args>(__args)...); }

      template<typename... _Args>

        iterator

        emplace_hint(const_iterator, _Args&&... __args)

        { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); }

      _Insert_Return_Type

      insert(const value_type& __v)

      { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }

      iterator

      insert(const_iterator, const value_type& __v)

      { return _Insert_Conv_Type()(insert(__v)); }

      template<typename _Pair, typename = typename

        std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,

                              std::is_convertible<_Pair,

                                                  value_type>>::value>::type>

        _Insert_Return_Type

        insert(_Pair&& __v)

        { return _M_insert(std::forward<_Pair>(__v),

                           integral_constant<bool, __unique_keys>()); }

      template<typename _Pair, typename = typename

        std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,

                              std::is_convertible<_Pair,

                                                  value_type>>::value>::type>

        iterator

        insert(const_iterator, _Pair&& __v)

        { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }

      template<typename _InputIterator>

        void

        insert(_InputIterator __first, _InputIterator __last);

      void

      insert(initializer_list<value_type> __l)

      { this->insert(__l.begin(), __l.end()); }

      iterator

      erase(const_iterator);

      // LWG 2059.

      iterator

      erase(iterator __it)

      { return erase(const_iterator(__it)); }

      size_type

      erase(const key_type&);

      iterator

      erase(const_iterator, const_iterator);

      void

      clear() noexcept;

      // Set number of buckets to be appropriate for container of n element.

      void rehash(size_type __n);

      // DR 1189.

      // reserve, if present, comes from _Rehash_base.

    private:

      // Unconditionally change size of bucket array to n, restore hash policy

      // state to __state on exception.

      void _M_rehash(size_type __n, const _RehashPolicyState& __state);

    };

  // Definitions of class template _Hashtable's out-of-line member functions.

  template<typename _Key, typename _Value,

           typename _Allocator, typename _ExtractKey, typename _Equal,

           typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

           bool __chc, bool __cit, bool __uk>

    template<typename... _Args>

      typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

                          _H1, _H2, _Hash, _RehashPolicy,

                          __chc, __cit, __uk>::_Node*

      _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

                 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

      _M_allocate_node(_Args&&... __args)

      {

        _Node* __n = _M_node_allocator.allocate(1);

        __try

          {

            _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);

            return __n;

          }

        __catch(...)

          {

            _M_node_allocator.deallocate(__n, 1);

            __throw_exception_again;

          }

      }

  template<typename _Key, typename _Value,

           typename _Allocator, typename _ExtractKey, typename _Equal,

           typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

           bool __chc, bool __cit, bool __uk>

    void

    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

    _M_deallocate_node(_Node* __n)

    {

      _M_node_allocator.destroy(__n);

      _M_node_allocator.deallocate(__n, 1);

    }

  template<typename _Key, typename _Value,

           typename _Allocator, typename _ExtractKey, typename _Equal,

           typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

           bool __chc, bool __cit, bool __uk>

    void

    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

    _M_deallocate_nodes(_Node* __n)

    {

      while (__n)

        {

          _Node* __tmp = __n;

          __n = __n->_M_next();

          _M_deallocate_node(__tmp);

        }

    }

  template<typename _Key, typename _Value,

           typename _Allocator, typename _ExtractKey, typename _Equal,

           typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

           bool __chc, bool __cit, bool __uk>

    typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

                        _H1, _H2, _Hash, _RehashPolicy,

                        __chc, __cit, __uk>::_Bucket*

    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

    _M_allocate_buckets(size_type __n)

    {

      _Bucket_allocator_type __alloc(_M_node_allocator);

      _Bucket* __p = __alloc.allocate(__n);

      __builtin_memset(__p, 0, __n * sizeof(_Bucket));

      return __p;

    }

  template<typename _Key, typename _Value,

           typename _Allocator, typename _ExtractKey, typename _Equal,

           typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

           bool __chc, bool __cit, bool __uk>

    void

    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

    _M_deallocate_buckets(_Bucket* __p, size_type __n)

    {

      _Bucket_allocator_type __alloc(_M_node_allocator);

      __alloc.deallocate(__p, __n);

    }

  template<typename _Key, typename _Value,

           typename _Allocator, typename _ExtractKey, typename _Equal,

           typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

           bool __chc, bool __cit, bool __uk>

    typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,

                        _Equal, _H1, _H2, _Hash, _RehashPolicy,

                        __chc, __cit, __uk>::_Node*

    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

    _M_bucket_begin(size_type __bkt) const

    {

      _BaseNode* __n = _M_buckets[__bkt];

      return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr;

    }

  template<typename _Key, typename _Value,

           typename _Allocator, typename _ExtractKey, typename _Equal,

           typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

           bool __chc, bool __cit, bool __uk>

    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

    _Hashtable(size_type __bucket_hint,

               const _H1& __h1, const _H2& __h2, const _Hash& __h,

               const _Equal& __eq, const _ExtractKey& __exk,