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