hash_set

Go to the documentation of this file.
00001 // Hashing set implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2004, 2005, 2006 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
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 backward/hash_set
00057  *  This file is a GNU extension to the Standard C++ Library (possibly
00058  *  containing extensions from the HP/SGI STL subset).
00059  */
00060 
00061 #ifndef _HASH_SET
00062 #define _HASH_SET 1
00063 
00064 #include "backward_warning.h"
00065 #include <bits/c++config.h>
00066 #include <backward/hashtable.h>
00067 #include <bits/concept_check.h>
00068 
00069 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00070 
00071   using std::equal_to;
00072   using std::allocator;
00073   using std::pair;
00074   using std::_Identity;
00075 
00076   /**
00077    *  This is an SGI extension.
00078    *  @ingroup SGIextensions
00079    *  @doctodo
00080    */
00081   template<class _Value, class _HashFcn  = hash<_Value>,
00082        class _EqualKey = equal_to<_Value>,
00083        class _Alloc = allocator<_Value> >
00084     class hash_set
00085     {
00086       // concept requirements
00087       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
00088       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
00089       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
00090 
00091     private:
00092       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
00093             _EqualKey, _Alloc> _Ht;
00094       _Ht _M_ht;
00095 
00096     public:
00097       typedef typename _Ht::key_type key_type;
00098       typedef typename _Ht::value_type value_type;
00099       typedef typename _Ht::hasher hasher;
00100       typedef typename _Ht::key_equal key_equal;
00101       
00102       typedef typename _Ht::size_type size_type;
00103       typedef typename _Ht::difference_type difference_type;
00104       typedef typename _Alloc::pointer pointer;
00105       typedef typename _Alloc::const_pointer const_pointer;
00106       typedef typename _Alloc::reference reference;
00107       typedef typename _Alloc::const_reference const_reference;
00108       
00109       typedef typename _Ht::const_iterator iterator;
00110       typedef typename _Ht::const_iterator const_iterator;
00111       
00112       typedef typename _Ht::allocator_type allocator_type;
00113       
00114       hasher
00115       hash_funct() const
00116       { return _M_ht.hash_funct(); }
00117 
00118       key_equal
00119       key_eq() const
00120       { return _M_ht.key_eq(); }
00121 
00122       allocator_type
00123       get_allocator() const
00124       { return _M_ht.get_allocator(); }
00125 
00126       hash_set()
00127       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00128 
00129       explicit
00130       hash_set(size_type __n)
00131       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00132 
00133       hash_set(size_type __n, const hasher& __hf)
00134       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00135 
00136       hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
00137            const allocator_type& __a = allocator_type())
00138       : _M_ht(__n, __hf, __eql, __a) {}
00139 
00140       template<class _InputIterator>
00141         hash_set(_InputIterator __f, _InputIterator __l)
00142     : _M_ht(100, hasher(), key_equal(), allocator_type())
00143         { _M_ht.insert_unique(__f, __l); }
00144 
00145       template<class _InputIterator>
00146         hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
00147     : _M_ht(__n, hasher(), key_equal(), allocator_type())
00148         { _M_ht.insert_unique(__f, __l); }
00149 
00150       template<class _InputIterator>
00151         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
00152          const hasher& __hf)
00153     : _M_ht(__n, __hf, key_equal(), allocator_type())
00154         { _M_ht.insert_unique(__f, __l); }
00155 
00156       template<class _InputIterator>
00157         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
00158          const hasher& __hf, const key_equal& __eql,
00159          const allocator_type& __a = allocator_type())
00160     : _M_ht(__n, __hf, __eql, __a)
00161         { _M_ht.insert_unique(__f, __l); }
00162 
00163       size_type
00164       size() const
00165       { return _M_ht.size(); }
00166 
00167       size_type
00168       max_size() const
00169       { return _M_ht.max_size(); }
00170       
00171       bool
00172       empty() const
00173       { return _M_ht.empty(); }
00174       
00175       void
00176       swap(hash_set& __hs)
00177       { _M_ht.swap(__hs._M_ht); }
00178 
00179       template<class _Val, class _HF, class _EqK, class _Al>
00180         friend bool
00181         operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
00182            const hash_set<_Val, _HF, _EqK, _Al>&);
00183 
00184       iterator
00185       begin() const
00186       { return _M_ht.begin(); }
00187       
00188       iterator
00189       end() const
00190       { return _M_ht.end(); }
00191 
00192       pair<iterator, bool>
00193       insert(const value_type& __obj)
00194       {
00195     pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
00196     return pair<iterator,bool>(__p.first, __p.second);
00197       }
00198 
00199       template<class _InputIterator>
00200         void
00201         insert(_InputIterator __f, _InputIterator __l)
00202         { _M_ht.insert_unique(__f, __l); }
00203 
00204       pair<iterator, bool>
00205       insert_noresize(const value_type& __obj)
00206       {
00207     pair<typename _Ht::iterator, bool> __p
00208       = _M_ht.insert_unique_noresize(__obj);
00209     return pair<iterator, bool>(__p.first, __p.second);
00210       }
00211 
00212       iterator
00213       find(const key_type& __key) const
00214       { return _M_ht.find(__key); }
00215 
00216       size_type
00217       count(const key_type& __key) const
00218       { return _M_ht.count(__key); }
00219 
00220       pair<iterator, iterator>
00221       equal_range(const key_type& __key) const
00222       { return _M_ht.equal_range(__key); }
00223 
00224       size_type
00225       erase(const key_type& __key)
00226       {return _M_ht.erase(__key); }
00227       
00228       void
00229       erase(iterator __it)
00230       { _M_ht.erase(__it); }
00231       
00232       void
00233       erase(iterator __f, iterator __l)
00234       { _M_ht.erase(__f, __l); }
00235       
00236       void
00237       clear()
00238       { _M_ht.clear(); }
00239 
00240       void
00241       resize(size_type __hint)
00242       { _M_ht.resize(__hint); }
00243       
00244       size_type
00245       bucket_count() const
00246       { return _M_ht.bucket_count(); }
00247       
00248       size_type
00249       max_bucket_count() const
00250       { return _M_ht.max_bucket_count(); }
00251       
00252       size_type
00253       elems_in_bucket(size_type __n) const
00254       { return _M_ht.elems_in_bucket(__n); }
00255     };
00256 
00257   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00258     inline bool
00259     operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
00260            const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
00261     { return __hs1._M_ht == __hs2._M_ht; }
00262 
00263   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00264     inline bool
00265     operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
00266            const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
00267     { return !(__hs1 == __hs2); }
00268 
00269   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00270     inline void
00271     swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
00272      hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
00273     { __hs1.swap(__hs2); }
00274 
00275 
00276   /**
00277    *  This is an SGI extension.
00278    *  @ingroup SGIextensions
00279    *  @doctodo
00280    */
00281   template<class _Value,
00282        class _HashFcn = hash<_Value>,
00283        class _EqualKey = equal_to<_Value>,
00284        class _Alloc = allocator<_Value> >
00285     class hash_multiset
00286     {
00287       // concept requirements
00288       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
00289       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
00290       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
00291 
00292     private:
00293       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
00294             _EqualKey, _Alloc> _Ht;
00295       _Ht _M_ht;
00296 
00297     public:
00298       typedef typename _Ht::key_type key_type;
00299       typedef typename _Ht::value_type value_type;
00300       typedef typename _Ht::hasher hasher;
00301       typedef typename _Ht::key_equal key_equal;
00302       
00303       typedef typename _Ht::size_type size_type;
00304       typedef typename _Ht::difference_type difference_type;
00305       typedef typename _Alloc::pointer pointer;
00306       typedef typename _Alloc::const_pointer const_pointer;
00307       typedef typename _Alloc::reference reference;
00308       typedef typename _Alloc::const_reference const_reference;
00309 
00310       typedef typename _Ht::const_iterator iterator;
00311       typedef typename _Ht::const_iterator const_iterator;
00312       
00313       typedef typename _Ht::allocator_type allocator_type;
00314       
00315       hasher
00316       hash_funct() const
00317       { return _M_ht.hash_funct(); }
00318       
00319       key_equal
00320       key_eq() const
00321       { return _M_ht.key_eq(); }
00322       
00323       allocator_type
00324       get_allocator() const
00325       { return _M_ht.get_allocator(); }
00326 
00327       hash_multiset()
00328       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00329 
00330       explicit
00331       hash_multiset(size_type __n)
00332       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00333 
00334       hash_multiset(size_type __n, const hasher& __hf)
00335       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00336       
00337       hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
00338             const allocator_type& __a = allocator_type())
00339       : _M_ht(__n, __hf, __eql, __a) {}
00340 
00341       template<class _InputIterator>
00342         hash_multiset(_InputIterator __f, _InputIterator __l)
00343     : _M_ht(100, hasher(), key_equal(), allocator_type())
00344         { _M_ht.insert_equal(__f, __l); }
00345 
00346       template<class _InputIterator>
00347         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
00348     : _M_ht(__n, hasher(), key_equal(), allocator_type())
00349         { _M_ht.insert_equal(__f, __l); }
00350 
00351       template<class _InputIterator>
00352         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
00353               const hasher& __hf)
00354     : _M_ht(__n, __hf, key_equal(), allocator_type())
00355         { _M_ht.insert_equal(__f, __l); }
00356 
00357       template<class _InputIterator>
00358         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
00359               const hasher& __hf, const key_equal& __eql,
00360               const allocator_type& __a = allocator_type())
00361     : _M_ht(__n, __hf, __eql, __a)
00362         { _M_ht.insert_equal(__f, __l); }
00363 
00364       size_type
00365       size() const
00366       { return _M_ht.size(); }
00367 
00368       size_type
00369       max_size() const
00370       { return _M_ht.max_size(); }
00371 
00372       bool
00373       empty() const
00374       { return _M_ht.empty(); }
00375 
00376       void
00377       swap(hash_multiset& hs)
00378       { _M_ht.swap(hs._M_ht); }
00379 
00380       template<class _Val, class _HF, class _EqK, class _Al>
00381         friend bool
00382         operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
00383            const hash_multiset<_Val, _HF, _EqK, _Al>&);
00384 
00385       iterator
00386       begin() const
00387       { return _M_ht.begin(); }
00388       
00389       iterator
00390       end() const
00391       { return _M_ht.end(); }
00392 
00393       iterator
00394       insert(const value_type& __obj)
00395       { return _M_ht.insert_equal(__obj); }
00396   
00397       template<class _InputIterator>
00398         void
00399         insert(_InputIterator __f, _InputIterator __l)
00400         { _M_ht.insert_equal(__f,__l); }
00401   
00402       iterator
00403       insert_noresize(const value_type& __obj)
00404       { return _M_ht.insert_equal_noresize(__obj); }
00405 
00406       iterator
00407       find(const key_type& __key) const
00408       { return _M_ht.find(__key); }
00409 
00410       size_type
00411       count(const key_type& __key) const
00412       { return _M_ht.count(__key); }
00413 
00414       pair<iterator, iterator>
00415       equal_range(const key_type& __key) const
00416       { return _M_ht.equal_range(__key); }
00417 
00418       size_type
00419       erase(const key_type& __key)
00420       { return _M_ht.erase(__key); }
00421   
00422       void
00423       erase(iterator __it)
00424       { _M_ht.erase(__it); }
00425   
00426       void
00427       erase(iterator __f, iterator __l)
00428       { _M_ht.erase(__f, __l); }
00429   
00430       void
00431       clear()
00432       { _M_ht.clear(); }
00433 
00434       void
00435       resize(size_type __hint)
00436       { _M_ht.resize(__hint); }
00437   
00438       size_type
00439       bucket_count() const
00440       { return _M_ht.bucket_count(); }
00441 
00442       size_type
00443       max_bucket_count() const
00444       { return _M_ht.max_bucket_count(); }
00445 
00446       size_type
00447       elems_in_bucket(size_type __n) const
00448       { return _M_ht.elems_in_bucket(__n); }
00449     };
00450 
00451   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00452     inline bool
00453     operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
00454            const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
00455     { return __hs1._M_ht == __hs2._M_ht; }
00456 
00457   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00458     inline bool
00459     operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
00460            const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
00461     { return !(__hs1 == __hs2); }
00462 
00463   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00464     inline void
00465     swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
00466      hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
00467     { __hs1.swap(__hs2); }
00468 
00469 _GLIBCXX_END_NAMESPACE
00470 
00471 _GLIBCXX_BEGIN_NAMESPACE(std)
00472 
00473   // Specialization of insert_iterator so that it will work for hash_set
00474   // and hash_multiset.
00475   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00476     class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
00477                           _EqualKey, _Alloc> >
00478     {
00479     protected:
00480       typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
00481         _Container;
00482       _Container* container;
00483 
00484     public:
00485       typedef _Container          container_type;
00486       typedef output_iterator_tag iterator_category;
00487       typedef void                value_type;
00488       typedef void                difference_type;
00489       typedef void                pointer;
00490       typedef void                reference;
00491 
00492       insert_iterator(_Container& __x)
00493       : container(&__x) {}
00494       
00495       insert_iterator(_Container& __x, typename _Container::iterator)
00496       : container(&__x) {}
00497 
00498       insert_iterator<_Container>&
00499       operator=(const typename _Container::value_type& __value)
00500       {
00501     container->insert(__value);
00502     return *this;
00503       }
00504 
00505       insert_iterator<_Container>&
00506       operator*()
00507       { return *this; }
00508       
00509       insert_iterator<_Container>&
00510       operator++()
00511       { return *this; }
00512       
00513       insert_iterator<_Container>&
00514       operator++(int)
00515       { return *this; }
00516     };
00517 
00518   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00519     class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
00520                            _EqualKey, _Alloc> >
00521     {
00522     protected:
00523       typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
00524         _Container;
00525       _Container* container;
00526       typename _Container::iterator iter;
00527 
00528     public:
00529       typedef _Container          container_type;
00530       typedef output_iterator_tag iterator_category;
00531       typedef void                value_type;
00532       typedef void                difference_type;
00533       typedef void                pointer;
00534       typedef void                reference;
00535       
00536       insert_iterator(_Container& __x)
00537       : container(&__x) {}
00538       
00539       insert_iterator(_Container& __x, typename _Container::iterator)
00540       : container(&__x) {}
00541 
00542       insert_iterator<_Container>&
00543       operator=(const typename _Container::value_type& __value)
00544       {
00545     container->insert(__value);
00546     return *this;
00547       }
00548 
00549       insert_iterator<_Container>&
00550       operator*()
00551       { return *this; }
00552 
00553       insert_iterator<_Container>&
00554       operator++()
00555       { return *this; }
00556 
00557       insert_iterator<_Container>&
00558       operator++(int) { return *this; }
00559     };
00560 
00561 _GLIBCXX_END_NAMESPACE
00562 
00563 #endif

Generated on Sat Oct 25 05:09:03 2008 for libstdc++ by  doxygen 1.5.6