include/g++-3/stl_hash_map.h

   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: