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(iterator __it)
00280       { return erase(const_iterator(__it)); }
00281 
00282       iterator
00283       erase(const_iterator __first, const_iterator __last)
00284       {
00285     __glibcxx_check_erase_range(__first, __last);
00286     for (_Base_const_iterator __tmp = __first.base();
00287          __tmp != __last.base(); ++__tmp)
00288       {
00289         _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00290                   _M_message(__gnu_debug::__msg_valid_range)
00291                   ._M_iterator(__first, "first")
00292                   ._M_iterator(__last, "last"));
00293         this->_M_invalidate_if(_Equal(__tmp));
00294       }
00295     return iterator(_Base::erase(__first.base(),
00296                      __last.base()), this);
00297       }
00298 
00299       _Base&
00300       _M_base() { return *this; }
00301 
00302       const _Base&
00303       _M_base() const { return *this; }
00304 
00305     private:
00306       void
00307       _M_invalidate_all()
00308       {
00309     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00310     this->_M_invalidate_if(_Not_equal(_Base::end()));
00311       }
00312     };
00313 
00314   template<typename _Key, typename _Tp, typename _Hash,
00315        typename _Pred, typename _Alloc>
00316     inline void
00317     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00318      unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00319     { __x.swap(__y); }
00320 
00321   template<typename _Key, typename _Tp, typename _Hash,
00322        typename _Pred, typename _Alloc>
00323     inline bool
00324     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00325            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00326     { return __x._M_equal(__y); }
00327 
00328   template<typename _Key, typename _Tp, typename _Hash,
00329        typename _Pred, typename _Alloc>
00330     inline bool
00331     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00332            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00333     { return !(__x == __y); }
00334 
00335 
00336   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
00337   template<typename _Key, typename _Tp,
00338        typename _Hash = std::hash<_Key>,
00339        typename _Pred = std::equal_to<_Key>,
00340        typename _Alloc = std::allocator<_Key> >
00341     class unordered_multimap
00342     : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
00343                         _Pred, _Alloc>,
00344       public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
00345                                 _Pred, _Alloc> >
00346     {
00347       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
00348                          _Pred, _Alloc> _Base;
00349       typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
00350       typedef typename _Base::const_iterator _Base_const_iterator;
00351       typedef typename _Base::iterator _Base_iterator;
00352       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00353 
00354     public:
00355       typedef typename _Base::size_type       size_type;
00356       typedef typename _Base::hasher          hasher;
00357       typedef typename _Base::key_equal       key_equal;
00358       typedef typename _Base::allocator_type  allocator_type;
00359 
00360       typedef typename _Base::key_type        key_type;
00361       typedef typename _Base::value_type      value_type;
00362 
00363       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00364                       unordered_multimap> iterator;
00365       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00366                       unordered_multimap> const_iterator;
00367 
00368       explicit
00369       unordered_multimap(size_type __n = 10,
00370              const hasher& __hf = hasher(),
00371              const key_equal& __eql = key_equal(),
00372              const allocator_type& __a = allocator_type())
00373       : _Base(__n, __hf, __eql, __a) { }
00374 
00375       template<typename _InputIterator>
00376         unordered_multimap(_InputIterator __first, _InputIterator __last, 
00377                size_type __n = 0,
00378                const hasher& __hf = hasher(), 
00379                const key_equal& __eql = key_equal(), 
00380                const allocator_type& __a = allocator_type())
00381     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00382                                      __last)),
00383         __gnu_debug::__base(__last), __n,
00384         __hf, __eql, __a), _Safe_base() { }
00385 
00386       unordered_multimap(const unordered_multimap& __x) 
00387       : _Base(__x), _Safe_base() { }
00388 
00389       unordered_multimap(const _Base& __x) 
00390       : _Base(__x), _Safe_base() { }
00391 
00392       unordered_multimap(unordered_multimap&& __x) 
00393       : _Base(std::move(__x)), _Safe_base() { }
00394 
00395       unordered_multimap(initializer_list<value_type> __l,
00396              size_type __n = 0,
00397              const hasher& __hf = hasher(),
00398              const key_equal& __eql = key_equal(),
00399              const allocator_type& __a = allocator_type())
00400       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
00401 
00402       unordered_multimap&
00403       operator=(const unordered_multimap& __x)
00404       {
00405     *static_cast<_Base*>(this) = __x;
00406     this->_M_invalidate_all();
00407     return *this;
00408       }
00409 
00410       unordered_multimap&
00411       operator=(unordered_multimap&& __x)
00412       {
00413     // NB: DR 1204.
00414     // NB: DR 675.
00415     clear();
00416     swap(__x);
00417     return *this;
00418       }
00419 
00420       unordered_multimap&
00421       operator=(initializer_list<value_type> __l)
00422       {
00423     this->clear();
00424     this->insert(__l);
00425     return *this;
00426       }
00427 
00428       void
00429       swap(unordered_multimap& __x)
00430       {
00431     _Base::swap(__x);
00432     _Safe_base::_M_swap(__x);
00433       }
00434 
00435       void
00436       clear()
00437       {
00438     _Base::clear();
00439     this->_M_invalidate_all();
00440       }
00441 
00442       iterator 
00443       begin()
00444       { return iterator(_Base::begin(), this); }
00445 
00446       const_iterator
00447       begin() const
00448       { return const_iterator(_Base::begin(), this); }
00449 
00450       iterator
00451       end()
00452       { return iterator(_Base::end(), this); }
00453 
00454       const_iterator
00455       end() const
00456       { return const_iterator(_Base::end(), this); }
00457 
00458       const_iterator
00459       cbegin() const
00460       { return const_iterator(_Base::begin(), this); }
00461 
00462       const_iterator
00463       cend() const
00464       { return const_iterator(_Base::end(), this); }
00465 
00466       // local versions
00467       using _Base::begin;
00468       using _Base::end;
00469       using _Base::cbegin;
00470       using _Base::cend;
00471 
00472       iterator
00473       insert(const value_type& __obj)
00474       { return iterator(_Base::insert(__obj), this); }
00475 
00476       iterator
00477       insert(const_iterator __hint, const value_type& __obj)
00478       {
00479     __glibcxx_check_insert(__hint);
00480     return iterator(_Base::insert(__hint.base(), __obj), this);
00481       }
00482 
00483       template<typename _Pair, typename = typename
00484            std::enable_if<std::is_convertible<_Pair,
00485                           value_type>::value>::type>
00486         iterator
00487         insert(_Pair&& __obj)
00488         { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
00489 
00490       template<typename _Pair, typename = typename
00491            std::enable_if<std::is_convertible<_Pair,
00492                           value_type>::value>::type>
00493     iterator
00494     insert(const_iterator __hint, _Pair&& __obj)
00495     {
00496       __glibcxx_check_insert(__hint);
00497       return iterator(_Base::insert(__hint.base(),
00498                     std::forward<_Pair>(__obj)),
00499               this);
00500     }
00501 
00502       void
00503       insert(std::initializer_list<value_type> __l)
00504       { _Base::insert(__l); }
00505 
00506       template<typename _InputIterator>
00507         void
00508         insert(_InputIterator __first, _InputIterator __last)
00509         {
00510       __glibcxx_check_valid_range(__first, __last);
00511       _Base::insert(__gnu_debug::__base(__first),
00512             __gnu_debug::__base(__last));
00513     }
00514 
00515       iterator
00516       find(const key_type& __key)
00517       { return iterator(_Base::find(__key), this); }
00518 
00519       const_iterator
00520       find(const key_type& __key) const
00521       { return const_iterator(_Base::find(__key), this); }
00522 
00523       std::pair<iterator, iterator>
00524       equal_range(const key_type& __key)
00525       {
00526     std::pair<_Base_iterator, _Base_iterator> __res =
00527       _Base::equal_range(__key);
00528     return std::make_pair(iterator(__res.first, this),
00529                   iterator(__res.second, this));
00530       }
00531 
00532       std::pair<const_iterator, const_iterator>
00533       equal_range(const key_type& __key) const
00534       {
00535     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00536       _Base::equal_range(__key);
00537     return std::make_pair(const_iterator(__res.first, this),
00538                   const_iterator(__res.second, this));
00539       }
00540 
00541       size_type
00542       erase(const key_type& __key)
00543       {
00544     size_type __ret(0);
00545     std::pair<_Base_iterator, _Base_iterator> __pair =
00546       _Base::equal_range(__key);
00547     for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
00548       {
00549         this->_M_invalidate_if(_Equal(__victim));
00550         _Base::erase(__victim++);
00551         ++__ret;
00552       }
00553     return __ret;
00554       }
00555 
00556       iterator
00557       erase(const_iterator __it)
00558       {
00559     __glibcxx_check_erase(__it);
00560     this->_M_invalidate_if(_Equal(__it.base()));
00561     return iterator(_Base::erase(__it.base()), this);
00562       }
00563 
00564       iterator
00565       erase(iterator __it)
00566       { return erase(const_iterator(__it)); }
00567 
00568       iterator
00569       erase(const_iterator __first, const_iterator __last)
00570       {
00571     __glibcxx_check_erase_range(__first, __last);
00572     for (_Base_const_iterator __tmp = __first.base();
00573          __tmp != __last.base(); ++__tmp)
00574       {
00575         _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00576                   _M_message(__gnu_debug::__msg_valid_range)
00577                   ._M_iterator(__first, "first")
00578                   ._M_iterator(__last, "last"));
00579         this->_M_invalidate_if(_Equal(__tmp));
00580       }
00581     return iterator(_Base::erase(__first.base(),
00582                      __last.base()), this);
00583       }
00584 
00585       _Base&
00586       _M_base() { return *this; }
00587 
00588       const _Base&
00589       _M_base() const { return *this; }
00590 
00591     private:
00592       void
00593       _M_invalidate_all()
00594       {
00595     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00596     this->_M_invalidate_if(_Not_equal(_Base::end()));
00597       }
00598     };
00599 
00600   template<typename _Key, typename _Tp, typename _Hash,
00601        typename _Pred, typename _Alloc>
00602     inline void
00603     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00604      unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00605     { __x.swap(__y); }
00606 
00607   template<typename _Key, typename _Tp, typename _Hash,
00608        typename _Pred, typename _Alloc>
00609     inline bool
00610     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00611            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00612     { return __x._M_equal(__y); }
00613 
00614   template<typename _Key, typename _Tp, typename _Hash,
00615        typename _Pred, typename _Alloc>
00616     inline bool
00617     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00618            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00619     { return !(__x == __y); }
00620 
00621 } // namespace __debug
00622 } // namespace std
00623 
00624 #endif // __GXX_EXPERIMENTAL_CXX0X__
00625 
00626 #endif