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