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