libstdc++
|
00001 // hashtable.h header -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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.h 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. @headername{unordered_map, unordered_set} 00028 */ 00029 00030 #ifndef _HASHTABLE_H 00031 #define _HASHTABLE_H 1 00032 00033 #pragma GCC system_header 00034 00035 #include <bits/hashtable_policy.h> 00036 00037 namespace std _GLIBCXX_VISIBILITY(default) 00038 { 00039 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00040 00041 // Class template _Hashtable, class definition. 00042 00043 // Meaning of class template _Hashtable's template parameters 00044 00045 // _Key and _Value: arbitrary CopyConstructible types. 00046 00047 // _Allocator: an allocator type ([lib.allocator.requirements]) whose 00048 // value type is Value. As a conforming extension, we allow for 00049 // value type != Value. 00050 00051 // _ExtractKey: function object that takes a object of type Value 00052 // and returns a value of type _Key. 00053 00054 // _Equal: function object that takes two objects of type k and returns 00055 // a bool-like value that is true if the two objects are considered equal. 00056 00057 // _H1: the hash function. A unary function object with argument type 00058 // Key and result type size_t. Return values should be distributed 00059 // over the entire range [0, numeric_limits<size_t>:::max()]. 00060 00061 // _H2: the range-hashing function (in the terminology of Tavori and 00062 // Dreizin). A binary function object whose argument types and result 00063 // type are all size_t. Given arguments r and N, the return value is 00064 // in the range [0, N). 00065 00066 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function 00067 // whose argument types are _Key and size_t and whose result type is 00068 // size_t. Given arguments k and N, the return value is in the range 00069 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other 00070 // than the default, _H1 and _H2 are ignored. 00071 00072 // _RehashPolicy: Policy class with three members, all of which govern 00073 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller 00074 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate 00075 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) 00076 // determines whether, if the current bucket count is n_bkt and the 00077 // current element count is n_elt, we need to increase the bucket 00078 // count. If so, returns make_pair(true, n), where n is the new 00079 // bucket count. If not, returns make_pair(false, <anything>). 00080 00081 // ??? Right now it is hard-wired that the number of buckets never 00082 // shrinks. Should we allow _RehashPolicy to change that? 00083 00084 // __cache_hash_code: bool. true if we store the value of the hash 00085 // function along with the value. This is a time-space tradeoff. 00086 // Storing it may improve lookup speed by reducing the number of times 00087 // we need to call the Equal function. 00088 00089 // __constant_iterators: bool. true if iterator and const_iterator are 00090 // both constant iterator types. This is true for unordered_set and 00091 // unordered_multiset, false for unordered_map and unordered_multimap. 00092 00093 // __unique_keys: bool. true if the return value of _Hashtable::count(k) 00094 // is always at most one, false if it may be an arbitrary number. This 00095 // true for unordered_set and unordered_map, false for unordered_multiset 00096 // and unordered_multimap. 00097 00098 template<typename _Key, typename _Value, typename _Allocator, 00099 typename _ExtractKey, typename _Equal, 00100 typename _H1, typename _H2, typename _Hash, 00101 typename _RehashPolicy, 00102 bool __cache_hash_code, 00103 bool __constant_iterators, 00104 bool __unique_keys> 00105 class _Hashtable 00106 : public __detail::_Rehash_base<_RehashPolicy, 00107 _Hashtable<_Key, _Value, _Allocator, 00108 _ExtractKey, 00109 _Equal, _H1, _H2, _Hash, 00110 _RehashPolicy, 00111 __cache_hash_code, 00112 __constant_iterators, 00113 __unique_keys> >, 00114 public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00115 _H1, _H2, _Hash, __cache_hash_code>, 00116 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, 00117 _Hashtable<_Key, _Value, _Allocator, 00118 _ExtractKey, 00119 _Equal, _H1, _H2, _Hash, 00120 _RehashPolicy, 00121 __cache_hash_code, 00122 __constant_iterators, 00123 __unique_keys> >, 00124 public __detail::_Equality_base<_ExtractKey, __unique_keys, 00125 _Hashtable<_Key, _Value, _Allocator, 00126 _ExtractKey, 00127 _Equal, _H1, _H2, _Hash, 00128 _RehashPolicy, 00129 __cache_hash_code, 00130 __constant_iterators, 00131 __unique_keys> > 00132 { 00133 public: 00134 typedef _Allocator allocator_type; 00135 typedef _Value value_type; 00136 typedef _Key key_type; 00137 typedef _Equal key_equal; 00138 // mapped_type, if present, comes from _Map_base. 00139 // hasher, if present, comes from _Hash_code_base. 00140 typedef typename _Allocator::pointer pointer; 00141 typedef typename _Allocator::const_pointer const_pointer; 00142 typedef typename _Allocator::reference reference; 00143 typedef typename _Allocator::const_reference const_reference; 00144 00145 typedef std::size_t size_type; 00146 typedef std::ptrdiff_t difference_type; 00147 typedef __detail::_Node_iterator<value_type, __constant_iterators, 00148 __cache_hash_code> 00149 local_iterator; 00150 typedef __detail::_Node_const_iterator<value_type, 00151 __constant_iterators, 00152 __cache_hash_code> 00153 const_local_iterator; 00154 00155 typedef __detail::_Hashtable_iterator<value_type, __constant_iterators, 00156 __cache_hash_code> 00157 iterator; 00158 typedef __detail::_Hashtable_const_iterator<value_type, 00159 __constant_iterators, 00160 __cache_hash_code> 00161 const_iterator; 00162 00163 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2, 00164 typename _Hashtable2> 00165 friend struct __detail::_Map_base; 00166 00167 private: 00168 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; 00169 typedef typename _Allocator::template rebind<_Node>::other 00170 _Node_allocator_type; 00171 typedef typename _Allocator::template rebind<_Node*>::other 00172 _Bucket_allocator_type; 00173 00174 typedef typename _Allocator::template rebind<_Value>::other 00175 _Value_allocator_type; 00176 00177 _Node_allocator_type _M_node_allocator; 00178 _Node** _M_buckets; 00179 size_type _M_bucket_count; 00180 size_type _M_begin_bucket_index; // First non-empty bucket. 00181 size_type _M_element_count; 00182 _RehashPolicy _M_rehash_policy; 00183 00184 template<typename... _Args> 00185 _Node* 00186 _M_allocate_node(_Args&&... __args); 00187 00188 void 00189 _M_deallocate_node(_Node* __n); 00190 00191 void 00192 _M_deallocate_nodes(_Node**, size_type); 00193 00194 _Node** 00195 _M_allocate_buckets(size_type __n); 00196 00197 void 00198 _M_deallocate_buckets(_Node**, size_type __n); 00199 00200 public: 00201 // Constructor, destructor, assignment, swap 00202 _Hashtable(size_type __bucket_hint, 00203 const _H1&, const _H2&, const _Hash&, 00204 const _Equal&, const _ExtractKey&, 00205 const allocator_type&); 00206 00207 template<typename _InputIterator> 00208 _Hashtable(_InputIterator __first, _InputIterator __last, 00209 size_type __bucket_hint, 00210 const _H1&, const _H2&, const _Hash&, 00211 const _Equal&, const _ExtractKey&, 00212 const allocator_type&); 00213 00214 _Hashtable(const _Hashtable&); 00215 00216 _Hashtable(_Hashtable&&); 00217 00218 _Hashtable& 00219 operator=(const _Hashtable& __ht) 00220 { 00221 _Hashtable __tmp(__ht); 00222 this->swap(__tmp); 00223 return *this; 00224 } 00225 00226 _Hashtable& 00227 operator=(_Hashtable&& __ht) 00228 { 00229 // NB: DR 1204. 00230 // NB: DR 675. 00231 this->clear(); 00232 this->swap(__ht); 00233 return *this; 00234 } 00235 00236 ~_Hashtable(); 00237 00238 void swap(_Hashtable&); 00239 00240 // Basic container operations 00241 iterator 00242 begin() 00243 { return iterator(_M_buckets + _M_begin_bucket_index); } 00244 00245 const_iterator 00246 begin() const 00247 { return const_iterator(_M_buckets + _M_begin_bucket_index); } 00248 00249 iterator 00250 end() 00251 { return iterator(_M_buckets + _M_bucket_count); } 00252 00253 const_iterator 00254 end() const 00255 { return const_iterator(_M_buckets + _M_bucket_count); } 00256 00257 const_iterator 00258 cbegin() const 00259 { return const_iterator(_M_buckets + _M_begin_bucket_index); } 00260 00261 const_iterator 00262 cend() const 00263 { return const_iterator(_M_buckets + _M_bucket_count); } 00264 00265 size_type 00266 size() const 00267 { return _M_element_count; } 00268 00269 bool 00270 empty() const 00271 { return size() == 0; } 00272 00273 allocator_type 00274 get_allocator() const 00275 { return allocator_type(_M_node_allocator); } 00276 00277 size_type 00278 max_size() const 00279 { return _M_node_allocator.max_size(); } 00280 00281 // Observers 00282 key_equal 00283 key_eq() const 00284 { return this->_M_eq; } 00285 00286 // hash_function, if present, comes from _Hash_code_base. 00287 00288 // Bucket operations 00289 size_type 00290 bucket_count() const 00291 { return _M_bucket_count; } 00292 00293 size_type 00294 max_bucket_count() const 00295 { return max_size(); } 00296 00297 size_type 00298 bucket_size(size_type __n) const 00299 { return std::distance(begin(__n), end(__n)); } 00300 00301 size_type 00302 bucket(const key_type& __k) const 00303 { 00304 return this->_M_bucket_index(__k, this->_M_hash_code(__k), 00305 bucket_count()); 00306 } 00307 00308 local_iterator 00309 begin(size_type __n) 00310 { return local_iterator(_M_buckets[__n]); } 00311 00312 local_iterator 00313 end(size_type) 00314 { return local_iterator(0); } 00315 00316 const_local_iterator 00317 begin(size_type __n) const 00318 { return const_local_iterator(_M_buckets[__n]); } 00319 00320 const_local_iterator 00321 end(size_type) const 00322 { return const_local_iterator(0); } 00323 00324 // DR 691. 00325 const_local_iterator 00326 cbegin(size_type __n) const 00327 { return const_local_iterator(_M_buckets[__n]); } 00328 00329 const_local_iterator 00330 cend(size_type) const 00331 { return const_local_iterator(0); } 00332 00333 float 00334 load_factor() const 00335 { 00336 return static_cast<float>(size()) / static_cast<float>(bucket_count()); 00337 } 00338 00339 // max_load_factor, if present, comes from _Rehash_base. 00340 00341 // Generalization of max_load_factor. Extension, not found in TR1. Only 00342 // useful if _RehashPolicy is something other than the default. 00343 const _RehashPolicy& 00344 __rehash_policy() const 00345 { return _M_rehash_policy; } 00346 00347 void 00348 __rehash_policy(const _RehashPolicy&); 00349 00350 // Lookup. 00351 iterator 00352 find(const key_type& __k); 00353 00354 const_iterator 00355 find(const key_type& __k) const; 00356 00357 size_type 00358 count(const key_type& __k) const; 00359 00360 std::pair<iterator, iterator> 00361 equal_range(const key_type& __k); 00362 00363 std::pair<const_iterator, const_iterator> 00364 equal_range(const key_type& __k) const; 00365 00366 private: 00367 // Find and insert helper functions and types 00368 _Node* 00369 _M_find_node(_Node*, const key_type&, 00370 typename _Hashtable::_Hash_code_type) const; 00371 00372 template<typename _Arg> 00373 iterator 00374 _M_insert_bucket(_Arg&&, size_type, 00375 typename _Hashtable::_Hash_code_type); 00376 00377 template<typename _Arg> 00378 std::pair<iterator, bool> 00379 _M_insert(_Arg&&, std::true_type); 00380 00381 template<typename _Arg> 00382 iterator 00383 _M_insert(_Arg&&, std::false_type); 00384 00385 typedef typename std::conditional<__unique_keys, 00386 std::pair<iterator, bool>, 00387 iterator>::type 00388 _Insert_Return_Type; 00389 00390 typedef typename std::conditional<__unique_keys, 00391 std::_Select1st<_Insert_Return_Type>, 00392 std::_Identity<_Insert_Return_Type> 00393 >::type 00394 _Insert_Conv_Type; 00395 00396 public: 00397 // Insert and erase 00398 _Insert_Return_Type 00399 insert(const value_type& __v) 00400 { return _M_insert(__v, std::integral_constant<bool, __unique_keys>()); } 00401 00402 iterator 00403 insert(const_iterator, const value_type& __v) 00404 { return _Insert_Conv_Type()(insert(__v)); } 00405 00406 _Insert_Return_Type 00407 insert(value_type&& __v) 00408 { return _M_insert(std::move(__v), 00409 std::integral_constant<bool, __unique_keys>()); } 00410 00411 iterator 00412 insert(const_iterator, value_type&& __v) 00413 { return _Insert_Conv_Type()(insert(std::move(__v))); } 00414 00415 template<typename _Pair, typename = typename 00416 std::enable_if<!__constant_iterators 00417 && std::is_convertible<_Pair, 00418 value_type>::value>::type> 00419 _Insert_Return_Type 00420 insert(_Pair&& __v) 00421 { return _M_insert(std::forward<_Pair>(__v), 00422 std::integral_constant<bool, __unique_keys>()); } 00423 00424 template<typename _Pair, typename = typename 00425 std::enable_if<!__constant_iterators 00426 && std::is_convertible<_Pair, 00427 value_type>::value>::type> 00428 iterator 00429 insert(const_iterator, _Pair&& __v) 00430 { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); } 00431 00432 template<typename _InputIterator> 00433 void 00434 insert(_InputIterator __first, _InputIterator __last); 00435 00436 void 00437 insert(initializer_list<value_type> __l) 00438 { this->insert(__l.begin(), __l.end()); } 00439 00440 iterator 00441 erase(const_iterator); 00442 00443 // LWG 2059. 00444 iterator 00445 erase(iterator __it) 00446 { return erase(const_iterator(__it)); } 00447 00448 size_type 00449 erase(const key_type&); 00450 00451 iterator 00452 erase(const_iterator, const_iterator); 00453 00454 void 00455 clear(); 00456 00457 // Set number of buckets to be appropriate for container of n element. 00458 void rehash(size_type __n); 00459 00460 // DR 1189. 00461 // reserve, if present, comes from _Rehash_base. 00462 00463 private: 00464 // Unconditionally change size of bucket array to n. 00465 void _M_rehash(size_type __n); 00466 }; 00467 00468 00469 // Definitions of class template _Hashtable's out-of-line member functions. 00470 template<typename _Key, typename _Value, 00471 typename _Allocator, typename _ExtractKey, typename _Equal, 00472 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00473 bool __chc, bool __cit, bool __uk> 00474 template<typename... _Args> 00475 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00476 _H1, _H2, _Hash, _RehashPolicy, 00477 __chc, __cit, __uk>::_Node* 00478 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00479 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00480 _M_allocate_node(_Args&&... __args) 00481 { 00482 _Node* __n = _M_node_allocator.allocate(1); 00483 __try 00484 { 00485 _M_node_allocator.construct(__n, std::forward<_Args>(__args)...); 00486 __n->_M_next = 0; 00487 return __n; 00488 } 00489 __catch(...) 00490 { 00491 _M_node_allocator.deallocate(__n, 1); 00492 __throw_exception_again; 00493 } 00494 } 00495 00496 template<typename _Key, typename _Value, 00497 typename _Allocator, typename _ExtractKey, typename _Equal, 00498 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00499 bool __chc, bool __cit, bool __uk> 00500 void 00501 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00502 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00503 _M_deallocate_node(_Node* __n) 00504 { 00505 _M_node_allocator.destroy(__n); 00506 _M_node_allocator.deallocate(__n, 1); 00507 } 00508 00509 template<typename _Key, typename _Value, 00510 typename _Allocator, typename _ExtractKey, typename _Equal, 00511 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00512 bool __chc, bool __cit, bool __uk> 00513 void 00514 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00515 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00516 _M_deallocate_nodes(_Node** __array, size_type __n) 00517 { 00518 for (size_type __i = 0; __i < __n; ++__i) 00519 { 00520 _Node* __p = __array[__i]; 00521 while (__p) 00522 { 00523 _Node* __tmp = __p; 00524 __p = __p->_M_next; 00525 _M_deallocate_node(__tmp); 00526 } 00527 __array[__i] = 0; 00528 } 00529 } 00530 00531 template<typename _Key, typename _Value, 00532 typename _Allocator, typename _ExtractKey, typename _Equal, 00533 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00534 bool __chc, bool __cit, bool __uk> 00535 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00536 _H1, _H2, _Hash, _RehashPolicy, 00537 __chc, __cit, __uk>::_Node** 00538 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00539 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00540 _M_allocate_buckets(size_type __n) 00541 { 00542 _Bucket_allocator_type __alloc(_M_node_allocator); 00543 00544 // We allocate one extra bucket to hold a sentinel, an arbitrary 00545 // non-null pointer. Iterator increment relies on this. 00546 _Node** __p = __alloc.allocate(__n + 1); 00547 std::fill(__p, __p + __n, (_Node*) 0); 00548 __p[__n] = reinterpret_cast<_Node*>(0x1000); 00549 return __p; 00550 } 00551 00552 template<typename _Key, typename _Value, 00553 typename _Allocator, typename _ExtractKey, typename _Equal, 00554 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00555 bool __chc, bool __cit, bool __uk> 00556 void 00557 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00558 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00559 _M_deallocate_buckets(_Node** __p, size_type __n) 00560 { 00561 _Bucket_allocator_type __alloc(_M_node_allocator); 00562 __alloc.deallocate(__p, __n + 1); 00563 } 00564 00565 template<typename _Key, typename _Value, 00566 typename _Allocator, typename _ExtractKey, typename _Equal, 00567 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00568 bool __chc, bool __cit, bool __uk> 00569 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00570 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00571 _Hashtable(size_type __bucket_hint, 00572 const _H1& __h1, const _H2& __h2, const _Hash& __h, 00573 const _Equal& __eq, const _ExtractKey& __exk, 00574 const allocator_type& __a) 00575 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 00576 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00577 _H1, _H2, _Hash, __chc>(__exk, __eq, 00578 __h1, __h2, __h), 00579 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 00580 _M_node_allocator(__a), 00581 _M_bucket_count(0), 00582 _M_element_count(0), 00583 _M_rehash_policy() 00584 { 00585 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); 00586 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00587 _M_begin_bucket_index = _M_bucket_count; 00588 } 00589 00590 template<typename _Key, typename _Value, 00591 typename _Allocator, typename _ExtractKey, typename _Equal, 00592 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00593 bool __chc, bool __cit, bool __uk> 00594 template<typename _InputIterator> 00595 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00596 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00597 _Hashtable(_InputIterator __f, _InputIterator __l, 00598 size_type __bucket_hint, 00599 const _H1& __h1, const _H2& __h2, const _Hash& __h, 00600 const _Equal& __eq, const _ExtractKey& __exk, 00601 const allocator_type& __a) 00602 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 00603 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00604 _H1, _H2, _Hash, __chc>(__exk, __eq, 00605 __h1, __h2, __h), 00606 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 00607 _M_node_allocator(__a), 00608 _M_bucket_count(0), 00609 _M_element_count(0), 00610 _M_rehash_policy() 00611 { 00612 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), 00613 _M_rehash_policy. 00614 _M_bkt_for_elements(__detail:: 00615 __distance_fw(__f, 00616 __l))); 00617 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00618 _M_begin_bucket_index = _M_bucket_count; 00619 __try 00620 { 00621 for (; __f != __l; ++__f) 00622 this->insert(*__f); 00623 } 00624 __catch(...) 00625 { 00626 clear(); 00627 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00628 __throw_exception_again; 00629 } 00630 } 00631 00632 template<typename _Key, typename _Value, 00633 typename _Allocator, typename _ExtractKey, typename _Equal, 00634 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00635 bool __chc, bool __cit, bool __uk> 00636 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00637 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00638 _Hashtable(const _Hashtable& __ht) 00639 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 00640 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00641 _H1, _H2, _Hash, __chc>(__ht), 00642 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 00643 _M_node_allocator(__ht._M_node_allocator), 00644 _M_bucket_count(__ht._M_bucket_count), 00645 _M_begin_bucket_index(__ht._M_begin_bucket_index), 00646 _M_element_count(__ht._M_element_count), 00647 _M_rehash_policy(__ht._M_rehash_policy) 00648 { 00649 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00650 __try 00651 { 00652 for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i) 00653 { 00654 _Node* __n = __ht._M_buckets[__i]; 00655 _Node** __tail = _M_buckets + __i; 00656 while (__n) 00657 { 00658 *__tail = _M_allocate_node(__n->_M_v); 00659 this->_M_copy_code(*__tail, __n); 00660 __tail = &((*__tail)->_M_next); 00661 __n = __n->_M_next; 00662 } 00663 } 00664 } 00665 __catch(...) 00666 { 00667 clear(); 00668 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00669 __throw_exception_again; 00670 } 00671 } 00672 00673 template<typename _Key, typename _Value, 00674 typename _Allocator, typename _ExtractKey, typename _Equal, 00675 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00676 bool __chc, bool __cit, bool __uk> 00677 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00678 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00679 _Hashtable(_Hashtable&& __ht) 00680 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 00681 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00682 _H1, _H2, _Hash, __chc>(__ht), 00683 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 00684 _M_node_allocator(__ht._M_node_allocator), 00685 _M_buckets(__ht._M_buckets), 00686 _M_bucket_count(__ht._M_bucket_count), 00687 _M_begin_bucket_index(__ht._M_begin_bucket_index), 00688 _M_element_count(__ht._M_element_count), 00689 _M_rehash_policy(__ht._M_rehash_policy) 00690 { 00691 __ht._M_rehash_policy = _RehashPolicy(); 00692 __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0); 00693 __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count); 00694 __ht._M_begin_bucket_index = __ht._M_bucket_count; 00695 __ht._M_element_count = 0; 00696 } 00697 00698 template<typename _Key, typename _Value, 00699 typename _Allocator, typename _ExtractKey, typename _Equal, 00700 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00701 bool __chc, bool __cit, bool __uk> 00702 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00703 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00704 ~_Hashtable() 00705 { 00706 clear(); 00707 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00708 } 00709 00710 template<typename _Key, typename _Value, 00711 typename _Allocator, typename _ExtractKey, typename _Equal, 00712 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00713 bool __chc, bool __cit, bool __uk> 00714 void 00715 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00716 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00717 swap(_Hashtable& __x) 00718 { 00719 // The only base class with member variables is hash_code_base. We 00720 // define _Hash_code_base::_M_swap because different specializations 00721 // have different members. 00722 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00723 _H1, _H2, _Hash, __chc>::_M_swap(__x); 00724 00725 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00726 // 431. Swapping containers with unequal allocators. 00727 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, 00728 __x._M_node_allocator); 00729 00730 std::swap(_M_rehash_policy, __x._M_rehash_policy); 00731 std::swap(_M_buckets, __x._M_buckets); 00732 std::swap(_M_bucket_count, __x._M_bucket_count); 00733 std::swap(_M_begin_bucket_index, __x._M_begin_bucket_index); 00734 std::swap(_M_element_count, __x._M_element_count); 00735 } 00736 00737 template<typename _Key, typename _Value, 00738 typename _Allocator, typename _ExtractKey, typename _Equal, 00739 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00740 bool __chc, bool __cit, bool __uk> 00741 void 00742 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00743 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00744 __rehash_policy(const _RehashPolicy& __pol) 00745 { 00746 _M_rehash_policy = __pol; 00747 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); 00748 if (__n_bkt > _M_bucket_count) 00749 _M_rehash(__n_bkt); 00750 } 00751 00752 template<typename _Key, typename _Value, 00753 typename _Allocator, typename _ExtractKey, typename _Equal, 00754 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00755 bool __chc, bool __cit, bool __uk> 00756 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00757 _H1, _H2, _Hash, _RehashPolicy, 00758 __chc, __cit, __uk>::iterator 00759 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00760 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00761 find(const key_type& __k) 00762 { 00763 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00764 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00765 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 00766 return __p ? iterator(__p, _M_buckets + __n) : this->end(); 00767 } 00768 00769 template<typename _Key, typename _Value, 00770 typename _Allocator, typename _ExtractKey, typename _Equal, 00771 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00772 bool __chc, bool __cit, bool __uk> 00773 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00774 _H1, _H2, _Hash, _RehashPolicy, 00775 __chc, __cit, __uk>::const_iterator 00776 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00777 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00778 find(const key_type& __k) const 00779 { 00780 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00781 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00782 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 00783 return __p ? const_iterator(__p, _M_buckets + __n) : this->end(); 00784 } 00785 00786 template<typename _Key, typename _Value, 00787 typename _Allocator, typename _ExtractKey, typename _Equal, 00788 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00789 bool __chc, bool __cit, bool __uk> 00790 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00791 _H1, _H2, _Hash, _RehashPolicy, 00792 __chc, __cit, __uk>::size_type 00793 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00794 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00795 count(const key_type& __k) const 00796 { 00797 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00798 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00799 std::size_t __result = 0; 00800 for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next) 00801 if (this->_M_compare(__k, __code, __p)) 00802 ++__result; 00803 return __result; 00804 } 00805 00806 template<typename _Key, typename _Value, 00807 typename _Allocator, typename _ExtractKey, typename _Equal, 00808 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00809 bool __chc, bool __cit, bool __uk> 00810 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 00811 _ExtractKey, _Equal, _H1, 00812 _H2, _Hash, _RehashPolicy, 00813 __chc, __cit, __uk>::iterator, 00814 typename _Hashtable<_Key, _Value, _Allocator, 00815 _ExtractKey, _Equal, _H1, 00816 _H2, _Hash, _RehashPolicy, 00817 __chc, __cit, __uk>::iterator> 00818 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00819 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00820 equal_range(const key_type& __k) 00821 { 00822 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00823 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00824 _Node** __head = _M_buckets + __n; 00825 _Node* __p = _M_find_node(*__head, __k, __code); 00826 00827 if (__p) 00828 { 00829 _Node* __p1 = __p->_M_next; 00830 for (; __p1; __p1 = __p1->_M_next) 00831 if (!this->_M_compare(__k, __code, __p1)) 00832 break; 00833 00834 iterator __first(__p, __head); 00835 iterator __last(__p1, __head); 00836 if (!__p1) 00837 __last._M_incr_bucket(); 00838 return std::make_pair(__first, __last); 00839 } 00840 else 00841 return std::make_pair(this->end(), this->end()); 00842 } 00843 00844 template<typename _Key, typename _Value, 00845 typename _Allocator, typename _ExtractKey, typename _Equal, 00846 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00847 bool __chc, bool __cit, bool __uk> 00848 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 00849 _ExtractKey, _Equal, _H1, 00850 _H2, _Hash, _RehashPolicy, 00851 __chc, __cit, __uk>::const_iterator, 00852 typename _Hashtable<_Key, _Value, _Allocator, 00853 _ExtractKey, _Equal, _H1, 00854 _H2, _Hash, _RehashPolicy, 00855 __chc, __cit, __uk>::const_iterator> 00856 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00857 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00858 equal_range(const key_type& __k) const 00859 { 00860 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00861 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00862 _Node** __head = _M_buckets + __n; 00863 _Node* __p = _M_find_node(*__head, __k, __code); 00864 00865 if (__p) 00866 { 00867 _Node* __p1 = __p->_M_next; 00868 for (; __p1; __p1 = __p1->_M_next) 00869 if (!this->_M_compare(__k, __code, __p1)) 00870 break; 00871 00872 const_iterator __first(__p, __head); 00873 const_iterator __last(__p1, __head); 00874 if (!__p1) 00875 __last._M_incr_bucket(); 00876 return std::make_pair(__first, __last); 00877 } 00878 else 00879 return std::make_pair(this->end(), this->end()); 00880 } 00881 00882 // Find the node whose key compares equal to k, beginning the search 00883 // at p (usually the head of a bucket). Return nil if no node is found. 00884 template<typename _Key, typename _Value, 00885 typename _Allocator, typename _ExtractKey, typename _Equal, 00886 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00887 bool __chc, bool __cit, bool __uk> 00888 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 00889 _Equal, _H1, _H2, _Hash, _RehashPolicy, 00890 __chc, __cit, __uk>::_Node* 00891 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00892 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00893 _M_find_node(_Node* __p, const key_type& __k, 00894 typename _Hashtable::_Hash_code_type __code) const 00895 { 00896 for (; __p; __p = __p->_M_next) 00897 if (this->_M_compare(__k, __code, __p)) 00898 return __p; 00899 return false; 00900 } 00901 00902 // Insert v in bucket n (assumes no element with its key already present). 00903 template<typename _Key, typename _Value, 00904 typename _Allocator, typename _ExtractKey, typename _Equal, 00905 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00906 bool __chc, bool __cit, bool __uk> 00907 template<typename _Arg> 00908 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00909 _H1, _H2, _Hash, _RehashPolicy, 00910 __chc, __cit, __uk>::iterator 00911 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00912 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00913 _M_insert_bucket(_Arg&& __v, size_type __n, 00914 typename _Hashtable::_Hash_code_type __code) 00915 { 00916 std::pair<bool, std::size_t> __do_rehash 00917 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 00918 _M_element_count, 1); 00919 00920 if (__do_rehash.first) 00921 { 00922 const key_type& __k = this->_M_extract(__v); 00923 __n = this->_M_bucket_index(__k, __code, __do_rehash.second); 00924 } 00925 00926 // Allocate the new node before doing the rehash so that we don't 00927 // do a rehash if the allocation throws. 00928 _Node* __new_node = _M_allocate_node(std::forward<_Arg>(__v)); 00929 00930 __try 00931 { 00932 if (__do_rehash.first) 00933 _M_rehash(__do_rehash.second); 00934 00935 __new_node->_M_next = _M_buckets[__n]; 00936 this->_M_store_code(__new_node, __code); 00937 _M_buckets[__n] = __new_node; 00938 ++_M_element_count; 00939 if (__n < _M_begin_bucket_index) 00940 _M_begin_bucket_index = __n; 00941 return iterator(__new_node, _M_buckets + __n); 00942 } 00943 __catch(...) 00944 { 00945 _M_deallocate_node(__new_node); 00946 __throw_exception_again; 00947 } 00948 } 00949 00950 // Insert v if no element with its key is already present. 00951 template<typename _Key, typename _Value, 00952 typename _Allocator, typename _ExtractKey, typename _Equal, 00953 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00954 bool __chc, bool __cit, bool __uk> 00955 template<typename _Arg> 00956 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 00957 _ExtractKey, _Equal, _H1, 00958 _H2, _Hash, _RehashPolicy, 00959 __chc, __cit, __uk>::iterator, bool> 00960 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00961 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00962 _M_insert(_Arg&& __v, std::true_type) 00963 { 00964 const key_type& __k = this->_M_extract(__v); 00965 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00966 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00967 00968 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code)) 00969 return std::make_pair(iterator(__p, _M_buckets + __n), false); 00970 return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v), 00971 __n, __code), true); 00972 } 00973 00974 // Insert v unconditionally. 00975 template<typename _Key, typename _Value, 00976 typename _Allocator, typename _ExtractKey, typename _Equal, 00977 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00978 bool __chc, bool __cit, bool __uk> 00979 template<typename _Arg> 00980 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00981 _H1, _H2, _Hash, _RehashPolicy, 00982 __chc, __cit, __uk>::iterator 00983 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00984 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00985 _M_insert(_Arg&& __v, std::false_type) 00986 { 00987 std::pair<bool, std::size_t> __do_rehash 00988 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 00989 _M_element_count, 1); 00990 if (__do_rehash.first) 00991 _M_rehash(__do_rehash.second); 00992 00993 const key_type& __k = this->_M_extract(__v); 00994 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00995 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00996 00997 // First find the node, avoid leaking new_node if compare throws. 00998 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code); 00999 _Node* __new_node = _M_allocate_node(std::forward<_Arg>(__v)); 01000 01001 if (__prev) 01002 { 01003 __new_node->_M_next = __prev->_M_next; 01004 __prev->_M_next = __new_node; 01005 } 01006 else 01007 { 01008 __new_node->_M_next = _M_buckets[__n]; 01009 _M_buckets[__n] = __new_node; 01010 if (__n < _M_begin_bucket_index) 01011 _M_begin_bucket_index = __n; 01012 } 01013 this->_M_store_code(__new_node, __code); 01014 01015 ++_M_element_count; 01016 return iterator(__new_node, _M_buckets + __n); 01017 } 01018 01019 template<typename _Key, typename _Value, 01020 typename _Allocator, typename _ExtractKey, typename _Equal, 01021 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01022 bool __chc, bool __cit, bool __uk> 01023 template<typename _InputIterator> 01024 void 01025 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01026 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01027 insert(_InputIterator __first, _InputIterator __last) 01028 { 01029 size_type __n_elt = __detail::__distance_fw(__first, __last); 01030 std::pair<bool, std::size_t> __do_rehash 01031 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01032 _M_element_count, __n_elt); 01033 if (__do_rehash.first) 01034 _M_rehash(__do_rehash.second); 01035 01036 for (; __first != __last; ++__first) 01037 this->insert(*__first); 01038 } 01039 01040 template<typename _Key, typename _Value, 01041 typename _Allocator, typename _ExtractKey, typename _Equal, 01042 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01043 bool __chc, bool __cit, bool __uk> 01044 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01045 _H1, _H2, _Hash, _RehashPolicy, 01046 __chc, __cit, __uk>::iterator 01047 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01048 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01049 erase(const_iterator __it) 01050 { 01051 iterator __result(__it._M_cur_node, __it._M_cur_bucket); 01052 ++__result; 01053 01054 _Node* __cur = *__it._M_cur_bucket; 01055 if (__cur == __it._M_cur_node) 01056 { 01057 *__it._M_cur_bucket = __cur->_M_next; 01058 01059 // If _M_begin_bucket_index no longer indexes the first non-empty 01060 // bucket - its single node is being erased - update it. 01061 if (!_M_buckets[_M_begin_bucket_index]) 01062 _M_begin_bucket_index = __result._M_cur_bucket - _M_buckets; 01063 } 01064 else 01065 { 01066 _Node* __next = __cur->_M_next; 01067 while (__next != __it._M_cur_node) 01068 { 01069 __cur = __next; 01070 __next = __cur->_M_next; 01071 } 01072 __cur->_M_next = __next->_M_next; 01073 } 01074 01075 _M_deallocate_node(__it._M_cur_node); 01076 --_M_element_count; 01077 01078 return __result; 01079 } 01080 01081 template<typename _Key, typename _Value, 01082 typename _Allocator, typename _ExtractKey, typename _Equal, 01083 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01084 bool __chc, bool __cit, bool __uk> 01085 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01086 _H1, _H2, _Hash, _RehashPolicy, 01087 __chc, __cit, __uk>::size_type 01088 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01089 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01090 erase(const key_type& __k) 01091 { 01092 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 01093 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 01094 size_type __result = 0; 01095 01096 _Node** __slot = _M_buckets + __n; 01097 while (*__slot && !this->_M_compare(__k, __code, *__slot)) 01098 __slot = &((*__slot)->_M_next); 01099 01100 _Node** __saved_slot = 0; 01101 while (*__slot && this->_M_compare(__k, __code, *__slot)) 01102 { 01103 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01104 // 526. Is it undefined if a function in the standard changes 01105 // in parameters? 01106 if (std::__addressof(this->_M_extract((*__slot)->_M_v)) 01107 != std::__addressof(__k)) 01108 { 01109 _Node* __p = *__slot; 01110 *__slot = __p->_M_next; 01111 _M_deallocate_node(__p); 01112 --_M_element_count; 01113 ++__result; 01114 } 01115 else 01116 { 01117 __saved_slot = __slot; 01118 __slot = &((*__slot)->_M_next); 01119 } 01120 } 01121 01122 if (__saved_slot) 01123 { 01124 _Node* __p = *__saved_slot; 01125 *__saved_slot = __p->_M_next; 01126 _M_deallocate_node(__p); 01127 --_M_element_count; 01128 ++__result; 01129 } 01130 01131 // If the entire bucket indexed by _M_begin_bucket_index has been 01132 // erased look forward for the first non-empty bucket. 01133 if (!_M_buckets[_M_begin_bucket_index]) 01134 { 01135 if (!_M_element_count) 01136 _M_begin_bucket_index = _M_bucket_count; 01137 else 01138 { 01139 ++_M_begin_bucket_index; 01140 while (!_M_buckets[_M_begin_bucket_index]) 01141 ++_M_begin_bucket_index; 01142 } 01143 } 01144 01145 return __result; 01146 } 01147 01148 // ??? This could be optimized by taking advantage of the bucket 01149 // structure, but it's not clear that it's worth doing. It probably 01150 // wouldn't even be an optimization unless the load factor is large. 01151 template<typename _Key, typename _Value, 01152 typename _Allocator, typename _ExtractKey, typename _Equal, 01153 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01154 bool __chc, bool __cit, bool __uk> 01155 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01156 _H1, _H2, _Hash, _RehashPolicy, 01157 __chc, __cit, __uk>::iterator 01158 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01159 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01160 erase(const_iterator __first, const_iterator __last) 01161 { 01162 while (__first != __last) 01163 __first = this->erase(__first); 01164 return iterator(__last._M_cur_node, __last._M_cur_bucket); 01165 } 01166 01167 template<typename _Key, typename _Value, 01168 typename _Allocator, typename _ExtractKey, typename _Equal, 01169 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01170 bool __chc, bool __cit, bool __uk> 01171 void 01172 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01173 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01174 clear() 01175 { 01176 _M_deallocate_nodes(_M_buckets, _M_bucket_count); 01177 _M_element_count = 0; 01178 _M_begin_bucket_index = _M_bucket_count; 01179 } 01180 01181 template<typename _Key, typename _Value, 01182 typename _Allocator, typename _ExtractKey, typename _Equal, 01183 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01184 bool __chc, bool __cit, bool __uk> 01185 void 01186 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01187 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01188 rehash(size_type __n) 01189 { 01190 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), 01191 _M_rehash_policy._M_bkt_for_elements(_M_element_count 01192 + 1))); 01193 } 01194 01195 template<typename _Key, typename _Value, 01196 typename _Allocator, typename _ExtractKey, typename _Equal, 01197 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01198 bool __chc, bool __cit, bool __uk> 01199 void 01200 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01201 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01202 _M_rehash(size_type __n) 01203 { 01204 _Node** __new_array = _M_allocate_buckets(__n); 01205 __try 01206 { 01207 _M_begin_bucket_index = __n; 01208 for (size_type __i = 0; __i < _M_bucket_count; ++__i) 01209 while (_Node* __p = _M_buckets[__i]) 01210 { 01211 std::size_t __new_index = this->_M_bucket_index(__p, __n); 01212 _M_buckets[__i] = __p->_M_next; 01213 __p->_M_next = __new_array[__new_index]; 01214 __new_array[__new_index] = __p; 01215 if (__new_index < _M_begin_bucket_index) 01216 _M_begin_bucket_index = __new_index; 01217 } 01218 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 01219 _M_bucket_count = __n; 01220 _M_buckets = __new_array; 01221 } 01222 __catch(...) 01223 { 01224 // A failure here means that a hash function threw an exception. 01225 // We can't restore the previous state without calling the hash 01226 // function again, so the only sensible recovery is to delete 01227 // everything. 01228 _M_deallocate_nodes(__new_array, __n); 01229 _M_deallocate_buckets(__new_array, __n); 01230 _M_deallocate_nodes(_M_buckets, _M_bucket_count); 01231 _M_element_count = 0; 01232 _M_begin_bucket_index = _M_bucket_count; 01233 __throw_exception_again; 01234 } 01235 } 01236 01237 _GLIBCXX_END_NAMESPACE_VERSION 01238 } // namespace std 01239 01240 #endif // _HASHTABLE_H