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 __SGI_STL_INTERNAL_HASH_SET_H
00063 #define __SGI_STL_INTERNAL_HASH_SET_H
00064 
00065 #include <ext/stl_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 declaration.
00076 
00077 template <class _Value,
00078           class _HashFcn  = hash<_Value>,
00079           class _EqualKey = equal_to<_Value>,
00080           class _Alloc =  allocator<_Value> >
00081 class hash_set;
00082 
00083 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00084 inline bool 
00085 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
00086            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2);
00087 
00088 /**
00089  *  This is an SGI extension.
00090  *  @ingroup SGIextensions
00091  *  @doctodo
00092 */
00093 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00094 class hash_set
00095 {
00096   // concept requirements
00097   __glibcpp_class_requires(_Value, _SGIAssignableConcept)
00098   __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept);
00099   __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept);
00100 
00101 private:
00102   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 
00103                     _EqualKey, _Alloc> _Ht;
00104   _Ht _M_ht;
00105 
00106 public:
00107   typedef typename _Ht::key_type key_type;
00108   typedef typename _Ht::value_type value_type;
00109   typedef typename _Ht::hasher hasher;
00110   typedef typename _Ht::key_equal key_equal;
00111 
00112   typedef typename _Ht::size_type size_type;
00113   typedef typename _Ht::difference_type difference_type;
00114   typedef typename _Alloc::pointer pointer;
00115   typedef typename _Alloc::const_pointer const_pointer;
00116   typedef typename _Alloc::reference reference;
00117   typedef typename _Alloc::const_reference const_reference;
00118 
00119   typedef typename _Ht::const_iterator iterator;
00120   typedef typename _Ht::const_iterator const_iterator;
00121 
00122   typedef typename _Ht::allocator_type allocator_type;
00123 
00124   hasher hash_funct() const { return _M_ht.hash_funct(); }
00125   key_equal key_eq() const { return _M_ht.key_eq(); }
00126   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
00127 
00128 public:
00129   hash_set()
00130     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00131   explicit hash_set(size_type __n)
00132     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00133   hash_set(size_type __n, const hasher& __hf)
00134     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00135   hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
00136            const allocator_type& __a = allocator_type())
00137     : _M_ht(__n, __hf, __eql, __a) {}
00138 
00139   template <class _InputIterator>
00140   hash_set(_InputIterator __f, _InputIterator __l)
00141     : _M_ht(100, hasher(), key_equal(), allocator_type())
00142     { _M_ht.insert_unique(__f, __l); }
00143   template <class _InputIterator>
00144   hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
00145     : _M_ht(__n, hasher(), key_equal(), allocator_type())
00146     { _M_ht.insert_unique(__f, __l); }
00147   template <class _InputIterator>
00148   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
00149            const hasher& __hf)
00150     : _M_ht(__n, __hf, key_equal(), allocator_type())
00151     { _M_ht.insert_unique(__f, __l); }
00152   template <class _InputIterator>
00153   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
00154            const hasher& __hf, const key_equal& __eql,
00155            const allocator_type& __a = allocator_type())
00156     : _M_ht(__n, __hf, __eql, __a)
00157     { _M_ht.insert_unique(__f, __l); }
00158 
00159 public:
00160   size_type size() const { return _M_ht.size(); }
00161   size_type max_size() const { return _M_ht.max_size(); }
00162   bool empty() const { return _M_ht.empty(); }
00163   void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); }
00164 
00165   template <class _Val, class _HF, class _EqK, class _Al>  
00166   friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&,
00167                           const hash_set<_Val, _HF, _EqK, _Al>&);
00168 
00169   iterator begin() const { return _M_ht.begin(); }
00170   iterator end() const { return _M_ht.end(); }
00171 
00172 public:
00173   pair<iterator, bool> insert(const value_type& __obj)
00174     {
00175       pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
00176       return pair<iterator,bool>(__p.first, __p.second);
00177     }
00178   template <class _InputIterator>
00179   void insert(_InputIterator __f, _InputIterator __l) 
00180     { _M_ht.insert_unique(__f,__l); }
00181   pair<iterator, bool> insert_noresize(const value_type& __obj)
00182   {
00183     pair<typename _Ht::iterator, bool> __p = 
00184       _M_ht.insert_unique_noresize(__obj);
00185     return pair<iterator, bool>(__p.first, __p.second);
00186   }
00187 
00188   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
00189 
00190   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
00191   
00192   pair<iterator, iterator> equal_range(const key_type& __key) const
00193     { return _M_ht.equal_range(__key); }
00194 
00195   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
00196   void erase(iterator __it) { _M_ht.erase(__it); }
00197   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
00198   void clear() { _M_ht.clear(); }
00199 
00200 public:
00201   void resize(size_type __hint) { _M_ht.resize(__hint); }
00202   size_type bucket_count() const { return _M_ht.bucket_count(); }
00203   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
00204   size_type elems_in_bucket(size_type __n) const
00205     { return _M_ht.elems_in_bucket(__n); }
00206 };
00207 
00208 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00209 inline bool 
00210 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
00211            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2)
00212 {
00213   return __hs1._M_ht == __hs2._M_ht;
00214 }
00215 
00216 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00217 inline bool 
00218 operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
00219            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) {
00220   return !(__hs1 == __hs2);
00221 }
00222 
00223 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00224 inline void 
00225 swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
00226      hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
00227 {
00228   __hs1.swap(__hs2);
00229 }
00230 
00231 
00232 template <class _Value,
00233           class _HashFcn  = hash<_Value>,
00234           class _EqualKey = equal_to<_Value>,
00235           class _Alloc =  allocator<_Value> >
00236 class hash_multiset;
00237 
00238 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00239 inline bool 
00240 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
00241            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2);
00242 
00243 
00244 /**
00245  *  This is an SGI extension.
00246  *  @ingroup SGIextensions
00247  *  @doctodo
00248 */
00249 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00250 class hash_multiset
00251 {
00252   // concept requirements
00253   __glibcpp_class_requires(_Value, _SGIAssignableConcept)
00254   __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept);
00255   __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept);
00256 
00257 private:
00258   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 
00259                     _EqualKey, _Alloc> _Ht;
00260   _Ht _M_ht;
00261 
00262 public:
00263   typedef typename _Ht::key_type key_type;
00264   typedef typename _Ht::value_type value_type;
00265   typedef typename _Ht::hasher hasher;
00266   typedef typename _Ht::key_equal key_equal;
00267 
00268   typedef typename _Ht::size_type size_type;
00269   typedef typename _Ht::difference_type difference_type;
00270   typedef typename _Alloc::pointer pointer;
00271   typedef typename _Alloc::const_pointer const_pointer;
00272   typedef typename _Alloc::reference reference;
00273   typedef typename _Alloc::const_reference const_reference;
00274 
00275   typedef typename _Ht::const_iterator iterator;
00276   typedef typename _Ht::const_iterator const_iterator;
00277 
00278   typedef typename _Ht::allocator_type allocator_type;
00279 
00280   hasher hash_funct() const { return _M_ht.hash_funct(); }
00281   key_equal key_eq() const { return _M_ht.key_eq(); }
00282   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
00283 
00284 public:
00285   hash_multiset()
00286     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00287   explicit hash_multiset(size_type __n)
00288     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00289   hash_multiset(size_type __n, const hasher& __hf)
00290     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00291   hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
00292                 const allocator_type& __a = allocator_type())
00293     : _M_ht(__n, __hf, __eql, __a) {}
00294 
00295   template <class _InputIterator>
00296   hash_multiset(_InputIterator __f, _InputIterator __l)
00297     : _M_ht(100, hasher(), key_equal(), allocator_type())
00298     { _M_ht.insert_equal(__f, __l); }
00299   template <class _InputIterator>
00300   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
00301     : _M_ht(__n, hasher(), key_equal(), allocator_type())
00302     { _M_ht.insert_equal(__f, __l); }
00303   template <class _InputIterator>
00304   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
00305                 const hasher& __hf)
00306     : _M_ht(__n, __hf, key_equal(), allocator_type())
00307     { _M_ht.insert_equal(__f, __l); }
00308   template <class _InputIterator>
00309   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
00310                 const hasher& __hf, const key_equal& __eql,
00311                 const allocator_type& __a = allocator_type())
00312     : _M_ht(__n, __hf, __eql, __a)
00313     { _M_ht.insert_equal(__f, __l); }
00314 
00315 public:
00316   size_type size() const { return _M_ht.size(); }
00317   size_type max_size() const { return _M_ht.max_size(); }
00318   bool empty() const { return _M_ht.empty(); }
00319   void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); }
00320 
00321   template <class _Val, class _HF, class _EqK, class _Al>  
00322   friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&,
00323                           const hash_multiset<_Val, _HF, _EqK, _Al>&);
00324 
00325   iterator begin() const { return _M_ht.begin(); }
00326   iterator end() const { return _M_ht.end(); }
00327 
00328 public:
00329   iterator insert(const value_type& __obj)
00330     { return _M_ht.insert_equal(__obj); }
00331   template <class _InputIterator>
00332   void insert(_InputIterator __f, _InputIterator __l) 
00333     { _M_ht.insert_equal(__f,__l); }
00334   iterator insert_noresize(const value_type& __obj)
00335     { return _M_ht.insert_equal_noresize(__obj); }    
00336 
00337   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
00338 
00339   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
00340   
00341   pair<iterator, iterator> equal_range(const key_type& __key) const
00342     { return _M_ht.equal_range(__key); }
00343 
00344   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
00345   void erase(iterator __it) { _M_ht.erase(__it); }
00346   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
00347   void clear() { _M_ht.clear(); }
00348 
00349 public:
00350   void resize(size_type __hint) { _M_ht.resize(__hint); }
00351   size_type bucket_count() const { return _M_ht.bucket_count(); }
00352   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
00353   size_type elems_in_bucket(size_type __n) const
00354     { return _M_ht.elems_in_bucket(__n); }
00355 };
00356 
00357 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00358 inline bool 
00359 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
00360            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
00361 {
00362   return __hs1._M_ht == __hs2._M_ht;
00363 }
00364 
00365 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00366 inline bool 
00367 operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
00368            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
00369   return !(__hs1 == __hs2);
00370 }
00371 
00372 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00373 inline void 
00374 swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
00375      hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
00376   __hs1.swap(__hs2);
00377 }
00378 
00379 } // namespace __gnu_cxx
00380 
00381 namespace std
00382 {
00383 // Specialization of insert_iterator so that it will work for hash_set
00384 // and hash_multiset.
00385 
00386 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00387 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
00388 protected:
00389   typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
00390   _Container* container;
00391 public:
00392   typedef _Container          container_type;
00393   typedef output_iterator_tag iterator_category;
00394   typedef void                value_type;
00395   typedef void                difference_type;
00396   typedef void                pointer;
00397   typedef void                reference;
00398 
00399   insert_iterator(_Container& __x) : container(&__x) {}
00400   insert_iterator(_Container& __x, typename _Container::iterator)
00401     : container(&__x) {}
00402   insert_iterator<_Container>&
00403   operator=(const typename _Container::value_type& __value) { 
00404     container->insert(__value);
00405     return *this;
00406   }
00407   insert_iterator<_Container>& operator*() { return *this; }
00408   insert_iterator<_Container>& operator++() { return *this; }
00409   insert_iterator<_Container>& operator++(int) { return *this; }
00410 };
00411 
00412 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00413 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
00414 protected:
00415   typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
00416   _Container* container;
00417   typename _Container::iterator iter;
00418 public:
00419   typedef _Container          container_type;
00420   typedef output_iterator_tag iterator_category;
00421   typedef void                value_type;
00422   typedef void                difference_type;
00423   typedef void                pointer;
00424   typedef void                reference;
00425 
00426   insert_iterator(_Container& __x) : container(&__x) {}
00427   insert_iterator(_Container& __x, typename _Container::iterator)
00428     : container(&__x) {}
00429   insert_iterator<_Container>&
00430   operator=(const typename _Container::value_type& __value) { 
00431     container->insert(__value);
00432     return *this;
00433   }
00434   insert_iterator<_Container>& operator*() { return *this; }
00435   insert_iterator<_Container>& operator++() { return *this; }
00436   insert_iterator<_Container>& operator++(int) { return *this; }
00437 };
00438 
00439 } // namespace std
00440 
00441 #endif /* __SGI_STL_INTERNAL_HASH_SET_H */
00442 
00443 // Local Variables:
00444 // mode:C++
00445 // End:

Generated on Thu Feb 10 23:22:55 2005 for libstdc++-v3 Source by  doxygen 1.4.0