00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
#ifndef _HASHTABLE_H
00063
#define _HASHTABLE_H 1
00064
00065
00066
00067
00068
#include <vector>
00069
#include <iterator>
00070
#include <bits/stl_algo.h>
00071
#include <bits/stl_function.h>
00072
#include <ext/hash_fun.h>
00073
00074
namespace __gnu_cxx
00075 {
00076
using std::size_t;
00077
using std::ptrdiff_t;
00078
using std::forward_iterator_tag;
00079
using std::input_iterator_tag;
00080
using std::_Construct;
00081
using std::_Destroy;
00082
using std::distance;
00083
using std::vector;
00084
using std::pair;
00085
using std::__iterator_category;
00086
00087
template <
class _Val>
00088
struct _Hashtable_node
00089 {
00090 _Hashtable_node* _M_next;
00091 _Val _M_val;
00092 };
00093
00094
template <
class _Val,
class _Key,
class _HashFcn,
class _ExtractKey,
00095
class _EqualKey,
class _Alloc =
std::allocator<_Val> >
00096
class hashtable;
00097
00098
template <
class _Val,
class _Key,
class _HashFcn,
00099
class _ExtractKey,
class _EqualKey,
class _Alloc>
00100
struct _Hashtable_iterator;
00101
00102
template <
class _Val,
class _Key,
class _HashFcn,
00103
class _ExtractKey,
class _EqualKey,
class _Alloc>
00104
struct _Hashtable_const_iterator;
00105
00106
template <
class _Val,
class _Key,
class _HashFcn,
00107
class _ExtractKey,
class _EqualKey,
class _Alloc>
00108
struct _Hashtable_iterator
00109 {
00110
typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
00111 _Hashtable;
00112
typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
00113 _ExtractKey, _EqualKey, _Alloc>
00114 iterator;
00115
typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
00116 _ExtractKey, _EqualKey, _Alloc>
00117 const_iterator;
00118
typedef _Hashtable_node<_Val> _Node;
00119
typedef forward_iterator_tag iterator_category;
00120
typedef _Val value_type;
00121
typedef ptrdiff_t difference_type;
00122
typedef size_t size_type;
00123
typedef _Val& reference;
00124
typedef _Val* pointer;
00125
00126 _Node* _M_cur;
00127 _Hashtable* _M_ht;
00128
00129 _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
00130 : _M_cur(__n), _M_ht(__tab) {}
00131
00132 _Hashtable_iterator() {}
00133
00134 reference
00135 operator*()
const
00136
{
return _M_cur->_M_val; }
00137
00138 pointer
00139 operator->()
const
00140
{
return &(operator*()); }
00141
00142 iterator&
00143 operator++();
00144
00145 iterator
00146 operator++(
int);
00147
00148
bool
00149 operator==(
const iterator& __it)
const
00150
{
return _M_cur == __it._M_cur; }
00151
00152
bool
00153 operator!=(
const iterator& __it)
const
00154
{
return _M_cur != __it._M_cur; }
00155 };
00156
00157
template <
class _Val,
class _Key,
class _HashFcn,
00158
class _ExtractKey,
class _EqualKey,
class _Alloc>
00159
struct _Hashtable_const_iterator
00160 {
00161
typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
00162 _Hashtable;
00163
typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
00164 _ExtractKey,_EqualKey,_Alloc>
00165 iterator;
00166
typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
00167 _ExtractKey, _EqualKey, _Alloc>
00168 const_iterator;
00169
typedef _Hashtable_node<_Val> _Node;
00170
00171
typedef forward_iterator_tag iterator_category;
00172
typedef _Val value_type;
00173
typedef ptrdiff_t difference_type;
00174
typedef size_t size_type;
00175
typedef const _Val& reference;
00176
typedef const _Val* pointer;
00177
00178
const _Node* _M_cur;
00179
const _Hashtable* _M_ht;
00180
00181 _Hashtable_const_iterator(
const _Node* __n,
const _Hashtable* __tab)
00182 : _M_cur(__n), _M_ht(__tab) {}
00183
00184 _Hashtable_const_iterator() {}
00185
00186 _Hashtable_const_iterator(
const iterator& __it)
00187 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) {}
00188
00189 reference
00190 operator*()
const
00191
{
return _M_cur->_M_val; }
00192
00193 pointer
00194 operator->()
const
00195
{
return &(operator*()); }
00196
00197 const_iterator&
00198 operator++();
00199
00200 const_iterator
00201 operator++(
int);
00202
00203
bool
00204 operator==(
const const_iterator& __it)
const
00205
{
return _M_cur == __it._M_cur; }
00206
00207
bool
00208 operator!=(
const const_iterator& __it)
const
00209
{
return _M_cur != __it._M_cur; }
00210 };
00211
00212
00213
enum { _S_num_primes = 28 };
00214
00215
static const unsigned long __stl_prime_list[_S_num_primes] =
00216 {
00217 53ul, 97ul, 193ul, 389ul, 769ul,
00218 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
00219 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
00220 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
00221 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
00222 1610612741ul, 3221225473ul, 4294967291ul
00223 };
00224
00225
inline unsigned long
00226 __stl_next_prime(
unsigned long __n)
00227 {
00228
const unsigned long* __first = __stl_prime_list;
00229
const unsigned long* __last = __stl_prime_list + (
int)_S_num_primes;
00230
const unsigned long* pos =
std::lower_bound(__first, __last, __n);
00231
return pos == __last ? *(__last - 1) : *pos;
00232 }
00233
00234
00235
00236
template <
class _Val,
class _Key,
class _HF,
class _Ex,
00237
class _Eq,
class _All>
00238
class hashtable;
00239
00240
template <
class _Val,
class _Key,
class _HF,
class _Ex,
00241
class _Eq,
class _All>
00242
bool
00243 operator==(
const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
00244
const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255
template <
class _Val,
class _Key,
class _HashFcn,
00256
class _ExtractKey,
class _EqualKey,
class _Alloc>
00257
class hashtable
00258 {
00259
public:
00260
typedef _Key key_type;
00261
typedef _Val value_type;
00262
typedef _HashFcn hasher;
00263
typedef _EqualKey key_equal;
00264
00265
typedef size_t size_type;
00266
typedef ptrdiff_t difference_type;
00267
typedef value_type* pointer;
00268
typedef const value_type* const_pointer;
00269
typedef value_type& reference;
00270
typedef const value_type& const_reference;
00271
00272 hasher
00273 hash_funct()
const
00274
{
return _M_hash; }
00275
00276 key_equal
00277 key_eq()
const
00278
{
return _M_equals; }
00279
00280
private:
00281
typedef _Hashtable_node<_Val> _Node;
00282
00283
public:
00284
typedef _Alloc allocator_type;
00285 allocator_type
00286 get_allocator()
const
00287
{
return _M_node_allocator; }
00288
00289
private:
00290
typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc;
00291
typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc;
00292
typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type;
00293
00294 _Node_Alloc _M_node_allocator;
00295
00296 _Node*
00297 _M_get_node()
00298 {
return _M_node_allocator.allocate(1); }
00299
00300
void
00301 _M_put_node(_Node* __p)
00302 { _M_node_allocator.deallocate(__p, 1); }
00303
00304
private:
00305 hasher _M_hash;
00306 key_equal _M_equals;
00307 _ExtractKey _M_get_key;
00308 _Vector_type _M_buckets;
00309 size_type _M_num_elements;
00310
00311
public:
00312
typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
00313 _EqualKey, _Alloc>
00314 iterator;
00315
typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
00316 _EqualKey, _Alloc>
00317 const_iterator;
00318
00319
friend struct
00320
_Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
00321
00322
friend struct
00323
_Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
00324 _EqualKey, _Alloc>;
00325
00326
public:
00327 hashtable(size_type __n,
const _HashFcn& __hf,
00328
const _EqualKey& __eql,
const _ExtractKey& __ext,
00329
const allocator_type& __a = allocator_type())
00330 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
00331 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
00332 { _M_initialize_buckets(__n); }
00333
00334 hashtable(size_type __n,
const _HashFcn& __hf,
00335
const _EqualKey& __eql,
00336
const allocator_type& __a = allocator_type())
00337 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
00338 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
00339 { _M_initialize_buckets(__n); }
00340
00341 hashtable(
const hashtable& __ht)
00342 : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),
00343 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
00344 _M_buckets(__ht.get_allocator()), _M_num_elements(0)
00345 { _M_copy_from(__ht); }
00346
00347 hashtable&
00348 operator= (
const hashtable& __ht)
00349 {
00350
if (&__ht !=
this)
00351 {
00352 clear();
00353 _M_hash = __ht._M_hash;
00354 _M_equals = __ht._M_equals;
00355 _M_get_key = __ht._M_get_key;
00356 _M_copy_from(__ht);
00357 }
00358
return *
this;
00359 }
00360
00361 ~hashtable()
00362 { clear(); }
00363
00364 size_type
00365 size()
const
00366
{
return _M_num_elements; }
00367
00368 size_type
00369 max_size()
const
00370
{
return size_type(-1); }
00371
00372
bool
00373 empty()
const
00374
{
return size() == 0; }
00375
00376
void
00377
swap(hashtable& __ht)
00378 {
00379
std::swap(_M_hash, __ht._M_hash);
00380
std::swap(_M_equals, __ht._M_equals);
00381
std::swap(_M_get_key, __ht._M_get_key);
00382 _M_buckets.swap(__ht._M_buckets);
00383
std::swap(_M_num_elements, __ht._M_num_elements);
00384 }
00385
00386 iterator
00387 begin()
00388 {
00389
for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
00390
if (_M_buckets[__n])
00391
return iterator(_M_buckets[__n],
this);
00392
return end();
00393 }
00394
00395 iterator
00396 end()
00397 {
return iterator(0,
this); }
00398
00399 const_iterator
00400 begin()
const
00401
{
00402
for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
00403
if (_M_buckets[__n])
00404
return const_iterator(_M_buckets[__n],
this);
00405
return end();
00406 }
00407
00408 const_iterator
00409 end()
const
00410
{
return const_iterator(0,
this); }
00411
00412
template <
class _Vl,
class _Ky,
class _HF,
class _Ex,
class _Eq,
00413
class _Al>
00414
friend bool
00415 operator==(
const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
00416
const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
00417
00418
public:
00419 size_type
00420 bucket_count()
const
00421
{
return _M_buckets.size(); }
00422
00423 size_type
00424 max_bucket_count()
const
00425
{
return __stl_prime_list[(
int)_S_num_primes - 1]; }
00426
00427 size_type
00428 elems_in_bucket(size_type __bucket)
const
00429
{
00430 size_type __result = 0;
00431
for (_Node* __cur = _M_buckets[__bucket]; __cur; __cur = __cur->_M_next)
00432 __result += 1;
00433
return __result;
00434 }
00435
00436 pair<iterator, bool>
00437 insert_unique(
const value_type& __obj)
00438 {
00439 resize(_M_num_elements + 1);
00440
return insert_unique_noresize(__obj);
00441 }
00442
00443 iterator
00444 insert_equal(
const value_type& __obj)
00445 {
00446 resize(_M_num_elements + 1);
00447
return insert_equal_noresize(__obj);
00448 }
00449
00450 pair<iterator, bool>
00451 insert_unique_noresize(
const value_type& __obj);
00452
00453 iterator
00454 insert_equal_noresize(
const value_type& __obj);
00455
00456
template <
class _InputIterator>
00457
void
00458 insert_unique(_InputIterator __f, _InputIterator __l)
00459 { insert_unique(__f, __l, __iterator_category(__f)); }
00460
00461
template <
class _InputIterator>
00462
void
00463 insert_equal(_InputIterator __f, _InputIterator __l)
00464 { insert_equal(__f, __l, __iterator_category(__f)); }
00465
00466
template <
class _InputIterator>
00467
void
00468 insert_unique(_InputIterator __f, _InputIterator __l,
00469 input_iterator_tag)
00470 {
00471
for ( ; __f != __l; ++__f)
00472 insert_unique(*__f);
00473 }
00474
00475
template <
class _InputIterator>
00476
void
00477 insert_equal(_InputIterator __f, _InputIterator __l,
00478 input_iterator_tag)
00479 {
00480
for ( ; __f != __l; ++__f)
00481 insert_equal(*__f);
00482 }
00483
00484
template <
class _ForwardIterator>
00485
void
00486 insert_unique(_ForwardIterator __f, _ForwardIterator __l,
00487 forward_iterator_tag)
00488 {
00489 size_type __n =
distance(__f, __l);
00490 resize(_M_num_elements + __n);
00491
for ( ; __n > 0; --__n, ++__f)
00492 insert_unique_noresize(*__f);
00493 }
00494
00495
template <
class _ForwardIterator>
00496
void
00497 insert_equal(_ForwardIterator __f, _ForwardIterator __l,
00498 forward_iterator_tag)
00499 {
00500 size_type __n =
distance(__f, __l);
00501 resize(_M_num_elements + __n);
00502
for ( ; __n > 0; --__n, ++__f)
00503 insert_equal_noresize(*__f);
00504 }
00505
00506 reference
00507 find_or_insert(
const value_type& __obj);
00508
00509 iterator
00510 find(
const key_type& __key)
00511 {
00512 size_type __n = _M_bkt_num_key(__key);
00513 _Node* __first;
00514
for (__first = _M_buckets[__n];
00515 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
00516 __first = __first->_M_next)
00517 {}
00518
return iterator(__first,
this);
00519 }
00520
00521 const_iterator
00522 find(
const key_type& __key)
const
00523
{
00524 size_type __n = _M_bkt_num_key(__key);
00525
const _Node* __first;
00526
for (__first = _M_buckets[__n];
00527 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
00528 __first = __first->_M_next)
00529 {}
00530
return const_iterator(__first,
this);
00531 }
00532
00533 size_type
00534
count(
const key_type& __key)
const
00535
{
00536
const size_type __n = _M_bkt_num_key(__key);
00537 size_type __result = 0;
00538
00539
for (
const _Node* __cur = _M_buckets[__n]; __cur;
00540 __cur = __cur->_M_next)
00541
if (_M_equals(_M_get_key(__cur->_M_val), __key))
00542 ++__result;
00543
return __result;
00544 }
00545
00546 pair<iterator, iterator>
00547
equal_range(
const key_type& __key);
00548
00549 pair<const_iterator, const_iterator>
00550
equal_range(
const key_type& __key)
const;
00551
00552 size_type
00553 erase(
const key_type& __key);
00554
00555
void
00556 erase(
const iterator& __it);
00557
00558
void
00559 erase(iterator __first, iterator __last);
00560
00561
void
00562 erase(
const const_iterator& __it);
00563
00564
void
00565 erase(const_iterator __first, const_iterator __last);
00566
00567
void
00568 resize(size_type __num_elements_hint);
00569
00570
void
00571 clear();
00572
00573
private:
00574 size_type
00575 _M_next_size(size_type __n)
const
00576
{
return __stl_next_prime(__n); }
00577
00578
void
00579 _M_initialize_buckets(size_type __n)
00580 {
00581
const size_type __n_buckets = _M_next_size(__n);
00582 _M_buckets.reserve(__n_buckets);
00583 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
00584 _M_num_elements = 0;
00585 }
00586
00587 size_type
00588 _M_bkt_num_key(
const key_type& __key)
const
00589
{
return _M_bkt_num_key(__key, _M_buckets.size()); }
00590
00591 size_type
00592 _M_bkt_num(
const value_type& __obj)
const
00593
{
return _M_bkt_num_key(_M_get_key(__obj)); }
00594
00595 size_type
00596 _M_bkt_num_key(
const key_type& __key, size_t __n)
const
00597
{
return _M_hash(__key) % __n; }
00598
00599 size_type
00600 _M_bkt_num(
const value_type& __obj, size_t __n)
const
00601
{
return _M_bkt_num_key(_M_get_key(__obj), __n); }
00602
00603 _Node*
00604 _M_new_node(
const value_type& __obj)
00605 {
00606 _Node* __n = _M_get_node();
00607 __n->_M_next = 0;
00608
try
00609 {
00610 _Construct(&__n->_M_val, __obj);
00611
return __n;
00612 }
00613
catch(...)
00614 {
00615 _M_put_node(__n);
00616 __throw_exception_again;
00617 }
00618 }
00619
00620
void
00621 _M_delete_node(_Node* __n)
00622 {
00623 _Destroy(&__n->_M_val);
00624 _M_put_node(__n);
00625 }
00626
00627
void
00628 _M_erase_bucket(
const size_type __n, _Node* __first, _Node* __last);
00629
00630
void
00631 _M_erase_bucket(
const size_type __n, _Node* __last);
00632
00633
void
00634 _M_copy_from(
const hashtable& __ht);
00635 };
00636
00637
template <
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
00638
class _All>
00639 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
00640 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
00641 operator++()
00642 {
00643
const _Node* __old = _M_cur;
00644 _M_cur = _M_cur->_M_next;
00645
if (!_M_cur)
00646 {
00647 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
00648
while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
00649 _M_cur = _M_ht->_M_buckets[__bucket];
00650 }
00651
return *
this;
00652 }
00653
00654
template <
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
00655
class _All>
00656
inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
00657 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
00658 operator++(
int)
00659 {
00660 iterator __tmp = *
this;
00661 ++*
this;
00662
return __tmp;
00663 }
00664
00665
template <
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
00666
class _All>
00667 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
00668 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
00669 operator++()
00670 {
00671
const _Node* __old = _M_cur;
00672 _M_cur = _M_cur->_M_next;
00673
if (!_M_cur)
00674 {
00675 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
00676
while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
00677 _M_cur = _M_ht->_M_buckets[__bucket];
00678 }
00679
return *
this;
00680 }
00681
00682
template <
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
00683
class _All>
00684
inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
00685 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
00686 operator++(
int)
00687 {
00688 const_iterator __tmp = *
this;
00689 ++*
this;
00690
return __tmp;
00691 }
00692
00693
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00694
bool
00695
operator==(
const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
00696
const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
00697 {
00698
typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
00699
00700
if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
00701
return false;
00702
00703
for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
00704 {
00705 _Node* __cur1 = __ht1._M_buckets[__n];
00706 _Node* __cur2 = __ht2._M_buckets[__n];
00707
00708
for (; __cur1 && __cur2;
00709 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
00710 {}
00711
if (__cur1 || __cur2)
00712
return false;
00713
00714
for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
00715 __cur1 = __cur1->_M_next)
00716 {
00717
bool _found__cur1 =
false;
00718
for (_Node* __cur2 = __ht2._M_buckets[__n];
00719 __cur2; __cur2 = __cur2->_M_next)
00720 {
00721
if (__cur1->_M_val == __cur2->_M_val)
00722 {
00723 _found__cur1 =
true;
00724
break;
00725 }
00726 }
00727
if (!_found__cur1)
00728
return false;
00729 }
00730 }
00731
return true;
00732 }
00733
00734
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00735
inline bool
00736
operator!=(
const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
00737
const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
00738 {
return !(__ht1 == __ht2); }
00739
00740
template <
class _Val,
class _Key,
class _HF,
class _Extract,
class _EqKey,
00741
class _All>
00742
inline void
00743
swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
00744 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
00745 { __ht1.swap(__ht2); }
00746
00747
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00748 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
bool>
00749 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00750 insert_unique_noresize(
const value_type& __obj)
00751 {
00752
const size_type __n = _M_bkt_num(__obj);
00753 _Node* __first = _M_buckets[__n];
00754
00755
for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
00756
if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
00757
return pair<iterator, bool>(iterator(__cur,
this),
false);
00758
00759 _Node* __tmp = _M_new_node(__obj);
00760 __tmp->_M_next = __first;
00761 _M_buckets[__n] = __tmp;
00762 ++_M_num_elements;
00763
return pair<iterator, bool>(iterator(__tmp,
this),
true);
00764 }
00765
00766
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00767
typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator
00768 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00769 insert_equal_noresize(
const value_type& __obj)
00770 {
00771
const size_type __n = _M_bkt_num(__obj);
00772 _Node* __first = _M_buckets[__n];
00773
00774
for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
00775
if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
00776 {
00777 _Node* __tmp = _M_new_node(__obj);
00778 __tmp->_M_next = __cur->_M_next;
00779 __cur->_M_next = __tmp;
00780 ++_M_num_elements;
00781
return iterator(__tmp,
this);
00782 }
00783
00784 _Node* __tmp = _M_new_node(__obj);
00785 __tmp->_M_next = __first;
00786 _M_buckets[__n] = __tmp;
00787 ++_M_num_elements;
00788
return iterator(__tmp,
this);
00789 }
00790
00791
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00792
typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference
00793 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00794 find_or_insert(
const value_type& __obj)
00795 {
00796 resize(_M_num_elements + 1);
00797
00798 size_type __n = _M_bkt_num(__obj);
00799 _Node* __first = _M_buckets[__n];
00800
00801
for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
00802
if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
00803
return __cur->_M_val;
00804
00805 _Node* __tmp = _M_new_node(__obj);
00806 __tmp->_M_next = __first;
00807 _M_buckets[__n] = __tmp;
00808 ++_M_num_elements;
00809
return __tmp->_M_val;
00810 }
00811
00812
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00813 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
00814
typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator>
00815
hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00816
equal_range(
const key_type& __key)
00817 {
00818
typedef pair<iterator, iterator> _Pii;
00819
const size_type __n = _M_bkt_num_key(__key);
00820
00821
for (_Node* __first = _M_buckets[__n]; __first;
00822 __first = __first->_M_next)
00823
if (_M_equals(_M_get_key(__first->_M_val), __key))
00824 {
00825
for (_Node* __cur = __first->_M_next; __cur;
00826 __cur = __cur->_M_next)
00827
if (!_M_equals(_M_get_key(__cur->_M_val), __key))
00828
return _Pii(iterator(__first,
this), iterator(__cur,
this));
00829
for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
00830
if (_M_buckets[__m])
00831
return _Pii(iterator(__first,
this),
00832 iterator(_M_buckets[__m],
this));
00833
return _Pii(iterator(__first,
this), end());
00834 }
00835
return _Pii(end(), end());
00836 }
00837
00838
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00839 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
00840
typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator>
00841
hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00842
equal_range(
const key_type& __key)
const
00843
{
00844
typedef pair<const_iterator, const_iterator> _Pii;
00845
const size_type __n = _M_bkt_num_key(__key);
00846
00847
for (
const _Node* __first = _M_buckets[__n]; __first;
00848 __first = __first->_M_next)
00849 {
00850
if (_M_equals(_M_get_key(__first->_M_val), __key))
00851 {
00852
for (
const _Node* __cur = __first->_M_next; __cur;
00853 __cur = __cur->_M_next)
00854
if (!_M_equals(_M_get_key(__cur->_M_val), __key))
00855
return _Pii(const_iterator(__first,
this),
00856 const_iterator(__cur,
this));
00857
for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
00858
if (_M_buckets[__m])
00859
return _Pii(const_iterator(__first,
this),
00860 const_iterator(_M_buckets[__m],
this));
00861
return _Pii(const_iterator(__first,
this), end());
00862 }
00863 }
00864
return _Pii(end(), end());
00865 }
00866
00867
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00868
typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
00869 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00870 erase(
const key_type& __key)
00871 {
00872
const size_type __n = _M_bkt_num_key(__key);
00873 _Node* __first = _M_buckets[__n];
00874 size_type __erased = 0;
00875
00876
if (__first)
00877 {
00878 _Node* __cur = __first;
00879 _Node* __next = __cur->_M_next;
00880
while (__next)
00881 {
00882
if (_M_equals(_M_get_key(__next->_M_val), __key))
00883 {
00884 __cur->_M_next = __next->_M_next;
00885 _M_delete_node(__next);
00886 __next = __cur->_M_next;
00887 ++__erased;
00888 --_M_num_elements;
00889 }
00890
else
00891 {
00892 __cur = __next;
00893 __next = __cur->_M_next;
00894 }
00895 }
00896
if (_M_equals(_M_get_key(__first->_M_val), __key))
00897 {
00898 _M_buckets[__n] = __first->_M_next;
00899 _M_delete_node(__first);
00900 ++__erased;
00901 --_M_num_elements;
00902 }
00903 }
00904
return __erased;
00905 }
00906
00907
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00908
void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00909 erase(
const iterator& __it)
00910 {
00911 _Node* __p = __it._M_cur;
00912
if (__p)
00913 {
00914
const size_type __n = _M_bkt_num(__p->_M_val);
00915 _Node* __cur = _M_buckets[__n];
00916
00917
if (__cur == __p)
00918 {
00919 _M_buckets[__n] = __cur->_M_next;
00920 _M_delete_node(__cur);
00921 --_M_num_elements;
00922 }
00923
else
00924 {
00925 _Node* __next = __cur->_M_next;
00926
while (__next)
00927 {
00928
if (__next == __p)
00929 {
00930 __cur->_M_next = __next->_M_next;
00931 _M_delete_node(__next);
00932 --_M_num_elements;
00933
break;
00934 }
00935
else
00936 {
00937 __cur = __next;
00938 __next = __cur->_M_next;
00939 }
00940 }
00941 }
00942 }
00943 }
00944
00945
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00946
void
00947 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00948 erase(iterator __first, iterator __last)
00949 {
00950 size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val)
00951 : _M_buckets.size();
00952
00953 size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val)
00954 : _M_buckets.size();
00955
00956
if (__first._M_cur == __last._M_cur)
00957
return;
00958
else if (__f_bucket == __l_bucket)
00959 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
00960
else
00961 {
00962 _M_erase_bucket(__f_bucket, __first._M_cur, 0);
00963
for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
00964 _M_erase_bucket(__n, 0);
00965
if (__l_bucket != _M_buckets.size())
00966 _M_erase_bucket(__l_bucket, __last._M_cur);
00967 }
00968 }
00969
00970
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00971
inline void
00972 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00973 erase(const_iterator __first, const_iterator __last)
00974 {
00975 erase(iterator(const_cast<_Node*>(__first._M_cur),
00976 const_cast<hashtable*>(__first._M_ht)),
00977 iterator(const_cast<_Node*>(__last._M_cur),
00978 const_cast<hashtable*>(__last._M_ht)));
00979 }
00980
00981
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00982
inline void
00983 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00984 erase(
const const_iterator& __it)
00985 { erase(iterator(const_cast<_Node*>(__it._M_cur),
00986 const_cast<hashtable*>(__it._M_ht))); }
00987
00988
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
00989
void
00990 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00991 resize(size_type __num_elements_hint)
00992 {
00993
const size_type __old_n = _M_buckets.size();
00994
if (__num_elements_hint > __old_n)
00995 {
00996
const size_type __n = _M_next_size(__num_elements_hint);
00997
if (__n > __old_n)
00998 {
00999 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
01000
try
01001 {
01002
for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
01003 {
01004 _Node* __first = _M_buckets[__bucket];
01005
while (__first)
01006 {
01007 size_type __new_bucket = _M_bkt_num(__first->_M_val,
01008 __n);
01009 _M_buckets[__bucket] = __first->_M_next;
01010 __first->_M_next = __tmp[__new_bucket];
01011 __tmp[__new_bucket] = __first;
01012 __first = _M_buckets[__bucket];
01013 }
01014 }
01015 _M_buckets.swap(__tmp);
01016 }
01017
catch(...)
01018 {
01019
for (size_type __bucket = 0; __bucket < __tmp.size();
01020 ++__bucket)
01021 {
01022
while (__tmp[__bucket])
01023 {
01024 _Node* __next = __tmp[__bucket]->_M_next;
01025 _M_delete_node(__tmp[__bucket]);
01026 __tmp[__bucket] = __next;
01027 }
01028 }
01029 __throw_exception_again;
01030 }
01031 }
01032 }
01033 }
01034
01035
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
01036
void
01037 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
01038 _M_erase_bucket(
const size_type __n, _Node* __first, _Node* __last)
01039 {
01040 _Node* __cur = _M_buckets[__n];
01041
if (__cur == __first)
01042 _M_erase_bucket(__n, __last);
01043
else
01044 {
01045 _Node* __next;
01046
for (__next = __cur->_M_next;
01047 __next != __first;
01048 __cur = __next, __next = __cur->_M_next)
01049 ;
01050
while (__next != __last)
01051 {
01052 __cur->_M_next = __next->_M_next;
01053 _M_delete_node(__next);
01054 __next = __cur->_M_next;
01055 --_M_num_elements;
01056 }
01057 }
01058 }
01059
01060
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
01061
void
01062 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
01063 _M_erase_bucket(
const size_type __n, _Node* __last)
01064 {
01065 _Node* __cur = _M_buckets[__n];
01066
while (__cur != __last)
01067 {
01068 _Node* __next = __cur->_M_next;
01069 _M_delete_node(__cur);
01070 __cur = __next;
01071 _M_buckets[__n] = __cur;
01072 --_M_num_elements;
01073 }
01074 }
01075
01076
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
01077
void
01078 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
01079 clear()
01080 {
01081
for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
01082 {
01083 _Node* __cur = _M_buckets[__i];
01084
while (__cur != 0)
01085 {
01086 _Node* __next = __cur->_M_next;
01087 _M_delete_node(__cur);
01088 __cur = __next;
01089 }
01090 _M_buckets[__i] = 0;
01091 }
01092 _M_num_elements = 0;
01093 }
01094
01095
template <
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
01096
void
01097 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
01098 _M_copy_from(
const hashtable& __ht)
01099 {
01100 _M_buckets.clear();
01101 _M_buckets.reserve(__ht._M_buckets.size());
01102 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
01103
try
01104 {
01105
for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
01106
const _Node* __cur = __ht._M_buckets[__i];
01107
if (__cur)
01108 {
01109 _Node* __local_copy = _M_new_node(__cur->_M_val);
01110 _M_buckets[__i] = __local_copy;
01111
01112
for (_Node* __next = __cur->_M_next;
01113 __next;
01114 __cur = __next, __next = __cur->_M_next)
01115 {
01116 __local_copy->_M_next = _M_new_node(__next->_M_val);
01117 __local_copy = __local_copy->_M_next;
01118 }
01119 }
01120 }
01121 _M_num_elements = __ht._M_num_elements;
01122 }
01123
catch(...)
01124 {
01125 clear();
01126 __throw_exception_again;
01127 }
01128 }
01129 }
01130
01131
#endif