libstdc++
hash_set
Go to the documentation of this file.
00001 // Hashing set implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2013 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 _BACKWARD_HASH_SET
00057 #define _BACKWARD_HASH_SET 1
00058 
00059 #ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
00060 #include "backward_warning.h"
00061 #endif
00062 
00063 #include <bits/c++config.h>
00064 #include <backward/hashtable.h>
00065 #include <bits/concept_check.h>
00066 
00067 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00068 {
00069 _GLIBCXX_BEGIN_NAMESPACE_VERSION
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_VERSION
00470 } // namespace
00471 
00472 namespace std _GLIBCXX_VISIBILITY(default)
00473 {
00474 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00475 
00476   // Specialization of insert_iterator so that it will work for hash_set
00477   // and hash_multiset.
00478   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00479     class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
00480                           _EqualKey, _Alloc> >
00481     {
00482     protected:
00483       typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
00484         _Container;
00485       _Container* container;
00486 
00487     public:
00488       typedef _Container          container_type;
00489       typedef output_iterator_tag iterator_category;
00490       typedef void                value_type;
00491       typedef void                difference_type;
00492       typedef void                pointer;
00493       typedef void                reference;
00494 
00495       insert_iterator(_Container& __x)
00496       : container(&__x) {}
00497       
00498       insert_iterator(_Container& __x, typename _Container::iterator)
00499       : container(&__x) {}
00500 
00501       insert_iterator<_Container>&
00502       operator=(const typename _Container::value_type& __value)
00503       {
00504     container->insert(__value);
00505     return *this;
00506       }
00507 
00508       insert_iterator<_Container>&
00509       operator*()
00510       { return *this; }
00511       
00512       insert_iterator<_Container>&
00513       operator++()
00514       { return *this; }
00515       
00516       insert_iterator<_Container>&
00517       operator++(int)
00518       { return *this; }
00519     };
00520 
00521   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00522     class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
00523                            _EqualKey, _Alloc> >
00524     {
00525     protected:
00526       typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
00527         _Container;
00528       _Container* container;
00529       typename _Container::iterator iter;
00530 
00531     public:
00532       typedef _Container          container_type;
00533       typedef output_iterator_tag iterator_category;
00534       typedef void                value_type;
00535       typedef void                difference_type;
00536       typedef void                pointer;
00537       typedef void                reference;
00538       
00539       insert_iterator(_Container& __x)
00540       : container(&__x) {}
00541       
00542       insert_iterator(_Container& __x, typename _Container::iterator)
00543       : container(&__x) {}
00544 
00545       insert_iterator<_Container>&
00546       operator=(const typename _Container::value_type& __value)
00547       {
00548     container->insert(__value);
00549     return *this;
00550       }
00551 
00552       insert_iterator<_Container>&
00553       operator*()
00554       { return *this; }
00555 
00556       insert_iterator<_Container>&
00557       operator++()
00558       { return *this; }
00559 
00560       insert_iterator<_Container>&
00561       operator++(int) { return *this; }
00562     };
00563 
00564 _GLIBCXX_END_NAMESPACE_VERSION
00565 } // namespace
00566 
00567 #endif