# hash_set

Go to the documentation of this file.

    00001 // Hashing set implementation -*- C++ -*-
    00002
    00003 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
    00004 //
    00005 // This file is part of the GNU ISO C++ Library.  This library is free
    00006 // software; you can redistribute it and/or modify it under the
    00007 // terms of the GNU General Public License as published by the
    00008 // Free Software Foundation; either version 2, or (at your option)
    00009 // any later version.
    00010
    00011 // This library is distributed in the hope that it will be useful,
    00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00014 // GNU General Public License for more details.
    00015
    00016 // You should have received a copy of the GNU General Public License along
    00017 // with this library; see the file COPYING.  If not, write to the Free
    00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
    00019 // USA.
    00020
    00021 // As a special exception, you may use this file as part of a free software
    00022 // library without restriction.  Specifically, if other files instantiate
    00023 // templates or use macros or inline functions from this file, or you compile
    00024 // this file and link it with other files to produce an executable, this
    00025 // file does not by itself cause the resulting executable to be covered by
    00026 // the GNU General Public License.  This exception does not however
    00027 // invalidate any other reasons why the executable file might be covered by
    00028 // the GNU General Public License.
    00029
    00030 /*
    00031  * Copyright (c) 1996
    00032  * Silicon Graphics Computer Systems, Inc.
    00033  *
    00034  * Permission to use, copy, modify, distribute and sell this software
    00035  * and its documentation for any purpose is hereby granted without fee,
    00036  * provided that the above copyright notice appear in all copies and
    00037  * that both that copyright notice and this permission notice appear
    00038  * in supporting documentation.  Silicon Graphics makes no
    00039  * representations about the suitability of this software for any
    00040  * purpose.  It is provided "as is" without express or implied warranty.
    00041  *
    00042  *
    00043  * Copyright (c) 1994
    00044  * Hewlett-Packard Company
    00045  *
    00046  * Permission to use, copy, modify, distribute and sell this software
    00047  * and its documentation for any purpose is hereby granted without fee,
    00048  * provided that the above copyright notice appear in all copies and
    00049  * that both that copyright notice and this permission notice appear
    00050  * in supporting documentation.  Hewlett-Packard Company makes no
    00051  * representations about the suitability of this software for any
    00052  * purpose.  It is provided "as is" without express or implied warranty.
    00053  *
    00054  */
    00055
    00056 /** @file ext/hash_set
    00057  *  This file is a GNU extension to the Standard C++ Library (possibly
    00058  *  containing extensions from the HP/SGI STL subset).  You should only
    00059  *  include this header if you are using GCC 3 or later.
    00060  */
    00061
    00062 #ifndef _HASH_SET
    00063 #define _HASH_SET 1
    00064
    00065 #include <ext/hashtable.h>
    00066 #include <bits/concept_check.h>
    00067
    00068 namespace __gnu_cxx
    00069 {
    00070   using std::equal_to;
    00071   using std::allocator;
    00072   using std::pair;
    00073   using std::_Identity;
    00074
    00075   // Forward declaration of equality operator; needed for friend
    00076   // declaration.
    00077   template <class _Value, class _HashFcn  = hash<_Value>,
    00078         class _EqualKey = equal_to<_Value>,
    00079         class _Alloc =  allocator<_Value> >
    00080   class hash_set;
    00081
    00082   template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
    00083     inline bool
    00084     operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
    00085            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2);
    00086
    00087 /**
    00088  *  This is an SGI extension.
    00089  *  @ingroup SGIextensions
    00090  *  @doctodo
    00091 */
    00092 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
    00093 class hash_set
    00094 {
    00095   // concept requirements
    00096   __glibcxx_class_requires(_Value, _SGIAssignableConcept)
    00097   __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
    00098   __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
    00099
    00100 private:
    00101   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
    00102                     _EqualKey, _Alloc> _Ht;
    00103   _Ht _M_ht;
    00104
    00105 public:
    00106   typedef typename _Ht::key_type key_type;
    00107   typedef typename _Ht::value_type value_type;
    00108   typedef typename _Ht::hasher hasher;
    00109   typedef typename _Ht::key_equal key_equal;
    00110
    00111   typedef typename _Ht::size_type size_type;
    00112   typedef typename _Ht::difference_type difference_type;
    00113   typedef typename _Alloc::pointer pointer;
    00114   typedef typename _Alloc::const_pointer const_pointer;
    00115   typedef typename _Alloc::reference reference;
    00116   typedef typename _Alloc::const_reference const_reference;
    00117
    00118   typedef typename _Ht::const_iterator iterator;
    00119   typedef typename _Ht::const_iterator const_iterator;
    00120
    00121   typedef typename _Ht::allocator_type allocator_type;
    00122
    00123   hasher hash_funct() const { return _M_ht.hash_funct(); }
    00124   key_equal key_eq() const { return _M_ht.key_eq(); }
    00125   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
    00126
    00127 public:
    00128   hash_set()
    00129     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
    00130   explicit hash_set(size_type __n)
    00131     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
    00132   hash_set(size_type __n, const hasher& __hf)
    00133     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
    00134   hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
    00135            const allocator_type& __a = allocator_type())
    00136     : _M_ht(__n, __hf, __eql, __a) {}
    00137
    00138   template <class _InputIterator>
    00139   hash_set(_InputIterator __f, _InputIterator __l)
    00140     : _M_ht(100, hasher(), key_equal(), allocator_type())
    00141     { _M_ht.insert_unique(__f, __l); }
    00142   template <class _InputIterator>
    00143   hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
    00144     : _M_ht(__n, hasher(), key_equal(), allocator_type())
    00145     { _M_ht.insert_unique(__f, __l); }
    00146   template <class _InputIterator>
    00147   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
    00148            const hasher& __hf)
    00149     : _M_ht(__n, __hf, key_equal(), allocator_type())
    00150     { _M_ht.insert_unique(__f, __l); }
    00151   template <class _InputIterator>
    00152   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
    00153            const hasher& __hf, const key_equal& __eql,
    00154            const allocator_type& __a = allocator_type())
    00155     : _M_ht(__n, __hf, __eql, __a)
    00156     { _M_ht.insert_unique(__f, __l); }
    00157
    00158 public:
    00159   size_type size() const { return _M_ht.size(); }
    00160   size_type max_size() const { return _M_ht.max_size(); }
    00161   bool empty() const { return _M_ht.empty(); }
    00162   void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); }
    00163
    00164   template <class _Val, class _HF, class _EqK, class _Al>
    00165   friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&,
    00166                           const hash_set<_Val, _HF, _EqK, _Al>&);
    00167
    00168   iterator begin() const { return _M_ht.begin(); }
    00169   iterator end() const { return _M_ht.end(); }
    00170
    00171 public:
    00172   pair<iterator, bool> insert(const value_type& __obj)
    00173     {
    00174       pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
    00175       return pair<iterator,bool>(__p.first, __p.second);
    00176     }
    00177   template <class _InputIterator>
    00178   void insert(_InputIterator __f, _InputIterator __l)
    00179     { _M_ht.insert_unique(__f,__l); }
    00180   pair<iterator, bool> insert_noresize(const value_type& __obj)
    00181   {
    00182     pair<typename _Ht::iterator, bool> __p =
    00183       _M_ht.insert_unique_noresize(__obj);
    00184     return pair<iterator, bool>(__p.first, __p.second);
    00185   }
    00186
    00187   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
    00188
    00189   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
    00190
    00191   pair<iterator, iterator> equal_range(const key_type& __key) const
    00192     { return _M_ht.equal_range(__key); }
    00193
    00194   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
    00195   void erase(iterator __it) { _M_ht.erase(__it); }
    00196   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
    00197   void clear() { _M_ht.clear(); }
    00198
    00199 public:
    00200   void resize(size_type __hint) { _M_ht.resize(__hint); }
    00201   size_type bucket_count() const { return _M_ht.bucket_count(); }
    00202   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
    00203   size_type elems_in_bucket(size_type __n) const
    00204     { return _M_ht.elems_in_bucket(__n); }
    00205 };
    00206
    00207 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
    00208 inline bool
    00209 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
    00210            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2)
    00211 {
    00212   return __hs1._M_ht == __hs2._M_ht;
    00213 }
    00214
    00215 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
    00216 inline bool
    00217 operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
    00218            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) {
    00219   return !(__hs1 == __hs2);
    00220 }
    00221
    00222 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
    00223 inline void
    00224 swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
    00225      hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
    00226 {
    00227   __hs1.swap(__hs2);
    00228 }
    00229
    00230
    00231 template <class _Value,
    00232           class _HashFcn  = hash<_Value>,
    00233           class _EqualKey = equal_to<_Value>,
    00234           class _Alloc =  allocator<_Value> >
    00235 class hash_multiset;
    00236
    00237 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
    00238 inline bool
    00239 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
    00240            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2);
    00241
    00242
    00243 /**
    00244  *  This is an SGI extension.
    00245  *  @ingroup SGIextensions
    00246  *  @doctodo
    00247 */
    00248 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
    00249 class hash_multiset
    00250 {
    00251   // concept requirements
    00252   __glibcxx_class_requires(_Value, _SGIAssignableConcept)
    00253   __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
    00254   __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
    00255
    00256 private:
    00257   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
    00258                     _EqualKey, _Alloc> _Ht;
    00259   _Ht _M_ht;
    00260
    00261 public:
    00262   typedef typename _Ht::key_type key_type;
    00263   typedef typename _Ht::value_type value_type;
    00264   typedef typename _Ht::hasher hasher;
    00265   typedef typename _Ht::key_equal key_equal;
    00266
    00267   typedef typename _Ht::size_type size_type;
    00268   typedef typename _Ht::difference_type difference_type;
    00269   typedef typename _Alloc::pointer pointer;
    00270   typedef typename _Alloc::const_pointer const_pointer;
    00271   typedef typename _Alloc::reference reference;
    00272   typedef typename _Alloc::const_reference const_reference;
    00273
    00274   typedef typename _Ht::const_iterator iterator;
    00275   typedef typename _Ht::const_iterator const_iterator;
    00276
    00277   typedef typename _Ht::allocator_type allocator_type;
    00278
    00279   hasher hash_funct() const { return _M_ht.hash_funct(); }
    00280   key_equal key_eq() const { return _M_ht.key_eq(); }
    00281   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
    00282
    00283 public:
    00284   hash_multiset()
    00285     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
    00286   explicit hash_multiset(size_type __n)
    00287     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
    00288   hash_multiset(size_type __n, const hasher& __hf)
    00289     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
    00290   hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
    00291                 const allocator_type& __a = allocator_type())
    00292     : _M_ht(__n, __hf, __eql, __a) {}
    00293
    00294   template <class _InputIterator>
    00295   hash_multiset(_InputIterator __f, _InputIterator __l)
    00296     : _M_ht(100, hasher(), key_equal(), allocator_type())
    00297     { _M_ht.insert_equal(__f, __l); }
    00298   template <class _InputIterator>
    00299   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
    00300     : _M_ht(__n, hasher(), key_equal(), allocator_type())
    00301     { _M_ht.insert_equal(__f, __l); }
    00302   template <class _InputIterator>
    00303   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
    00304                 const hasher& __hf)
    00305     : _M_ht(__n, __hf, key_equal(), allocator_type())
    00306     { _M_ht.insert_equal(__f, __l); }
    00307   template <class _InputIterator>
    00308   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
    00309                 const hasher& __hf, const key_equal& __eql,
    00310                 const allocator_type& __a = allocator_type())
    00311     : _M_ht(__n, __hf, __eql, __a)
    00312     { _M_ht.insert_equal(__f, __l); }
    00313
    00314 public:
    00315   size_type size() const { return _M_ht.size(); }
    00316   size_type max_size() const { return _M_ht.max_size(); }
    00317   bool empty() const { return _M_ht.empty(); }
    00318   void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); }
    00319
    00320   template <class _Val, class _HF, class _EqK, class _Al>
    00321   friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&,
    00322                           const hash_multiset<_Val, _HF, _EqK, _Al>&);
    00323
    00324   iterator begin() const { return _M_ht.begin(); }
    00325   iterator end() const { return _M_ht.end(); }
    00326
    00327 public:
    00328   iterator insert(const value_type& __obj)
    00329     { return _M_ht.insert_equal(__obj); }
    00330   template <class _InputIterator>
    00331   void insert(_InputIterator __f, _InputIterator __l)
    00332     { _M_ht.insert_equal(__f,__l); }
    00333   iterator insert_noresize(const value_type& __obj)
    00334     { return _M_ht.insert_equal_noresize(__obj); }
    00335
    00336   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
    00337
    00338   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
    00339
    00340   pair<iterator, iterator> equal_range(const key_type& __key) const
    00341     { return _M_ht.equal_range(__key); }
    00342
    00343   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
    00344   void erase(iterator __it) { _M_ht.erase(__it); }
    00345   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
    00346   void clear() { _M_ht.clear(); }
    00347
    00348 public:
    00349   void resize(size_type __hint) { _M_ht.resize(__hint); }
    00350   size_type bucket_count() const { return _M_ht.bucket_count(); }
    00351   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
    00352   size_type elems_in_bucket(size_type __n) const
    00353     { return _M_ht.elems_in_bucket(__n); }
    00354 };
    00355
    00356 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
    00357 inline bool
    00358 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
    00359            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
    00360 {
    00361   return __hs1._M_ht == __hs2._M_ht;
    00362 }
    00363
    00364 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
    00365 inline bool
    00366 operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
    00367            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
    00368   return !(__hs1 == __hs2);
    00369 }
    00370
    00371 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
    00372 inline void
    00373 swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
    00374      hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
    00375   __hs1.swap(__hs2);
    00376 }
    00377
    00378 } // namespace __gnu_cxx
    00379
    00380 namespace std
    00381 {
    00382 // Specialization of insert_iterator so that it will work for hash_set
    00383 // and hash_multiset.
    00384
    00385 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
    00386 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
    00387 protected:
    00388   typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
    00389   _Container* container;
    00390 public:
    00391   typedef _Container          container_type;
    00392   typedef output_iterator_tag iterator_category;
    00393   typedef void                value_type;
    00394   typedef void                difference_type;
    00395   typedef void                pointer;
    00396   typedef void                reference;
    00397
    00398   insert_iterator(_Container& __x) : container(&__x) {}
    00399   insert_iterator(_Container& __x, typename _Container::iterator)
    00400     : container(&__x) {}
    00401   insert_iterator<_Container>&
    00402   operator=(const typename _Container::value_type& __value) {
    00403     container->insert(__value);
    00404     return *this;
    00405   }
    00406   insert_iterator<_Container>& operator*() { return *this; }
    00407   insert_iterator<_Container>& operator++() { return *this; }
    00408   insert_iterator<_Container>& operator++(int) { return *this; }
    00409 };
    00410
    00411 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
    00412 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
    00413 protected:
    00414   typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
    00415   _Container* container;
    00416   typename _Container::iterator iter;
    00417 public:
    00418   typedef _Container          container_type;
    00419   typedef output_iterator_tag iterator_category;
    00420   typedef void                value_type;
    00421   typedef void                difference_type;
    00422   typedef void                pointer;
    00423   typedef void                reference;
    00424
    00425   insert_iterator(_Container& __x) : container(&__x) {}
    00426   insert_iterator(_Container& __x, typename _Container::iterator)
    00427     : container(&__x) {}
    00428   insert_iterator<_Container>&
    00429   operator=(const typename _Container::value_type& __value) {
    00430     container->insert(__value);
    00431     return *this;
    00432   }
    00433   insert_iterator<_Container>& operator*() { return *this; }
    00434   insert_iterator<_Container>& operator++() { return *this; }
    00435   insert_iterator<_Container>& operator++(int) { return *this; }
    00436 };
    00437 } // namespace std
    00438
    00439 #endif