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