libstdc++/stl/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 #endif
  39
  40 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  41 template <class Value, class HashFcn = hash<Value>,
  42           class EqualKey = equal_to<Value>,
  43           class Alloc = alloc>
  44 #else
  45 template <class Value, class HashFcn, class EqualKey, class Alloc = alloc>
  46 #endif
  47 class hash_set
  48 {
  49 private:
  50   typedef hashtable<Value, Value, HashFcn, identity<Value>,
  51                     EqualKey, Alloc> ht;
  52   ht rep;
  53
  54 public:
  55   typedef typename ht::key_type key_type;
  56   typedef typename ht::value_type value_type;
  57   typedef typename ht::hasher hasher;
  58   typedef typename ht::key_equal key_equal;
  59
  60   typedef typename ht::size_type size_type;
  61   typedef typename ht::difference_type difference_type;
  62   typedef typename ht::const_pointer pointer;
  63   typedef typename ht::const_pointer const_pointer;
  64   typedef typename ht::const_reference reference;
  65   typedef typename ht::const_reference const_reference;
  66
  67   typedef typename ht::const_iterator iterator;
  68   typedef typename ht::const_iterator const_iterator;
  69
  70   hasher hash_funct() const { return rep.hash_funct(); }
  71   key_equal key_eq() const { return rep.key_eq(); }
  72
  73 public:
  74   hash_set() : rep(100, hasher(), key_equal()) {}
  75   explicit hash_set(size_type n) : rep(n, hasher(), key_equal()) {}
  76   hash_set(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
  77   hash_set(size_type n, const hasher& hf, const key_equal& eql)
  78     : rep(n, hf, eql) {}
  79
  80 #ifdef __STL_MEMBER_TEMPLATES
  81   template <class InputIterator>
  82   hash_set(InputIterator f, InputIterator l)
  83     : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
  84   template <class InputIterator>
  85   hash_set(InputIterator f, InputIterator l, size_type n)
  86     : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
  87   template <class InputIterator>
  88   hash_set(InputIterator f, InputIterator l, size_type n,
  89            const hasher& hf)
  90     : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
  91   template <class InputIterator>
  92   hash_set(InputIterator f, InputIterator l, size_type n,
  93            const hasher& hf, const key_equal& eql)
  94     : rep(n, hf, eql) { rep.insert_unique(f, l); }
  95 #else
  96
  97   hash_set(const value_type* f, const value_type* l)
  98     : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
  99   hash_set(const value_type* f, const value_type* l, size_type n)
 100     : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
 101   hash_set(const value_type* f, const value_type* l, size_type n,
 102            const hasher& hf)
 103     : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
 104   hash_set(const value_type* f, const value_type* l, size_type n,
 105            const hasher& hf, const key_equal& eql)
 106     : rep(n, hf, eql) { rep.insert_unique(f, l); }
 107
 108   hash_set(const_iterator f, const_iterator l)
 109     : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
 110   hash_set(const_iterator f, const_iterator l, size_type n)
 111     : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
 112   hash_set(const_iterator f, const_iterator l, size_type n,
 113            const hasher& hf)
 114     : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
 115   hash_set(const_iterator f, const_iterator l, size_type n,
 116            const hasher& hf, const key_equal& eql)
 117     : rep(n, hf, eql) { rep.insert_unique(f, l); }
 118 #endif /*__STL_MEMBER_TEMPLATES */
 119
 120 public:
 121   size_type size() const { return rep.size(); }
 122   size_type max_size() const { return rep.max_size(); }
 123   bool empty() const { return rep.empty(); }
 124   void swap(hash_set& hs) { rep.swap(hs.rep); }
 125   friend bool operator== __STL_NULL_TMPL_ARGS (const hash_set&,
 126                                                const hash_set&);
 127
 128   iterator begin() const { return rep.begin(); }
 129   iterator end() const { return rep.end(); }
 130
 131 public:
 132   pair<iterator, bool> insert(const value_type& obj)
 133     {
 134       pair<typename ht::iterator, bool> p = rep.insert_unique(obj);
 135       return pair<iterator, bool>(p.first, p.second);
 136     }
 137 #ifdef __STL_MEMBER_TEMPLATES
 138   template <class InputIterator>
 139   void insert(InputIterator f, InputIterator l) { rep.insert_unique(f,l); }
 140 #else
 141   void insert(const value_type* f, const value_type* l) {
 142     rep.insert_unique(f,l);
 143   }
 144   void insert(const_iterator f, const_iterator l) {rep.insert_unique(f, l); }
 145 #endif /*__STL_MEMBER_TEMPLATES */
 146   pair<iterator, bool> insert_noresize(const value_type& obj)
 147   {
 148     pair<typename ht::iterator, bool> p = rep.insert_unique_noresize(obj);
 149     return pair<iterator, bool>(p.first, p.second);
 150   }
 151
 152   iterator find(const key_type& key) const { return rep.find(key); }
 153
 154   size_type count(const key_type& key) const { return rep.count(key); }
 155
 156   pair<iterator, iterator> equal_range(const key_type& key) const
 157     { return rep.equal_range(key); }
 158
 159   size_type erase(const key_type& key) {return rep.erase(key); }
 160   void erase(iterator it) { rep.erase(it); }
 161   void erase(iterator f, iterator l) { rep.erase(f, l); }
 162   void clear() { rep.clear(); }
 163
 164 public:
 165   void resize(size_type hint) { rep.resize(hint); }
 166   size_type bucket_count() const { return rep.bucket_count(); }
 167   size_type max_bucket_count() const { return rep.max_bucket_count(); }
 168   size_type elems_in_bucket(size_type n) const
 169     { return rep.elems_in_bucket(n); }
 170 };
 171
 172 template <class Value, class HashFcn, class EqualKey, class Alloc>
 173 inline bool operator==(const hash_set<Value, HashFcn, EqualKey, Alloc>& hs1,
 174                        const hash_set<Value, HashFcn, EqualKey, Alloc>& hs2)
 175 {
 176   return hs1.rep == hs2.rep;
 177 }
 178
 179 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 180
 181 template <class Val, class HashFcn, class EqualKey, class Alloc>
 182 inline void swap(hash_set<Val, HashFcn, EqualKey, Alloc>& hs1,
 183                  hash_set<Val, HashFcn, EqualKey, Alloc>& hs2) {
 184   hs1.swap(hs2);
 185 }
 186
 187 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 188
 189
 190 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
 191 template <class Value, class HashFcn = hash<Value>,
 192           class EqualKey = equal_to<Value>,
 193           class Alloc = alloc>
 194 #else
 195 template <class Value, class HashFcn, class EqualKey, class Alloc = alloc>
 196 #endif
 197 class hash_multiset
 198 {
 199 private:
 200   typedef hashtable<Value, Value, HashFcn, identity<Value>,
 201                     EqualKey, Alloc> ht;
 202   ht rep;
 203
 204 public:
 205   typedef typename ht::key_type key_type;
 206   typedef typename ht::value_type value_type;
 207   typedef typename ht::hasher hasher;
 208   typedef typename ht::key_equal key_equal;
 209
 210   typedef typename ht::size_type size_type;
 211   typedef typename ht::difference_type difference_type;
 212   typedef typename ht::const_pointer pointer;
 213   typedef typename ht::const_pointer const_pointer;
 214   typedef typename ht::const_reference reference;
 215   typedef typename ht::const_reference const_reference;
 216
 217   typedef typename ht::const_iterator iterator;
 218   typedef typename ht::const_iterator const_iterator;
 219
 220   hasher hash_funct() const { return rep.hash_funct(); }
 221   key_equal key_eq() const { return rep.key_eq(); }
 222
 223 public:
 224   hash_multiset() : rep(100, hasher(), key_equal()) {}
 225   explicit hash_multiset(size_type n) : rep(n, hasher(), key_equal()) {}
 226   hash_multiset(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
 227   hash_multiset(size_type n, const hasher& hf, const key_equal& eql)
 228     : rep(n, hf, eql) {}
 229
 230 #ifdef __STL_MEMBER_TEMPLATES
 231   template <class InputIterator>
 232   hash_multiset(InputIterator f, InputIterator l)
 233     : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
 234   template <class InputIterator>
 235   hash_multiset(InputIterator f, InputIterator l, size_type n)
 236     : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
 237   template <class InputIterator>
 238   hash_multiset(InputIterator f, InputIterator l, size_type n,
 239                 const hasher& hf)
 240     : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
 241   template <class InputIterator>
 242   hash_multiset(InputIterator f, InputIterator l, size_type n,
 243                 const hasher& hf, const key_equal& eql)
 244     : rep(n, hf, eql) { rep.insert_equal(f, l); }
 245 #else
 246
 247   hash_multiset(const value_type* f, const value_type* l)
 248     : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
 249   hash_multiset(const value_type* f, const value_type* l, size_type n)
 250     : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
 251   hash_multiset(const value_type* f, const value_type* l, size_type n,
 252                 const hasher& hf)
 253     : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
 254   hash_multiset(const value_type* f, const value_type* l, size_type n,
 255                 const hasher& hf, const key_equal& eql)
 256     : rep(n, hf, eql) { rep.insert_equal(f, l); }
 257
 258   hash_multiset(const_iterator f, const_iterator l)
 259     : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
 260   hash_multiset(const_iterator f, const_iterator l, size_type n)
 261     : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
 262   hash_multiset(const_iterator f, const_iterator l, size_type n,
 263                 const hasher& hf)
 264     : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
 265   hash_multiset(const_iterator f, const_iterator l, size_type n,
 266                 const hasher& hf, const key_equal& eql)
 267     : rep(n, hf, eql) { rep.insert_equal(f, l); }
 268 #endif /*__STL_MEMBER_TEMPLATES */
 269
 270 public:
 271   size_type size() const { return rep.size(); }
 272   size_type max_size() const { return rep.max_size(); }
 273   bool empty() const { return rep.empty(); }
 274   void swap(hash_multiset& hs) { rep.swap(hs.rep); }
 275   friend bool operator== __STL_NULL_TMPL_ARGS (const hash_multiset&,
 276                                                const hash_multiset&);
 277
 278   iterator begin() const { return rep.begin(); }
 279   iterator end() const { return rep.end(); }
 280
 281 public:
 282   iterator insert(const value_type& obj) { return rep.insert_equal(obj); }
 283 #ifdef __STL_MEMBER_TEMPLATES
 284   template <class InputIterator>
 285   void insert(InputIterator f, InputIterator l) { rep.insert_equal(f,l); }
 286 #else
 287   void insert(const value_type* f, const value_type* l) {
 288     rep.insert_equal(f,l);
 289   }
 290   void insert(const_iterator f, const_iterator l) { rep.insert_equal(f, l); }
 291 #endif /*__STL_MEMBER_TEMPLATES */
 292   iterator insert_noresize(const value_type& obj)
 293     { return rep.insert_equal_noresize(obj); }
 294
 295   iterator find(const key_type& key) const { return rep.find(key); }
 296
 297   size_type count(const key_type& key) const { return rep.count(key); }
 298
 299   pair<iterator, iterator> equal_range(const key_type& key) const
 300     { return rep.equal_range(key); }
 301
 302   size_type erase(const key_type& key) {return rep.erase(key); }
 303   void erase(iterator it) { rep.erase(it); }
 304   void erase(iterator f, iterator l) { rep.erase(f, l); }
 305   void clear() { rep.clear(); }
 306
 307 public:
 308   void resize(size_type hint) { rep.resize(hint); }
 309   size_type bucket_count() const { return rep.bucket_count(); }
 310   size_type max_bucket_count() const { return rep.max_bucket_count(); }
 311   size_type elems_in_bucket(size_type n) const
 312     { return rep.elems_in_bucket(n); }
 313 };
 314
 315 template <class Val, class HashFcn, class EqualKey, class Alloc>
 316 inline bool operator==(const hash_multiset<Val, HashFcn, EqualKey, Alloc>& hs1,
 317                        const hash_multiset<Val, HashFcn, EqualKey, Alloc>& hs2)
 318 {
 319   return hs1.rep == hs2.rep;
 320 }
 321
 322 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 323
 324 template <class Val, class HashFcn, class EqualKey, class Alloc>
 325 inline void swap(hash_multiset<Val, HashFcn, EqualKey, Alloc>& hs1,
 326                  hash_multiset<Val, HashFcn, EqualKey, Alloc>& hs2)
 327   hs1.swap(hs2);
 328 }
 329
 330 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 331
 332 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
 333 #pragma reset woff 1174
 334 #endif
 335
 336 __STL_END_NAMESPACE
 337
 338 #endif /* __SGI_STL_INTERNAL_HASH_SET_H */
 339
 340 // Local Variables:
 341 // mode:C++
 342 // End: