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
00062 #ifndef __SGI_STL_INTERNAL_HASH_MAP_H
00063 #define __SGI_STL_INTERNAL_HASH_MAP_H
00064
00065 #include <ext/stl_hashtable.h>
00066 #include <bits/concept_check.h>
00067
00068 namespace __gnu_cxx
00069 {
00070 using std::equal_to;
00071 using std::allocator;
00072 using std::pair;
00073 using std::_Select1st;
00074
00075
00076
00077 template <class _Key, class _Tp,
00078 class _HashFcn = hash<_Key>,
00079 class _EqualKey = equal_to<_Key>,
00080 class _Alloc = allocator<_Tp> >
00081 class hash_map;
00082
00083 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
00084 inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&,
00085 const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&);
00086
00087
00088
00089
00090
00091 template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
00092 class _Alloc>
00093 class hash_map
00094 {
00095 private:
00096 typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn,
00097 _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht;
00098 _Ht _M_ht;
00099
00100 public:
00101 typedef typename _Ht::key_type key_type;
00102 typedef _Tp data_type;
00103 typedef _Tp mapped_type;
00104 typedef typename _Ht::value_type value_type;
00105 typedef typename _Ht::hasher hasher;
00106 typedef typename _Ht::key_equal key_equal;
00107
00108 typedef typename _Ht::size_type size_type;
00109 typedef typename _Ht::difference_type difference_type;
00110 typedef typename _Ht::pointer pointer;
00111 typedef typename _Ht::const_pointer const_pointer;
00112 typedef typename _Ht::reference reference;
00113 typedef typename _Ht::const_reference const_reference;
00114
00115 typedef typename _Ht::iterator iterator;
00116 typedef typename _Ht::const_iterator const_iterator;
00117
00118 typedef typename _Ht::allocator_type allocator_type;
00119
00120 hasher hash_funct() const { return _M_ht.hash_funct(); }
00121 key_equal key_eq() const { return _M_ht.key_eq(); }
00122 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
00123
00124 public:
00125 hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00126 explicit hash_map(size_type __n)
00127 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00128 hash_map(size_type __n, const hasher& __hf)
00129 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
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 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 template <class _InputIterator>
00143 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
00144 const hasher& __hf)
00145 : _M_ht(__n, __hf, key_equal(), allocator_type())
00146 { _M_ht.insert_unique(__f, __l); }
00147 template <class _InputIterator>
00148 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
00149 const hasher& __hf, const key_equal& __eql,
00150 const allocator_type& __a = allocator_type())
00151 : _M_ht(__n, __hf, __eql, __a)
00152 { _M_ht.insert_unique(__f, __l); }
00153
00154 public:
00155 size_type size() const { return _M_ht.size(); }
00156 size_type max_size() const { return _M_ht.max_size(); }
00157 bool empty() const { return _M_ht.empty(); }
00158 void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); }
00159
00160 template <class _K1, class _T1, class _HF, class _EqK, class _Al>
00161 friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
00162 const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
00163
00164 iterator begin() { return _M_ht.begin(); }
00165 iterator end() { return _M_ht.end(); }
00166 const_iterator begin() const { return _M_ht.begin(); }
00167 const_iterator end() const { return _M_ht.end(); }
00168
00169 public:
00170 pair<iterator,bool> insert(const value_type& __obj)
00171 { return _M_ht.insert_unique(__obj); }
00172 template <class _InputIterator>
00173 void insert(_InputIterator __f, _InputIterator __l)
00174 { _M_ht.insert_unique(__f,__l); }
00175 pair<iterator,bool> insert_noresize(const value_type& __obj)
00176 { return _M_ht.insert_unique_noresize(__obj); }
00177
00178 iterator find(const key_type& __key) { return _M_ht.find(__key); }
00179 const_iterator find(const key_type& __key) const
00180 { return _M_ht.find(__key); }
00181
00182 _Tp& operator[](const key_type& __key) {
00183 return _M_ht.find_or_insert(value_type(__key, _Tp())).second;
00184 }
00185
00186 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
00187
00188 pair<iterator, iterator> equal_range(const key_type& __key)
00189 { return _M_ht.equal_range(__key); }
00190 pair<const_iterator, const_iterator>
00191 equal_range(const key_type& __key) const
00192 { return _M_ht.equal_range(__key); }
00193
00194 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
00195 void erase(iterator __it) { _M_ht.erase(__it); }
00196 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
00197 void clear() { _M_ht.clear(); }
00198
00199 void resize(size_type __hint) { _M_ht.resize(__hint); }
00200 size_type bucket_count() const { return _M_ht.bucket_count(); }
00201 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
00202 size_type elems_in_bucket(size_type __n) const
00203 { return _M_ht.elems_in_bucket(__n); }
00204 };
00205
00206 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
00207 inline bool
00208 operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
00209 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
00210 {
00211 return __hm1._M_ht == __hm2._M_ht;
00212 }
00213
00214 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
00215 inline bool
00216 operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
00217 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) {
00218 return !(__hm1 == __hm2);
00219 }
00220
00221 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
00222 inline void
00223 swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
00224 hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
00225 {
00226 __hm1.swap(__hm2);
00227 }
00228
00229
00230
00231 template <class _Key, class _Tp,
00232 class _HashFcn = hash<_Key>,
00233 class _EqualKey = equal_to<_Key>,
00234 class _Alloc = allocator<_Tp> >
00235 class hash_multimap;
00236
00237 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
00238 inline bool
00239 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
00240 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2);
00241
00242
00243
00244
00245
00246
00247 template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc>
00248 class hash_multimap
00249 {
00250
00251 __glibcpp_class_requires(_Key, _SGIAssignableConcept)
00252 __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00253 __glibcpp_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept);
00254 __glibcpp_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept);
00255
00256 private:
00257 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn,
00258 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
00259 _Ht;
00260 _Ht _M_ht;
00261
00262 public:
00263 typedef typename _Ht::key_type key_type;
00264 typedef _Tp data_type;
00265 typedef _Tp mapped_type;
00266 typedef typename _Ht::value_type value_type;
00267 typedef typename _Ht::hasher hasher;
00268 typedef typename _Ht::key_equal key_equal;
00269
00270 typedef typename _Ht::size_type size_type;
00271 typedef typename _Ht::difference_type difference_type;
00272 typedef typename _Ht::pointer pointer;
00273 typedef typename _Ht::const_pointer const_pointer;
00274 typedef typename _Ht::reference reference;
00275 typedef typename _Ht::const_reference const_reference;
00276
00277 typedef typename _Ht::iterator iterator;
00278 typedef typename _Ht::const_iterator const_iterator;
00279
00280 typedef typename _Ht::allocator_type allocator_type;
00281
00282 hasher hash_funct() const { return _M_ht.hash_funct(); }
00283 key_equal key_eq() const { return _M_ht.key_eq(); }
00284 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
00285
00286 public:
00287 hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00288 explicit hash_multimap(size_type __n)
00289 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00290 hash_multimap(size_type __n, const hasher& __hf)
00291 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00292 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
00293 const allocator_type& __a = allocator_type())
00294 : _M_ht(__n, __hf, __eql, __a) {}
00295
00296 template <class _InputIterator>
00297 hash_multimap(_InputIterator __f, _InputIterator __l)
00298 : _M_ht(100, hasher(), key_equal(), allocator_type())
00299 { _M_ht.insert_equal(__f, __l); }
00300 template <class _InputIterator>
00301 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
00302 : _M_ht(__n, hasher(), key_equal(), allocator_type())
00303 { _M_ht.insert_equal(__f, __l); }
00304 template <class _InputIterator>
00305 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
00306 const hasher& __hf)
00307 : _M_ht(__n, __hf, key_equal(), allocator_type())
00308 { _M_ht.insert_equal(__f, __l); }
00309 template <class _InputIterator>
00310 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
00311 const hasher& __hf, const key_equal& __eql,
00312 const allocator_type& __a = allocator_type())
00313 : _M_ht(__n, __hf, __eql, __a)
00314 { _M_ht.insert_equal(__f, __l); }
00315
00316 public:
00317 size_type size() const { return _M_ht.size(); }
00318 size_type max_size() const { return _M_ht.max_size(); }
00319 bool empty() const { return _M_ht.empty(); }
00320 void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); }
00321
00322 template <class _K1, class _T1, class _HF, class _EqK, class _Al>
00323 friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
00324 const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
00325
00326 iterator begin() { return _M_ht.begin(); }
00327 iterator end() { return _M_ht.end(); }
00328 const_iterator begin() const { return _M_ht.begin(); }
00329 const_iterator end() const { return _M_ht.end(); }
00330
00331 public:
00332 iterator insert(const value_type& __obj)
00333 { return _M_ht.insert_equal(__obj); }
00334 template <class _InputIterator>
00335 void insert(_InputIterator __f, _InputIterator __l)
00336 { _M_ht.insert_equal(__f,__l); }
00337 iterator insert_noresize(const value_type& __obj)
00338 { return _M_ht.insert_equal_noresize(__obj); }
00339
00340 iterator find(const key_type& __key) { return _M_ht.find(__key); }
00341 const_iterator find(const key_type& __key) const
00342 { return _M_ht.find(__key); }
00343
00344 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
00345
00346 pair<iterator, iterator> equal_range(const key_type& __key)
00347 { return _M_ht.equal_range(__key); }
00348 pair<const_iterator, const_iterator>
00349 equal_range(const key_type& __key) const
00350 { return _M_ht.equal_range(__key); }
00351
00352 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
00353 void erase(iterator __it) { _M_ht.erase(__it); }
00354 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
00355 void clear() { _M_ht.clear(); }
00356
00357 public:
00358 void resize(size_type __hint) { _M_ht.resize(__hint); }
00359 size_type bucket_count() const { return _M_ht.bucket_count(); }
00360 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
00361 size_type elems_in_bucket(size_type __n) const
00362 { return _M_ht.elems_in_bucket(__n); }
00363 };
00364
00365 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
00366 inline bool
00367 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
00368 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2)
00369 {
00370 return __hm1._M_ht == __hm2._M_ht;
00371 }
00372
00373 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
00374 inline bool
00375 operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
00376 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) {
00377 return !(__hm1 == __hm2);
00378 }
00379
00380 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
00381 inline void
00382 swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
00383 hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
00384 {
00385 __hm1.swap(__hm2);
00386 }
00387
00388 }
00389
00390 namespace std
00391 {
00392
00393
00394
00395 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
00396 class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
00397 protected:
00398 typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
00399 _Container* container;
00400 public:
00401 typedef _Container container_type;
00402 typedef output_iterator_tag iterator_category;
00403 typedef void value_type;
00404 typedef void difference_type;
00405 typedef void pointer;
00406 typedef void reference;
00407
00408 insert_iterator(_Container& __x) : container(&__x) {}
00409 insert_iterator(_Container& __x, typename _Container::iterator)
00410 : container(&__x) {}
00411 insert_iterator<_Container>&
00412 operator=(const typename _Container::value_type& __value) {
00413 container->insert(__value);
00414 return *this;
00415 }
00416 insert_iterator<_Container>& operator*() { return *this; }
00417 insert_iterator<_Container>& operator++() { return *this; }
00418 insert_iterator<_Container>& operator++(int) { return *this; }
00419 };
00420
00421 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
00422 class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
00423 protected:
00424 typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
00425 _Container* container;
00426 typename _Container::iterator iter;
00427 public:
00428 typedef _Container container_type;
00429 typedef output_iterator_tag iterator_category;
00430 typedef void value_type;
00431 typedef void difference_type;
00432 typedef void pointer;
00433 typedef void reference;
00434
00435 insert_iterator(_Container& __x) : container(&__x) {}
00436 insert_iterator(_Container& __x, typename _Container::iterator)
00437 : container(&__x) {}
00438 insert_iterator<_Container>&
00439 operator=(const typename _Container::value_type& __value) {
00440 container->insert(__value);
00441 return *this;
00442 }
00443 insert_iterator<_Container>& operator*() { return *this; }
00444 insert_iterator<_Container>& operator++() { return *this; }
00445 insert_iterator<_Container>& operator++(int) { return *this; }
00446 };
00447
00448 }
00449
00450 #endif
00451
00452
00453
00454