# hash_multiset.h

    00001 // Debugging hash_multiset implementation -*- C++ -*-
    00002
    00003 // Copyright (C) 2003
    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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
    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 #ifndef _GLIBCXX_DEBUG_HASH_MULTISET_H
    00032 #define _GLIBCXX_DEBUG_HASH_MULTISET_H 1
    00033
    00034 #include <debug/safe_sequence.h>
    00035 #include <debug/safe_iterator.h>
    00036
    00037 namespace __gnu_debug_def
    00038 {
    00039   template<typename _Value,
    00040        typename _HashFcn  = __gnu_cxx::hash<_Value>,
    00041        typename _EqualKey = std::equal_to<_Value>,
    00042        typename _Alloc =  std::allocator<_Value> >
    00043     class hash_multiset
    00044     : public __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>,
    00045       public __gnu_debug::_Safe_sequence<hash_multiset<_Value, _HashFcn,
    00046                                _EqualKey, _Alloc> >
    00047     {
    00048       typedef __gnu_cxx:: hash_multiset<_Value,_HashFcn, _EqualKey,_Alloc>
    00049                             _Base;
    00050       typedef __gnu_debug::_Safe_sequence<hash_multiset> _Safe_base;
    00051
    00052   public:
    00053     typedef typename _Base::key_type            key_type;
    00054     typedef typename _Base::value_type          value_type;
    00055     typedef typename _Base::hasher          hasher;
    00056     typedef typename _Base::key_equal           key_equal;
    00057     typedef typename _Base::size_type           size_type;
    00058     typedef typename _Base::difference_type     difference_type;
    00059     typedef typename _Base::pointer         pointer;
    00060     typedef typename _Base::const_pointer       const_pointer;
    00061     typedef typename _Base::reference           reference;
    00062     typedef typename _Base::const_reference     const_reference;
    00063
    00064     typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
    00065                      hash_multiset> iterator;
    00066     typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
    00067                      hash_multiset> const_iterator;
    00068
    00069     typedef typename _Base::allocator_type              allocator_type;
    00070
    00071     using _Base::hash_funct;
    00072     using _Base::key_eq;
    00073     using _Base::get_allocator;
    00074
    00075     hash_multiset() { }
    00076
    00077     explicit hash_multiset(size_type __n) : _Base(__n) { }
    00078
    00079     hash_multiset(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
    00080
    00081     hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
    00082           const allocator_type& __a = allocator_type())
    00083     : _Base(__n, __hf, __eql, __a)
    00084     { }
    00085
    00086     template<typename _InputIterator>
    00087       hash_multiset(_InputIterator __f, _InputIterator __l)
    00088       : _Base(__gnu_debug::__check_valid_range(__f, __l), __l)
    00089       { }
    00090
    00091     template<typename _InputIterator>
    00092       hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
    00093       : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n)
    00094       { }
    00095
    00096     template<typename _InputIterator>
    00097       hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
    00098             const hasher& __hf)
    00099       : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf)
    00100       { }
    00101
    00102     template<typename _InputIterator>
    00103       hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
    00104             const hasher& __hf, const key_equal& __eql,
    00105             const allocator_type& __a = allocator_type())
    00106       : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
    00107           __eql, __a)
    00108       { }
    00109
    00110     hash_multiset(const _Base& __x) : _Base(__x), _Safe_base() { }
    00111
    00112     using _Base::size;
    00113     using _Base::max_size;
    00114     using _Base::empty;
    00115
    00116     void
    00117     swap(hash_multiset& __x)
    00118     {
    00119       _Base::swap(__x);
    00120       this->_M_swap(__x);
    00121     }
    00122
    00123     iterator begin() const { return iterator(_Base::begin(), this); }
    00124     iterator end() const   { return iterator(_Base::end(),   this); }
    00125
    00126     iterator
    00127     insert(const value_type& __obj)
    00128     { return iterator(_Base::insert(__obj), this); }
    00129
    00130     template <typename _InputIterator>
    00131       void
    00132       insert(_InputIterator __first, _InputIterator __last)
    00133       {
    00134     __glibcxx_check_valid_range(__first, __last);
    00135     _Base::insert(__first.base(), __last.base());
    00136       }
    00137
    00138
    00139     iterator
    00140     insert_noresize(const value_type& __obj)
    00141     { return iterator(_Base::insert_noresize(__obj), this); }
    00142
    00143     iterator
    00144     find(const key_type& __key) const
    00145     { return iterator(_Base::find(__key), this); }
    00146
    00147     using _Base::count;
    00148
    00149     std::pair<iterator, iterator>
    00150     equal_range(const key_type& __key) const
    00151     {
    00152       typedef typename _Base::iterator _Base_iterator;
    00153       std::pair<_Base_iterator, _Base_iterator> __res =
    00154     _Base::equal_range(__key);
    00155       return std::make_pair(iterator(__res.first, this),
    00156                 iterator(__res.second, this));
    00157     }
    00158
    00159     size_type
    00160     erase(const key_type& __key)
    00161     {
    00162       size_type __count = 0;
    00163       std::pair<iterator, iterator> __victims = this->equal_range(__key);
    00164       while (__victims.first != __victims.second)
    00165     {
    00166       this->erase(__victims++);
    00167       ++__count;
    00168     }
    00169       return __count;
    00170     }
    00171
    00172     void
    00173     erase(iterator __it)
    00174     {
    00175       __glibcxx_check_erase(__it);
    00176       __it._M_invalidate();
    00177       _Base::erase(__it.base());
    00178     }
    00179
    00180     void
    00181     erase(iterator __first, iterator __last)
    00182     {
    00183       __glibcxx_check_erase_range(__first, __last);
    00184       for (iterator __tmp = __first; __tmp != __last;)
    00185     {
    00186       iterator __victim = __tmp++;
    00187       __victim._M_invalidate();
    00188     }
    00189       _Base::erase(__first.base(), __last.base());
    00190     }
    00191
    00192     void
    00193     clear()
    00194     {
    00195       _Base::clear();
    00196       this->_M_invalidate_all();
    00197     }
    00198
    00199     using _Base::resize;
    00200     using _Base::bucket_count;
    00201     using _Base::max_bucket_count;
    00202     using _Base::elems_in_bucket;
    00203
    00204     _Base&       _M_base()       { return *this; }
    00205     const _Base& _M_base() const { return *this; }
    00206
    00207   private:
    00208     void
    00209     _M_invalidate_all()
    00210     {
    00211       typedef typename _Base::const_iterator _Base_const_iterator;
    00212       typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
    00213       this->_M_invalidate_if(_Not_equal(_M_base().end()));
    00214     }
    00215   };
    00216
    00217 template<typename _Value, typename _HashFcn, typename _EqualKey, typename _Alloc>
    00218   inline bool
    00219   operator==(const hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
    00220          const hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
    00221   { return __x._M_base() == __y._M_base(); }
    00222
    00223 template<typename _Value, typename _HashFcn, typename _EqualKey, typename _Alloc>
    00224   inline bool
    00225   operator!=(const hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
    00226          const hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
    00227   { return __x._M_base() != __y._M_base(); }
    00228
    00229 template<typename _Value, typename _HashFcn, typename _EqualKey, typename _Alloc>
    00230   inline void
    00231   swap(hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
    00232        hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
    00233   { __x.swap(__y); }
    00234 } // namespace __gnu_debug_def
    00235
    00236 #endif