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