hash_set

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

Generated on Thu Jul 23 21:16:08 2009 for libstdc++ by  doxygen 1.5.8