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