libstdc++
debug/unordered_set
Go to the documentation of this file.
00001 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
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_set
00027  *  This file is a GNU debug extension to the Standard C++ Library.
00028  */
00029 
00030 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
00031 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
00032 
00033 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00034 # include <bits/c++0x_warning.h>
00035 #else
00036 # include <unordered_set>
00037 
00038 #include <debug/safe_unordered_container.h>
00039 #include <debug/safe_iterator.h>
00040 #include <debug/safe_local_iterator.h>
00041 
00042 namespace std _GLIBCXX_VISIBILITY(default)
00043 {
00044 namespace __debug
00045 {
00046   /// Class std::unordered_set with safety/checking/debug instrumentation.
00047   template<typename _Value,
00048        typename _Hash = std::hash<_Value>,
00049        typename _Pred = std::equal_to<_Value>,
00050        typename _Alloc = std::allocator<_Value> >
00051     class unordered_set
00052     : public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>,
00053       public __gnu_debug::_Safe_unordered_container<unordered_set<_Value, _Hash,
00054                                _Pred, _Alloc> >
00055     {
00056       typedef _GLIBCXX_STD_C::unordered_set<_Value, _Hash,
00057                         _Pred, _Alloc> _Base;
00058       typedef __gnu_debug::_Safe_unordered_container<unordered_set> _Safe_base;
00059       typedef typename _Base::const_iterator _Base_const_iterator;
00060       typedef typename _Base::iterator _Base_iterator;
00061       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
00062       typedef typename _Base::local_iterator _Base_local_iterator;
00063 
00064     public:
00065       typedef typename _Base::size_type       size_type;
00066       typedef typename _Base::hasher          hasher;
00067       typedef typename _Base::key_equal       key_equal;
00068       typedef typename _Base::allocator_type  allocator_type;
00069 
00070       typedef typename _Base::key_type        key_type;
00071       typedef typename _Base::value_type      value_type;
00072 
00073       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00074                       unordered_set> iterator;
00075       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00076                       unordered_set> const_iterator;
00077       typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
00078                       unordered_set> local_iterator;
00079       typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
00080                       unordered_set> const_local_iterator;
00081 
00082       explicit
00083       unordered_set(size_type __n = 10,
00084             const hasher& __hf = hasher(),
00085             const key_equal& __eql = key_equal(),
00086             const allocator_type& __a = allocator_type())
00087       : _Base(__n, __hf, __eql, __a) { }
00088 
00089       template<typename _InputIterator>
00090         unordered_set(_InputIterator __first, _InputIterator __last, 
00091               size_type __n = 0,
00092               const hasher& __hf = hasher(), 
00093               const key_equal& __eql = key_equal(), 
00094               const allocator_type& __a = allocator_type())
00095     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00096                                      __last)),
00097         __gnu_debug::__base(__last), __n,
00098         __hf, __eql, __a) { }
00099 
00100       unordered_set(const unordered_set& __x) 
00101       : _Base(__x) { }
00102 
00103       unordered_set(const _Base& __x) 
00104       : _Base(__x) { }
00105 
00106       unordered_set(unordered_set&& __x)
00107       : _Base(std::move(__x)) { }
00108 
00109       unordered_set(initializer_list<value_type> __l,
00110             size_type __n = 0,
00111             const hasher& __hf = hasher(),
00112             const key_equal& __eql = key_equal(),
00113             const allocator_type& __a = allocator_type())
00114       : _Base(__l, __n, __hf, __eql, __a) { }
00115 
00116       ~unordered_set() noexcept { }
00117 
00118       unordered_set&
00119       operator=(const unordered_set& __x)
00120       {
00121     *static_cast<_Base*>(this) = __x;
00122     this->_M_invalidate_all();
00123     return *this;
00124       }
00125 
00126       unordered_set&
00127       operator=(unordered_set&& __x)
00128       {
00129     // NB: DR 1204.
00130     // NB: DR 675.
00131     clear();
00132     swap(__x);
00133     return *this;
00134       }
00135 
00136       unordered_set&
00137       operator=(initializer_list<value_type> __l)
00138       {
00139     this->clear();
00140     this->insert(__l);
00141     return *this;
00142       }
00143 
00144       void
00145       swap(unordered_set& __x)
00146       {
00147     _Base::swap(__x);
00148     _Safe_base::_M_swap(__x);
00149       }
00150 
00151       void
00152       clear() noexcept
00153       {
00154     _Base::clear();
00155     this->_M_invalidate_all();
00156       }
00157 
00158       iterator 
00159       begin() noexcept
00160       { return iterator(_Base::begin(), this); }
00161 
00162       const_iterator
00163       begin() const noexcept
00164       { return const_iterator(_Base::begin(), this); }
00165 
00166       iterator
00167       end() noexcept
00168       { return iterator(_Base::end(), this); }
00169 
00170       const_iterator
00171       end() const noexcept
00172       { return const_iterator(_Base::end(), this); }
00173 
00174       const_iterator
00175       cbegin() const noexcept
00176       { return const_iterator(_Base::begin(), this); }
00177 
00178       const_iterator
00179       cend() const noexcept
00180       { return const_iterator(_Base::end(), this); }
00181 
00182       // local versions
00183       local_iterator
00184       begin(size_type __b)
00185       { return local_iterator(_Base::begin(__b), __b, this); }
00186 
00187       local_iterator
00188       end(size_type __b)
00189       { return local_iterator(_Base::end(__b), __b, this); }
00190 
00191       const_local_iterator
00192       begin(size_type __b) const
00193       { return const_local_iterator(_Base::begin(__b), __b, this); }
00194 
00195       const_local_iterator
00196       end(size_type __b) const
00197       { return const_local_iterator(_Base::end(__b), __b, this); }
00198 
00199       const_local_iterator
00200       cbegin(size_type __b) const
00201       { return const_local_iterator(_Base::cbegin(__b), __b, this); }
00202 
00203       const_local_iterator
00204       cend(size_type __b) const
00205       { return const_local_iterator(_Base::cend(__b), __b, this); }
00206 
00207       template<typename... _Args>
00208     std::pair<iterator, bool>
00209     emplace(_Args&&... __args)
00210     {
00211       size_type __bucket_count = this->bucket_count();
00212       std::pair<_Base_iterator, bool> __res
00213         = _Base::emplace(std::forward<_Args>(__args)...);
00214       _M_check_rehashed(__bucket_count);
00215       return std::make_pair(iterator(__res.first, this), __res.second);
00216     }
00217 
00218       template<typename... _Args>
00219     iterator
00220     emplace_hint(const_iterator __hint, _Args&&... __args)
00221     {
00222       __glibcxx_check_insert(__hint);
00223       size_type __bucket_count = this->bucket_count();
00224       _Base_iterator __it = _Base::emplace_hint(__hint.base(),
00225                     std::forward<_Args>(__args)...);
00226       _M_check_rehashed(__bucket_count);
00227       return iterator(__it, this);
00228     }
00229 
00230       std::pair<iterator, bool>
00231       insert(const value_type& __obj)
00232       {
00233     size_type __bucket_count = this->bucket_count();
00234     typedef std::pair<_Base_iterator, bool> __pair_type;
00235       __pair_type __res = _Base::insert(__obj);
00236     _M_check_rehashed(__bucket_count);
00237     return std::make_pair(iterator(__res.first, this), __res.second);
00238       }
00239 
00240       iterator
00241       insert(const_iterator __hint, const value_type& __obj)
00242       {
00243     __glibcxx_check_insert(__hint);
00244     size_type __bucket_count = this->bucket_count();
00245     _Base_iterator __it = _Base::insert(__hint.base(), __obj);
00246     _M_check_rehashed(__bucket_count);
00247     return iterator(__it, this);
00248       }
00249 
00250       std::pair<iterator, bool>
00251       insert(value_type&& __obj)
00252       {
00253     size_type __bucket_count = this->bucket_count();
00254     typedef std::pair<typename _Base::iterator, bool> __pair_type;
00255       __pair_type __res = _Base::insert(std::move(__obj));
00256     _M_check_rehashed(__bucket_count);
00257     return std::make_pair(iterator(__res.first, this), __res.second);
00258       }
00259 
00260       iterator
00261       insert(const_iterator __hint, value_type&& __obj)
00262       {
00263     __glibcxx_check_insert(__hint);
00264     size_type __bucket_count = this->bucket_count();
00265     _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
00266     _M_check_rehashed(__bucket_count);
00267     return iterator(__it, this);
00268       }
00269 
00270       void
00271       insert(std::initializer_list<value_type> __l)
00272       {
00273     size_type __bucket_count = this->bucket_count();
00274     _Base::insert(__l);
00275     _M_check_rehashed(__bucket_count);
00276       }
00277 
00278       template<typename _InputIterator>
00279     void
00280     insert(_InputIterator __first, _InputIterator __last)
00281     {
00282       __glibcxx_check_valid_range(__first, __last);
00283       size_type __bucket_count = this->bucket_count();
00284       _Base::insert(__gnu_debug::__base(__first),
00285             __gnu_debug::__base(__last));
00286       _M_check_rehashed(__bucket_count);
00287     }
00288 
00289       iterator
00290       find(const key_type& __key)
00291       { return iterator(_Base::find(__key), this); }
00292 
00293       const_iterator
00294       find(const key_type& __key) const
00295       { return const_iterator(_Base::find(__key), this); }
00296 
00297       std::pair<iterator, iterator>
00298       equal_range(const key_type& __key)
00299       {
00300     typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00301     __pair_type __res = _Base::equal_range(__key);
00302     return std::make_pair(iterator(__res.first, this),
00303                   iterator(__res.second, this));
00304       }
00305 
00306       std::pair<const_iterator, const_iterator>
00307       equal_range(const key_type& __key) const
00308       {
00309     std::pair<_Base_const_iterator, _Base_const_iterator>
00310       __res = _Base::equal_range(__key);
00311     return std::make_pair(const_iterator(__res.first, this),
00312                   const_iterator(__res.second, this));
00313       }
00314 
00315       size_type
00316       erase(const key_type& __key)
00317       {
00318     size_type __ret(0);
00319     _Base_iterator __victim(_Base::find(__key));
00320     if (__victim != _Base::end())
00321       {
00322         this->_M_invalidate_if(
00323                 [__victim](_Base_const_iterator __it)
00324                 { return __it == __victim; });
00325         _Base_local_iterator __local_victim = _S_to_local(__victim);
00326         this->_M_invalidate_local_if(
00327                 [__local_victim](_Base_const_local_iterator __it)
00328                 { return __it == __local_victim; });
00329         size_type __bucket_count = this->bucket_count();
00330         _Base::erase(__victim);
00331         _M_check_rehashed(__bucket_count);
00332         __ret = 1;
00333       }
00334     return __ret;
00335       }
00336 
00337       iterator
00338       erase(const_iterator __it)
00339       {
00340     __glibcxx_check_erase(__it);
00341     _Base_const_iterator __victim = __it.base();
00342     this->_M_invalidate_if(
00343             [__victim](_Base_const_iterator __it)
00344             { return __it == __victim; });
00345     _Base_const_local_iterator __local_victim = _S_to_local(__victim);
00346     this->_M_invalidate_local_if(
00347             [__local_victim](_Base_const_local_iterator __it)
00348             { return __it == __local_victim; });
00349     size_type __bucket_count = this->bucket_count();
00350     _Base_iterator __next = _Base::erase(__it.base());
00351     _M_check_rehashed(__bucket_count);
00352     return iterator(__next, this);
00353       }
00354 
00355       iterator
00356       erase(iterator __it)
00357       { return erase(const_iterator(__it)); }
00358 
00359       iterator
00360       erase(const_iterator __first, const_iterator __last)
00361       {
00362     __glibcxx_check_erase_range(__first, __last);
00363     for (_Base_const_iterator __tmp = __first.base();
00364          __tmp != __last.base(); ++__tmp)
00365       {
00366         _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00367                   _M_message(__gnu_debug::__msg_valid_range)
00368                   ._M_iterator(__first, "first")
00369                   ._M_iterator(__last, "last"));
00370         this->_M_invalidate_if(
00371                 [__tmp](_Base_const_iterator __it)
00372                 { return __it == __tmp; });
00373         _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
00374         this->_M_invalidate_local_if(
00375                 [__local_tmp](_Base_const_local_iterator __it)
00376                 { return __it == __local_tmp; });
00377       }
00378     size_type __bucket_count = this->bucket_count();
00379     _Base_iterator __next = _Base::erase(__first.base(),
00380                          __last.base());
00381     _M_check_rehashed(__bucket_count);
00382     return iterator(__next, this);
00383       }
00384 
00385       _Base&
00386       _M_base() noexcept       { return *this; }
00387 
00388       const _Base&
00389       _M_base() const noexcept { return *this; }
00390 
00391     private:
00392       void
00393       _M_invalidate_locals()
00394       {
00395     _Base_local_iterator __local_end = _Base::end(0);
00396     this->_M_invalidate_local_if(
00397             [__local_end](_Base_const_local_iterator __it)
00398             { return __it != __local_end; });
00399       }
00400 
00401       void
00402       _M_invalidate_all()
00403       {
00404     _Base_iterator __end = _Base::end();
00405     this->_M_invalidate_if(
00406             [__end](_Base_const_iterator __it)
00407             { return __it != __end; });
00408     _M_invalidate_locals();
00409       }
00410 
00411       void
00412       _M_check_rehashed(size_type __prev_count)
00413       {
00414     if (__prev_count != this->bucket_count())
00415       _M_invalidate_locals();
00416       }
00417 
00418       static _Base_local_iterator
00419       _S_to_local(_Base_iterator __it)
00420       {
00421         // The returned local iterator will not be incremented so we don't
00422     // need to compute __it's node bucket
00423     return _Base_local_iterator(__it._M_cur, 0, 0);
00424       }
00425 
00426       static _Base_const_local_iterator
00427       _S_to_local(_Base_const_iterator __it)
00428       {
00429         // The returned local iterator will not be incremented so we don't
00430     // need to compute __it's node bucket
00431     return _Base_const_local_iterator(__it._M_cur, 0, 0);
00432       }
00433     };
00434 
00435   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00436     inline void
00437     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00438      unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00439     { __x.swap(__y); }
00440 
00441   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00442     inline bool
00443     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00444            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00445     { return __x._M_equal(__y); }
00446 
00447   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00448     inline bool
00449     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00450            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00451     { return !(__x == __y); }
00452 
00453 
00454   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
00455   template<typename _Value,
00456        typename _Hash = std::hash<_Value>,
00457        typename _Pred = std::equal_to<_Value>,
00458        typename _Alloc = std::allocator<_Value> >
00459     class unordered_multiset
00460     : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
00461       public __gnu_debug::_Safe_unordered_container<
00462         unordered_multiset<_Value, _Hash, _Pred, _Alloc> >
00463     {
00464       typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash,
00465                          _Pred, _Alloc> _Base;
00466       typedef __gnu_debug::_Safe_unordered_container<unordered_multiset>
00467         _Safe_base;
00468       typedef typename _Base::const_iterator _Base_const_iterator;
00469       typedef typename _Base::iterator _Base_iterator;
00470       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
00471       typedef typename _Base::local_iterator _Base_local_iterator;
00472 
00473     public:
00474       typedef typename _Base::size_type       size_type;
00475       typedef typename _Base::hasher          hasher;
00476       typedef typename _Base::key_equal       key_equal;
00477       typedef typename _Base::allocator_type  allocator_type;
00478 
00479       typedef typename _Base::key_type        key_type;
00480       typedef typename _Base::value_type      value_type;
00481 
00482       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00483                       unordered_multiset> iterator;
00484       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00485                       unordered_multiset> const_iterator;
00486       typedef __gnu_debug::_Safe_local_iterator<
00487     _Base_local_iterator, unordered_multiset> local_iterator;
00488       typedef __gnu_debug::_Safe_local_iterator<
00489     _Base_const_local_iterator, unordered_multiset> const_local_iterator;
00490 
00491       explicit
00492       unordered_multiset(size_type __n = 10,
00493              const hasher& __hf = hasher(),
00494              const key_equal& __eql = key_equal(),
00495              const allocator_type& __a = allocator_type())
00496       : _Base(__n, __hf, __eql, __a) { }
00497 
00498       template<typename _InputIterator>
00499         unordered_multiset(_InputIterator __first, _InputIterator __last, 
00500                size_type __n = 0,
00501                const hasher& __hf = hasher(), 
00502                const key_equal& __eql = key_equal(), 
00503                const allocator_type& __a = allocator_type())
00504     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00505                                      __last)),
00506         __gnu_debug::__base(__last), __n,
00507         __hf, __eql, __a) { }
00508 
00509       unordered_multiset(const unordered_multiset& __x) 
00510       : _Base(__x) { }
00511 
00512       unordered_multiset(const _Base& __x) 
00513       : _Base(__x) { }
00514 
00515       unordered_multiset(unordered_multiset&& __x)
00516       : _Base(std::move(__x)) { }
00517 
00518       unordered_multiset(initializer_list<value_type> __l,
00519              size_type __n = 0,
00520              const hasher& __hf = hasher(),
00521              const key_equal& __eql = key_equal(),
00522              const allocator_type& __a = allocator_type())
00523       : _Base(__l, __n, __hf, __eql, __a) { }
00524 
00525       ~unordered_multiset() noexcept { }
00526 
00527       unordered_multiset&
00528       operator=(const unordered_multiset& __x)
00529       {
00530     *static_cast<_Base*>(this) = __x;
00531     this->_M_invalidate_all();
00532     return *this;
00533       }
00534 
00535       unordered_multiset&
00536       operator=(unordered_multiset&& __x)
00537       {
00538     // NB: DR 1204.
00539         // NB: DR 675.
00540     clear();
00541     swap(__x);
00542     return *this;
00543       }
00544 
00545       unordered_multiset&
00546       operator=(initializer_list<value_type> __l)
00547       {
00548     this->clear();
00549     this->insert(__l);
00550     return *this;
00551       }
00552 
00553       void
00554       swap(unordered_multiset& __x)
00555       {
00556     _Base::swap(__x);
00557     _Safe_base::_M_swap(__x);
00558       }
00559 
00560       void
00561       clear() noexcept
00562       {
00563     _Base::clear();
00564     this->_M_invalidate_all();
00565       }
00566 
00567       iterator
00568       begin() noexcept
00569       { return iterator(_Base::begin(), this); }
00570 
00571       const_iterator
00572       begin() const noexcept
00573       { return const_iterator(_Base::begin(), this); }
00574 
00575       iterator
00576       end() noexcept
00577       { return iterator(_Base::end(), this); }
00578 
00579       const_iterator
00580       end() const noexcept
00581       { return const_iterator(_Base::end(), this); }
00582 
00583       const_iterator
00584       cbegin() const noexcept
00585       { return const_iterator(_Base::begin(), this); }
00586 
00587       const_iterator
00588       cend() const noexcept
00589       { return const_iterator(_Base::end(), this); }
00590 
00591       // local versions
00592       local_iterator
00593       begin(size_type __b)
00594       { return local_iterator(_Base::begin(__b), __b, this); }
00595 
00596       local_iterator
00597       end(size_type __b)
00598       { return local_iterator(_Base::end(__b), __b, this); }
00599 
00600       const_local_iterator
00601       begin(size_type __b) const
00602       { return const_local_iterator(_Base::begin(__b), __b, this); }
00603 
00604       const_local_iterator
00605       end(size_type __b) const
00606       { return const_local_iterator(_Base::end(__b), __b, this); }
00607 
00608       const_local_iterator
00609       cbegin(size_type __b) const
00610       { return const_local_iterator(_Base::cbegin(__b), __b, this); }
00611 
00612       const_local_iterator
00613       cend(size_type __b) const
00614       { return const_local_iterator(_Base::cend(__b), __b, this); }
00615 
00616       template<typename... _Args>
00617     iterator
00618     emplace(_Args&&... __args)
00619     {
00620       size_type __bucket_count = this->bucket_count();
00621       _Base_iterator __it
00622         = _Base::emplace(std::forward<_Args>(__args)...);
00623       _M_check_rehashed(__bucket_count);
00624       return iterator(__it, this);
00625     }
00626 
00627       template<typename... _Args>
00628     iterator
00629     emplace_hint(const_iterator __hint, _Args&&... __args)
00630     {
00631       __glibcxx_check_insert(__hint);
00632       size_type __bucket_count = this->bucket_count();
00633       _Base_iterator __it = _Base::emplace_hint(__hint.base(),
00634                     std::forward<_Args>(__args)...);
00635       _M_check_rehashed(__bucket_count);
00636       return iterator(__it, this);
00637     }
00638 
00639       iterator
00640       insert(const value_type& __obj)
00641       {
00642     size_type __bucket_count = this->bucket_count();
00643     _Base_iterator __it = _Base::insert(__obj);
00644     _M_check_rehashed(__bucket_count);
00645     return iterator(__it, this);
00646       }
00647 
00648       iterator
00649       insert(const_iterator __hint, const value_type& __obj)
00650       {
00651     __glibcxx_check_insert(__hint);
00652     size_type __bucket_count = this->bucket_count();
00653     _Base_iterator __it = _Base::insert(__hint.base(), __obj); 
00654     _M_check_rehashed(__bucket_count);
00655     return iterator(__it, this);
00656       }
00657 
00658       iterator
00659       insert(value_type&& __obj)
00660       {
00661     size_type __bucket_count = this->bucket_count();
00662     _Base_iterator __it = _Base::insert(std::move(__obj)); 
00663     _M_check_rehashed(__bucket_count);
00664     return iterator(__it, this);
00665       }
00666 
00667       iterator
00668       insert(const_iterator __hint, value_type&& __obj)
00669       {
00670     __glibcxx_check_insert(__hint);
00671     size_type __bucket_count = this->bucket_count();
00672     _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); 
00673     _M_check_rehashed(__bucket_count);
00674     return iterator(__it, this);
00675       }
00676 
00677       void
00678       insert(std::initializer_list<value_type> __l)
00679       {
00680     size_type __bucket_count = this->bucket_count();
00681     _Base::insert(__l);
00682     _M_check_rehashed(__bucket_count);
00683       }
00684 
00685       template<typename _InputIterator>
00686     void
00687     insert(_InputIterator __first, _InputIterator __last)
00688     {
00689       __glibcxx_check_valid_range(__first, __last);
00690       size_type __bucket_count = this->bucket_count();
00691       _Base::insert(__gnu_debug::__base(__first),
00692             __gnu_debug::__base(__last));
00693       _M_check_rehashed(__bucket_count);
00694     }
00695 
00696       iterator
00697       find(const key_type& __key)
00698       { return iterator(_Base::find(__key), this); }
00699 
00700       const_iterator
00701       find(const key_type& __key) const
00702       { return const_iterator(_Base::find(__key), this); }
00703 
00704       std::pair<iterator, iterator>
00705       equal_range(const key_type& __key)
00706       {
00707     typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00708     __pair_type __res = _Base::equal_range(__key);
00709     return std::make_pair(iterator(__res.first, this),
00710                   iterator(__res.second, this));
00711       }
00712 
00713       std::pair<const_iterator, const_iterator>
00714       equal_range(const key_type& __key) const
00715       {
00716     std::pair<_Base_const_iterator, _Base_const_iterator>
00717       __res = _Base::equal_range(__key);
00718     return std::make_pair(const_iterator(__res.first, this),
00719                   const_iterator(__res.second, this));
00720       }
00721 
00722       size_type
00723       erase(const key_type& __key)
00724       {
00725     size_type __ret(0);
00726     std::pair<_Base_iterator, _Base_iterator> __pair =
00727       _Base::equal_range(__key);
00728     for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
00729       {
00730         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00731                 { return __it == __victim; });
00732         _Base_local_iterator __local_victim = _S_to_local(__victim);
00733         this->_M_invalidate_local_if(
00734                 [__local_victim](_Base_const_local_iterator __it)
00735                 { return __it == __local_victim; });
00736         _Base::erase(__victim++);
00737         ++__ret;
00738       }
00739     return __ret;
00740       }
00741 
00742       iterator
00743       erase(const_iterator __it)
00744       {
00745     __glibcxx_check_erase(__it);
00746     _Base_const_iterator __victim = __it.base();
00747     this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00748             { return __it == __victim; });
00749     _Base_const_local_iterator __local_victim = _S_to_local(__victim);
00750     this->_M_invalidate_local_if(
00751             [__local_victim](_Base_const_local_iterator __it)
00752             { return __it == __local_victim; });
00753     return iterator(_Base::erase(__it.base()), this);
00754       }
00755 
00756       iterator
00757       erase(iterator __it)
00758       { return erase(const_iterator(__it)); }
00759 
00760       iterator
00761       erase(const_iterator __first, const_iterator __last)
00762       {
00763     __glibcxx_check_erase_range(__first, __last);
00764     for (_Base_const_iterator __tmp = __first.base();
00765          __tmp != __last.base(); ++__tmp)
00766       {
00767         _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00768                   _M_message(__gnu_debug::__msg_valid_range)
00769                   ._M_iterator(__first, "first")
00770                   ._M_iterator(__last, "last"));
00771         this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
00772                 { return __it == __tmp; });
00773         _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
00774         this->_M_invalidate_local_if(
00775                 [__local_tmp](_Base_const_local_iterator __it)
00776                 { return __it == __local_tmp; });
00777       }
00778     return iterator(_Base::erase(__first.base(),
00779                      __last.base()), this);
00780       }
00781 
00782       _Base&
00783       _M_base() noexcept       { return *this; }
00784 
00785       const _Base&
00786       _M_base() const noexcept { return *this; }
00787 
00788     private:
00789       void
00790       _M_invalidate_locals()
00791       {
00792     _Base_local_iterator __local_end = _Base::end(0);
00793     this->_M_invalidate_local_if(
00794             [__local_end](_Base_const_local_iterator __it)
00795             { return __it != __local_end; });
00796       }
00797 
00798       void
00799       _M_invalidate_all()
00800       {
00801     _Base_iterator __end = _Base::end();
00802     this->_M_invalidate_if([__end](_Base_const_iterator __it)
00803             { return __it != __end; });
00804     _M_invalidate_locals();
00805       }
00806 
00807       void
00808       _M_check_rehashed(size_type __prev_count)
00809       {
00810     if (__prev_count != this->bucket_count())
00811       _M_invalidate_locals();
00812       }
00813 
00814       static _Base_local_iterator
00815       _S_to_local(_Base_iterator __it)
00816       {
00817         // The returned local iterator will not be incremented so we don't
00818     // need to compute __it's node bucket
00819     return _Base_local_iterator(__it._M_cur, 0, 0);
00820       }
00821 
00822       static _Base_const_local_iterator
00823       _S_to_local(_Base_const_iterator __it)
00824       {
00825         // The returned local iterator will not be incremented so we don't
00826     // need to compute __it's node bucket
00827     return _Base_const_local_iterator(__it._M_cur, 0, 0);
00828       }
00829     };
00830 
00831   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00832     inline void
00833     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00834      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00835     { __x.swap(__y); }
00836 
00837   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00838     inline bool
00839     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00840            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00841     { return __x._M_equal(__y); }
00842 
00843   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00844     inline bool
00845     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00846            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00847     { return !(__x == __y); }
00848 
00849 } // namespace __debug
00850 } // namespace std
00851 
00852 #endif // __GXX_EXPERIMENTAL_CXX0X__
00853 
00854 #endif