1 /* 2 * Copyright (c) 1996 3 * Silicon Graphics Computer Systems, Inc. 4 * 5 * Permission to use, copy, modify, distribute and sell this software 6 * and its documentation for any purpose is hereby granted without fee, 7 * provided that the above copyright notice appear in all copies and 8 * that both that copyright notice and this permission notice appear 9 * in supporting documentation. Silicon Graphics makes no 10 * representations about the suitability of this software for any 11 * purpose. It is provided "as is" without express or implied warranty. 12 * 13 * 14 * Copyright (c) 1994 15 * Hewlett-Packard Company 16 * 17 * Permission to use, copy, modify, distribute and sell this software 18 * and its documentation for any purpose is hereby granted without fee, 19 * provided that the above copyright notice appear in all copies and 20 * that both that copyright notice and this permission notice appear 21 * in supporting documentation. Hewlett-Packard Company makes no 22 * representations about the suitability of this software for any 23 * purpose. It is provided "as is" without express or implied warranty. 24 * 25 */ 26 27 /* NOTE: This is an internal header file, included by other STL headers. 28 * You should not attempt to use it directly. 29 */ 30 31 #ifndef __SGI_STL_INTERNAL_HASH_MAP_H 32 #define __SGI_STL_INTERNAL_HASH_MAP_H 33 34 35 __STL_BEGIN_NAMESPACE 36 37 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 38 #pragma set woff 1174 39 #pragma set woff 1375 40 #endif 41 42 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES 43 template <class _Key, class _Tp, class _HashFcn = hash<_Key>, 44 class _EqualKey = equal_to<_Key>, 45 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > 46 #else 47 template <class _Key, class _Tp, class _HashFcn, class _EqualKey, 48 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > 49 #endif 50 class hash_map 51 { 52 private: 53 typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn, 54 _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht; 55 _Ht _M_ht; 56 57 public: 58 typedef typename _Ht::key_type key_type; 59 typedef _Tp data_type; 60 typedef _Tp mapped_type; 61 typedef typename _Ht::value_type value_type; 62 typedef typename _Ht::hasher hasher; 63 typedef typename _Ht::key_equal key_equal; 64 65 typedef typename _Ht::size_type size_type; 66 typedef typename _Ht::difference_type difference_type; 67 typedef typename _Ht::pointer pointer; 68 typedef typename _Ht::const_pointer const_pointer; 69 typedef typename _Ht::reference reference; 70 typedef typename _Ht::const_reference const_reference; 71 72 typedef typename _Ht::iterator iterator; 73 typedef typename _Ht::const_iterator const_iterator; 74 75 typedef typename _Ht::allocator_type allocator_type; 76 77 hasher hash_funct() const { return _M_ht.hash_funct(); } 78 key_equal key_eq() const { return _M_ht.key_eq(); } 79 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 80 81 public: 82 hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 83 explicit hash_map(size_type __n) 84 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 85 hash_map(size_type __n, const hasher& __hf) 86 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 87 hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, 88 const allocator_type& __a = allocator_type()) 89 : _M_ht(__n, __hf, __eql, __a) {} 90 91 #ifdef __STL_MEMBER_TEMPLATES 92 template <class _InputIterator> 93 hash_map(_InputIterator __f, _InputIterator __l) 94 : _M_ht(100, hasher(), key_equal(), allocator_type()) 95 { _M_ht.insert_unique(__f, __l); } 96 template <class _InputIterator> 97 hash_map(_InputIterator __f, _InputIterator __l, size_type __n) 98 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 99 { _M_ht.insert_unique(__f, __l); } 100 template <class _InputIterator> 101 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 102 const hasher& __hf) 103 : _M_ht(__n, __hf, key_equal(), allocator_type()) 104 { _M_ht.insert_unique(__f, __l); } 105 template <class _InputIterator> 106 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 107 const hasher& __hf, const key_equal& __eql, 108 const allocator_type& __a = allocator_type()) 109 : _M_ht(__n, __hf, __eql, __a) 110 { _M_ht.insert_unique(__f, __l); } 111 112 #else 113 hash_map(const value_type* __f, const value_type* __l) 114 : _M_ht(100, hasher(), key_equal(), allocator_type()) 115 { _M_ht.insert_unique(__f, __l); } 116 hash_map(const value_type* __f, const value_type* __l, size_type __n) 117 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 118 { _M_ht.insert_unique(__f, __l); } 119 hash_map(const value_type* __f, const value_type* __l, size_type __n, 120 const hasher& __hf) 121 : _M_ht(__n, __hf, key_equal(), allocator_type()) 122 { _M_ht.insert_unique(__f, __l); } 123 hash_map(const value_type* __f, const value_type* __l, size_type __n, 124 const hasher& __hf, const key_equal& __eql, 125 const allocator_type& __a = allocator_type()) 126 : _M_ht(__n, __hf, __eql, __a) 127 { _M_ht.insert_unique(__f, __l); } 128 129 hash_map(const_iterator __f, const_iterator __l) 130 : _M_ht(100, hasher(), key_equal(), allocator_type()) 131 { _M_ht.insert_unique(__f, __l); } 132 hash_map(const_iterator __f, const_iterator __l, size_type __n) 133 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 134 { _M_ht.insert_unique(__f, __l); } 135 hash_map(const_iterator __f, const_iterator __l, size_type __n, 136 const hasher& __hf) 137 : _M_ht(__n, __hf, key_equal(), allocator_type()) 138 { _M_ht.insert_unique(__f, __l); } 139 hash_map(const_iterator __f, const_iterator __l, size_type __n, 140 const hasher& __hf, const key_equal& __eql, 141 const allocator_type& __a = allocator_type()) 142 : _M_ht(__n, __hf, __eql, __a) 143 { _M_ht.insert_unique(__f, __l); } 144 #endif /*__STL_MEMBER_TEMPLATES */ 145 146 public: 147 size_type size() const { return _M_ht.size(); } 148 size_type max_size() const { return _M_ht.max_size(); } 149 bool empty() const { return _M_ht.empty(); } 150 void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); } 151 friend bool 152 operator== __STL_NULL_TMPL_ARGS (const hash_map&, const hash_map&); 153 154 iterator begin() { return _M_ht.begin(); } 155 iterator end() { return _M_ht.end(); } 156 const_iterator begin() const { return _M_ht.begin(); } 157 const_iterator end() const { return _M_ht.end(); } 158 159 public: 160 pair<iterator,bool> insert(const value_type& __obj) 161 { return _M_ht.insert_unique(__obj); } 162 #ifdef __STL_MEMBER_TEMPLATES 163 template <class _InputIterator> 164 void insert(_InputIterator __f, _InputIterator __l) 165 { _M_ht.insert_unique(__f,__l); } 166 #else 167 void insert(const value_type* __f, const value_type* __l) { 168 _M_ht.insert_unique(__f,__l); 169 } 170 void insert(const_iterator __f, const_iterator __l) 171 { _M_ht.insert_unique(__f, __l); } 172 #endif /*__STL_MEMBER_TEMPLATES */ 173 pair<iterator,bool> insert_noresize(const value_type& __obj) 174 { return _M_ht.insert_unique_noresize(__obj); } 175 176 iterator find(const key_type& __key) { return _M_ht.find(__key); } 177 const_iterator find(const key_type& __key) const 178 { return _M_ht.find(__key); } 179 180 _Tp& operator[](const key_type& __key) { 181 return _M_ht.find_or_insert(value_type(__key, _Tp())).second; 182 } 183 184 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 185 186 pair<iterator, iterator> equal_range(const key_type& __key) 187 { return _M_ht.equal_range(__key); } 188 pair<const_iterator, const_iterator> 189 equal_range(const key_type& __key) const 190 { return _M_ht.equal_range(__key); } 191 192 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 193 void erase(iterator __it) { _M_ht.erase(__it); } 194 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 195 void clear() { _M_ht.clear(); } 196 197 void resize(size_type __hint) { _M_ht.resize(__hint); } 198 size_type bucket_count() const { return _M_ht.bucket_count(); } 199 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 200 size_type elems_in_bucket(size_type __n) const 201 { return _M_ht.elems_in_bucket(__n); } 202 }; 203 204 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 205 inline bool 206 operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 207 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 208 { 209 return __hm1._M_ht == __hm2._M_ht; 210 } 211 212 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 213 214 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 215 inline void 216 swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 217 hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 218 { 219 __hm1.swap(__hm2); 220 } 221 222 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 223 224 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES 225 template <class _Key, class _Tp, class _HashFcn = hash<_Key>, 226 class _EqualKey = equal_to<_Key>, 227 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > 228 #else 229 template <class _Key, class _Tp, class _HashFcn, class _EqualKey, 230 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > 231 #endif 232 class hash_multimap 233 { 234 private: 235 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn, 236 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc> 237 _Ht; 238 _Ht _M_ht; 239 240 public: 241 typedef typename _Ht::key_type key_type; 242 typedef _Tp data_type; 243 typedef _Tp mapped_type; 244 typedef typename _Ht::value_type value_type; 245 typedef typename _Ht::hasher hasher; 246 typedef typename _Ht::key_equal key_equal; 247 248 typedef typename _Ht::size_type size_type; 249 typedef typename _Ht::difference_type difference_type; 250 typedef typename _Ht::pointer pointer; 251 typedef typename _Ht::const_pointer const_pointer; 252 typedef typename _Ht::reference reference; 253 typedef typename _Ht::const_reference const_reference; 254 255 typedef typename _Ht::iterator iterator; 256 typedef typename _Ht::const_iterator const_iterator; 257 258 typedef typename _Ht::allocator_type allocator_type; 259 260 hasher hash_funct() const { return _M_ht.hash_funct(); } 261 key_equal key_eq() const { return _M_ht.key_eq(); } 262 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 263 264 public: 265 hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 266 explicit hash_multimap(size_type __n) 267 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 268 hash_multimap(size_type __n, const hasher& __hf) 269 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 270 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, 271 const allocator_type& __a = allocator_type()) 272 : _M_ht(__n, __hf, __eql, __a) {} 273 274 #ifdef __STL_MEMBER_TEMPLATES 275 template <class _InputIterator> 276 hash_multimap(_InputIterator __f, _InputIterator __l) 277 : _M_ht(100, hasher(), key_equal(), allocator_type()) 278 { _M_ht.insert_equal(__f, __l); } 279 template <class _InputIterator> 280 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n) 281 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 282 { _M_ht.insert_equal(__f, __l); } 283 template <class _InputIterator> 284 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 285 const hasher& __hf) 286 : _M_ht(__n, __hf, key_equal(), allocator_type()) 287 { _M_ht.insert_equal(__f, __l); } 288 template <class _InputIterator> 289 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 290 const hasher& __hf, const key_equal& __eql, 291 const allocator_type& __a = allocator_type()) 292 : _M_ht(__n, __hf, __eql, __a) 293 { _M_ht.insert_equal(__f, __l); } 294 295 #else 296 hash_multimap(const value_type* __f, const value_type* __l) 297 : _M_ht(100, hasher(), key_equal(), allocator_type()) 298 { _M_ht.insert_equal(__f, __l); } 299 hash_multimap(const value_type* __f, const value_type* __l, size_type __n) 300 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 301 { _M_ht.insert_equal(__f, __l); } 302 hash_multimap(const value_type* __f, const value_type* __l, size_type __n, 303 const hasher& __hf) 304 : _M_ht(__n, __hf, key_equal(), allocator_type()) 305 { _M_ht.insert_equal(__f, __l); } 306 hash_multimap(const value_type* __f, const value_type* __l, size_type __n, 307 const hasher& __hf, const key_equal& __eql, 308 const allocator_type& __a = allocator_type()) 309 : _M_ht(__n, __hf, __eql, __a) 310 { _M_ht.insert_equal(__f, __l); } 311 312 hash_multimap(const_iterator __f, const_iterator __l) 313 : _M_ht(100, hasher(), key_equal(), allocator_type()) 314 { _M_ht.insert_equal(__f, __l); } 315 hash_multimap(const_iterator __f, const_iterator __l, size_type __n) 316 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 317 { _M_ht.insert_equal(__f, __l); } 318 hash_multimap(const_iterator __f, const_iterator __l, size_type __n, 319 const hasher& __hf) 320 : _M_ht(__n, __hf, key_equal(), allocator_type()) 321 { _M_ht.insert_equal(__f, __l); } 322 hash_multimap(const_iterator __f, const_iterator __l, size_type __n, 323 const hasher& __hf, const key_equal& __eql, 324 const allocator_type& __a = allocator_type()) 325 : _M_ht(__n, __hf, __eql, __a) 326 { _M_ht.insert_equal(__f, __l); } 327 #endif /*__STL_MEMBER_TEMPLATES */ 328 329 public: 330 size_type size() const { return _M_ht.size(); } 331 size_type max_size() const { return _M_ht.max_size(); } 332 bool empty() const { return _M_ht.empty(); } 333 void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); } 334 friend bool 335 operator== __STL_NULL_TMPL_ARGS (const hash_multimap&, 336 const hash_multimap&); 337 338 iterator begin() { return _M_ht.begin(); } 339 iterator end() { return _M_ht.end(); } 340 const_iterator begin() const { return _M_ht.begin(); } 341 const_iterator end() const { return _M_ht.end(); } 342 343 public: 344 iterator insert(const value_type& __obj) 345 { return _M_ht.insert_equal(__obj); } 346 #ifdef __STL_MEMBER_TEMPLATES 347 template <class _InputIterator> 348 void insert(_InputIterator __f, _InputIterator __l) 349 { _M_ht.insert_equal(__f,__l); } 350 #else 351 void insert(const value_type* __f, const value_type* __l) { 352 _M_ht.insert_equal(__f,__l); 353 } 354 void insert(const_iterator __f, const_iterator __l) 355 { _M_ht.insert_equal(__f, __l); } 356 #endif /*__STL_MEMBER_TEMPLATES */ 357 iterator insert_noresize(const value_type& __obj) 358 { return _M_ht.insert_equal_noresize(__obj); } 359 360 iterator find(const key_type& __key) { return _M_ht.find(__key); } 361 const_iterator find(const key_type& __key) const 362 { return _M_ht.find(__key); } 363 364 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 365 366 pair<iterator, iterator> equal_range(const key_type& __key) 367 { return _M_ht.equal_range(__key); } 368 pair<const_iterator, const_iterator> 369 equal_range(const key_type& __key) const 370 { return _M_ht.equal_range(__key); } 371 372 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 373 void erase(iterator __it) { _M_ht.erase(__it); } 374 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 375 void clear() { _M_ht.clear(); } 376 377 public: 378 void resize(size_type __hint) { _M_ht.resize(__hint); } 379 size_type bucket_count() const { return _M_ht.bucket_count(); } 380 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 381 size_type elems_in_bucket(size_type __n) const 382 { return _M_ht.elems_in_bucket(__n); } 383 }; 384 385 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 386 inline bool 387 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 388 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) 389 { 390 return __hm1._M_ht == __hm2._M_ht; 391 } 392 393 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 394 395 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 396 inline void 397 swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 398 hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 399 { 400 __hm1.swap(__hm2); 401 } 402 403 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 404 405 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 406 #pragma reset woff 1174 407 #pragma reset woff 1375 408 #endif 409 410 __STL_END_NAMESPACE 411 412 #endif /* __SGI_STL_INTERNAL_HASH_MAP_H */ 413 414 // Local Variables: 415 // mode:C++ 416 // End: 417