headers/cpp/stl_hash_set.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_SET_H
  32 #define __SGI_STL_INTERNAL_HASH_SET_H
  33
  34 __STL_BEGIN_NAMESPACE
  35
  36 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  37 #pragma set woff 1174
  38 #pragma set woff 1375
  39 #endif
  40
  41 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  42 template <class _Value, class _HashFcn = hash<_Value>,
  43           class _EqualKey = equal_to<_Value>,
  44           class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
  45 #else
  46 template <class _Value, class _HashFcn, class _EqualKey,
  47           class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
  48 #endif
  49 class hash_set
  50 {
  51 private:
  52   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
  53                     _EqualKey, _Alloc> _Ht;
  54   _Ht _M_ht;
  55
  56 public:
  57   typedef typename _Ht::key_type key_type;
  58   typedef typename _Ht::value_type value_type;
  59   typedef typename _Ht::hasher hasher;
  60   typedef typename _Ht::key_equal key_equal;
  61
  62   typedef typename _Ht::size_type size_type;
  63   typedef typename _Ht::difference_type difference_type;
  64   typedef typename _Ht::const_pointer pointer;
  65   typedef typename _Ht::const_pointer const_pointer;
  66   typedef typename _Ht::const_reference reference;
  67   typedef typename _Ht::const_reference const_reference;
  68
  69   typedef typename _Ht::const_iterator iterator;
  70   typedef typename _Ht::const_iterator const_iterator;
  71
  72   typedef typename _Ht::allocator_type allocator_type;
  73
  74   hasher hash_funct() const { return _M_ht.hash_funct(); }
  75   key_equal key_eq() const { return _M_ht.key_eq(); }
  76   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  77
  78 public:
  79   hash_set()
  80     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  81   explicit hash_set(size_type __n)
  82     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  83   hash_set(size_type __n, const hasher& __hf)
  84     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  85   hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
  86            const allocator_type& __a = allocator_type())
  87     : _M_ht(__n, __hf, __eql, __a) {}
  88
  89 #ifdef __STL_MEMBER_TEMPLATES
  90   template <class _InputIterator>
  91   hash_set(_InputIterator __f, _InputIterator __l)
  92     : _M_ht(100, hasher(), key_equal(), allocator_type())
  93     { _M_ht.insert_unique(__f, __l); }
  94   template <class _InputIterator>
  95   hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
  96     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  97     { _M_ht.insert_unique(__f, __l); }
  98   template <class _InputIterator>
  99   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
 100            const hasher& __hf)
 101     : _M_ht(__n, __hf, key_equal(), allocator_type())
 102     { _M_ht.insert_unique(__f, __l); }
 103   template <class _InputIterator>
 104   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
 105            const hasher& __hf, const key_equal& __eql,
 106            const allocator_type& __a = allocator_type())
 107     : _M_ht(__n, __hf, __eql, __a)
 108     { _M_ht.insert_unique(__f, __l); }
 109 #else
 110
 111   hash_set(const value_type* __f, const value_type* __l)
 112     : _M_ht(100, hasher(), key_equal(), allocator_type())
 113     { _M_ht.insert_unique(__f, __l); }
 114   hash_set(const value_type* __f, const value_type* __l, size_type __n)
 115     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 116     { _M_ht.insert_unique(__f, __l); }
 117   hash_set(const value_type* __f, const value_type* __l, size_type __n,
 118            const hasher& __hf)
 119     : _M_ht(__n, __hf, key_equal(), allocator_type())
 120     { _M_ht.insert_unique(__f, __l); }
 121   hash_set(const value_type* __f, const value_type* __l, size_type __n,
 122            const hasher& __hf, const key_equal& __eql,
 123            const allocator_type& __a = allocator_type())
 124     : _M_ht(__n, __hf, __eql, __a)
 125     { _M_ht.insert_unique(__f, __l); }
 126
 127   hash_set(const_iterator __f, const_iterator __l)
 128     : _M_ht(100, hasher(), key_equal(), allocator_type())
 129     { _M_ht.insert_unique(__f, __l); }
 130   hash_set(const_iterator __f, const_iterator __l, size_type __n)
 131     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 132     { _M_ht.insert_unique(__f, __l); }
 133   hash_set(const_iterator __f, const_iterator __l, size_type __n,
 134            const hasher& __hf)
 135     : _M_ht(__n, __hf, key_equal(), allocator_type())
 136     { _M_ht.insert_unique(__f, __l); }
 137   hash_set(const_iterator __f, const_iterator __l, size_type __n,
 138            const hasher& __hf, const key_equal& __eql,
 139            const allocator_type& __a = allocator_type())
 140     : _M_ht(__n, __hf, __eql, __a)
 141     { _M_ht.insert_unique(__f, __l); }
 142 #endif /*__STL_MEMBER_TEMPLATES */
 143
 144 public:
 145   size_type size() const { return _M_ht.size(); }
 146   size_type max_size() const { return _M_ht.max_size(); }
 147   bool empty() const { return _M_ht.empty(); }
 148   void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); }
 149   friend bool operator== __STL_NULL_TMPL_ARGS (const hash_set&,
 150                                                const hash_set&);
 151
 152   iterator begin() const { return _M_ht.begin(); }
 153   iterator end() const { return _M_ht.end(); }
 154
 155 public:
 156   pair<iterator, bool> insert(const value_type& __obj)
 157     {
 158       pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
 159       return pair<iterator,bool>(__p.first, __p.second);
 160     }
 161 #ifdef __STL_MEMBER_TEMPLATES
 162   template <class _InputIterator>
 163   void insert(_InputIterator __f, _InputIterator __l)
 164     { _M_ht.insert_unique(__f,__l); }
 165 #else
 166   void insert(const value_type* __f, const value_type* __l) {
 167     _M_ht.insert_unique(__f,__l);
 168   }
 169   void insert(const_iterator __f, const_iterator __l)
 170     {_M_ht.insert_unique(__f, __l); }
 171 #endif /*__STL_MEMBER_TEMPLATES */
 172   pair<iterator, bool> insert_noresize(const value_type& __obj)
 173   {
 174     pair<typename _Ht::iterator, bool> __p =
 175       _M_ht.insert_unique_noresize(__obj);
 176     return pair<iterator, bool>(__p.first, __p.second);
 177   }
 178
 179   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
 180
 181   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
 182
 183   pair<iterator, iterator> equal_range(const key_type& __key) const
 184     { return _M_ht.equal_range(__key); }
 185
 186   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
 187   void erase(iterator __it) { _M_ht.erase(__it); }
 188   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 189   void clear() { _M_ht.clear(); }
 190
 191 public:
 192   void resize(size_type __hint) { _M_ht.resize(__hint); }
 193   size_type bucket_count() const { return _M_ht.bucket_count(); }
 194   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 195   size_type elems_in_bucket(size_type __n) const
 196     { return _M_ht.elems_in_bucket(__n); }
 197 };
 198
 199 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 200 inline bool
 201 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
 202            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2)
 203 {
 204   return __hs1._M_ht == __hs2._M_ht;
 205 }
 206
 207 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 208
 209 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 210 inline void
 211 swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
 212      hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
 213 {
 214   __hs1.swap(__hs2);
 215 }
 216
 217 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 218
 219
 220 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
 221 template <class _Value, class _HashFcn = hash<_Value>,
 222           class _EqualKey = equal_to<_Value>,
 223           class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
 224 #else
 225 template <class _Value, class _HashFcn, class _EqualKey,
 226           class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
 227 #endif
 228 class hash_multiset
 229 {
 230 private:
 231   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
 232                     _EqualKey, _Alloc> _Ht;
 233   _Ht _M_ht;
 234
 235 public:
 236   typedef typename _Ht::key_type key_type;
 237   typedef typename _Ht::value_type value_type;
 238   typedef typename _Ht::hasher hasher;
 239   typedef typename _Ht::key_equal key_equal;
 240
 241   typedef typename _Ht::size_type size_type;
 242   typedef typename _Ht::difference_type difference_type;
 243   typedef typename _Ht::const_pointer pointer;
 244   typedef typename _Ht::const_pointer const_pointer;
 245   typedef typename _Ht::const_reference reference;
 246   typedef typename _Ht::const_reference const_reference;
 247
 248   typedef typename _Ht::const_iterator iterator;
 249   typedef typename _Ht::const_iterator const_iterator;
 250
 251   typedef typename _Ht::allocator_type allocator_type;
 252
 253   hasher hash_funct() const { return _M_ht.hash_funct(); }
 254   key_equal key_eq() const { return _M_ht.key_eq(); }
 255   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
 256
 257 public:
 258   hash_multiset()
 259     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 260   explicit hash_multiset(size_type __n)
 261     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 262   hash_multiset(size_type __n, const hasher& __hf)
 263     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 264   hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
 265                 const allocator_type& __a = allocator_type())
 266     : _M_ht(__n, __hf, __eql, __a) {}
 267
 268 #ifdef __STL_MEMBER_TEMPLATES
 269   template <class _InputIterator>
 270   hash_multiset(_InputIterator __f, _InputIterator __l)
 271     : _M_ht(100, hasher(), key_equal(), allocator_type())
 272     { _M_ht.insert_equal(__f, __l); }
 273   template <class _InputIterator>
 274   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
 275     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 276     { _M_ht.insert_equal(__f, __l); }
 277   template <class _InputIterator>
 278   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 279                 const hasher& __hf)
 280     : _M_ht(__n, __hf, key_equal(), allocator_type())
 281     { _M_ht.insert_equal(__f, __l); }
 282   template <class _InputIterator>
 283   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 284                 const hasher& __hf, const key_equal& __eql,
 285                 const allocator_type& __a = allocator_type())
 286     : _M_ht(__n, __hf, __eql, __a)
 287     { _M_ht.insert_equal(__f, __l); }
 288 #else
 289
 290   hash_multiset(const value_type* __f, const value_type* __l)
 291     : _M_ht(100, hasher(), key_equal(), allocator_type())
 292     { _M_ht.insert_equal(__f, __l); }
 293   hash_multiset(const value_type* __f, const value_type* __l, size_type __n)
 294     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 295     { _M_ht.insert_equal(__f, __l); }
 296   hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
 297                 const hasher& __hf)
 298     : _M_ht(__n, __hf, key_equal(), allocator_type())
 299     { _M_ht.insert_equal(__f, __l); }
 300   hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
 301                 const hasher& __hf, const key_equal& __eql,
 302                 const allocator_type& __a = allocator_type())
 303     : _M_ht(__n, __hf, __eql, __a)
 304     { _M_ht.insert_equal(__f, __l); }
 305
 306   hash_multiset(const_iterator __f, const_iterator __l)
 307     : _M_ht(100, hasher(), key_equal(), allocator_type())
 308     { _M_ht.insert_equal(__f, __l); }
 309   hash_multiset(const_iterator __f, const_iterator __l, size_type __n)
 310     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 311     { _M_ht.insert_equal(__f, __l); }
 312   hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
 313                 const hasher& __hf)
 314     : _M_ht(__n, __hf, key_equal(), allocator_type())
 315     { _M_ht.insert_equal(__f, __l); }
 316   hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
 317                 const hasher& __hf, const key_equal& __eql,
 318                 const allocator_type& __a = allocator_type())
 319     : _M_ht(__n, __hf, __eql, __a)
 320     { _M_ht.insert_equal(__f, __l); }
 321 #endif /*__STL_MEMBER_TEMPLATES */
 322
 323 public:
 324   size_type size() const { return _M_ht.size(); }
 325   size_type max_size() const { return _M_ht.max_size(); }
 326   bool empty() const { return _M_ht.empty(); }
 327   void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); }
 328   friend bool operator== __STL_NULL_TMPL_ARGS (const hash_multiset&,
 329                                                const hash_multiset&);
 330
 331   iterator begin() const { return _M_ht.begin(); }
 332   iterator end() const { return _M_ht.end(); }
 333
 334 public:
 335   iterator insert(const value_type& __obj)
 336     { return _M_ht.insert_equal(__obj); }
 337 #ifdef __STL_MEMBER_TEMPLATES
 338   template <class _InputIterator>
 339   void insert(_InputIterator __f, _InputIterator __l)
 340     { _M_ht.insert_equal(__f,__l); }
 341 #else
 342   void insert(const value_type* __f, const value_type* __l) {
 343     _M_ht.insert_equal(__f,__l);
 344   }
 345   void insert(const_iterator __f, const_iterator __l)
 346     { _M_ht.insert_equal(__f, __l); }
 347 #endif /*__STL_MEMBER_TEMPLATES */
 348   iterator insert_noresize(const value_type& __obj)
 349     { return _M_ht.insert_equal_noresize(__obj); }
 350
 351   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
 352
 353   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
 354
 355   pair<iterator, iterator> equal_range(const key_type& __key) const
 356     { return _M_ht.equal_range(__key); }
 357
 358   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
 359   void erase(iterator __it) { _M_ht.erase(__it); }
 360   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 361   void clear() { _M_ht.clear(); }
 362
 363 public:
 364   void resize(size_type __hint) { _M_ht.resize(__hint); }
 365   size_type bucket_count() const { return _M_ht.bucket_count(); }
 366   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 367   size_type elems_in_bucket(size_type __n) const
 368     { return _M_ht.elems_in_bucket(__n); }
 369 };
 370
 371 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 372 inline bool
 373 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
 374            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
 375 {
 376   return __hs1._M_ht == __hs2._M_ht;
 377 }
 378
 379 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 380
 381 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 382 inline void
 383 swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
 384      hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
 385   __hs1.swap(__hs2);
 386 }
 387
 388 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 389
 390 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
 391 #pragma reset woff 1174
 392 #pragma reset woff 1375
 393 #endif
 394
 395 __STL_END_NAMESPACE
 396
 397 #endif /* __SGI_STL_INTERNAL_HASH_SET_H */
 398
 399 // Local Variables:
 400 // mode:C++
 401 // End: