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