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