libstdc++
debug/unordered_map
Go to the documentation of this file.
00001 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /** @file debug/unordered_map
00027  *  This file is a GNU debug extension to the Standard C++ Library.
00028  */
00029 
00030 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
00031 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
00032 
00033 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00034 # include <bits/c++0x_warning.h>
00035 #else
00036 # include <unordered_map>
00037 
00038 #include <debug/safe_sequence.h>
00039 #include <debug/safe_iterator.h>
00040 
00041 namespace std _GLIBCXX_VISIBILITY(default)
00042 {
00043 namespace __debug
00044 {
00045   /// Class std::unordered_map with safety/checking/debug instrumentation.
00046   template<typename _Key, typename _Tp,
00047        typename _Hash = std::hash<_Key>,
00048        typename _Pred = std::equal_to<_Key>,
00049        typename _Alloc = std::allocator<_Key> >
00050     class unordered_map
00051     : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
00052       public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,
00053                                _Pred, _Alloc> >
00054     {
00055       typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
00056                         _Pred, _Alloc> _Base;
00057       typedef __gnu_debug::_Safe_sequence<unordered_map> _Safe_base;
00058       typedef typename _Base::const_iterator _Base_const_iterator;
00059       typedef typename _Base::iterator _Base_iterator;
00060       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00061 
00062     public:
00063       typedef typename _Base::size_type       size_type;
00064       typedef typename _Base::hasher          hasher;
00065       typedef typename _Base::key_equal       key_equal;
00066       typedef typename _Base::allocator_type  allocator_type;
00067 
00068       typedef typename _Base::key_type        key_type;
00069       typedef typename _Base::value_type      value_type;
00070 
00071       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00072                       unordered_map> iterator;
00073       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00074                       unordered_map> const_iterator;
00075 
00076       explicit
00077       unordered_map(size_type __n = 10,
00078             const hasher& __hf = hasher(),
00079             const key_equal& __eql = key_equal(),
00080             const allocator_type& __a = allocator_type())
00081       : _Base(__n, __hf, __eql, __a) { }
00082 
00083       template<typename _InputIterator>
00084         unordered_map(_InputIterator __first, _InputIterator __last, 
00085               size_type __n = 0,
00086               const hasher& __hf = hasher(), 
00087               const key_equal& __eql = key_equal(), 
00088               const allocator_type& __a = allocator_type())
00089     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00090                                      __last)),
00091         __gnu_debug::__base(__last), __n,
00092         __hf, __eql, __a), _Safe_base() { }
00093 
00094       unordered_map(const unordered_map& __x) 
00095       : _Base(__x), _Safe_base() { }
00096 
00097       unordered_map(const _Base& __x)
00098       : _Base(__x), _Safe_base() { }
00099 
00100       unordered_map(unordered_map&& __x)
00101       : _Base(std::move(__x)), _Safe_base() { }
00102 
00103       unordered_map(initializer_list<value_type> __l,
00104             size_type __n = 0,
00105             const hasher& __hf = hasher(),
00106             const key_equal& __eql = key_equal(),
00107             const allocator_type& __a = allocator_type())
00108       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
00109 
00110       unordered_map&
00111       operator=(const unordered_map& __x)
00112       {
00113     *static_cast<_Base*>(this) = __x;
00114     this->_M_invalidate_all();
00115     return *this;
00116       }
00117 
00118       unordered_map&
00119       operator=(unordered_map&& __x)
00120       {
00121     // NB: DR 1204.
00122     // NB: DR 675.
00123     clear();
00124     swap(__x);
00125     return *this;
00126       }
00127 
00128       unordered_map&
00129       operator=(initializer_list<value_type> __l)
00130       {
00131     this->clear();
00132     this->insert(__l);
00133     return *this;
00134       }
00135 
00136       void
00137       swap(unordered_map& __x)
00138       {
00139     _Base::swap(__x);
00140     _Safe_base::_M_swap(__x);
00141       }
00142 
00143       void
00144       clear()
00145       {
00146     _Base::clear();
00147     this->_M_invalidate_all();
00148       }
00149 
00150       iterator 
00151       begin()
00152       { return iterator(_Base::begin(), this); }
00153 
00154       const_iterator
00155       begin() const
00156       { return const_iterator(_Base::begin(), this); }
00157 
00158       iterator
00159       end()
00160       { return iterator(_Base::end(), this); }
00161 
00162       const_iterator
00163       end() const
00164       { return const_iterator(_Base::end(), this); }
00165 
00166       const_iterator
00167       cbegin() const
00168       { return const_iterator(_Base::begin(), this); }
00169 
00170       const_iterator
00171       cend() const
00172       { return const_iterator(_Base::end(), this); }
00173 
00174       // local versions
00175       using _Base::begin;
00176       using _Base::end;
00177       using _Base::cbegin;
00178       using _Base::cend;
00179 
00180       std::pair<iterator, bool>
00181       insert(const value_type& __obj)
00182       {
00183     std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
00184     return std::make_pair(iterator(__res.first, this), __res.second);
00185       }
00186 
00187       iterator
00188       insert(const_iterator __hint, const value_type& __obj)
00189       {
00190     __glibcxx_check_insert(__hint);
00191     return iterator(_Base::insert(__hint.base(), __obj), this);
00192       }
00193 
00194       template<typename _Pair, typename = typename
00195            std::enable_if<std::is_convertible<_Pair,
00196                           value_type>::value>::type>
00197         std::pair<iterator, bool>
00198         insert(_Pair&& __obj)
00199         {
00200       std::pair<_Base_iterator, bool> __res =
00201         _Base::insert(std::forward<_Pair>(__obj));
00202       return std::make_pair(iterator(__res.first, this), __res.second);
00203     }
00204 
00205       template<typename _Pair, typename = typename
00206            std::enable_if<std::is_convertible<_Pair,
00207                           value_type>::value>::type>
00208         iterator
00209         insert(const_iterator __hint, _Pair&& __obj)
00210         {
00211       __glibcxx_check_insert(__hint);
00212       return iterator(_Base::insert(__hint.base(),
00213                     std::forward<_Pair>(__obj)),
00214               this);
00215     }
00216 
00217       void
00218       insert(std::initializer_list<value_type> __l)
00219       { _Base::insert(__l); }
00220 
00221       template<typename _InputIterator>
00222         void
00223         insert(_InputIterator __first, _InputIterator __last)
00224         {
00225       __glibcxx_check_valid_range(__first, __last);
00226       _Base::insert(__gnu_debug::__base(__first),
00227             __gnu_debug::__base(__last));
00228     }
00229 
00230       iterator
00231       find(const key_type& __key)
00232       { return iterator(_Base::find(__key), this); }
00233 
00234       const_iterator
00235       find(const key_type& __key) const
00236       { return const_iterator(_Base::find(__key), this); }
00237 
00238       std::pair<iterator, iterator>
00239       equal_range(const key_type& __key)
00240       {
00241     std::pair<_Base_iterator, _Base_iterator> __res =
00242       _Base::equal_range(__key);
00243     return std::make_pair(iterator(__res.first, this),
00244                   iterator(__res.second, this));
00245       }
00246 
00247       std::pair<const_iterator, const_iterator>
00248       equal_range(const key_type& __key) const
00249       {
00250     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00251       _Base::equal_range(__key);
00252     return std::make_pair(const_iterator(__res.first, this),
00253                   const_iterator(__res.second, this));
00254       }
00255 
00256       size_type
00257       erase(const key_type& __key)
00258       {
00259     size_type __ret(0);
00260     _Base_iterator __victim(_Base::find(__key));
00261     if (__victim != _Base::end())
00262       {
00263         this->_M_invalidate_if(_Equal(__victim));
00264         _Base::erase(__victim);
00265         __ret = 1;
00266       }
00267     return __ret;
00268       }
00269 
00270       iterator
00271       erase(const_iterator __it)
00272       {
00273     __glibcxx_check_erase(__it);
00274     this->_M_invalidate_if(_Equal(__it.base()));
00275     return iterator(_Base::erase(__it.base()), this);
00276       }
00277 
00278       iterator
00279       erase(const_iterator __first, const_iterator __last)
00280       {
00281     __glibcxx_check_erase_range(__first, __last);
00282     for (_Base_const_iterator __tmp = __first.base();
00283          __tmp != __last.base(); ++__tmp)
00284       {
00285         _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00286                   _M_message(__gnu_debug::__msg_valid_range)
00287                   ._M_iterator(__first, "first")
00288                   ._M_iterator(__last, "last"));
00289         this->_M_invalidate_if(_Equal(__tmp));
00290       }
00291     return iterator(_Base::erase(__first.base(),
00292                      __last.base()), this);
00293       }
00294 
00295       _Base&
00296       _M_base() { return *this; }
00297 
00298       const _Base&
00299       _M_base() const { return *this; }
00300 
00301     private:
00302       void
00303       _M_invalidate_all()
00304       {
00305     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00306     this->_M_invalidate_if(_Not_equal(_Base::end()));
00307       }
00308     };
00309 
00310   template<typename _Key, typename _Tp, typename _Hash,
00311        typename _Pred, typename _Alloc>
00312     inline void
00313     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00314      unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00315     { __x.swap(__y); }
00316 
00317   template<typename _Key, typename _Tp, typename _Hash,
00318        typename _Pred, typename _Alloc>
00319     inline bool
00320     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00321            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00322     { return __x._M_equal(__y); }
00323 
00324   template<typename _Key, typename _Tp, typename _Hash,
00325        typename _Pred, typename _Alloc>
00326     inline bool
00327     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00328            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00329     { return !(__x == __y); }
00330 
00331 
00332   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
00333   template<typename _Key, typename _Tp,
00334        typename _Hash = std::hash<_Key>,
00335        typename _Pred = std::equal_to<_Key>,
00336        typename _Alloc = std::allocator<_Key> >
00337     class unordered_multimap
00338     : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
00339                         _Pred, _Alloc>,
00340       public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
00341                                 _Pred, _Alloc> >
00342     {
00343       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
00344                          _Pred, _Alloc> _Base;
00345       typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
00346       typedef typename _Base::const_iterator _Base_const_iterator;
00347       typedef typename _Base::iterator _Base_iterator;
00348       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00349 
00350     public:
00351       typedef typename _Base::size_type       size_type;
00352       typedef typename _Base::hasher          hasher;
00353       typedef typename _Base::key_equal       key_equal;
00354       typedef typename _Base::allocator_type  allocator_type;
00355 
00356       typedef typename _Base::key_type        key_type;
00357       typedef typename _Base::value_type      value_type;
00358 
00359       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00360                       unordered_multimap> iterator;
00361       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00362                       unordered_multimap> const_iterator;
00363 
00364       explicit
00365       unordered_multimap(size_type __n = 10,
00366              const hasher& __hf = hasher(),
00367              const key_equal& __eql = key_equal(),
00368              const allocator_type& __a = allocator_type())
00369       : _Base(__n, __hf, __eql, __a) { }
00370 
00371       template<typename _InputIterator>
00372         unordered_multimap(_InputIterator __first, _InputIterator __last, 
00373                size_type __n = 0,
00374                const hasher& __hf = hasher(), 
00375                const key_equal& __eql = key_equal(), 
00376                const allocator_type& __a = allocator_type())
00377     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00378                                      __last)),
00379         __gnu_debug::__base(__last), __n,
00380         __hf, __eql, __a), _Safe_base() { }
00381 
00382       unordered_multimap(const unordered_multimap& __x) 
00383       : _Base(__x), _Safe_base() { }
00384 
00385       unordered_multimap(const _Base& __x) 
00386       : _Base(__x), _Safe_base() { }
00387 
00388       unordered_multimap(unordered_multimap&& __x) 
00389       : _Base(std::move(__x)), _Safe_base() { }
00390 
00391       unordered_multimap(initializer_list<value_type> __l,
00392              size_type __n = 0,
00393              const hasher& __hf = hasher(),
00394              const key_equal& __eql = key_equal(),
00395              const allocator_type& __a = allocator_type())
00396       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
00397 
00398       unordered_multimap&
00399       operator=(const unordered_multimap& __x)
00400       {
00401     *static_cast<_Base*>(this) = __x;
00402     this->_M_invalidate_all();
00403     return *this;
00404       }
00405 
00406       unordered_multimap&
00407       operator=(unordered_multimap&& __x)
00408       {
00409     // NB: DR 1204.
00410     // NB: DR 675.
00411     clear();
00412     swap(__x);
00413     return *this;
00414       }
00415 
00416       unordered_multimap&
00417       operator=(initializer_list<value_type> __l)
00418       {
00419     this->clear();
00420     this->insert(__l);
00421     return *this;
00422       }
00423 
00424       void
00425       swap(unordered_multimap& __x)
00426       {
00427     _Base::swap(__x);
00428     _Safe_base::_M_swap(__x);
00429       }
00430 
00431       void
00432       clear()
00433       {
00434     _Base::clear();
00435     this->_M_invalidate_all();
00436       }
00437 
00438       iterator 
00439       begin()
00440       { return iterator(_Base::begin(), this); }
00441 
00442       const_iterator
00443       begin() const
00444       { return const_iterator(_Base::begin(), this); }
00445 
00446       iterator
00447       end()
00448       { return iterator(_Base::end(), this); }
00449 
00450       const_iterator
00451       end() const
00452       { return const_iterator(_Base::end(), this); }
00453 
00454       const_iterator
00455       cbegin() const
00456       { return const_iterator(_Base::begin(), this); }
00457 
00458       const_iterator
00459       cend() const
00460       { return const_iterator(_Base::end(), this); }
00461 
00462       // local versions
00463       using _Base::begin;
00464       using _Base::end;
00465       using _Base::cbegin;
00466       using _Base::cend;
00467 
00468       iterator
00469       insert(const value_type& __obj)
00470       { return iterator(_Base::insert(__obj), this); }
00471 
00472       iterator
00473       insert(const_iterator __hint, const value_type& __obj)
00474       {
00475     __glibcxx_check_insert(__hint);
00476     return iterator(_Base::insert(__hint.base(), __obj), this);
00477       }
00478 
00479       template<typename _Pair, typename = typename
00480            std::enable_if<std::is_convertible<_Pair,
00481                           value_type>::value>::type>
00482         iterator
00483         insert(_Pair&& __obj)
00484         { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
00485 
00486       template<typename _Pair, typename = typename
00487            std::enable_if<std::is_convertible<_Pair,
00488                           value_type>::value>::type>
00489     iterator
00490     insert(const_iterator __hint, _Pair&& __obj)
00491     {
00492       __glibcxx_check_insert(__hint);
00493       return iterator(_Base::insert(__hint.base(),
00494                     std::forward<_Pair>(__obj)),
00495               this);
00496     }
00497 
00498       void
00499       insert(std::initializer_list<value_type> __l)
00500       { _Base::insert(__l); }
00501 
00502       template<typename _InputIterator>
00503         void
00504         insert(_InputIterator __first, _InputIterator __last)
00505         {
00506       __glibcxx_check_valid_range(__first, __last);
00507       _Base::insert(__gnu_debug::__base(__first),
00508             __gnu_debug::__base(__last));
00509     }
00510 
00511       iterator
00512       find(const key_type& __key)
00513       { return iterator(_Base::find(__key), this); }
00514 
00515       const_iterator
00516       find(const key_type& __key) const
00517       { return const_iterator(_Base::find(__key), this); }
00518 
00519       std::pair<iterator, iterator>
00520       equal_range(const key_type& __key)
00521       {
00522     std::pair<_Base_iterator, _Base_iterator> __res =
00523       _Base::equal_range(__key);
00524     return std::make_pair(iterator(__res.first, this),
00525                   iterator(__res.second, this));
00526       }
00527 
00528       std::pair<const_iterator, const_iterator>
00529       equal_range(const key_type& __key) const
00530       {
00531     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00532       _Base::equal_range(__key);
00533     return std::make_pair(const_iterator(__res.first, this),
00534                   const_iterator(__res.second, this));
00535       }
00536 
00537       size_type
00538       erase(const key_type& __key)
00539       {
00540     size_type __ret(0);
00541     std::pair<_Base_iterator, _Base_iterator> __pair =
00542       _Base::equal_range(__key);
00543     for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
00544       {
00545         this->_M_invalidate_if(_Equal(__victim));
00546         _Base::erase(__victim++);
00547         ++__ret;
00548       }
00549     return __ret;
00550       }
00551 
00552       iterator
00553       erase(const_iterator __it)
00554       {
00555     __glibcxx_check_erase(__it);
00556     this->_M_invalidate_if(_Equal(__it.base()));
00557     return iterator(_Base::erase(__it.base()), this);
00558       }
00559 
00560       iterator
00561       erase(const_iterator __first, const_iterator __last)
00562       {
00563     __glibcxx_check_erase_range(__first, __last);
00564     for (_Base_const_iterator __tmp = __first.base();
00565          __tmp != __last.base(); ++__tmp)
00566       {
00567         _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00568                   _M_message(__gnu_debug::__msg_valid_range)
00569                   ._M_iterator(__first, "first")
00570                   ._M_iterator(__last, "last"));
00571         this->_M_invalidate_if(_Equal(__tmp));
00572       }
00573     return iterator(_Base::erase(__first.base(),
00574                      __last.base()), this);
00575       }
00576 
00577       _Base&
00578       _M_base() { return *this; }
00579 
00580       const _Base&
00581       _M_base() const { return *this; }
00582 
00583     private:
00584       void
00585       _M_invalidate_all()
00586       {
00587     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00588     this->_M_invalidate_if(_Not_equal(_Base::end()));
00589       }
00590     };
00591 
00592   template<typename _Key, typename _Tp, typename _Hash,
00593        typename _Pred, typename _Alloc>
00594     inline void
00595     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00596      unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00597     { __x.swap(__y); }
00598 
00599   template<typename _Key, typename _Tp, typename _Hash,
00600        typename _Pred, typename _Alloc>
00601     inline bool
00602     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00603            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00604     { return __x._M_equal(__y); }
00605 
00606   template<typename _Key, typename _Tp, typename _Hash,
00607        typename _Pred, typename _Alloc>
00608     inline bool
00609     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00610            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00611     { return !(__x == __y); }
00612 
00613 } // namespace __debug
00614 } // namespace std
00615 
00616 #endif // __GXX_EXPERIMENTAL_CXX0X__
00617 
00618 #endif