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
00061 #ifndef _HASH_MAP
00062 #define _HASH_MAP 1
00063
00064 #include <ext/hashtable.h>
00065 #include <bits/concept_check.h>
00066
00067 namespace __gnu_cxx
00068 {
00069 using std::equal_to;
00070 using std::allocator;
00071 using std::pair;
00072 using std::_Select1st;
00073
00074
00075
00076 template<class _Key, class _Tp, class _HashFcn = hash<_Key>,
00077 class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
00078 class hash_map;
00079
00080 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
00081 inline bool
00082 operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&,
00083 const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&);
00084
00090 template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
00091 class _Alloc>
00092 class hash_map
00093 {
00094 private:
00095 typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFcn,
00096 _Select1st<pair<const _Key, _Tp> >,
00097 _EqualKey, _Alloc> _Ht;
00098
00099 _Ht _M_ht;
00100
00101 public:
00102 typedef typename _Ht::key_type key_type;
00103 typedef _Tp data_type;
00104 typedef _Tp mapped_type;
00105 typedef typename _Ht::value_type value_type;
00106 typedef typename _Ht::hasher hasher;
00107 typedef typename _Ht::key_equal key_equal;
00108
00109 typedef typename _Ht::size_type size_type;
00110 typedef typename _Ht::difference_type difference_type;
00111 typedef typename _Ht::pointer pointer;
00112 typedef typename _Ht::const_pointer const_pointer;
00113 typedef typename _Ht::reference reference;
00114 typedef typename _Ht::const_reference const_reference;
00115
00116 typedef typename _Ht::iterator iterator;
00117 typedef typename _Ht::const_iterator const_iterator;
00118
00119 typedef typename _Ht::allocator_type allocator_type;
00120
00121 hasher
00122 hash_funct() const
00123 { return _M_ht.hash_funct(); }
00124
00125 key_equal
00126 key_eq() const
00127 { return _M_ht.key_eq(); }
00128
00129 allocator_type
00130 get_allocator() const
00131 { return _M_ht.get_allocator(); }
00132
00133 public:
00134 hash_map()
00135 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00136
00137 explicit
00138 hash_map(size_type __n)
00139 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00140
00141 hash_map(size_type __n, const hasher& __hf)
00142 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00143
00144 hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
00145 const allocator_type& __a = allocator_type())
00146 : _M_ht(__n, __hf, __eql, __a) {}
00147
00148 template <class _InputIterator>
00149 hash_map(_InputIterator __f, _InputIterator __l)
00150 : _M_ht(100, hasher(), key_equal(), allocator_type())
00151 { _M_ht.insert_unique(__f, __l); }
00152
00153 template <class _InputIterator>
00154 hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
00155 : _M_ht(__n, hasher(), key_equal(), allocator_type())
00156 { _M_ht.insert_unique(__f, __l); }
00157
00158 template <class _InputIterator>
00159 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
00160 const hasher& __hf)
00161 : _M_ht(__n, __hf, key_equal(), allocator_type())
00162 { _M_ht.insert_unique(__f, __l); }
00163
00164 template <class _InputIterator>
00165 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
00166 const hasher& __hf, const key_equal& __eql,
00167 const allocator_type& __a = allocator_type())
00168 : _M_ht(__n, __hf, __eql, __a)
00169 { _M_ht.insert_unique(__f, __l); }
00170
00171 public:
00172 size_type
00173 size() const
00174 { return _M_ht.size(); }
00175
00176 size_type
00177 max_size() const
00178 { return _M_ht.max_size(); }
00179
00180 bool
00181 empty() const
00182 { return _M_ht.empty(); }
00183
00184 void
00185 swap(hash_map& __hs)
00186 { _M_ht.swap(__hs._M_ht); }
00187
00188 template <class _K1, class _T1, class _HF, class _EqK, class _Al>
00189 friend bool
00190 operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
00191 const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
00192
00193 iterator
00194 begin()
00195 { return _M_ht.begin(); }
00196
00197 iterator
00198 end()
00199 { return _M_ht.end(); }
00200
00201 const_iterator
00202 begin() const
00203 { return _M_ht.begin(); }
00204
00205 const_iterator
00206 end() const
00207 { return _M_ht.end(); }
00208
00209 public:
00210 pair<iterator, bool>
00211 insert(const value_type& __obj)
00212 { return _M_ht.insert_unique(__obj); }
00213
00214 template <class _InputIterator>
00215 void
00216 insert(_InputIterator __f, _InputIterator __l)
00217 { _M_ht.insert_unique(__f, __l); }
00218
00219 pair<iterator, bool>
00220 insert_noresize(const value_type& __obj)
00221 { return _M_ht.insert_unique_noresize(__obj); }
00222
00223 iterator
00224 find(const key_type& __key)
00225 { return _M_ht.find(__key); }
00226
00227 const_iterator
00228 find(const key_type& __key) const
00229 { return _M_ht.find(__key); }
00230
00231 _Tp&
00232 operator[](const key_type& __key)
00233 { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
00234
00235 size_type
00236 count(const key_type& __key) const
00237 { return _M_ht.count(__key); }
00238
00239 pair<iterator, iterator>
00240 equal_range(const key_type& __key)
00241 { return _M_ht.equal_range(__key); }
00242
00243 pair<const_iterator, const_iterator>
00244 equal_range(const key_type& __key) const
00245 { return _M_ht.equal_range(__key); }
00246
00247 size_type
00248 erase(const key_type& __key)
00249 {return _M_ht.erase(__key); }
00250
00251 void
00252 erase(iterator __it)
00253 { _M_ht.erase(__it); }
00254
00255 void
00256 erase(iterator __f, iterator __l)
00257 { _M_ht.erase(__f, __l); }
00258
00259 void
00260 clear()
00261 { _M_ht.clear(); }
00262
00263 void
00264 resize(size_type __hint)
00265 { _M_ht.resize(__hint); }
00266
00267 size_type
00268 bucket_count() const
00269 { return _M_ht.bucket_count(); }
00270
00271 size_type
00272 max_bucket_count() const
00273 { return _M_ht.max_bucket_count(); }
00274
00275 size_type
00276 elems_in_bucket(size_type __n) const
00277 { return _M_ht.elems_in_bucket(__n); }
00278 };
00279
00280 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
00281 inline bool
00282 operator==(const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,
00283 const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2)
00284 { return __hm1._M_ht == __hm2._M_ht; }
00285
00286 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
00287 inline bool
00288 operator!=(const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,
00289 const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2)
00290 { return !(__hm1 == __hm2); }
00291
00292 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
00293 inline void
00294 swap(hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,
00295 hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2)
00296 { __hm1.swap(__hm2); }
00297
00298
00299
00300 template <class _Key, class _Tp,
00301 class _HashFcn = hash<_Key>,
00302 class _EqualKey = equal_to<_Key>,
00303 class _Alloc = allocator<_Tp> >
00304 class hash_multimap;
00305
00306 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
00307 inline bool
00308 operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
00309 const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2);
00310
00316 template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
00317 class _Alloc>
00318 class hash_multimap
00319 {
00320
00321 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
00322 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00323 __glibcxx_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept)
00324 __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
00325
00326 private:
00327 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn,
00328 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
00329 _Ht;
00330
00331 _Ht _M_ht;
00332
00333 public:
00334 typedef typename _Ht::key_type key_type;
00335 typedef _Tp data_type;
00336 typedef _Tp mapped_type;
00337 typedef typename _Ht::value_type value_type;
00338 typedef typename _Ht::hasher hasher;
00339 typedef typename _Ht::key_equal key_equal;
00340
00341 typedef typename _Ht::size_type size_type;
00342 typedef typename _Ht::difference_type difference_type;
00343 typedef typename _Ht::pointer pointer;
00344 typedef typename _Ht::const_pointer const_pointer;
00345 typedef typename _Ht::reference reference;
00346 typedef typename _Ht::const_reference const_reference;
00347
00348 typedef typename _Ht::iterator iterator;
00349 typedef typename _Ht::const_iterator const_iterator;
00350
00351 typedef typename _Ht::allocator_type allocator_type;
00352
00353 hasher
00354 hash_funct() const
00355 { return _M_ht.hash_funct(); }
00356
00357 key_equal
00358 key_eq() const
00359 { return _M_ht.key_eq(); }
00360
00361 allocator_type
00362 get_allocator() const
00363 { return _M_ht.get_allocator(); }
00364
00365 public:
00366 hash_multimap()
00367 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00368
00369 explicit
00370 hash_multimap(size_type __n)
00371 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00372
00373 hash_multimap(size_type __n, const hasher& __hf)
00374 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00375
00376 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
00377 const allocator_type& __a = allocator_type())
00378 : _M_ht(__n, __hf, __eql, __a) {}
00379
00380 template <class _InputIterator>
00381 hash_multimap(_InputIterator __f, _InputIterator __l)
00382 : _M_ht(100, hasher(), key_equal(), allocator_type())
00383 { _M_ht.insert_equal(__f, __l); }
00384
00385 template <class _InputIterator>
00386 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
00387 : _M_ht(__n, hasher(), key_equal(), allocator_type())
00388 { _M_ht.insert_equal(__f, __l); }
00389
00390 template <class _InputIterator>
00391 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
00392 const hasher& __hf)
00393 : _M_ht(__n, __hf, key_equal(), allocator_type())
00394 { _M_ht.insert_equal(__f, __l); }
00395
00396 template <class _InputIterator>
00397 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
00398 const hasher& __hf, const key_equal& __eql,
00399 const allocator_type& __a = allocator_type())
00400 : _M_ht(__n, __hf, __eql, __a)
00401 { _M_ht.insert_equal(__f, __l); }
00402
00403 public:
00404 size_type
00405 size() const
00406 { return _M_ht.size(); }
00407
00408 size_type
00409 max_size() const
00410 { return _M_ht.max_size(); }
00411
00412 bool
00413 empty() const
00414 { return _M_ht.empty(); }
00415
00416 void
00417 swap(hash_multimap& __hs)
00418 { _M_ht.swap(__hs._M_ht); }
00419
00420 template <class _K1, class _T1, class _HF, class _EqK, class _Al>
00421 friend bool
00422 operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
00423 const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
00424
00425 iterator
00426 begin()
00427 { return _M_ht.begin(); }
00428
00429 iterator
00430 end()
00431 { return _M_ht.end(); }
00432
00433 const_iterator
00434 begin() const
00435 { return _M_ht.begin(); }
00436
00437 const_iterator
00438 end() const
00439 { return _M_ht.end(); }
00440
00441 public:
00442 iterator
00443 insert(const value_type& __obj)
00444 { return _M_ht.insert_equal(__obj); }
00445
00446 template <class _InputIterator>
00447 void
00448 insert(_InputIterator __f, _InputIterator __l)
00449 { _M_ht.insert_equal(__f,__l); }
00450
00451 iterator
00452 insert_noresize(const value_type& __obj)
00453 { return _M_ht.insert_equal_noresize(__obj); }
00454
00455 iterator
00456 find(const key_type& __key)
00457 { return _M_ht.find(__key); }
00458
00459 const_iterator
00460 find(const key_type& __key) const
00461 { return _M_ht.find(__key); }
00462
00463 size_type
00464 count(const key_type& __key) const
00465 { return _M_ht.count(__key); }
00466
00467 pair<iterator, iterator>
00468 equal_range(const key_type& __key)
00469 { return _M_ht.equal_range(__key); }
00470
00471 pair<const_iterator, const_iterator>
00472 equal_range(const key_type& __key) const
00473 { return _M_ht.equal_range(__key); }
00474
00475 size_type
00476 erase(const key_type& __key)
00477 { return _M_ht.erase(__key); }
00478
00479 void
00480 erase(iterator __it)
00481 { _M_ht.erase(__it); }
00482
00483 void
00484 erase(iterator __f, iterator __l)
00485 { _M_ht.erase(__f, __l); }
00486
00487 void
00488 clear()
00489 { _M_ht.clear(); }
00490
00491 public:
00492 void
00493 resize(size_type __hint)
00494 { _M_ht.resize(__hint); }
00495
00496 size_type
00497 bucket_count() const
00498 { return _M_ht.bucket_count(); }
00499
00500 size_type
00501 max_bucket_count() const
00502 { return _M_ht.max_bucket_count(); }
00503
00504 size_type
00505 elems_in_bucket(size_type __n) const
00506 { return _M_ht.elems_in_bucket(__n); }
00507 };
00508
00509 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
00510 inline bool
00511 operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
00512 const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
00513 { return __hm1._M_ht == __hm2._M_ht; }
00514
00515 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
00516 inline bool
00517 operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
00518 const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
00519 { return !(__hm1 == __hm2); }
00520
00521 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
00522 inline void
00523 swap(hash_multimap<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,
00524 hash_multimap<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2)
00525 { __hm1.swap(__hm2); }
00526
00527 }
00528
00529 namespace std
00530 {
00531
00532
00533
00534 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
00535 class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,
00536 _EqKey, _Alloc> >
00537 {
00538 protected:
00539 typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
00540 _Container;
00541 _Container* container;
00542
00543 public:
00544 typedef _Container container_type;
00545 typedef output_iterator_tag iterator_category;
00546 typedef void value_type;
00547 typedef void difference_type;
00548 typedef void pointer;
00549 typedef void reference;
00550
00551 insert_iterator(_Container& __x)
00552 : container(&__x) {}
00553
00554 insert_iterator(_Container& __x, typename _Container::iterator)
00555 : container(&__x) {}
00556
00557 insert_iterator<_Container>&
00558 operator=(const typename _Container::value_type& __value)
00559 {
00560 container->insert(__value);
00561 return *this;
00562 }
00563
00564 insert_iterator<_Container>&
00565 operator*()
00566 { return *this; }
00567
00568 insert_iterator<_Container>&
00569 operator++() { return *this; }
00570
00571 insert_iterator<_Container>&
00572 operator++(int)
00573 { return *this; }
00574 };
00575
00576 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
00577 class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
00578 _EqKey, _Alloc> >
00579 {
00580 protected:
00581 typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
00582 _Container;
00583 _Container* container;
00584 typename _Container::iterator iter;
00585
00586 public:
00587 typedef _Container container_type;
00588 typedef output_iterator_tag iterator_category;
00589 typedef void value_type;
00590 typedef void difference_type;
00591 typedef void pointer;
00592 typedef void reference;
00593
00594 insert_iterator(_Container& __x)
00595 : container(&__x) {}
00596
00597 insert_iterator(_Container& __x, typename _Container::iterator)
00598 : container(&__x) {}
00599
00600 insert_iterator<_Container>&
00601 operator=(const typename _Container::value_type& __value)
00602 {
00603 container->insert(__value);
00604 return *this;
00605 }
00606
00607 insert_iterator<_Container>&
00608 operator*()
00609 { return *this; }
00610
00611 insert_iterator<_Container>&
00612 operator++()
00613 { return *this; }
00614
00615 insert_iterator<_Container>&
00616 operator++(int)
00617 { return *this; }
00618 };
00619 }
00620
00621 #ifdef _GLIBCXX_DEBUG
00622 # include <debug/hash_map>
00623 #endif
00624
00625 #endif