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