# hash_multimap.h

Go to the documentation of this file.

    00001 // Debugging hash_multimap 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_multimap.h
    00032  *  This file is a GNU debug extension to the Standard C++ Library.
    00033  */
    00034
    00035 #ifndef _GLIBCXX_DEBUG_HASH_MULTIMAP_H
    00036 #define _GLIBCXX_DEBUG_HASH_MULTIMAP_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, typename _Tp,
    00046        typename _HashFcn  = __gnu_cxx::hash<_Value>,
    00047        typename _EqualKey = std::equal_to<_Value>,
    00048        typename _Alloc =  std::allocator<_Value> >
    00049     class hash_multimap
    00050     : public _GLIBCXX_EXT::hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>,
    00051       public __gnu_debug::_Safe_sequence<hash_multimap<_Value, _Tp, _HashFcn,
    00052                                _EqualKey, _Alloc> >
    00053     {
    00054       typedef _GLIBCXX_EXT::hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>
    00055                             _Base;
    00056       typedef __gnu_debug::_Safe_sequence<hash_multimap> _Safe_base;
    00057
    00058   public:
    00059       typedef typename _Base::key_type          key_type;
    00060       typedef typename _Base::data_type         data_type;
    00061       typedef typename _Base::mapped_type       mapped_type;
    00062       typedef typename _Base::value_type        value_type;
    00063       typedef typename _Base::hasher            hasher;
    00064       typedef typename _Base::key_equal         key_equal;
    00065       typedef typename _Base::size_type         size_type;
    00066       typedef typename _Base::difference_type       difference_type;
    00067       typedef typename _Base::pointer           pointer;
    00068       typedef typename _Base::const_pointer     const_pointer;
    00069       typedef typename _Base::reference         reference;
    00070       typedef typename _Base::const_reference       const_reference;
    00071
    00072       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
    00073                       hash_multimap> iterator;
    00074       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
    00075                       hash_multimap> const_iterator;
    00076
    00077       typedef typename _Base::allocator_type              allocator_type;
    00078
    00079       using _Base::hash_funct;
    00080       using _Base::key_eq;
    00081       using _Base::get_allocator;
    00082
    00083       hash_multimap() { }
    00084
    00085       explicit hash_multimap(size_type __n) : _Base(__n) { }
    00086
    00087       hash_multimap(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
    00088
    00089       hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
    00090             const allocator_type& __a = allocator_type())
    00091       : _Base(__n, __hf, __eql, __a) { }
    00092
    00093       template<typename _InputIterator>
    00094         hash_multimap(_InputIterator __f, _InputIterator __l)
    00095     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
    00096
    00097       template<typename _InputIterator>
    00098         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
    00099         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
    00100
    00101       template<typename _InputIterator>
    00102         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
    00103               const hasher& __hf)
    00104     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
    00105
    00106       template<typename _InputIterator>
    00107         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
    00108               const hasher& __hf, const key_equal& __eql,
    00109               const allocator_type& __a = allocator_type())
    00110     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
    00111         __eql, __a) { }
    00112
    00113       using _Base::size;
    00114       using _Base::max_size;
    00115       using _Base::empty;
    00116
    00117       void
    00118       swap(hash_multimap& __x)
    00119       {
    00120     _Base::swap(__x);
    00121     this->_M_swap(__x);
    00122       }
    00123
    00124       iterator
    00125       begin() { return iterator(_Base::begin(), this); }
    00126
    00127       iterator
    00128       end()   { return iterator(_Base::end(),   this); }
    00129
    00130       const_iterator
    00131       begin() const
    00132       { return const_iterator(_Base::begin(), this); }
    00133
    00134       const_iterator
    00135       end() const
    00136       { return const_iterator(_Base::end(),   this); }
    00137
    00138       iterator
    00139       insert(const value_type& __obj)
    00140       { return iterator(_Base::insert(__obj), this); }
    00141
    00142       template <typename _InputIterator>
    00143         void
    00144         insert(_InputIterator __first, _InputIterator __last)
    00145         {
    00146       __glibcxx_check_valid_range(__first, __last);
    00147       _Base::insert(__first.base(), __last.base());
    00148     }
    00149
    00150       iterator
    00151       insert_noresize(const value_type& __obj)
    00152       { return iterator(_Base::insert_noresize(__obj), this); }
    00153
    00154       iterator
    00155       find(const key_type& __key)
    00156       { return iterator(_Base::find(__key), this); }
    00157
    00158       const_iterator
    00159       find(const key_type& __key) const
    00160       { return const_iterator(_Base::find(__key), this); }
    00161
    00162       using _Base::count;
    00163
    00164       std::pair<iterator, iterator>
    00165       equal_range(const key_type& __key)
    00166       {
    00167     typedef typename _Base::iterator _Base_iterator;
    00168     std::pair<_Base_iterator, _Base_iterator> __res =
    00169                                                  _Base::equal_range(__key);
    00170     return std::make_pair(iterator(__res.first, this),
    00171                   iterator(__res.second, this));
    00172       }
    00173
    00174       std::pair<const_iterator, const_iterator>
    00175       equal_range(const key_type& __key) const
    00176       {
    00177     typedef typename _Base::const_iterator _Base_iterator;
    00178     std::pair<_Base_iterator, _Base_iterator> __res =
    00179         _Base::equal_range(__key);
    00180     return std::make_pair(const_iterator(__res.first, this),
    00181                   const_iterator(__res.second, this));
    00182       }
    00183
    00184       size_type
    00185       erase(const key_type& __key)
    00186       {
    00187     std::pair<iterator, iterator> __victims = this->equal_range(__key);
    00188     std::size_t __num_victims = 0;
    00189     while (__victims.first != __victims.second)
    00190     {
    00191       this->erase(__victims.first++);
    00192       ++__num_victims;
    00193     }
    00194     return __num_victims;
    00195       }
    00196
    00197       void
    00198       erase(iterator __it)
    00199       {
    00200     __glibcxx_check_erase(__it);
    00201     __it._M_invalidate();
    00202     _Base::erase(__it.base());
    00203       }
    00204
    00205       void
    00206       erase(iterator __first, iterator __last)
    00207       {
    00208     __glibcxx_check_erase_range(__first, __last);
    00209     for (iterator __tmp = __first; __tmp != __last;)
    00210     {
    00211       iterator __victim = __tmp++;
    00212       __victim._M_invalidate();
    00213     }
    00214     _Base::erase(__first.base(), __last.base());
    00215       }
    00216
    00217       void
    00218       clear()
    00219       {
    00220     _Base::clear();
    00221     this->_M_invalidate_all();
    00222       }
    00223
    00224       using _Base::resize;
    00225       using _Base::bucket_count;
    00226       using _Base::max_bucket_count;
    00227       using _Base::elems_in_bucket;
    00228
    00229       _Base&
    00230       _M_base()       { return *this; }
    00231
    00232       const _Base&
    00233       _M_base() const { return *this; }
    00234
    00235     private:
    00236       void
    00237       _M_invalidate_all()
    00238       {
    00239     typedef typename _Base::const_iterator _Base_const_iterator;
    00240     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
    00241     this->_M_invalidate_if(_Not_equal(_M_base().end()));
    00242       }
    00243     };
    00244
    00245   template<typename _Value, typename _Tp, typename _HashFcn,
    00246        typename _EqualKey, typename _Alloc>
    00247     inline bool
    00248     operator==(const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __x,
    00249            const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __y)
    00250     { return __x._M_base() == __y._M_base(); }
    00251
    00252   template<typename _Value, typename _Tp, typename _HashFcn,
    00253        typename _EqualKey, typename _Alloc>
    00254     inline bool
    00255     operator!=(const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __x,
    00256            const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __y)
    00257     { return __x._M_base() != __y._M_base(); }
    00258
    00259   template<typename _Value, typename _Tp, typename _HashFcn,
    00260        typename _EqualKey, typename _Alloc>
    00261     inline void
    00262     swap(hash_multimap<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
    00263      hash_multimap<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
    00264     { __x.swap(__y); }
    00265 } // namespace __debug
    00266 } // namespace __gnu_cxx
    00267
    00268 #endif