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