libstdc++-v3/include/bits/hashtable.h

   1 // hashtable.h header -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file bits/hashtable.h
  26  *  This is an internal header file, included by other library headers.
  27  *  You should not attempt to use it directly.
  28  */
  29
  30 #ifndef _HASHTABLE_H
  31 #define _HASHTABLE_H 1
  32
  33 #pragma GCC system_header
  34
  35 #include <bits/hashtable_policy.h>
  36
  37 namespace std
  38 {
  39   // Class template _Hashtable, class definition.
  40
  41   // Meaning of class template _Hashtable's template parameters
  42
  43   // _Key and _Value: arbitrary CopyConstructible types.
  44
  45   // _Allocator: an allocator type ([lib.allocator.requirements]) whose
  46   // value type is Value.  As a conforming extension, we allow for
  47   // value type != Value.
  48
  49   // _ExtractKey: function object that takes a object of type Value
  50   // and returns a value of type _Key.
  51
  52   // _Equal: function object that takes two objects of type k and returns
  53   // a bool-like value that is true if the two objects are considered equal.
  54
  55   // _H1: the hash function.  A unary function object with argument type
  56   // Key and result type size_t.  Return values should be distributed
  57   // over the entire range [0, numeric_limits<size_t>:::max()].
  58
  59   // _H2: the range-hashing function (in the terminology of Tavori and
  60   // Dreizin).  A binary function object whose argument types and result
  61   // type are all size_t.  Given arguments r and N, the return value is
  62   // in the range [0, N).
  63
  64   // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
  65   // whose argument types are _Key and size_t and whose result type is
  66   // size_t.  Given arguments k and N, the return value is in the range
  67   // [0, N).  Default: hash(k, N) = h2(h1(k), N).  If _Hash is anything other
  68   // than the default, _H1 and _H2 are ignored.
  69
  70   // _RehashPolicy: Policy class with three members, all of which govern
  71   // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
  72   // than n.  _M_bkt_for_elements(n) returns a bucket count appropriate
  73   // for an element count of n.  _M_need_rehash(n_bkt, n_elt, n_ins)
  74   // determines whether, if the current bucket count is n_bkt and the
  75   // current element count is n_elt, we need to increase the bucket
  76   // count.  If so, returns make_pair(true, n), where n is the new
  77   // bucket count.  If not, returns make_pair(false, <anything>).
  78
  79   // ??? Right now it is hard-wired that the number of buckets never
  80   // shrinks.  Should we allow _RehashPolicy to change that?
  81
  82   // __cache_hash_code: bool.  true if we store the value of the hash
  83   // function along with the value.  This is a time-space tradeoff.
  84   // Storing it may improve lookup speed by reducing the number of times
  85   // we need to call the Equal function.
  86
  87   // __constant_iterators: bool.  true if iterator and const_iterator are
  88   // both constant iterator types.  This is true for unordered_set and
  89   // unordered_multiset, false for unordered_map and unordered_multimap.
  90
  91   // __unique_keys: bool.  true if the return value of _Hashtable::count(k)
  92   // is always at most one, false if it may be an arbitrary number.  This
  93   // true for unordered_set and unordered_map, false for unordered_multiset
  94   // and unordered_multimap.
  95
  96   template<typename _Key, typename _Value, typename _Allocator,
  97            typename _ExtractKey, typename _Equal,
  98            typename _H1, typename _H2, typename _Hash,
  99            typename _RehashPolicy,
 100            bool __cache_hash_code,
 101            bool __constant_iterators,
 102            bool __unique_keys>
 103     class _Hashtable
 104     : public __detail::_Rehash_base<_RehashPolicy,
 105                                     _Hashtable<_Key, _Value, _Allocator,
 106                                                _ExtractKey,
 107                                                _Equal, _H1, _H2, _Hash,
 108                                                _RehashPolicy,
 109                                                __cache_hash_code,
 110                                                __constant_iterators,
 111                                                __unique_keys> >,
 112       public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 113                                        _H1, _H2, _Hash, __cache_hash_code>,
 114       public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
 115                                  _Hashtable<_Key, _Value, _Allocator,
 116                                             _ExtractKey,
 117                                             _Equal, _H1, _H2, _Hash,
 118                                             _RehashPolicy,
 119                                             __cache_hash_code,
 120                                             __constant_iterators,
 121                                             __unique_keys> >,
 122       public __detail::_Equality_base<_ExtractKey, __unique_keys,
 123                                       _Hashtable<_Key, _Value, _Allocator,
 124                                                  _ExtractKey,
 125                                                  _Equal, _H1, _H2, _Hash,
 126                                                  _RehashPolicy,
 127                                                  __cache_hash_code,
 128                                                  __constant_iterators,
 129                                                  __unique_keys> >
 130     {
 131     public:
 132       typedef _Allocator                                  allocator_type;
 133       typedef _Value                                      value_type;
 134       typedef _Key                                        key_type;
 135       typedef _Equal                                      key_equal;
 136       // mapped_type, if present, comes from _Map_base.
 137       // hasher, if present, comes from _Hash_code_base.
 138       typedef typename _Allocator::pointer                pointer;
 139       typedef typename _Allocator::const_pointer          const_pointer;
 140       typedef typename _Allocator::reference              reference;
 141       typedef typename _Allocator::const_reference        const_reference;
 142
 143       typedef std::size_t                                 size_type;
 144       typedef std::ptrdiff_t                              difference_type;
 145       typedef __detail::_Node_iterator<value_type, __constant_iterators,
 146                                        __cache_hash_code>
 147                                                           local_iterator;
 148       typedef __detail::_Node_const_iterator<value_type,
 149                                              __constant_iterators,
 150                                              __cache_hash_code>
 151                                                           const_local_iterator;
 152
 153       typedef __detail::_Hashtable_iterator<value_type, __constant_iterators,
 154                                             __cache_hash_code>
 155                                                           iterator;
 156       typedef __detail::_Hashtable_const_iterator<value_type,
 157                                                   __constant_iterators,
 158                                                   __cache_hash_code>
 159                                                           const_iterator;
 160
 161       template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
 162                typename _Hashtable2>
 163         friend struct __detail::_Map_base;
 164
 165     private:
 166       typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
 167       typedef typename _Allocator::template rebind<_Node>::other
 168                                                         _Node_allocator_type;
 169       typedef typename _Allocator::template rebind<_Node*>::other
 170                                                         _Bucket_allocator_type;
 171
 172       typedef typename _Allocator::template rebind<_Value>::other
 173                                                         _Value_allocator_type;
 174
 175       _Node_allocator_type   _M_node_allocator;
 176       _Node**                _M_buckets;
 177       size_type              _M_bucket_count;
 178       size_type              _M_begin_bucket_index; // First non-empty bucket.
 179       size_type              _M_element_count;
 180       _RehashPolicy          _M_rehash_policy;
 181
 182       template<typename... _Args>
 183         _Node*
 184         _M_allocate_node(_Args&&... __args);
 185
 186       void
 187       _M_deallocate_node(_Node* __n);
 188
 189       void
 190       _M_deallocate_nodes(_Node**, size_type);
 191
 192       _Node**
 193       _M_allocate_buckets(size_type __n);
 194
 195       void
 196       _M_deallocate_buckets(_Node**, size_type __n);
 197
 198     public:
 199       // Constructor, destructor, assignment, swap
 200       _Hashtable(size_type __bucket_hint,
 201                  const _H1&, const _H2&, const _Hash&,
 202                  const _Equal&, const _ExtractKey&,
 203                  const allocator_type&);
 204
 205       template<typename _InputIterator>
 206         _Hashtable(_InputIterator __first, _InputIterator __last,
 207                    size_type __bucket_hint,
 208                    const _H1&, const _H2&, const _Hash&,
 209                    const _Equal&, const _ExtractKey&,
 210                    const allocator_type&);
 211
 212       _Hashtable(const _Hashtable&);
 213
 214       _Hashtable(_Hashtable&&);
 215
 216       _Hashtable&
 217       operator=(const _Hashtable& __ht)
 218       {
 219         _Hashtable __tmp(__ht);
 220         this->swap(__tmp);
 221         return *this;
 222       }
 223
 224       _Hashtable&
 225       operator=(_Hashtable&& __ht)
 226       {
 227         // NB: DR 1204.
 228         // NB: DR 675.
 229         this->clear();
 230         this->swap(__ht);
 231         return *this;
 232       }
 233
 234       ~_Hashtable();
 235
 236       void swap(_Hashtable&);
 237
 238       // Basic container operations
 239       iterator
 240       begin()
 241       { return iterator(_M_buckets + _M_begin_bucket_index); }
 242
 243       const_iterator
 244       begin() const
 245       { return const_iterator(_M_buckets + _M_begin_bucket_index); }
 246
 247       iterator
 248       end()
 249       { return iterator(_M_buckets + _M_bucket_count); }
 250
 251       const_iterator
 252       end() const
 253       { return const_iterator(_M_buckets + _M_bucket_count); }
 254
 255       const_iterator
 256       cbegin() const
 257       { return const_iterator(_M_buckets + _M_begin_bucket_index); }
 258
 259       const_iterator
 260       cend() const
 261       { return const_iterator(_M_buckets + _M_bucket_count); }
 262
 263       size_type
 264       size() const
 265       { return _M_element_count; }
 266
 267       bool
 268       empty() const
 269       { return size() == 0; }
 270
 271       allocator_type
 272       get_allocator() const
 273       { return allocator_type(_M_node_allocator); }
 274
 275       size_type
 276       max_size() const
 277       { return _M_node_allocator.max_size(); }
 278
 279       // Observers
 280       key_equal
 281       key_eq() const
 282       { return this->_M_eq; }
 283
 284       // hash_function, if present, comes from _Hash_code_base.
 285
 286       // Bucket operations
 287       size_type
 288       bucket_count() const
 289       { return _M_bucket_count; }
 290
 291       size_type
 292       max_bucket_count() const
 293       { return max_size(); }
 294
 295       size_type
 296       bucket_size(size_type __n) const
 297       { return std::distance(begin(__n), end(__n)); }
 298
 299       size_type
 300       bucket(const key_type& __k) const
 301       {
 302         return this->_M_bucket_index(__k, this->_M_hash_code(__k),
 303                                      bucket_count());
 304       }
 305
 306       local_iterator
 307       begin(size_type __n)
 308       { return local_iterator(_M_buckets[__n]); }
 309
 310       local_iterator
 311       end(size_type)
 312       { return local_iterator(0); }
 313
 314       const_local_iterator
 315       begin(size_type __n) const
 316       { return const_local_iterator(_M_buckets[__n]); }
 317
 318       const_local_iterator
 319       end(size_type) const
 320       { return const_local_iterator(0); }
 321
 322       // DR 691.
 323       const_local_iterator
 324       cbegin(size_type __n) const
 325       { return const_local_iterator(_M_buckets[__n]); }
 326
 327       const_local_iterator
 328       cend(size_type) const
 329       { return const_local_iterator(0); }
 330
 331       float
 332       load_factor() const
 333       {
 334         return static_cast<float>(size()) / static_cast<float>(bucket_count());
 335       }
 336
 337       // max_load_factor, if present, comes from _Rehash_base.
 338
 339       // Generalization of max_load_factor.  Extension, not found in TR1.  Only
 340       // useful if _RehashPolicy is something other than the default.
 341       const _RehashPolicy&
 342       __rehash_policy() const
 343       { return _M_rehash_policy; }
 344
 345       void
 346       __rehash_policy(const _RehashPolicy&);
 347
 348       // Lookup.
 349       iterator
 350       find(const key_type& __k);
 351
 352       const_iterator
 353       find(const key_type& __k) const;
 354
 355       size_type
 356       count(const key_type& __k) const;
 357
 358       std::pair<iterator, iterator>
 359       equal_range(const key_type& __k);
 360
 361       std::pair<const_iterator, const_iterator>
 362       equal_range(const key_type& __k) const;
 363
 364     private:
 365       // Find and insert helper functions and types
 366       _Node*
 367       _M_find_node(_Node*, const key_type&,
 368                    typename _Hashtable::_Hash_code_type) const;
 369
 370       template<typename _Pair>
 371         iterator
 372         _M_insert_bucket(_Pair&&, size_type,
 373                          typename _Hashtable::_Hash_code_type);
 374
 375       template<typename _Pair>
 376         std::pair<iterator, bool>
 377         _M_insert(_Pair&&, std::true_type);
 378
 379       template<typename _Pair>
 380         iterator
 381         _M_insert(_Pair&&, std::false_type);
 382
 383       typedef typename std::conditional<__unique_keys,
 384                                         std::pair<iterator, bool>,
 385                                         iterator>::type
 386         _Insert_Return_Type;
 387
 388       typedef typename std::conditional<__unique_keys,
 389                                         std::_Select1st<_Insert_Return_Type>,
 390                                         std::_Identity<_Insert_Return_Type>
 391                                    >::type
 392         _Insert_Conv_Type;
 393
 394     public:
 395       // Insert and erase
 396       _Insert_Return_Type
 397       insert(const value_type& __v)
 398       { return _M_insert(__v, std::integral_constant<bool, __unique_keys>()); }
 399
 400       iterator
 401       insert(const_iterator, const value_type& __v)
 402       { return _Insert_Conv_Type()(insert(__v)); }
 403
 404       _Insert_Return_Type
 405       insert(value_type&& __v)
 406       { return _M_insert(std::move(__v),
 407                          std::integral_constant<bool, __unique_keys>()); }
 408
 409       iterator
 410       insert(const_iterator, value_type&& __v)
 411       { return _Insert_Conv_Type()(insert(std::move(__v))); }
 412
 413       template<typename _Pair, typename = typename
 414                std::enable_if<!__constant_iterators
 415                               && std::is_convertible<_Pair,
 416                                                      value_type>::value>::type>
 417         _Insert_Return_Type
 418         insert(_Pair&& __v)
 419         { return _M_insert(std::forward<_Pair>(__v),
 420                            std::integral_constant<bool, __unique_keys>()); }
 421
 422       template<typename _Pair, typename = typename
 423                std::enable_if<!__constant_iterators
 424                               && std::is_convertible<_Pair,
 425                                                      value_type>::value>::type>
 426         iterator
 427         insert(const_iterator, _Pair&& __v)
 428         { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
 429
 430       template<typename _InputIterator>
 431         void
 432         insert(_InputIterator __first, _InputIterator __last);
 433
 434       void
 435       insert(initializer_list<value_type> __l)
 436       { this->insert(__l.begin(), __l.end()); }
 437
 438       iterator
 439       erase(const_iterator);
 440
 441       size_type
 442       erase(const key_type&);
 443
 444       iterator
 445       erase(const_iterator, const_iterator);
 446
 447       void
 448       clear();
 449
 450       // Set number of buckets to be appropriate for container of n element.
 451       void rehash(size_type __n);
 452
 453       // DR 1189.
 454       // reserve, if present, comes from _Rehash_base.
 455
 456     private:
 457       // Unconditionally change size of bucket array to n.
 458       void _M_rehash(size_type __n);
 459     };
 460
 461
 462   // Definitions of class template _Hashtable's out-of-line member functions.
 463   template<typename _Key, typename _Value,
 464            typename _Allocator, typename _ExtractKey, typename _Equal,
 465            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 466            bool __chc, bool __cit, bool __uk>
 467     template<typename... _Args>
 468       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 469                           _H1, _H2, _Hash, _RehashPolicy,
 470                           __chc, __cit, __uk>::_Node*
 471       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 472                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 473       _M_allocate_node(_Args&&... __args)
 474       {
 475         _Node* __n = _M_node_allocator.allocate(1);
 476         __try
 477           {
 478             _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
 479             __n->_M_next = 0;
 480             return __n;
 481           }
 482         __catch(...)
 483           {
 484             _M_node_allocator.deallocate(__n, 1);
 485             __throw_exception_again;
 486           }
 487       }
 488
 489   template<typename _Key, typename _Value,
 490            typename _Allocator, typename _ExtractKey, typename _Equal,
 491            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 492            bool __chc, bool __cit, bool __uk>
 493     void
 494     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 495                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 496     _M_deallocate_node(_Node* __n)
 497     {
 498       _M_node_allocator.destroy(__n);
 499       _M_node_allocator.deallocate(__n, 1);
 500     }
 501
 502   template<typename _Key, typename _Value,
 503            typename _Allocator, typename _ExtractKey, typename _Equal,
 504            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 505            bool __chc, bool __cit, bool __uk>
 506     void
 507     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 508                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 509     _M_deallocate_nodes(_Node** __array, size_type __n)
 510     {
 511       for (size_type __i = 0; __i < __n; ++__i)
 512         {
 513           _Node* __p = __array[__i];
 514           while (__p)
 515             {
 516               _Node* __tmp = __p;
 517               __p = __p->_M_next;
 518               _M_deallocate_node(__tmp);
 519             }
 520           __array[__i] = 0;
 521         }
 522     }
 523
 524   template<typename _Key, typename _Value,
 525            typename _Allocator, typename _ExtractKey, typename _Equal,
 526            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 527            bool __chc, bool __cit, bool __uk>
 528     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 529                         _H1, _H2, _Hash, _RehashPolicy,
 530                         __chc, __cit, __uk>::_Node**
 531     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 532                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 533     _M_allocate_buckets(size_type __n)
 534     {
 535       _Bucket_allocator_type __alloc(_M_node_allocator);
 536
 537       // We allocate one extra bucket to hold a sentinel, an arbitrary
 538       // non-null pointer.  Iterator increment relies on this.
 539       _Node** __p = __alloc.allocate(__n + 1);
 540       std::fill(__p, __p + __n, (_Node*) 0);
 541       __p[__n] = reinterpret_cast<_Node*>(0x1000);
 542       return __p;
 543     }
 544
 545   template<typename _Key, typename _Value,
 546            typename _Allocator, typename _ExtractKey, typename _Equal,
 547            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 548            bool __chc, bool __cit, bool __uk>
 549     void
 550     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 551                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 552     _M_deallocate_buckets(_Node** __p, size_type __n)
 553     {
 554       _Bucket_allocator_type __alloc(_M_node_allocator);
 555       __alloc.deallocate(__p, __n + 1);
 556     }
 557
 558   template<typename _Key, typename _Value,
 559            typename _Allocator, typename _ExtractKey, typename _Equal,
 560            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 561            bool __chc, bool __cit, bool __uk>
 562     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 563                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 564     _Hashtable(size_type __bucket_hint,
 565                const _H1& __h1, const _H2& __h2, const _Hash& __h,
 566                const _Equal& __eq, const _ExtractKey& __exk,
 567                const allocator_type& __a)
 568     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
 569       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 570                                 _H1, _H2, _Hash, __chc>(__exk, __eq,
 571                                                         __h1, __h2, __h),
 572       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
 573       _M_node_allocator(__a),
 574       _M_bucket_count(0),
 575       _M_element_count(0),
 576       _M_rehash_policy()
 577     {
 578       _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
 579       _M_buckets = _M_allocate_buckets(_M_bucket_count);
 580       _M_begin_bucket_index = _M_bucket_count;
 581     }
 582
 583   template<typename _Key, typename _Value,
 584            typename _Allocator, typename _ExtractKey, typename _Equal,
 585            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 586            bool __chc, bool __cit, bool __uk>
 587     template<typename _InputIterator>
 588       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 589                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 590       _Hashtable(_InputIterator __f, _InputIterator __l,
 591                  size_type __bucket_hint,
 592                  const _H1& __h1, const _H2& __h2, const _Hash& __h,
 593                  const _Equal& __eq, const _ExtractKey& __exk,
 594                  const allocator_type& __a)
 595       : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
 596         __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 597                                   _H1, _H2, _Hash, __chc>(__exk, __eq,
 598                                                           __h1, __h2, __h),
 599         __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
 600         _M_node_allocator(__a),
 601         _M_bucket_count(0),
 602         _M_element_count(0),
 603         _M_rehash_policy()
 604       {
 605         _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
 606                                    _M_rehash_policy.
 607                                    _M_bkt_for_elements(__detail::
 608                                                        __distance_fw(__f,
 609                                                                      __l)));
 610         _M_buckets = _M_allocate_buckets(_M_bucket_count);
 611         _M_begin_bucket_index = _M_bucket_count;
 612         __try
 613           {
 614             for (; __f != __l; ++__f)
 615               this->insert(*__f);
 616           }
 617         __catch(...)
 618           {
 619             clear();
 620             _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 621             __throw_exception_again;
 622           }
 623       }
 624
 625   template<typename _Key, typename _Value,
 626            typename _Allocator, typename _ExtractKey, typename _Equal,
 627            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 628            bool __chc, bool __cit, bool __uk>
 629     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 630                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 631     _Hashtable(const _Hashtable& __ht)
 632     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
 633       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 634                                 _H1, _H2, _Hash, __chc>(__ht),
 635       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
 636       _M_node_allocator(__ht._M_node_allocator),
 637       _M_bucket_count(__ht._M_bucket_count),
 638       _M_begin_bucket_index(__ht._M_begin_bucket_index),
 639       _M_element_count(__ht._M_element_count),
 640       _M_rehash_policy(__ht._M_rehash_policy)
 641     {
 642       _M_buckets = _M_allocate_buckets(_M_bucket_count);
 643       __try
 644         {
 645           for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
 646             {
 647               _Node* __n = __ht._M_buckets[__i];
 648               _Node** __tail = _M_buckets + __i;
 649               while (__n)
 650                 {
 651                   *__tail = _M_allocate_node(__n->_M_v);
 652                   this->_M_copy_code(*__tail, __n);
 653                   __tail = &((*__tail)->_M_next);
 654                   __n = __n->_M_next;
 655                 }
 656             }
 657         }
 658       __catch(...)
 659         {
 660           clear();
 661           _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 662           __throw_exception_again;
 663         }
 664     }
 665
 666   template<typename _Key, typename _Value,
 667            typename _Allocator, typename _ExtractKey, typename _Equal,
 668            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 669            bool __chc, bool __cit, bool __uk>
 670     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 671                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 672     _Hashtable(_Hashtable&& __ht)
 673     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
 674       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 675                                 _H1, _H2, _Hash, __chc>(__ht),
 676       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
 677       _M_node_allocator(__ht._M_node_allocator),
 678       _M_buckets(__ht._M_buckets),
 679       _M_bucket_count(__ht._M_bucket_count),
 680       _M_begin_bucket_index(__ht._M_begin_bucket_index),
 681       _M_element_count(__ht._M_element_count),
 682       _M_rehash_policy(__ht._M_rehash_policy)
 683     {
 684       size_type __n_bkt = __ht._M_rehash_policy._M_next_bkt(0);
 685       __ht._M_buckets = __ht._M_allocate_buckets(__n_bkt);
 686       __ht._M_bucket_count = __n_bkt;
 687       __ht._M_begin_bucket_index = __ht._M_bucket_count;
 688       __ht._M_element_count = 0;
 689       __ht._M_rehash_policy = _RehashPolicy();
 690     }
 691
 692   template<typename _Key, typename _Value,
 693            typename _Allocator, typename _ExtractKey, typename _Equal,
 694            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 695            bool __chc, bool __cit, bool __uk>
 696     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 697                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 698     ~_Hashtable()
 699     {
 700       clear();
 701       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 702     }
 703
 704   template<typename _Key, typename _Value,
 705            typename _Allocator, typename _ExtractKey, typename _Equal,
 706            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 707            bool __chc, bool __cit, bool __uk>
 708     void
 709     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 710                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 711     swap(_Hashtable& __x)
 712     {
 713       // The only base class with member variables is hash_code_base.  We
 714       // define _Hash_code_base::_M_swap because different specializations
 715       // have different members.
 716       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 717         _H1, _H2, _Hash, __chc>::_M_swap(__x);
 718
 719       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 720       // 431. Swapping containers with unequal allocators.
 721       std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
 722                                                         __x._M_node_allocator);
 723
 724       std::swap(_M_rehash_policy, __x._M_rehash_policy);
 725       std::swap(_M_buckets, __x._M_buckets);
 726       std::swap(_M_bucket_count, __x._M_bucket_count);
 727       std::swap(_M_begin_bucket_index, __x._M_begin_bucket_index);
 728       std::swap(_M_element_count, __x._M_element_count);
 729     }
 730
 731   template<typename _Key, typename _Value,
 732            typename _Allocator, typename _ExtractKey, typename _Equal,
 733            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 734            bool __chc, bool __cit, bool __uk>
 735     void
 736     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 737                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 738     __rehash_policy(const _RehashPolicy& __pol)
 739     {
 740       _M_rehash_policy = __pol;
 741       size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
 742       if (__n_bkt > _M_bucket_count)
 743         _M_rehash(__n_bkt);
 744     }
 745
 746   template<typename _Key, typename _Value,
 747            typename _Allocator, typename _ExtractKey, typename _Equal,
 748            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 749            bool __chc, bool __cit, bool __uk>
 750     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 751                         _H1, _H2, _Hash, _RehashPolicy,
 752                         __chc, __cit, __uk>::iterator
 753     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 754                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 755     find(const key_type& __k)
 756     {
 757       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 758       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 759       _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
 760       return __p ? iterator(__p, _M_buckets + __n) : this->end();
 761     }
 762
 763   template<typename _Key, typename _Value,
 764            typename _Allocator, typename _ExtractKey, typename _Equal,
 765            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 766            bool __chc, bool __cit, bool __uk>
 767     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 768                         _H1, _H2, _Hash, _RehashPolicy,
 769                         __chc, __cit, __uk>::const_iterator
 770     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 771                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 772     find(const key_type& __k) const
 773     {
 774       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 775       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 776       _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
 777       return __p ? const_iterator(__p, _M_buckets + __n) : this->end();
 778     }
 779
 780   template<typename _Key, typename _Value,
 781            typename _Allocator, typename _ExtractKey, typename _Equal,
 782            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 783            bool __chc, bool __cit, bool __uk>
 784     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 785                         _H1, _H2, _Hash, _RehashPolicy,
 786                         __chc, __cit, __uk>::size_type
 787     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 788                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 789     count(const key_type& __k) const
 790     {
 791       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 792       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 793       std::size_t __result = 0;
 794       for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next)
 795         if (this->_M_compare(__k, __code, __p))
 796           ++__result;
 797       return __result;
 798     }
 799
 800   template<typename _Key, typename _Value,
 801            typename _Allocator, typename _ExtractKey, typename _Equal,
 802            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 803            bool __chc, bool __cit, bool __uk>
 804     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
 805                                   _ExtractKey, _Equal, _H1,
 806                                   _H2, _Hash, _RehashPolicy,
 807                                   __chc, __cit, __uk>::iterator,
 808               typename _Hashtable<_Key, _Value, _Allocator,
 809                                   _ExtractKey, _Equal, _H1,
 810                                   _H2, _Hash, _RehashPolicy,
 811                                   __chc, __cit, __uk>::iterator>
 812     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 813                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 814     equal_range(const key_type& __k)
 815     {
 816       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 817       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 818       _Node** __head = _M_buckets + __n;
 819       _Node* __p = _M_find_node(*__head, __k, __code);
 820
 821       if (__p)
 822         {
 823           _Node* __p1 = __p->_M_next;
 824           for (; __p1; __p1 = __p1->_M_next)
 825             if (!this->_M_compare(__k, __code, __p1))
 826               break;
 827
 828           iterator __first(__p, __head);
 829           iterator __last(__p1, __head);
 830           if (!__p1)
 831             __last._M_incr_bucket();
 832           return std::make_pair(__first, __last);
 833         }
 834       else
 835         return std::make_pair(this->end(), this->end());
 836     }
 837
 838   template<typename _Key, typename _Value,
 839            typename _Allocator, typename _ExtractKey, typename _Equal,
 840            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 841            bool __chc, bool __cit, bool __uk>
 842     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
 843                                   _ExtractKey, _Equal, _H1,
 844                                   _H2, _Hash, _RehashPolicy,
 845                                   __chc, __cit, __uk>::const_iterator,
 846               typename _Hashtable<_Key, _Value, _Allocator,
 847                                   _ExtractKey, _Equal, _H1,
 848                                   _H2, _Hash, _RehashPolicy,
 849                                   __chc, __cit, __uk>::const_iterator>
 850     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 851                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 852     equal_range(const key_type& __k) const
 853     {
 854       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 855       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 856       _Node** __head = _M_buckets + __n;
 857       _Node* __p = _M_find_node(*__head, __k, __code);
 858
 859       if (__p)
 860         {
 861           _Node* __p1 = __p->_M_next;
 862           for (; __p1; __p1 = __p1->_M_next)
 863             if (!this->_M_compare(__k, __code, __p1))
 864               break;
 865
 866           const_iterator __first(__p, __head);
 867           const_iterator __last(__p1, __head);
 868           if (!__p1)
 869             __last._M_incr_bucket();
 870           return std::make_pair(__first, __last);
 871         }
 872       else
 873         return std::make_pair(this->end(), this->end());
 874     }
 875
 876   // Find the node whose key compares equal to k, beginning the search
 877   // at p (usually the head of a bucket).  Return nil if no node is found.
 878   template<typename _Key, typename _Value,
 879            typename _Allocator, typename _ExtractKey, typename _Equal,
 880            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 881            bool __chc, bool __cit, bool __uk>
 882     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
 883                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
 884                         __chc, __cit, __uk>::_Node*
 885     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 886                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 887     _M_find_node(_Node* __p, const key_type& __k,
 888                 typename _Hashtable::_Hash_code_type __code) const
 889     {
 890       for (; __p; __p = __p->_M_next)
 891         if (this->_M_compare(__k, __code, __p))
 892           return __p;
 893       return false;
 894     }
 895
 896   // Insert v in bucket n (assumes no element with its key already present).
 897   template<typename _Key, typename _Value,
 898            typename _Allocator, typename _ExtractKey, typename _Equal,
 899            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 900            bool __chc, bool __cit, bool __uk>
 901     template<typename _Pair>
 902       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 903                           _H1, _H2, _Hash, _RehashPolicy,
 904                           __chc, __cit, __uk>::iterator
 905       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 906                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 907       _M_insert_bucket(_Pair&& __v, size_type __n,
 908                        typename _Hashtable::_Hash_code_type __code)
 909       {
 910         std::pair<bool, std::size_t> __do_rehash
 911           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
 912                                             _M_element_count, 1);
 913
 914         if (__do_rehash.first)
 915           {
 916             const key_type& __k = this->_M_extract(__v);
 917             __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
 918           }
 919
 920         // Allocate the new node before doing the rehash so that we don't
 921         // do a rehash if the allocation throws.
 922         _Node* __new_node = _M_allocate_node(std::forward<_Pair>(__v));
 923
 924         __try
 925           {
 926             if (__do_rehash.first)
 927               _M_rehash(__do_rehash.second);
 928
 929             __new_node->_M_next = _M_buckets[__n];
 930             this->_M_store_code(__new_node, __code);
 931             _M_buckets[__n] = __new_node;
 932             ++_M_element_count;
 933             if (__n < _M_begin_bucket_index)
 934               _M_begin_bucket_index = __n;
 935             return iterator(__new_node, _M_buckets + __n);
 936           }
 937         __catch(...)
 938           {
 939             _M_deallocate_node(__new_node);
 940             __throw_exception_again;
 941           }
 942       }
 943
 944   // Insert v if no element with its key is already present.
 945   template<typename _Key, typename _Value,
 946            typename _Allocator, typename _ExtractKey, typename _Equal,
 947            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 948            bool __chc, bool __cit, bool __uk>
 949     template<typename _Pair>
 950       std::pair<typename _Hashtable<_Key, _Value, _Allocator,
 951                                     _ExtractKey, _Equal, _H1,
 952                                     _H2, _Hash, _RehashPolicy,
 953                                     __chc, __cit, __uk>::iterator, bool>
 954       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 955                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 956       _M_insert(_Pair&& __v, std::true_type)
 957       {
 958         const key_type& __k = this->_M_extract(__v);
 959         typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 960         size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 961
 962         if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
 963           return std::make_pair(iterator(__p, _M_buckets + __n), false);
 964         return std::make_pair(_M_insert_bucket(std::forward<_Pair>(__v),
 965                               __n, __code), true);
 966       }
 967
 968   // Insert v unconditionally.
 969   template<typename _Key, typename _Value,
 970            typename _Allocator, typename _ExtractKey, typename _Equal,
 971            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 972            bool __chc, bool __cit, bool __uk>
 973     template<typename _Pair>
 974       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 975                           _H1, _H2, _Hash, _RehashPolicy,
 976                           __chc, __cit, __uk>::iterator
 977       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 978                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 979       _M_insert(_Pair&& __v, std::false_type)
 980       {
 981         std::pair<bool, std::size_t> __do_rehash
 982           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
 983                                             _M_element_count, 1);
 984         if (__do_rehash.first)
 985           _M_rehash(__do_rehash.second);
 986
 987         const key_type& __k = this->_M_extract(__v);
 988         typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 989         size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 990
 991         // First find the node, avoid leaking new_node if compare throws.
 992         _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
 993         _Node* __new_node = _M_allocate_node(std::forward<_Pair>(__v));
 994
 995         if (__prev)
 996           {
 997             __new_node->_M_next = __prev->_M_next;
 998             __prev->_M_next = __new_node;
 999           }
1000         else
1001           {
1002             __new_node->_M_next = _M_buckets[__n];
1003             _M_buckets[__n] = __new_node;
1004             if (__n < _M_begin_bucket_index)
1005               _M_begin_bucket_index = __n;
1006           }
1007         this->_M_store_code(__new_node, __code);
1008
1009         ++_M_element_count;
1010         return iterator(__new_node, _M_buckets + __n);
1011       }
1012
1013   template<typename _Key, typename _Value,
1014            typename _Allocator, typename _ExtractKey, typename _Equal,
1015            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1016            bool __chc, bool __cit, bool __uk>
1017     template<typename _InputIterator>
1018       void
1019       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1020                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1021       insert(_InputIterator __first, _InputIterator __last)
1022       {
1023         size_type __n_elt = __detail::__distance_fw(__first, __last);
1024         std::pair<bool, std::size_t> __do_rehash
1025           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1026                                             _M_element_count, __n_elt);
1027         if (__do_rehash.first)
1028           _M_rehash(__do_rehash.second);
1029
1030         for (; __first != __last; ++__first)
1031           this->insert(*__first);
1032       }
1033
1034   template<typename _Key, typename _Value,
1035            typename _Allocator, typename _ExtractKey, typename _Equal,
1036            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1037            bool __chc, bool __cit, bool __uk>
1038     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1039                         _H1, _H2, _Hash, _RehashPolicy,
1040                         __chc, __cit, __uk>::iterator
1041     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1042                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1043     erase(const_iterator __it)
1044     {
1045       iterator __result(__it._M_cur_node, __it._M_cur_bucket);
1046       ++__result;
1047
1048       _Node* __cur = *__it._M_cur_bucket;
1049       if (__cur == __it._M_cur_node)
1050         {
1051           *__it._M_cur_bucket = __cur->_M_next;
1052
1053           // If _M_begin_bucket_index no longer indexes the first non-empty
1054           // bucket - its single node is being erased - update it.
1055           if (!_M_buckets[_M_begin_bucket_index])
1056             _M_begin_bucket_index = __result._M_cur_bucket - _M_buckets;
1057         }
1058       else
1059         {
1060           _Node* __next = __cur->_M_next;
1061           while (__next != __it._M_cur_node)
1062             {
1063               __cur = __next;
1064               __next = __cur->_M_next;
1065             }
1066           __cur->_M_next = __next->_M_next;
1067         }
1068
1069       _M_deallocate_node(__it._M_cur_node);
1070       --_M_element_count;
1071
1072       return __result;
1073     }
1074
1075   template<typename _Key, typename _Value,
1076            typename _Allocator, typename _ExtractKey, typename _Equal,
1077            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1078            bool __chc, bool __cit, bool __uk>
1079     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1080                         _H1, _H2, _Hash, _RehashPolicy,
1081                         __chc, __cit, __uk>::size_type
1082     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1083                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1084     erase(const key_type& __k)
1085     {
1086       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1087       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
1088       size_type __result = 0;
1089
1090       _Node** __slot = _M_buckets + __n;
1091       while (*__slot && !this->_M_compare(__k, __code, *__slot))
1092         __slot = &((*__slot)->_M_next);
1093
1094       _Node** __saved_slot = 0;
1095       while (*__slot && this->_M_compare(__k, __code, *__slot))
1096         {
1097           // _GLIBCXX_RESOLVE_LIB_DEFECTS
1098           // 526. Is it undefined if a function in the standard changes
1099           // in parameters?
1100           if (std::__addressof(this->_M_extract((*__slot)->_M_v))
1101               != std::__addressof(__k))
1102             {
1103               _Node* __p = *__slot;
1104               *__slot = __p->_M_next;
1105               _M_deallocate_node(__p);
1106               --_M_element_count;
1107               ++__result;
1108             }
1109           else
1110             {
1111               __saved_slot = __slot;
1112               __slot = &((*__slot)->_M_next);
1113             }
1114         }
1115
1116       if (__saved_slot)
1117         {
1118           _Node* __p = *__saved_slot;
1119           *__saved_slot = __p->_M_next;
1120           _M_deallocate_node(__p);
1121           --_M_element_count;
1122           ++__result;
1123         }
1124
1125       // If the entire bucket indexed by _M_begin_bucket_index has been
1126       // erased look forward for the first non-empty bucket.
1127       if (!_M_buckets[_M_begin_bucket_index])
1128         {
1129           if (!_M_element_count)
1130             _M_begin_bucket_index = _M_bucket_count;
1131           else
1132             {
1133               ++_M_begin_bucket_index;
1134               while (!_M_buckets[_M_begin_bucket_index])
1135                 ++_M_begin_bucket_index;
1136             }
1137         }
1138
1139       return __result;
1140     }
1141
1142   // ??? This could be optimized by taking advantage of the bucket
1143   // structure, but it's not clear that it's worth doing.  It probably
1144   // wouldn't even be an optimization unless the load factor is large.
1145   template<typename _Key, typename _Value,
1146            typename _Allocator, typename _ExtractKey, typename _Equal,
1147            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1148            bool __chc, bool __cit, bool __uk>
1149     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1150                         _H1, _H2, _Hash, _RehashPolicy,
1151                         __chc, __cit, __uk>::iterator
1152     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1153                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1154     erase(const_iterator __first, const_iterator __last)
1155     {
1156        while (__first != __last)
1157          __first = this->erase(__first);
1158       return iterator(__last._M_cur_node, __last._M_cur_bucket);
1159     }
1160
1161   template<typename _Key, typename _Value,
1162            typename _Allocator, typename _ExtractKey, typename _Equal,
1163            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1164            bool __chc, bool __cit, bool __uk>
1165     void
1166     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1167                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1168     clear()
1169     {
1170       _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1171       _M_element_count = 0;
1172       _M_begin_bucket_index = _M_bucket_count;
1173     }
1174
1175   template<typename _Key, typename _Value,
1176            typename _Allocator, typename _ExtractKey, typename _Equal,
1177            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1178            bool __chc, bool __cit, bool __uk>
1179     void
1180     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1181                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1182     rehash(size_type __n)
1183     {
1184       _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
1185                          _M_rehash_policy._M_bkt_for_elements(_M_element_count
1186                                                               + 1)));
1187     }
1188
1189   template<typename _Key, typename _Value,
1190            typename _Allocator, typename _ExtractKey, typename _Equal,
1191            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1192            bool __chc, bool __cit, bool __uk>
1193     void
1194     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1195                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1196     _M_rehash(size_type __n)
1197     {
1198       _Node** __new_array = _M_allocate_buckets(__n);
1199       __try
1200         {
1201           _M_begin_bucket_index = __n;
1202           for (size_type __i = 0; __i < _M_bucket_count; ++__i)
1203             while (_Node* __p = _M_buckets[__i])
1204               {
1205                 std::size_t __new_index = this->_M_bucket_index(__p, __n);
1206                 _M_buckets[__i] = __p->_M_next;
1207                 __p->_M_next = __new_array[__new_index];
1208                 __new_array[__new_index] = __p;
1209                 if (__new_index < _M_begin_bucket_index)
1210                   _M_begin_bucket_index = __new_index;
1211               }
1212           _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1213           _M_bucket_count = __n;
1214           _M_buckets = __new_array;
1215         }
1216       __catch(...)
1217         {
1218           // A failure here means that a hash function threw an exception.
1219           // We can't restore the previous state without calling the hash
1220           // function again, so the only sensible recovery is to delete
1221           // everything.
1222           _M_deallocate_nodes(__new_array, __n);
1223           _M_deallocate_buckets(__new_array, __n);
1224           _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1225           _M_element_count = 0;
1226           _M_begin_bucket_index = _M_bucket_count;
1227           __throw_exception_again;
1228         }
1229     }
1230 }
1231
1232 #endif // _HASHTABLE_H