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

Generated on 19 Jun 2018 for libstdc++ by  doxygen 1.6.1