# hash_set.h

Go to the documentation of this file.

    00001 // Debugging hash_set implementation -*- C++ -*-
    00002
    00003 // Copyright (C) 2003, 2005, 2006
    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 2, 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 // You should have received a copy of the GNU General Public License along
    00018 // with this library; see the file COPYING.  If not, write to the Free
    00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    00020 // USA.
    00021
    00022 // As a special exception, you may use this file as part of a free software
    00023 // library without restriction.  Specifically, if other files instantiate
    00024 // templates or use macros or inline functions from this file, or you compile
    00025 // this file and link it with other files to produce an executable, this
    00026 // file does not by itself cause the resulting executable to be covered by
    00027 // the GNU General Public License.  This exception does not however
    00028 // invalidate any other reasons why the executable file might be covered by
    00029 // the GNU General Public License.
    00030
    00031 /** @file debug/hash_set.h
    00032  *  This file is a GNU debug extension to the Standard C++ Library.
    00033  */
    00034
    00035 #ifndef _GLIBCXX_DEBUG_HASH_SET_H
    00036 #define _GLIBCXX_DEBUG_HASH_SET_H 1
    00037
    00038 #include <debug/safe_sequence.h>
    00039 #include <debug/safe_iterator.h>
    00040
    00041 namespace __gnu_cxx
    00042 {
    00043 namespace __debug
    00044 {
    00045   template<typename _Value,
    00046        typename _HashFcn  = __gnu_cxx::hash<_Value>,
    00047        typename _EqualKey = std::equal_to<_Value>,
    00048        typename _Alloc =  std::allocator<_Value> >
    00049     class hash_set
    00050     : public _GLIBCXX_EXT::hash_set<_Value, _HashFcn, _EqualKey,_Alloc>,
    00051       public __gnu_debug::_Safe_sequence<hash_set<_Value, _HashFcn, _EqualKey,
    00052                           _Alloc> >
    00053     {
    00054       typedef _GLIBCXX_EXT::hash_set<_Value, _HashFcn, _EqualKey,_Alloc> _Base;
    00055       typedef __gnu_debug::_Safe_sequence<hash_set> _Safe_base;
    00056
    00057     public:
    00058       typedef typename _Base::key_type        key_type;
    00059       typedef typename _Base::value_type      value_type;
    00060       typedef typename _Base::hasher          hasher;
    00061       typedef typename _Base::key_equal       key_equal;
    00062       typedef typename _Base::size_type       size_type;
    00063       typedef typename _Base::difference_type difference_type;
    00064       typedef typename _Base::pointer         pointer;
    00065       typedef typename _Base::const_pointer   const_pointer;
    00066       typedef typename _Base::reference       reference;
    00067       typedef typename _Base::const_reference const_reference;
    00068
    00069       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, hash_set>
    00070                                               iterator;
    00071       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
    00072                       hash_set>
    00073                                               const_iterator;
    00074
    00075       typedef typename _Base::allocator_type allocator_type;
    00076
    00077       using _Base::hash_funct;
    00078       using _Base::key_eq;
    00079       using _Base::get_allocator;
    00080
    00081       hash_set() { }
    00082
    00083       explicit hash_set(size_type __n) : _Base(__n) { }
    00084
    00085       hash_set(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
    00086
    00087       hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
    00088            const allocator_type& __a = allocator_type())
    00089       : _Base(__n, __hf, __eql, __a) { }
    00090
    00091       template<typename _InputIterator>
    00092         hash_set(_InputIterator __f, _InputIterator __l)
    00093         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
    00094
    00095       template<typename _InputIterator>
    00096         hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
    00097     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
    00098
    00099       template<typename _InputIterator>
    00100         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
    00101          const hasher& __hf)
    00102     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
    00103
    00104       template<typename _InputIterator>
    00105         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
    00106          const hasher& __hf, const key_equal& __eql,
    00107          const allocator_type& __a = allocator_type())
    00108     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
    00109         __eql, __a) { }
    00110
    00111       hash_set(const _Base& __x) : _Base(__x), _Safe_base() { }
    00112
    00113       using _Base::size;
    00114       using _Base::max_size;
    00115       using _Base::empty;
    00116
    00117       void
    00118       swap(hash_set& __x)
    00119       {
    00120     _Base::swap(__x);
    00121     this->_M_swap(__x);
    00122       }
    00123
    00124       iterator
    00125       begin() const { return iterator(_Base::begin(), this); }
    00126
    00127       iterator
    00128       end() const   { return iterator(_Base::end(),   this); }
    00129
    00130       std::pair<iterator, bool>
    00131       insert(const value_type& __obj)
    00132       {
    00133     std::pair<typename _Base::iterator, bool> __res =
    00134         _Base::insert(__obj);
    00135     return std::make_pair(iterator(__res.first, this), __res.second);
    00136       }
    00137
    00138       void
    00139       insert(const value_type* __first, const value_type* __last)
    00140       {
    00141     __glibcxx_check_valid_range(__first, __last);
    00142     _Base::insert(__first, __last);
    00143       }
    00144
    00145       template<typename _InputIterator>
    00146         void
    00147         insert(_InputIterator __first, _InputIterator __last)
    00148         {
    00149       __glibcxx_check_valid_range(__first, __last);
    00150       _Base::insert(__first.base(), __last.base());
    00151     }
    00152
    00153
    00154       std::pair<iterator, bool>
    00155       insert_noresize(const value_type& __obj)
    00156       {
    00157     std::pair<typename _Base::iterator, bool> __res =
    00158         _Base::insert_noresize(__obj);
    00159     return std::make_pair(iterator(__res.first, this), __res.second);
    00160       }
    00161
    00162       iterator
    00163       find(const key_type& __key) const
    00164       { return iterator(_Base::find(__key), this); }
    00165
    00166       using _Base::count;
    00167
    00168       std::pair<iterator, iterator>
    00169       equal_range(const key_type& __key) const
    00170       {
    00171     typedef typename _Base::iterator _Base_iterator;
    00172     std::pair<_Base_iterator, _Base_iterator> __res =
    00173       _Base::equal_range(__key);
    00174     return std::make_pair(iterator(__res.first, this),
    00175                   iterator(__res.second, this));
    00176       }
    00177
    00178       size_type
    00179       erase(const key_type& __key)
    00180       {
    00181     iterator __victim(_Base::find(__key), this);
    00182     if (__victim != end())
    00183       return this->erase(__victim), 1;
    00184     else
    00185       return 0;
    00186       }
    00187
    00188       void
    00189       erase(iterator __it)
    00190       {
    00191     __glibcxx_check_erase(__it);
    00192     __it._M_invalidate();
    00193     _Base::erase(__it.base());
    00194       }
    00195
    00196       void
    00197       erase(iterator __first, iterator __last)
    00198       {
    00199     __glibcxx_check_erase_range(__first, __last);
    00200     for (iterator __tmp = __first; __tmp != __last;)
    00201     {
    00202       iterator __victim = __tmp++;
    00203       __victim._M_invalidate();
    00204     }
    00205     _Base::erase(__first.base(), __last.base());
    00206       }
    00207
    00208       void
    00209       clear()
    00210       {
    00211     _Base::clear();
    00212     this->_M_invalidate_all();
    00213       }
    00214
    00215       using _Base::resize;
    00216       using _Base::bucket_count;
    00217       using _Base::max_bucket_count;
    00218       using _Base::elems_in_bucket;
    00219
    00220       _Base&
    00221       _M_base()       { return *this; }
    00222
    00223       const _Base&
    00224       _M_base() const { return *this; }
    00225
    00226     private:
    00227       void
    00228       _M_invalidate_all()
    00229       {
    00230     typedef typename _Base::const_iterator _Base_const_iterator;
    00231     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
    00232     this->_M_invalidate_if(_Not_equal(_M_base().end()));
    00233       }
    00234     };
    00235
    00236   template<typename _Value, typename _HashFcn, typename _EqualKey,
    00237        typename _Alloc>
    00238     inline bool
    00239     operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
    00240            const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
    00241     { return __x._M_base() == __y._M_base(); }
    00242
    00243   template<typename _Value, typename _HashFcn, typename _EqualKey,
    00244        typename _Alloc>
    00245     inline bool
    00246     operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
    00247            const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
    00248     { return __x._M_base() != __y._M_base(); }
    00249
    00250   template<typename _Value, typename _HashFcn, typename _EqualKey,
    00251        typename _Alloc>
    00252     inline void
    00253     swap(hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
    00254      hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
    00255     { __x.swap(__y); }
    00256 } // namespace __debug
    00257 } // namespace __gnu_cxx
    00258
    00259 #endif