libstdc++
hashtable_policy.h
Go to the documentation of this file.
00001 // Internal policy header for unordered_set and unordered_map -*- C++ -*-
00002 
00003 // Copyright (C) 2010-2015 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/hashtable_policy.h
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly.
00028  *  @headername{unordered_map,unordered_set}
00029  */
00030 
00031 #ifndef _HASHTABLE_POLICY_H
00032 #define _HASHTABLE_POLICY_H 1
00033 
00034 namespace std _GLIBCXX_VISIBILITY(default)
00035 {
00036 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00037 
00038   template<typename _Key, typename _Value, typename _Alloc,
00039            typename _ExtractKey, typename _Equal,
00040            typename _H1, typename _H2, typename _Hash,
00041            typename _RehashPolicy, typename _Traits>
00042     class _Hashtable;
00043 
00044 _GLIBCXX_END_NAMESPACE_VERSION
00045 
00046 namespace __detail
00047 {
00048 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00049 
00050   /**
00051    *  @defgroup hashtable-detail Base and Implementation Classes
00052    *  @ingroup unordered_associative_containers
00053    *  @{
00054    */
00055   template<typename _Key, typename _Value,
00056            typename _ExtractKey, typename _Equal,
00057            typename _H1, typename _H2, typename _Hash, typename _Traits>
00058     struct _Hashtable_base;
00059 
00060   // Helper function: return distance(first, last) for forward
00061   // iterators, or 0 for input iterators.
00062   template<class _Iterator>
00063     inline typename std::iterator_traits<_Iterator>::difference_type
00064     __distance_fw(_Iterator __first, _Iterator __last,
00065                   std::input_iterator_tag)
00066     { return 0; }
00067 
00068   template<class _Iterator>
00069     inline typename std::iterator_traits<_Iterator>::difference_type
00070     __distance_fw(_Iterator __first, _Iterator __last,
00071                   std::forward_iterator_tag)
00072     { return std::distance(__first, __last); }
00073 
00074   template<class _Iterator>
00075     inline typename std::iterator_traits<_Iterator>::difference_type
00076     __distance_fw(_Iterator __first, _Iterator __last)
00077     {
00078       typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
00079       return __distance_fw(__first, __last, _Tag());
00080     }
00081 
00082   // Helper type used to detect whether the hash functor is noexcept.
00083   template <typename _Key, typename _Hash>
00084     struct __is_noexcept_hash : std::__bool_constant<
00085         noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
00086     { };
00087 
00088   struct _Identity
00089   {
00090     template<typename _Tp>
00091       _Tp&&
00092       operator()(_Tp&& __x) const
00093       { return std::forward<_Tp>(__x); }
00094   };
00095 
00096   struct _Select1st
00097   {
00098     template<typename _Tp>
00099       auto
00100       operator()(_Tp&& __x) const
00101       -> decltype(std::get<0>(std::forward<_Tp>(__x)))
00102       { return std::get<0>(std::forward<_Tp>(__x)); }
00103   };
00104 
00105   template<typename _NodeAlloc>
00106     struct _Hashtable_alloc;
00107 
00108   // Functor recycling a pool of nodes and using allocation once the pool is
00109   // empty.
00110   template<typename _NodeAlloc>
00111     struct _ReuseOrAllocNode
00112     {
00113     private:
00114       using __node_alloc_type = _NodeAlloc;
00115       using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>;
00116       using __value_alloc_type = typename __hashtable_alloc::__value_alloc_type;
00117       using __value_alloc_traits =
00118         typename __hashtable_alloc::__value_alloc_traits;
00119       using __node_alloc_traits =
00120         typename __hashtable_alloc::__node_alloc_traits;
00121       using __node_type = typename __hashtable_alloc::__node_type;
00122 
00123     public:
00124       _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
00125         : _M_nodes(__nodes), _M_h(__h) { }
00126       _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
00127 
00128       ~_ReuseOrAllocNode()
00129       { _M_h._M_deallocate_nodes(_M_nodes); }
00130 
00131       template<typename _Arg>
00132         __node_type*
00133         operator()(_Arg&& __arg) const
00134         {
00135           if (_M_nodes)
00136             {
00137               __node_type* __node = _M_nodes;
00138               _M_nodes = _M_nodes->_M_next();
00139               __node->_M_nxt = nullptr;
00140               __value_alloc_type __a(_M_h._M_node_allocator());
00141               __value_alloc_traits::destroy(__a, __node->_M_valptr());
00142               __try
00143                 {
00144                   __value_alloc_traits::construct(__a, __node->_M_valptr(),
00145                                                   std::forward<_Arg>(__arg));
00146                 }
00147               __catch(...)
00148                 {
00149                   __node->~__node_type();
00150                   __node_alloc_traits::deallocate(_M_h._M_node_allocator(),
00151                                                   __node, 1);
00152                   __throw_exception_again;
00153                 }
00154               return __node;
00155             }
00156           return _M_h._M_allocate_node(std::forward<_Arg>(__arg));
00157         }
00158 
00159     private:
00160       mutable __node_type* _M_nodes;
00161       __hashtable_alloc& _M_h;
00162     };
00163 
00164   // Functor similar to the previous one but without any pool of nodes to
00165   // recycle.
00166   template<typename _NodeAlloc>
00167     struct _AllocNode
00168     {
00169     private:
00170       using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
00171       using __node_type = typename __hashtable_alloc::__node_type;
00172 
00173     public:
00174       _AllocNode(__hashtable_alloc& __h)
00175         : _M_h(__h) { }
00176 
00177       template<typename _Arg>
00178         __node_type*
00179         operator()(_Arg&& __arg) const
00180         { return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
00181 
00182     private:
00183       __hashtable_alloc& _M_h;
00184     };
00185 
00186   // Auxiliary types used for all instantiations of _Hashtable nodes
00187   // and iterators.
00188 
00189   /**
00190    *  struct _Hashtable_traits
00191    *
00192    *  Important traits for hash tables.
00193    *
00194    *  @tparam _Cache_hash_code  Boolean value. True if the value of
00195    *  the hash function is stored along with the value. This is a
00196    *  time-space tradeoff.  Storing it may improve lookup speed by
00197    *  reducing the number of times we need to call the _Equal
00198    *  function.
00199    *
00200    *  @tparam _Constant_iterators  Boolean value. True if iterator and
00201    *  const_iterator are both constant iterator types. This is true
00202    *  for unordered_set and unordered_multiset, false for
00203    *  unordered_map and unordered_multimap.
00204    *
00205    *  @tparam _Unique_keys  Boolean value. True if the return value
00206    *  of _Hashtable::count(k) is always at most one, false if it may
00207    *  be an arbitrary number. This is true for unordered_set and
00208    *  unordered_map, false for unordered_multiset and
00209    *  unordered_multimap.
00210    */
00211   template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys>
00212     struct _Hashtable_traits
00213     {
00214       using __hash_cached = __bool_constant<_Cache_hash_code>;
00215       using __constant_iterators = __bool_constant<_Constant_iterators>;
00216       using __unique_keys = __bool_constant<_Unique_keys>;
00217     };
00218 
00219   /**
00220    *  struct _Hash_node_base
00221    *
00222    *  Nodes, used to wrap elements stored in the hash table.  A policy
00223    *  template parameter of class template _Hashtable controls whether
00224    *  nodes also store a hash code. In some cases (e.g. strings) this
00225    *  may be a performance win.
00226    */
00227   struct _Hash_node_base
00228   {
00229     _Hash_node_base* _M_nxt;
00230 
00231     _Hash_node_base() noexcept : _M_nxt() { }
00232 
00233     _Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
00234   };
00235 
00236   /**
00237    *  struct _Hash_node_value_base
00238    *
00239    *  Node type with the value to store.
00240    */
00241   template<typename _Value>
00242     struct _Hash_node_value_base : _Hash_node_base
00243     {
00244       typedef _Value value_type;
00245 
00246       __gnu_cxx::__aligned_buffer<_Value> _M_storage;
00247 
00248       _Value*
00249       _M_valptr() noexcept
00250       { return _M_storage._M_ptr(); }
00251 
00252       const _Value*
00253       _M_valptr() const noexcept
00254       { return _M_storage._M_ptr(); }
00255 
00256       _Value&
00257       _M_v() noexcept
00258       { return *_M_valptr(); }
00259 
00260       const _Value&
00261       _M_v() const noexcept
00262       { return *_M_valptr(); }
00263     };
00264 
00265   /**
00266    *  Primary template struct _Hash_node.
00267    */
00268   template<typename _Value, bool _Cache_hash_code>
00269     struct _Hash_node;
00270 
00271   /**
00272    *  Specialization for nodes with caches, struct _Hash_node.
00273    *
00274    *  Base class is __detail::_Hash_node_value_base.
00275    */
00276   template<typename _Value>
00277     struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value>
00278     {
00279       std::size_t  _M_hash_code;
00280 
00281       _Hash_node*
00282       _M_next() const noexcept
00283       { return static_cast<_Hash_node*>(this->_M_nxt); }
00284     };
00285 
00286   /**
00287    *  Specialization for nodes without caches, struct _Hash_node.
00288    *
00289    *  Base class is __detail::_Hash_node_value_base.
00290    */
00291   template<typename _Value>
00292     struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value>
00293     {
00294       _Hash_node*
00295       _M_next() const noexcept
00296       { return static_cast<_Hash_node*>(this->_M_nxt); }
00297     };
00298 
00299   /// Base class for node iterators.
00300   template<typename _Value, bool _Cache_hash_code>
00301     struct _Node_iterator_base
00302     {
00303       using __node_type = _Hash_node<_Value, _Cache_hash_code>;
00304 
00305       __node_type*  _M_cur;
00306 
00307       _Node_iterator_base(__node_type* __p) noexcept
00308       : _M_cur(__p) { }
00309 
00310       void
00311       _M_incr() noexcept
00312       { _M_cur = _M_cur->_M_next(); }
00313     };
00314 
00315   template<typename _Value, bool _Cache_hash_code>
00316     inline bool
00317     operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
00318                const _Node_iterator_base<_Value, _Cache_hash_code >& __y)
00319     noexcept
00320     { return __x._M_cur == __y._M_cur; }
00321 
00322   template<typename _Value, bool _Cache_hash_code>
00323     inline bool
00324     operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
00325                const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
00326     noexcept
00327     { return __x._M_cur != __y._M_cur; }
00328 
00329   /// Node iterators, used to iterate through all the hashtable.
00330   template<typename _Value, bool __constant_iterators, bool __cache>
00331     struct _Node_iterator
00332     : public _Node_iterator_base<_Value, __cache>
00333     {
00334     private:
00335       using __base_type = _Node_iterator_base<_Value, __cache>;
00336       using __node_type = typename __base_type::__node_type;
00337 
00338     public:
00339       typedef _Value                                    value_type;
00340       typedef std::ptrdiff_t                            difference_type;
00341       typedef std::forward_iterator_tag                 iterator_category;
00342 
00343       using pointer = typename std::conditional<__constant_iterators,
00344                                                 const _Value*, _Value*>::type;
00345 
00346       using reference = typename std::conditional<__constant_iterators,
00347                                                   const _Value&, _Value&>::type;
00348 
00349       _Node_iterator() noexcept
00350       : __base_type(0) { }
00351 
00352       explicit
00353       _Node_iterator(__node_type* __p) noexcept
00354       : __base_type(__p) { }
00355 
00356       reference
00357       operator*() const noexcept
00358       { return this->_M_cur->_M_v(); }
00359 
00360       pointer
00361       operator->() const noexcept
00362       { return this->_M_cur->_M_valptr(); }
00363 
00364       _Node_iterator&
00365       operator++() noexcept
00366       {
00367         this->_M_incr();
00368         return *this;
00369       }
00370 
00371       _Node_iterator
00372       operator++(int) noexcept
00373       {
00374         _Node_iterator __tmp(*this);
00375         this->_M_incr();
00376         return __tmp;
00377       }
00378     };
00379 
00380   /// Node const_iterators, used to iterate through all the hashtable.
00381   template<typename _Value, bool __constant_iterators, bool __cache>
00382     struct _Node_const_iterator
00383     : public _Node_iterator_base<_Value, __cache>
00384     {
00385     private:
00386       using __base_type = _Node_iterator_base<_Value, __cache>;
00387       using __node_type = typename __base_type::__node_type;
00388 
00389     public:
00390       typedef _Value                                    value_type;
00391       typedef std::ptrdiff_t                            difference_type;
00392       typedef std::forward_iterator_tag                 iterator_category;
00393 
00394       typedef const _Value*                             pointer;
00395       typedef const _Value&                             reference;
00396 
00397       _Node_const_iterator() noexcept
00398       : __base_type(0) { }
00399 
00400       explicit
00401       _Node_const_iterator(__node_type* __p) noexcept
00402       : __base_type(__p) { }
00403 
00404       _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
00405                            __cache>& __x) noexcept
00406       : __base_type(__x._M_cur) { }
00407 
00408       reference
00409       operator*() const noexcept
00410       { return this->_M_cur->_M_v(); }
00411 
00412       pointer
00413       operator->() const noexcept
00414       { return this->_M_cur->_M_valptr(); }
00415 
00416       _Node_const_iterator&
00417       operator++() noexcept
00418       {
00419         this->_M_incr();
00420         return *this;
00421       }
00422 
00423       _Node_const_iterator
00424       operator++(int) noexcept
00425       {
00426         _Node_const_iterator __tmp(*this);
00427         this->_M_incr();
00428         return __tmp;
00429       }
00430     };
00431 
00432   // Many of class template _Hashtable's template parameters are policy
00433   // classes.  These are defaults for the policies.
00434 
00435   /// Default range hashing function: use division to fold a large number
00436   /// into the range [0, N).
00437   struct _Mod_range_hashing
00438   {
00439     typedef std::size_t first_argument_type;
00440     typedef std::size_t second_argument_type;
00441     typedef std::size_t result_type;
00442 
00443     result_type
00444     operator()(first_argument_type __num,
00445                second_argument_type __den) const noexcept
00446     { return __num % __den; }
00447   };
00448 
00449   /// Default ranged hash function H.  In principle it should be a
00450   /// function object composed from objects of type H1 and H2 such that
00451   /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of
00452   /// h1 and h2.  So instead we'll just use a tag to tell class template
00453   /// hashtable to do that composition.
00454   struct _Default_ranged_hash { };
00455 
00456   /// Default value for rehash policy.  Bucket size is (usually) the
00457   /// smallest prime that keeps the load factor small enough.
00458   struct _Prime_rehash_policy
00459   {
00460     _Prime_rehash_policy(float __z = 1.0) noexcept
00461     : _M_max_load_factor(__z), _M_next_resize(0) { }
00462 
00463     float
00464     max_load_factor() const noexcept
00465     { return _M_max_load_factor; }
00466 
00467     // Return a bucket size no smaller than n.
00468     std::size_t
00469     _M_next_bkt(std::size_t __n) const;
00470 
00471     // Return a bucket count appropriate for n elements
00472     std::size_t
00473     _M_bkt_for_elements(std::size_t __n) const
00474     { return __builtin_ceil(__n / (long double)_M_max_load_factor); }
00475 
00476     // __n_bkt is current bucket count, __n_elt is current element count,
00477     // and __n_ins is number of elements to be inserted.  Do we need to
00478     // increase bucket count?  If so, return make_pair(true, n), where n
00479     // is the new bucket count.  If not, return make_pair(false, 0).
00480     std::pair<bool, std::size_t>
00481     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00482                    std::size_t __n_ins) const;
00483 
00484     typedef std::size_t _State;
00485 
00486     _State
00487     _M_state() const
00488     { return _M_next_resize; }
00489 
00490     void
00491     _M_reset() noexcept
00492     { _M_next_resize = 0; }
00493 
00494     void
00495     _M_reset(_State __state)
00496     { _M_next_resize = __state; }
00497 
00498     enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
00499 
00500     static const std::size_t _S_growth_factor = 2;
00501 
00502     float               _M_max_load_factor;
00503     mutable std::size_t _M_next_resize;
00504   };
00505 
00506   // Base classes for std::_Hashtable.  We define these base classes
00507   // because in some cases we want to do different things depending on
00508   // the value of a policy class.  In some cases the policy class
00509   // affects which member functions and nested typedefs are defined;
00510   // we handle that by specializing base class templates.  Several of
00511   // the base class templates need to access other members of class
00512   // template _Hashtable, so we use a variant of the "Curiously
00513   // Recurring Template Pattern" (CRTP) technique.
00514 
00515   /**
00516    *  Primary class template _Map_base.
00517    *
00518    *  If the hashtable has a value type of the form pair<T1, T2> and a
00519    *  key extraction policy (_ExtractKey) that returns the first part
00520    *  of the pair, the hashtable gets a mapped_type typedef.  If it
00521    *  satisfies those criteria and also has unique keys, then it also
00522    *  gets an operator[].
00523    */
00524   template<typename _Key, typename _Value, typename _Alloc,
00525            typename _ExtractKey, typename _Equal,
00526            typename _H1, typename _H2, typename _Hash,
00527            typename _RehashPolicy, typename _Traits,
00528            bool _Unique_keys = _Traits::__unique_keys::value>
00529     struct _Map_base { };
00530 
00531   /// Partial specialization, __unique_keys set to false.
00532   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
00533            typename _H1, typename _H2, typename _Hash,
00534            typename _RehashPolicy, typename _Traits>
00535     struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
00536                      _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
00537     {
00538       using mapped_type = typename std::tuple_element<1, _Pair>::type;
00539     };
00540 
00541   /// Partial specialization, __unique_keys set to true.
00542   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
00543            typename _H1, typename _H2, typename _Hash,
00544            typename _RehashPolicy, typename _Traits>
00545     struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
00546                      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
00547     {
00548     private:
00549       using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair,
00550                                                          _Select1st,
00551                                                         _Equal, _H1, _H2, _Hash,
00552                                                           _Traits>;
00553 
00554       using __hashtable = _Hashtable<_Key, _Pair, _Alloc,
00555                                      _Select1st, _Equal,
00556                                      _H1, _H2, _Hash, _RehashPolicy, _Traits>;
00557 
00558       using __hash_code = typename __hashtable_base::__hash_code;
00559       using __node_type = typename __hashtable_base::__node_type;
00560 
00561     public:
00562       using key_type = typename __hashtable_base::key_type;
00563       using iterator = typename __hashtable_base::iterator;
00564       using mapped_type = typename std::tuple_element<1, _Pair>::type;
00565 
00566       mapped_type&
00567       operator[](const key_type& __k);
00568 
00569       mapped_type&
00570       operator[](key_type&& __k);
00571 
00572       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00573       // DR 761. unordered_map needs an at() member function.
00574       mapped_type&
00575       at(const key_type& __k);
00576 
00577       const mapped_type&
00578       at(const key_type& __k) const;
00579     };
00580 
00581   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
00582            typename _H1, typename _H2, typename _Hash,
00583            typename _RehashPolicy, typename _Traits>
00584     auto
00585     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
00586               _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
00587     operator[](const key_type& __k)
00588     -> mapped_type&
00589     {
00590       __hashtable* __h = static_cast<__hashtable*>(this);
00591       __hash_code __code = __h->_M_hash_code(__k);
00592       std::size_t __n = __h->_M_bucket_index(__k, __code);
00593       __node_type* __p = __h->_M_find_node(__n, __k, __code);
00594 
00595       if (!__p)
00596         {
00597           __p = __h->_M_allocate_node(std::piecewise_construct,
00598                                       std::tuple<const key_type&>(__k),
00599                                       std::tuple<>());
00600           return __h->_M_insert_unique_node(__n, __code, __p)->second;
00601         }
00602 
00603       return __p->_M_v().second;
00604     }
00605 
00606   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
00607            typename _H1, typename _H2, typename _Hash,
00608            typename _RehashPolicy, typename _Traits>
00609     auto
00610     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
00611               _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
00612     operator[](key_type&& __k)
00613     -> mapped_type&
00614     {
00615       __hashtable* __h = static_cast<__hashtable*>(this);
00616       __hash_code __code = __h->_M_hash_code(__k);
00617       std::size_t __n = __h->_M_bucket_index(__k, __code);
00618       __node_type* __p = __h->_M_find_node(__n, __k, __code);
00619 
00620       if (!__p)
00621         {
00622           __p = __h->_M_allocate_node(std::piecewise_construct,
00623                                       std::forward_as_tuple(std::move(__k)),
00624                                       std::tuple<>());
00625           return __h->_M_insert_unique_node(__n, __code, __p)->second;
00626         }
00627 
00628       return __p->_M_v().second;
00629     }
00630 
00631   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
00632            typename _H1, typename _H2, typename _Hash,
00633            typename _RehashPolicy, typename _Traits>
00634     auto
00635     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
00636               _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
00637     at(const key_type& __k)
00638     -> mapped_type&
00639     {
00640       __hashtable* __h = static_cast<__hashtable*>(this);
00641       __hash_code __code = __h->_M_hash_code(__k);
00642       std::size_t __n = __h->_M_bucket_index(__k, __code);
00643       __node_type* __p = __h->_M_find_node(__n, __k, __code);
00644 
00645       if (!__p)
00646         __throw_out_of_range(__N("_Map_base::at"));
00647       return __p->_M_v().second;
00648     }
00649 
00650   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
00651            typename _H1, typename _H2, typename _Hash,
00652            typename _RehashPolicy, typename _Traits>
00653     auto
00654     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
00655               _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
00656     at(const key_type& __k) const
00657     -> const mapped_type&
00658     {
00659       const __hashtable* __h = static_cast<const __hashtable*>(this);
00660       __hash_code __code = __h->_M_hash_code(__k);
00661       std::size_t __n = __h->_M_bucket_index(__k, __code);
00662       __node_type* __p = __h->_M_find_node(__n, __k, __code);
00663 
00664       if (!__p)
00665         __throw_out_of_range(__N("_Map_base::at"));
00666       return __p->_M_v().second;
00667     }
00668 
00669   /**
00670    *  Primary class template _Insert_base.
00671    *
00672    *  insert member functions appropriate to all _Hashtables.
00673    */
00674   template<typename _Key, typename _Value, typename _Alloc,
00675            typename _ExtractKey, typename _Equal,
00676            typename _H1, typename _H2, typename _Hash,
00677            typename _RehashPolicy, typename _Traits>
00678     struct _Insert_base
00679     {
00680     protected:
00681       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
00682                                      _Equal, _H1, _H2, _Hash,
00683                                      _RehashPolicy, _Traits>;
00684 
00685       using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
00686                                                _Equal, _H1, _H2, _Hash,
00687                                                _Traits>;
00688 
00689       using value_type = typename __hashtable_base::value_type;
00690       using iterator = typename __hashtable_base::iterator;
00691       using const_iterator =  typename __hashtable_base::const_iterator;
00692       using size_type = typename __hashtable_base::size_type;
00693 
00694       using __unique_keys = typename __hashtable_base::__unique_keys;
00695       using __ireturn_type = typename __hashtable_base::__ireturn_type;
00696       using __node_type = _Hash_node<_Value, _Traits::__hash_cached::value>;
00697       using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
00698       using __node_gen_type = _AllocNode<__node_alloc_type>;
00699 
00700       __hashtable&
00701       _M_conjure_hashtable()
00702       { return *(static_cast<__hashtable*>(this)); }
00703 
00704       template<typename _InputIterator, typename _NodeGetter>
00705         void
00706         _M_insert_range(_InputIterator __first, _InputIterator __last,
00707                         const _NodeGetter&);
00708 
00709     public:
00710       __ireturn_type
00711       insert(const value_type& __v)
00712       {
00713         __hashtable& __h = _M_conjure_hashtable();
00714         __node_gen_type __node_gen(__h);
00715         return __h._M_insert(__v, __node_gen, __unique_keys());
00716       }
00717 
00718       iterator
00719       insert(const_iterator __hint, const value_type& __v)
00720       {
00721         __hashtable& __h = _M_conjure_hashtable();
00722         __node_gen_type __node_gen(__h);        
00723         return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
00724       }
00725 
00726       void
00727       insert(initializer_list<value_type> __l)
00728       { this->insert(__l.begin(), __l.end()); }
00729 
00730       template<typename _InputIterator>
00731         void
00732         insert(_InputIterator __first, _InputIterator __last)
00733         {
00734           __hashtable& __h = _M_conjure_hashtable();
00735           __node_gen_type __node_gen(__h);
00736           return _M_insert_range(__first, __last, __node_gen);
00737         }
00738     };
00739 
00740   template<typename _Key, typename _Value, typename _Alloc,
00741            typename _ExtractKey, typename _Equal,
00742            typename _H1, typename _H2, typename _Hash,
00743            typename _RehashPolicy, typename _Traits>
00744     template<typename _InputIterator, typename _NodeGetter>
00745       void
00746       _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
00747                     _RehashPolicy, _Traits>::
00748       _M_insert_range(_InputIterator __first, _InputIterator __last,
00749                       const _NodeGetter& __node_gen)
00750       {
00751         using __rehash_type = typename __hashtable::__rehash_type;
00752         using __rehash_state = typename __hashtable::__rehash_state;
00753         using pair_type = std::pair<bool, std::size_t>;
00754 
00755         size_type __n_elt = __detail::__distance_fw(__first, __last);
00756 
00757         __hashtable& __h = _M_conjure_hashtable();
00758         __rehash_type& __rehash = __h._M_rehash_policy;
00759         const __rehash_state& __saved_state = __rehash._M_state();
00760         pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
00761                                                         __h._M_element_count,
00762                                                         __n_elt);
00763 
00764         if (__do_rehash.first)
00765           __h._M_rehash(__do_rehash.second, __saved_state);
00766 
00767         for (; __first != __last; ++__first)
00768           __h._M_insert(*__first, __node_gen, __unique_keys());
00769       }
00770 
00771   /**
00772    *  Primary class template _Insert.
00773    *
00774    *  Select insert member functions appropriate to _Hashtable policy choices.
00775    */
00776   template<typename _Key, typename _Value, typename _Alloc,
00777            typename _ExtractKey, typename _Equal,
00778            typename _H1, typename _H2, typename _Hash,
00779            typename _RehashPolicy, typename _Traits,
00780            bool _Constant_iterators = _Traits::__constant_iterators::value,
00781            bool _Unique_keys = _Traits::__unique_keys::value>
00782     struct _Insert;
00783 
00784   /// Specialization.
00785   template<typename _Key, typename _Value, typename _Alloc,
00786            typename _ExtractKey, typename _Equal,
00787            typename _H1, typename _H2, typename _Hash,
00788            typename _RehashPolicy, typename _Traits>
00789     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
00790                    _RehashPolicy, _Traits, true, true>
00791     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
00792                            _H1, _H2, _Hash, _RehashPolicy, _Traits>
00793     {
00794       using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
00795                                         _Equal, _H1, _H2, _Hash,
00796                                         _RehashPolicy, _Traits>;
00797       using value_type = typename __base_type::value_type;
00798       using iterator = typename __base_type::iterator;
00799       using const_iterator =  typename __base_type::const_iterator;
00800 
00801       using __unique_keys = typename __base_type::__unique_keys;
00802       using __hashtable = typename __base_type::__hashtable;
00803       using __node_gen_type = typename __base_type::__node_gen_type;
00804 
00805       using __base_type::insert;
00806 
00807       std::pair<iterator, bool>
00808       insert(value_type&& __v)
00809       {
00810         __hashtable& __h = this->_M_conjure_hashtable();
00811         __node_gen_type __node_gen(__h);
00812         return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
00813       }
00814 
00815       iterator
00816       insert(const_iterator __hint, value_type&& __v)
00817       {
00818         __hashtable& __h = this->_M_conjure_hashtable();
00819         __node_gen_type __node_gen(__h);
00820         return __h._M_insert(__hint, std::move(__v), __node_gen,
00821                              __unique_keys());
00822       }
00823     };
00824 
00825   /// Specialization.
00826   template<typename _Key, typename _Value, typename _Alloc,
00827            typename _ExtractKey, typename _Equal,
00828            typename _H1, typename _H2, typename _Hash,
00829            typename _RehashPolicy, typename _Traits>
00830     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
00831                    _RehashPolicy, _Traits, true, false>
00832     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
00833                            _H1, _H2, _Hash, _RehashPolicy, _Traits>
00834     {
00835       using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
00836                                         _Equal, _H1, _H2, _Hash,
00837                                         _RehashPolicy, _Traits>;
00838       using value_type = typename __base_type::value_type;
00839       using iterator = typename __base_type::iterator;
00840       using const_iterator =  typename __base_type::const_iterator;
00841 
00842       using __unique_keys = typename __base_type::__unique_keys;
00843       using __hashtable = typename __base_type::__hashtable;
00844       using __node_gen_type = typename __base_type::__node_gen_type;
00845 
00846       using __base_type::insert;
00847 
00848       iterator
00849       insert(value_type&& __v)
00850       {
00851         __hashtable& __h = this->_M_conjure_hashtable();
00852         __node_gen_type __node_gen(__h);
00853         return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
00854       }
00855 
00856       iterator
00857       insert(const_iterator __hint, value_type&& __v)
00858       {
00859         __hashtable& __h = this->_M_conjure_hashtable();
00860         __node_gen_type __node_gen(__h);
00861         return __h._M_insert(__hint, std::move(__v), __node_gen,
00862                              __unique_keys());
00863       }
00864     };
00865 
00866   /// Specialization.
00867   template<typename _Key, typename _Value, typename _Alloc,
00868            typename _ExtractKey, typename _Equal,
00869            typename _H1, typename _H2, typename _Hash,
00870            typename _RehashPolicy, typename _Traits, bool _Unique_keys>
00871     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
00872                    _RehashPolicy, _Traits, false, _Unique_keys>
00873     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
00874                            _H1, _H2, _Hash, _RehashPolicy, _Traits>
00875     {
00876       using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
00877                                        _Equal, _H1, _H2, _Hash,
00878                                        _RehashPolicy, _Traits>;
00879       using value_type = typename __base_type::value_type;
00880       using iterator = typename __base_type::iterator;
00881       using const_iterator =  typename __base_type::const_iterator;
00882 
00883       using __unique_keys = typename __base_type::__unique_keys;
00884       using __hashtable = typename __base_type::__hashtable;
00885       using __ireturn_type = typename __base_type::__ireturn_type;
00886 
00887       using __base_type::insert;
00888 
00889       template<typename _Pair>
00890         using __is_cons = std::is_constructible<value_type, _Pair&&>;
00891 
00892       template<typename _Pair>
00893         using _IFcons = std::enable_if<__is_cons<_Pair>::value>;
00894 
00895       template<typename _Pair>
00896         using _IFconsp = typename _IFcons<_Pair>::type;
00897 
00898       template<typename _Pair, typename = _IFconsp<_Pair>>
00899         __ireturn_type
00900         insert(_Pair&& __v)
00901         {
00902           __hashtable& __h = this->_M_conjure_hashtable();
00903           return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
00904         }
00905 
00906       template<typename _Pair, typename = _IFconsp<_Pair>>
00907         iterator
00908         insert(const_iterator __hint, _Pair&& __v)
00909         {
00910           __hashtable& __h = this->_M_conjure_hashtable();
00911           return __h._M_emplace(__hint, __unique_keys(),
00912                                 std::forward<_Pair>(__v));
00913         }
00914    };
00915 
00916   /**
00917    *  Primary class template  _Rehash_base.
00918    *
00919    *  Give hashtable the max_load_factor functions and reserve iff the
00920    *  rehash policy is _Prime_rehash_policy.
00921   */
00922   template<typename _Key, typename _Value, typename _Alloc,
00923            typename _ExtractKey, typename _Equal,
00924            typename _H1, typename _H2, typename _Hash,
00925            typename _RehashPolicy, typename _Traits>
00926     struct _Rehash_base;
00927 
00928   /// Specialization.
00929   template<typename _Key, typename _Value, typename _Alloc,
00930            typename _ExtractKey, typename _Equal,
00931            typename _H1, typename _H2, typename _Hash, typename _Traits>
00932     struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
00933                         _H1, _H2, _Hash, _Prime_rehash_policy, _Traits>
00934     {
00935       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
00936                                      _Equal, _H1, _H2, _Hash,
00937                                      _Prime_rehash_policy, _Traits>;
00938 
00939       float
00940       max_load_factor() const noexcept
00941       {
00942         const __hashtable* __this = static_cast<const __hashtable*>(this);
00943         return __this->__rehash_policy().max_load_factor();
00944       }
00945 
00946       void
00947       max_load_factor(float __z)
00948       {
00949         __hashtable* __this = static_cast<__hashtable*>(this);
00950         __this->__rehash_policy(_Prime_rehash_policy(__z));
00951       }
00952 
00953       void
00954       reserve(std::size_t __n)
00955       {
00956         __hashtable* __this = static_cast<__hashtable*>(this);
00957         __this->rehash(__builtin_ceil(__n / max_load_factor()));
00958       }
00959     };
00960 
00961   /**
00962    *  Primary class template _Hashtable_ebo_helper.
00963    *
00964    *  Helper class using EBO when it is not forbidden (the type is not
00965    *  final) and when it is worth it (the type is empty.)
00966    */
00967   template<int _Nm, typename _Tp,
00968            bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
00969     struct _Hashtable_ebo_helper;
00970 
00971   /// Specialization using EBO.
00972   template<int _Nm, typename _Tp>
00973     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
00974     : private _Tp
00975     {
00976       _Hashtable_ebo_helper() = default;
00977 
00978       template<typename _OtherTp>
00979         _Hashtable_ebo_helper(_OtherTp&& __tp)
00980           : _Tp(std::forward<_OtherTp>(__tp))
00981         { }
00982 
00983       static const _Tp&
00984       _S_cget(const _Hashtable_ebo_helper& __eboh)
00985       { return static_cast<const _Tp&>(__eboh); }
00986 
00987       static _Tp&
00988       _S_get(_Hashtable_ebo_helper& __eboh)
00989       { return static_cast<_Tp&>(__eboh); }
00990     };
00991 
00992   /// Specialization not using EBO.
00993   template<int _Nm, typename _Tp>
00994     struct _Hashtable_ebo_helper<_Nm, _Tp, false>
00995     {
00996       _Hashtable_ebo_helper() = default;
00997 
00998       template<typename _OtherTp>
00999         _Hashtable_ebo_helper(_OtherTp&& __tp)
01000           : _M_tp(std::forward<_OtherTp>(__tp))
01001         { }
01002 
01003       static const _Tp&
01004       _S_cget(const _Hashtable_ebo_helper& __eboh)
01005       { return __eboh._M_tp; }
01006 
01007       static _Tp&
01008       _S_get(_Hashtable_ebo_helper& __eboh)
01009       { return __eboh._M_tp; }
01010 
01011     private:
01012       _Tp _M_tp;
01013     };
01014 
01015   /**
01016    *  Primary class template _Local_iterator_base.
01017    *
01018    *  Base class for local iterators, used to iterate within a bucket
01019    *  but not between buckets.
01020    */
01021   template<typename _Key, typename _Value, typename _ExtractKey,
01022            typename _H1, typename _H2, typename _Hash,
01023            bool __cache_hash_code>
01024     struct _Local_iterator_base;
01025 
01026   /**
01027    *  Primary class template _Hash_code_base.
01028    *
01029    *  Encapsulates two policy issues that aren't quite orthogonal.
01030    *   (1) the difference between using a ranged hash function and using
01031    *       the combination of a hash function and a range-hashing function.
01032    *       In the former case we don't have such things as hash codes, so
01033    *       we have a dummy type as placeholder.
01034    *   (2) Whether or not we cache hash codes.  Caching hash codes is
01035    *       meaningless if we have a ranged hash function.
01036    *
01037    *  We also put the key extraction objects here, for convenience.
01038    *  Each specialization derives from one or more of the template
01039    *  parameters to benefit from Ebo. This is important as this type
01040    *  is inherited in some cases by the _Local_iterator_base type used
01041    *  to implement local_iterator and const_local_iterator. As with
01042    *  any iterator type we prefer to make it as small as possible.
01043    *
01044    *  Primary template is unused except as a hook for specializations.
01045    */
01046   template<typename _Key, typename _Value, typename _ExtractKey,
01047            typename _H1, typename _H2, typename _Hash,
01048            bool __cache_hash_code>
01049     struct _Hash_code_base;
01050 
01051   /// Specialization: ranged hash function, no caching hash codes.  H1
01052   /// and H2 are provided but ignored.  We define a dummy hash code type.
01053   template<typename _Key, typename _Value, typename _ExtractKey,
01054            typename _H1, typename _H2, typename _Hash>
01055     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
01056     : private _Hashtable_ebo_helper<0, _ExtractKey>,
01057       private _Hashtable_ebo_helper<1, _Hash>
01058     {
01059     private:
01060       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
01061       using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>;
01062 
01063     protected:
01064       typedef void*                                     __hash_code;
01065       typedef _Hash_node<_Value, false>                 __node_type;
01066 
01067       // We need the default constructor for the local iterators and _Hashtable
01068       // default constructor.
01069       _Hash_code_base() = default;
01070 
01071       _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
01072                       const _Hash& __h)
01073       : __ebo_extract_key(__ex), __ebo_hash(__h) { }
01074 
01075       __hash_code
01076       _M_hash_code(const _Key& __key) const
01077       { return 0; }
01078 
01079       std::size_t
01080       _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const
01081       { return _M_ranged_hash()(__k, __n); }
01082 
01083       std::size_t
01084       _M_bucket_index(const __node_type* __p, std::size_t __n) const
01085         noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(),
01086                                                    (std::size_t)0)) )
01087       { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
01088 
01089       void
01090       _M_store_code(__node_type*, __hash_code) const
01091       { }
01092 
01093       void
01094       _M_copy_code(__node_type*, const __node_type*) const
01095       { }
01096 
01097       void
01098       _M_swap(_Hash_code_base& __x)
01099       {
01100         std::swap(_M_extract(), __x._M_extract());
01101         std::swap(_M_ranged_hash(), __x._M_ranged_hash());
01102       }
01103 
01104       const _ExtractKey&
01105       _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
01106 
01107       _ExtractKey&
01108       _M_extract() { return __ebo_extract_key::_S_get(*this); }
01109 
01110       const _Hash&
01111       _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); }
01112 
01113       _Hash&
01114       _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
01115     };
01116 
01117   // No specialization for ranged hash function while caching hash codes.
01118   // That combination is meaningless, and trying to do it is an error.
01119 
01120   /// Specialization: ranged hash function, cache hash codes.  This
01121   /// combination is meaningless, so we provide only a declaration
01122   /// and no definition.
01123   template<typename _Key, typename _Value, typename _ExtractKey,
01124            typename _H1, typename _H2, typename _Hash>
01125     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
01126 
01127   /// Specialization: hash function and range-hashing function, no
01128   /// caching of hash codes.
01129   /// Provides typedef and accessor required by C++ 11.
01130   template<typename _Key, typename _Value, typename _ExtractKey,
01131            typename _H1, typename _H2>
01132     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
01133                            _Default_ranged_hash, false>
01134     : private _Hashtable_ebo_helper<0, _ExtractKey>,
01135       private _Hashtable_ebo_helper<1, _H1>,
01136       private _Hashtable_ebo_helper<2, _H2>
01137     {
01138     private:
01139       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
01140       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
01141       using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
01142 
01143       // Gives the local iterator implementation access to _M_bucket_index().
01144       friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
01145                                          _Default_ranged_hash, false>;
01146 
01147     public:
01148       typedef _H1                                       hasher;
01149 
01150       hasher
01151       hash_function() const
01152       { return _M_h1(); }
01153 
01154     protected:
01155       typedef std::size_t                               __hash_code;
01156       typedef _Hash_node<_Value, false>                 __node_type;
01157 
01158       // We need the default constructor for the local iterators and _Hashtable
01159       // default constructor.
01160       _Hash_code_base() = default;
01161 
01162       _Hash_code_base(const _ExtractKey& __ex,
01163                       const _H1& __h1, const _H2& __h2,
01164                       const _Default_ranged_hash&)
01165       : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
01166 
01167       __hash_code
01168       _M_hash_code(const _Key& __k) const
01169       { return _M_h1()(__k); }
01170 
01171       std::size_t
01172       _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const
01173       { return _M_h2()(__c, __n); }
01174 
01175       std::size_t
01176       _M_bucket_index(const __node_type* __p, std::size_t __n) const
01177         noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
01178                   && noexcept(declval<const _H2&>()((__hash_code)0,
01179                                                     (std::size_t)0)) )
01180       { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
01181 
01182       void
01183       _M_store_code(__node_type*, __hash_code) const
01184       { }
01185 
01186       void
01187       _M_copy_code(__node_type*, const __node_type*) const
01188       { }
01189 
01190       void
01191       _M_swap(_Hash_code_base& __x)
01192       {
01193         std::swap(_M_extract(), __x._M_extract());
01194         std::swap(_M_h1(), __x._M_h1());
01195         std::swap(_M_h2(), __x._M_h2());
01196       }
01197 
01198       const _ExtractKey&
01199       _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
01200 
01201       _ExtractKey&
01202       _M_extract() { return __ebo_extract_key::_S_get(*this); }
01203 
01204       const _H1&
01205       _M_h1() const { return __ebo_h1::_S_cget(*this); }
01206 
01207       _H1&
01208       _M_h1() { return __ebo_h1::_S_get(*this); }
01209 
01210       const _H2&
01211       _M_h2() const { return __ebo_h2::_S_cget(*this); }
01212 
01213       _H2&
01214       _M_h2() { return __ebo_h2::_S_get(*this); }
01215     };
01216 
01217   /// Specialization: hash function and range-hashing function,
01218   /// caching hash codes.  H is provided but ignored.  Provides
01219   /// typedef and accessor required by C++ 11.
01220   template<typename _Key, typename _Value, typename _ExtractKey,
01221            typename _H1, typename _H2>
01222     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
01223                            _Default_ranged_hash, true>
01224     : private _Hashtable_ebo_helper<0, _ExtractKey>,
01225       private _Hashtable_ebo_helper<1, _H1>,
01226       private _Hashtable_ebo_helper<2, _H2>
01227     {
01228     private:
01229       // Gives the local iterator implementation access to _M_h2().
01230       friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
01231                                          _Default_ranged_hash, true>;
01232 
01233       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
01234       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
01235       using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
01236 
01237     public:
01238       typedef _H1                                       hasher;
01239 
01240       hasher
01241       hash_function() const
01242       { return _M_h1(); }
01243 
01244     protected:
01245       typedef std::size_t                               __hash_code;
01246       typedef _Hash_node<_Value, true>                  __node_type;
01247 
01248       // We need the default constructor for _Hashtable default constructor.
01249       _Hash_code_base() = default;
01250       _Hash_code_base(const _ExtractKey& __ex,
01251                       const _H1& __h1, const _H2& __h2,
01252                       const _Default_ranged_hash&)
01253       : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
01254 
01255       __hash_code
01256       _M_hash_code(const _Key& __k) const
01257       { return _M_h1()(__k); }
01258 
01259       std::size_t
01260       _M_bucket_index(const _Key&, __hash_code __c,
01261                       std::size_t __n) const
01262       { return _M_h2()(__c, __n); }
01263 
01264       std::size_t
01265       _M_bucket_index(const __node_type* __p, std::size_t __n) const
01266         noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
01267                                                  (std::size_t)0)) )
01268       { return _M_h2()(__p->_M_hash_code, __n); }
01269 
01270       void
01271       _M_store_code(__node_type* __n, __hash_code __c) const
01272       { __n->_M_hash_code = __c; }
01273 
01274       void
01275       _M_copy_code(__node_type* __to, const __node_type* __from) const
01276       { __to->_M_hash_code = __from->_M_hash_code; }
01277 
01278       void
01279       _M_swap(_Hash_code_base& __x)
01280       {
01281         std::swap(_M_extract(), __x._M_extract());
01282         std::swap(_M_h1(), __x._M_h1());
01283         std::swap(_M_h2(), __x._M_h2());
01284       }
01285 
01286       const _ExtractKey&
01287       _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
01288 
01289       _ExtractKey&
01290       _M_extract() { return __ebo_extract_key::_S_get(*this); }
01291 
01292       const _H1&
01293       _M_h1() const { return __ebo_h1::_S_cget(*this); }
01294 
01295       _H1&
01296       _M_h1() { return __ebo_h1::_S_get(*this); }
01297 
01298       const _H2&
01299       _M_h2() const { return __ebo_h2::_S_cget(*this); }
01300 
01301       _H2&
01302       _M_h2() { return __ebo_h2::_S_get(*this); }
01303     };
01304 
01305   /**
01306    *  Primary class template _Equal_helper.
01307    *
01308    */
01309   template <typename _Key, typename _Value, typename _ExtractKey,
01310             typename _Equal, typename _HashCodeType,
01311             bool __cache_hash_code>
01312   struct _Equal_helper;
01313 
01314   /// Specialization.
01315   template<typename _Key, typename _Value, typename _ExtractKey,
01316            typename _Equal, typename _HashCodeType>
01317   struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
01318   {
01319     static bool
01320     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
01321               const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n)
01322     { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
01323   };
01324 
01325   /// Specialization.
01326   template<typename _Key, typename _Value, typename _ExtractKey,
01327            typename _Equal, typename _HashCodeType>
01328   struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
01329   {
01330     static bool
01331     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
01332               const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n)
01333     { return __eq(__k, __extract(__n->_M_v())); }
01334   };
01335 
01336 
01337   /// Partial specialization used when nodes contain a cached hash code.
01338   template<typename _Key, typename _Value, typename _ExtractKey,
01339            typename _H1, typename _H2, typename _Hash>
01340     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
01341                                 _H1, _H2, _Hash, true>
01342     : private _Hashtable_ebo_helper<0, _H2>
01343     {
01344     protected:
01345       using __base_type = _Hashtable_ebo_helper<0, _H2>;
01346       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
01347                                                _H1, _H2, _Hash, true>;
01348 
01349       _Local_iterator_base() = default;
01350       _Local_iterator_base(const __hash_code_base& __base,
01351                            _Hash_node<_Value, true>* __p,
01352                            std::size_t __bkt, std::size_t __bkt_count)
01353       : __base_type(__base._M_h2()),
01354         _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
01355 
01356       void
01357       _M_incr()
01358       {
01359         _M_cur = _M_cur->_M_next();
01360         if (_M_cur)
01361           {
01362             std::size_t __bkt
01363               = __base_type::_S_get(*this)(_M_cur->_M_hash_code,
01364                                            _M_bucket_count);
01365             if (__bkt != _M_bucket)
01366               _M_cur = nullptr;
01367           }
01368       }
01369 
01370       _Hash_node<_Value, true>*  _M_cur;
01371       std::size_t _M_bucket;
01372       std::size_t _M_bucket_count;
01373 
01374     public:
01375       const void*
01376       _M_curr() const { return _M_cur; }  // for equality ops
01377 
01378       std::size_t
01379       _M_get_bucket() const { return _M_bucket; }  // for debug mode
01380     };
01381 
01382   // Uninitialized storage for a _Hash_code_base.
01383   // This type is DefaultConstructible and Assignable even if the
01384   // _Hash_code_base type isn't, so that _Local_iterator_base<..., false>
01385   // can be DefaultConstructible and Assignable.
01386   template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
01387     struct _Hash_code_storage
01388     {
01389       __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
01390 
01391       _Tp*
01392       _M_h() { return _M_storage._M_ptr(); }
01393 
01394       const _Tp*
01395       _M_h() const { return _M_storage._M_ptr(); }
01396     };
01397 
01398   // Empty partial specialization for empty _Hash_code_base types.
01399   template<typename _Tp>
01400     struct _Hash_code_storage<_Tp, true>
01401     {
01402       static_assert( std::is_empty<_Tp>::value, "Type must be empty" );
01403 
01404       // As _Tp is an empty type there will be no bytes written/read through
01405       // the cast pointer, so no strict-aliasing violation.
01406       _Tp*
01407       _M_h() { return reinterpret_cast<_Tp*>(this); }
01408 
01409       const _Tp*
01410       _M_h() const { return reinterpret_cast<const _Tp*>(this); }
01411     };
01412 
01413   template<typename _Key, typename _Value, typename _ExtractKey,
01414            typename _H1, typename _H2, typename _Hash>
01415     using __hash_code_for_local_iter
01416       = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
01417                                            _H1, _H2, _Hash, false>>;
01418 
01419   // Partial specialization used when hash codes are not cached
01420   template<typename _Key, typename _Value, typename _ExtractKey,
01421            typename _H1, typename _H2, typename _Hash>
01422     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
01423                                 _H1, _H2, _Hash, false>
01424     : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
01425     {
01426     protected:
01427       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
01428                                                _H1, _H2, _Hash, false>;
01429 
01430       _Local_iterator_base() : _M_bucket_count(-1) { }
01431 
01432       _Local_iterator_base(const __hash_code_base& __base,
01433                            _Hash_node<_Value, false>* __p,
01434                            std::size_t __bkt, std::size_t __bkt_count)
01435       : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
01436       { _M_init(__base); }
01437 
01438       ~_Local_iterator_base()
01439       {
01440         if (_M_bucket_count != -1)
01441           _M_destroy();
01442       }
01443 
01444       _Local_iterator_base(const _Local_iterator_base& __iter)
01445       : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
01446         _M_bucket_count(__iter._M_bucket_count)
01447       {
01448         if (_M_bucket_count != -1)
01449           _M_init(*__iter._M_h());
01450       }
01451 
01452       _Local_iterator_base&
01453       operator=(const _Local_iterator_base& __iter)
01454       {
01455         if (_M_bucket_count != -1)
01456           _M_destroy();
01457         _M_cur = __iter._M_cur;
01458         _M_bucket = __iter._M_bucket;
01459         _M_bucket_count = __iter._M_bucket_count;
01460         if (_M_bucket_count != -1)
01461           _M_init(*__iter._M_h());
01462         return *this;
01463       }
01464 
01465       void
01466       _M_incr()
01467       {
01468         _M_cur = _M_cur->_M_next();
01469         if (_M_cur)
01470           {
01471             std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
01472                                                               _M_bucket_count);
01473             if (__bkt != _M_bucket)
01474               _M_cur = nullptr;
01475           }
01476       }
01477 
01478       _Hash_node<_Value, false>*  _M_cur;
01479       std::size_t _M_bucket;
01480       std::size_t _M_bucket_count;
01481 
01482       void
01483       _M_init(const __hash_code_base& __base)
01484       { ::new(this->_M_h()) __hash_code_base(__base); }
01485 
01486       void
01487       _M_destroy() { this->_M_h()->~__hash_code_base(); }
01488 
01489     public:
01490       const void*
01491       _M_curr() const { return _M_cur; }  // for equality ops and debug mode
01492 
01493       std::size_t
01494       _M_get_bucket() const { return _M_bucket; }  // for debug mode
01495     };
01496 
01497   template<typename _Key, typename _Value, typename _ExtractKey,
01498            typename _H1, typename _H2, typename _Hash, bool __cache>
01499     inline bool
01500     operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
01501                                           _H1, _H2, _Hash, __cache>& __x,
01502                const _Local_iterator_base<_Key, _Value, _ExtractKey,
01503                                           _H1, _H2, _Hash, __cache>& __y)
01504     { return __x._M_curr() == __y._M_curr(); }
01505 
01506   template<typename _Key, typename _Value, typename _ExtractKey,
01507            typename _H1, typename _H2, typename _Hash, bool __cache>
01508     inline bool
01509     operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
01510                                           _H1, _H2, _Hash, __cache>& __x,
01511                const _Local_iterator_base<_Key, _Value, _ExtractKey,
01512                                           _H1, _H2, _Hash, __cache>& __y)
01513     { return __x._M_curr() != __y._M_curr(); }
01514 
01515   /// local iterators
01516   template<typename _Key, typename _Value, typename _ExtractKey,
01517            typename _H1, typename _H2, typename _Hash,
01518            bool __constant_iterators, bool __cache>
01519     struct _Local_iterator
01520     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
01521                                   _H1, _H2, _Hash, __cache>
01522     {
01523     private:
01524       using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
01525                                                _H1, _H2, _Hash, __cache>;
01526       using __hash_code_base = typename __base_type::__hash_code_base;
01527     public:
01528       typedef _Value                                    value_type;
01529       typedef typename std::conditional<__constant_iterators,
01530                                         const _Value*, _Value*>::type
01531                                                        pointer;
01532       typedef typename std::conditional<__constant_iterators,
01533                                         const _Value&, _Value&>::type
01534                                                        reference;
01535       typedef std::ptrdiff_t                            difference_type;
01536       typedef std::forward_iterator_tag                 iterator_category;
01537 
01538       _Local_iterator() = default;
01539 
01540       _Local_iterator(const __hash_code_base& __base,
01541                       _Hash_node<_Value, __cache>* __p,
01542                       std::size_t __bkt, std::size_t __bkt_count)
01543         : __base_type(__base, __p, __bkt, __bkt_count)
01544       { }
01545 
01546       reference
01547       operator*() const
01548       { return this->_M_cur->_M_v(); }
01549 
01550       pointer
01551       operator->() const
01552       { return this->_M_cur->_M_valptr(); }
01553 
01554       _Local_iterator&
01555       operator++()
01556       {
01557         this->_M_incr();
01558         return *this;
01559       }
01560 
01561       _Local_iterator
01562       operator++(int)
01563       {
01564         _Local_iterator __tmp(*this);
01565         this->_M_incr();
01566         return __tmp;
01567       }
01568     };
01569 
01570   /// local const_iterators
01571   template<typename _Key, typename _Value, typename _ExtractKey,
01572            typename _H1, typename _H2, typename _Hash,
01573            bool __constant_iterators, bool __cache>
01574     struct _Local_const_iterator
01575     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
01576                                   _H1, _H2, _Hash, __cache>
01577     {
01578     private:
01579       using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
01580                                                _H1, _H2, _Hash, __cache>;
01581       using __hash_code_base = typename __base_type::__hash_code_base;
01582 
01583     public:
01584       typedef _Value                                    value_type;
01585       typedef const _Value*                             pointer;
01586       typedef const _Value&                             reference;
01587       typedef std::ptrdiff_t                            difference_type;
01588       typedef std::forward_iterator_tag                 iterator_category;
01589 
01590       _Local_const_iterator() = default;
01591 
01592       _Local_const_iterator(const __hash_code_base& __base,
01593                             _Hash_node<_Value, __cache>* __p,
01594                             std::size_t __bkt, std::size_t __bkt_count)
01595         : __base_type(__base, __p, __bkt, __bkt_count)
01596       { }
01597 
01598       _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
01599                                                   _H1, _H2, _Hash,
01600                                                   __constant_iterators,
01601                                                   __cache>& __x)
01602         : __base_type(__x)
01603       { }
01604 
01605       reference
01606       operator*() const
01607       { return this->_M_cur->_M_v(); }
01608 
01609       pointer
01610       operator->() const
01611       { return this->_M_cur->_M_valptr(); }
01612 
01613       _Local_const_iterator&
01614       operator++()
01615       {
01616         this->_M_incr();
01617         return *this;
01618       }
01619 
01620       _Local_const_iterator
01621       operator++(int)
01622       {
01623         _Local_const_iterator __tmp(*this);
01624         this->_M_incr();
01625         return __tmp;
01626       }
01627     };
01628 
01629   /**
01630    *  Primary class template _Hashtable_base.
01631    *
01632    *  Helper class adding management of _Equal functor to
01633    *  _Hash_code_base type.
01634    *
01635    *  Base class templates are:
01636    *    - __detail::_Hash_code_base
01637    *    - __detail::_Hashtable_ebo_helper
01638    */
01639   template<typename _Key, typename _Value,
01640            typename _ExtractKey, typename _Equal,
01641            typename _H1, typename _H2, typename _Hash, typename _Traits>
01642   struct _Hashtable_base
01643   : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
01644                            _Traits::__hash_cached::value>,
01645     private _Hashtable_ebo_helper<0, _Equal>
01646   {
01647   public:
01648     typedef _Key                                        key_type;
01649     typedef _Value                                      value_type;
01650     typedef _Equal                                      key_equal;
01651     typedef std::size_t                                 size_type;
01652     typedef std::ptrdiff_t                              difference_type;
01653 
01654     using __traits_type = _Traits;
01655     using __hash_cached = typename __traits_type::__hash_cached;
01656     using __constant_iterators = typename __traits_type::__constant_iterators;
01657     using __unique_keys = typename __traits_type::__unique_keys;
01658 
01659     using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
01660                                              _H1, _H2, _Hash,
01661                                              __hash_cached::value>;
01662 
01663     using __hash_code = typename __hash_code_base::__hash_code;
01664     using __node_type = typename __hash_code_base::__node_type;
01665 
01666     using iterator = __detail::_Node_iterator<value_type,
01667                                               __constant_iterators::value,
01668                                               __hash_cached::value>;
01669 
01670     using const_iterator = __detail::_Node_const_iterator<value_type,
01671                                                    __constant_iterators::value,
01672                                                    __hash_cached::value>;
01673 
01674     using local_iterator = __detail::_Local_iterator<key_type, value_type,
01675                                                   _ExtractKey, _H1, _H2, _Hash,
01676                                                   __constant_iterators::value,
01677                                                      __hash_cached::value>;
01678 
01679     using const_local_iterator = __detail::_Local_const_iterator<key_type,
01680                                                                  value_type,
01681                                         _ExtractKey, _H1, _H2, _Hash,
01682                                         __constant_iterators::value,
01683                                         __hash_cached::value>;
01684 
01685     using __ireturn_type = typename std::conditional<__unique_keys::value,
01686                                                      std::pair<iterator, bool>,
01687                                                      iterator>::type;
01688   private:
01689     using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>;
01690     using _EqualHelper =  _Equal_helper<_Key, _Value, _ExtractKey, _Equal,
01691                                         __hash_code, __hash_cached::value>;
01692 
01693   protected:
01694     _Hashtable_base() = default;
01695     _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2,
01696                     const _Hash& __hash, const _Equal& __eq)
01697     : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
01698     { }
01699 
01700     bool
01701     _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const
01702     {
01703       return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
01704                                      __k, __c, __n);
01705     }
01706 
01707     void
01708     _M_swap(_Hashtable_base& __x)
01709     {
01710       __hash_code_base::_M_swap(__x);
01711       std::swap(_M_eq(), __x._M_eq());
01712     }
01713 
01714     const _Equal&
01715     _M_eq() const { return _EqualEBO::_S_cget(*this); }
01716 
01717     _Equal&
01718     _M_eq() { return _EqualEBO::_S_get(*this); }
01719   };
01720 
01721   /**
01722    *  struct _Equality_base.
01723    *
01724    *  Common types and functions for class _Equality.
01725    */
01726   struct _Equality_base
01727   {
01728   protected:
01729     template<typename _Uiterator>
01730       static bool
01731       _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
01732   };
01733 
01734   // See std::is_permutation in N3068.
01735   template<typename _Uiterator>
01736     bool
01737     _Equality_base::
01738     _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
01739                       _Uiterator __first2)
01740     {
01741       for (; __first1 != __last1; ++__first1, ++__first2)
01742         if (!(*__first1 == *__first2))
01743           break;
01744 
01745       if (__first1 == __last1)
01746         return true;
01747 
01748       _Uiterator __last2 = __first2;
01749       std::advance(__last2, std::distance(__first1, __last1));
01750 
01751       for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
01752         {
01753           _Uiterator __tmp =  __first1;
01754           while (__tmp != __it1 && !bool(*__tmp == *__it1))
01755             ++__tmp;
01756 
01757           // We've seen this one before.
01758           if (__tmp != __it1)
01759             continue;
01760 
01761           std::ptrdiff_t __n2 = 0;
01762           for (__tmp = __first2; __tmp != __last2; ++__tmp)
01763             if (*__tmp == *__it1)
01764               ++__n2;
01765 
01766           if (!__n2)
01767             return false;
01768 
01769           std::ptrdiff_t __n1 = 0;
01770           for (__tmp = __it1; __tmp != __last1; ++__tmp)
01771             if (*__tmp == *__it1)
01772               ++__n1;
01773 
01774           if (__n1 != __n2)
01775             return false;
01776         }
01777       return true;
01778     }
01779 
01780   /**
01781    *  Primary class template  _Equality.
01782    *
01783    *  This is for implementing equality comparison for unordered
01784    *  containers, per N3068, by John Lakos and Pablo Halpern.
01785    *  Algorithmically, we follow closely the reference implementations
01786    *  therein.
01787    */
01788   template<typename _Key, typename _Value, typename _Alloc,
01789            typename _ExtractKey, typename _Equal,
01790            typename _H1, typename _H2, typename _Hash,
01791            typename _RehashPolicy, typename _Traits,
01792            bool _Unique_keys = _Traits::__unique_keys::value>
01793     struct _Equality;
01794 
01795   /// Specialization.
01796   template<typename _Key, typename _Value, typename _Alloc,
01797            typename _ExtractKey, typename _Equal,
01798            typename _H1, typename _H2, typename _Hash,
01799            typename _RehashPolicy, typename _Traits>
01800     struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01801                      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
01802     {
01803       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01804                                      _H1, _H2, _Hash, _RehashPolicy, _Traits>;
01805 
01806       bool
01807       _M_equal(const __hashtable&) const;
01808     };
01809 
01810   template<typename _Key, typename _Value, typename _Alloc,
01811            typename _ExtractKey, typename _Equal,
01812            typename _H1, typename _H2, typename _Hash,
01813            typename _RehashPolicy, typename _Traits>
01814     bool
01815     _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01816               _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
01817     _M_equal(const __hashtable& __other) const
01818     {
01819       const __hashtable* __this = static_cast<const __hashtable*>(this);
01820 
01821       if (__this->size() != __other.size())
01822         return false;
01823 
01824       for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
01825         {
01826           const auto __ity = __other.find(_ExtractKey()(*__itx));
01827           if (__ity == __other.end() || !bool(*__ity == *__itx))
01828             return false;
01829         }
01830       return true;
01831     }
01832 
01833   /// Specialization.
01834   template<typename _Key, typename _Value, typename _Alloc,
01835            typename _ExtractKey, typename _Equal,
01836            typename _H1, typename _H2, typename _Hash,
01837            typename _RehashPolicy, typename _Traits>
01838     struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01839                      _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
01840     : public _Equality_base
01841     {
01842       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01843                                      _H1, _H2, _Hash, _RehashPolicy, _Traits>;
01844 
01845       bool
01846       _M_equal(const __hashtable&) const;
01847     };
01848 
01849   template<typename _Key, typename _Value, typename _Alloc,
01850            typename _ExtractKey, typename _Equal,
01851            typename _H1, typename _H2, typename _Hash,
01852            typename _RehashPolicy, typename _Traits>
01853     bool
01854     _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01855               _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
01856     _M_equal(const __hashtable& __other) const
01857     {
01858       const __hashtable* __this = static_cast<const __hashtable*>(this);
01859 
01860       if (__this->size() != __other.size())
01861         return false;
01862 
01863       for (auto __itx = __this->begin(); __itx != __this->end();)
01864         {
01865           const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
01866           const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
01867 
01868           if (std::distance(__xrange.first, __xrange.second)
01869               != std::distance(__yrange.first, __yrange.second))
01870             return false;
01871 
01872           if (!_S_is_permutation(__xrange.first, __xrange.second,
01873                                  __yrange.first))
01874             return false;
01875 
01876           __itx = __xrange.second;
01877         }
01878       return true;
01879     }
01880 
01881   /**
01882    * This type deals with all allocation and keeps an allocator instance through
01883    * inheritance to benefit from EBO when possible.
01884    */
01885   template<typename _NodeAlloc>
01886     struct _Hashtable_alloc : private _Hashtable_ebo_helper<0, _NodeAlloc>
01887     {
01888     private:
01889       using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>;
01890     public:
01891       using __node_type = typename _NodeAlloc::value_type;
01892       using __node_alloc_type = _NodeAlloc;
01893       // Use __gnu_cxx to benefit from _S_always_equal and al.
01894       using __node_alloc_traits = __gnu_cxx::__alloc_traits<__node_alloc_type>;
01895 
01896       using __value_type = typename __node_type::value_type;
01897       using __value_alloc_type =
01898         __alloc_rebind<__node_alloc_type, __value_type>;
01899       using __value_alloc_traits = std::allocator_traits<__value_alloc_type>;
01900 
01901       using __node_base = __detail::_Hash_node_base;
01902       using __bucket_type = __node_base*;      
01903       using __bucket_alloc_type =
01904         __alloc_rebind<__node_alloc_type, __bucket_type>;
01905       using __bucket_alloc_traits = std::allocator_traits<__bucket_alloc_type>;
01906 
01907       _Hashtable_alloc() = default;
01908       _Hashtable_alloc(const _Hashtable_alloc&) = default;
01909       _Hashtable_alloc(_Hashtable_alloc&&) = default;
01910 
01911       template<typename _Alloc>
01912         _Hashtable_alloc(_Alloc&& __a)
01913           : __ebo_node_alloc(std::forward<_Alloc>(__a))
01914         { }
01915 
01916       __node_alloc_type&
01917       _M_node_allocator()
01918       { return __ebo_node_alloc::_S_get(*this); }
01919 
01920       const __node_alloc_type&
01921       _M_node_allocator() const
01922       { return __ebo_node_alloc::_S_cget(*this); }
01923 
01924       template<typename... _Args>
01925         __node_type*
01926         _M_allocate_node(_Args&&... __args);
01927 
01928       void
01929       _M_deallocate_node(__node_type* __n);
01930 
01931       // Deallocate the linked list of nodes pointed to by __n
01932       void
01933       _M_deallocate_nodes(__node_type* __n);
01934 
01935       __bucket_type*
01936       _M_allocate_buckets(std::size_t __n);
01937 
01938       void
01939       _M_deallocate_buckets(__bucket_type*, std::size_t __n);
01940     };
01941 
01942   // Definitions of class template _Hashtable_alloc's out-of-line member
01943   // functions.
01944   template<typename _NodeAlloc>
01945     template<typename... _Args>
01946       typename _Hashtable_alloc<_NodeAlloc>::__node_type*
01947       _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
01948       {
01949         auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
01950         __node_type* __n = std::__addressof(*__nptr);
01951         __try
01952           {
01953             __value_alloc_type __a(_M_node_allocator());
01954             ::new ((void*)__n) __node_type;
01955             __value_alloc_traits::construct(__a, __n->_M_valptr(),
01956                                             std::forward<_Args>(__args)...);
01957             return __n;
01958           }
01959         __catch(...)
01960           {
01961             __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
01962             __throw_exception_again;
01963           }
01964       }
01965 
01966   template<typename _NodeAlloc>
01967     void
01968     _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
01969     {
01970       typedef typename __node_alloc_traits::pointer _Ptr;
01971       auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n);
01972       __value_alloc_type __a(_M_node_allocator());
01973       __value_alloc_traits::destroy(__a, __n->_M_valptr());
01974       __n->~__node_type();
01975       __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
01976     }
01977 
01978   template<typename _NodeAlloc>
01979     void
01980     _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n)
01981     {
01982       while (__n)
01983         {
01984           __node_type* __tmp = __n;
01985           __n = __n->_M_next();
01986           _M_deallocate_node(__tmp);
01987         }
01988     }
01989 
01990   template<typename _NodeAlloc>
01991     typename _Hashtable_alloc<_NodeAlloc>::__bucket_type*
01992     _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __n)
01993     {
01994       __bucket_alloc_type __alloc(_M_node_allocator());
01995 
01996       auto __ptr = __bucket_alloc_traits::allocate(__alloc, __n);
01997       __bucket_type* __p = std::__addressof(*__ptr);
01998       __builtin_memset(__p, 0, __n * sizeof(__bucket_type));
01999       return __p;
02000     }
02001 
02002   template<typename _NodeAlloc>
02003     void
02004     _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts,
02005                                                         std::size_t __n)
02006     {
02007       typedef typename __bucket_alloc_traits::pointer _Ptr;
02008       auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
02009       __bucket_alloc_type __alloc(_M_node_allocator());
02010       __bucket_alloc_traits::deallocate(__alloc, __ptr, __n);
02011     }
02012 
02013  //@} hashtable-detail
02014 _GLIBCXX_END_NAMESPACE_VERSION
02015 } // namespace __detail
02016 } // namespace std
02017 
02018 #endif // _HASHTABLE_POLICY_H