libstdc++
unordered_set
Go to the documentation of this file.
00001 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2016 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           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00359           __glibcxx_check_valid_range2(__first, __last, __dist);
00360           size_type __bucket_count = this->bucket_count();
00361 
00362           if (__dist.second >= __gnu_debug::__dp_sign)
00363             _Base::insert(__gnu_debug::__unsafe(__first),
00364                           __gnu_debug::__unsafe(__last));
00365           else
00366             _Base::insert(__first, __last);
00367 
00368           _M_check_rehashed(__bucket_count);
00369         }
00370 
00371       iterator
00372       find(const key_type& __key)
00373       { return iterator(_Base::find(__key), this); }
00374 
00375       const_iterator
00376       find(const key_type& __key) const
00377       { return const_iterator(_Base::find(__key), this); }
00378 
00379       std::pair<iterator, iterator>
00380       equal_range(const key_type& __key)
00381       {
00382         std::pair<_Base_iterator, _Base_iterator> __res
00383           = _Base::equal_range(__key);
00384         return std::make_pair(iterator(__res.first, this),
00385                               iterator(__res.second, this));
00386       }
00387 
00388       std::pair<const_iterator, const_iterator>
00389       equal_range(const key_type& __key) const
00390       {
00391         std::pair<_Base_const_iterator, _Base_const_iterator>
00392           __res = _Base::equal_range(__key);
00393         return std::make_pair(const_iterator(__res.first, this),
00394                               const_iterator(__res.second, this));
00395       }
00396 
00397       size_type
00398       erase(const key_type& __key)
00399       {
00400         size_type __ret(0);
00401         _Base_iterator __victim(_Base::find(__key));
00402         if (__victim != _Base::end())
00403           {
00404             this->_M_invalidate_if(
00405                             [__victim](_Base_const_iterator __it)
00406                             { return __it == __victim; });
00407             this->_M_invalidate_local_if(
00408                             [__victim](_Base_const_local_iterator __it)
00409                             { return __it._M_curr() == __victim._M_cur; });
00410             size_type __bucket_count = this->bucket_count();
00411             _Base::erase(__victim);
00412             _M_check_rehashed(__bucket_count);
00413             __ret = 1;
00414           }
00415         return __ret;
00416       }
00417 
00418       iterator
00419       erase(const_iterator __it)
00420       {
00421         __glibcxx_check_erase(__it);
00422         _Base_const_iterator __victim = __it.base();
00423         this->_M_invalidate_if(
00424                         [__victim](_Base_const_iterator __it)
00425                         { return __it == __victim; });
00426         this->_M_invalidate_local_if(
00427                         [__victim](_Base_const_local_iterator __it)
00428                         { return __it._M_curr() == __victim._M_cur; });
00429         size_type __bucket_count = this->bucket_count();
00430         _Base_iterator __next = _Base::erase(__it.base());
00431         _M_check_rehashed(__bucket_count);
00432         return iterator(__next, this);
00433       }
00434 
00435       iterator
00436       erase(iterator __it)
00437       { return erase(const_iterator(__it)); }
00438 
00439       iterator
00440       erase(const_iterator __first, const_iterator __last)
00441       {
00442         __glibcxx_check_erase_range(__first, __last);
00443         for (_Base_const_iterator __tmp = __first.base();
00444              __tmp != __last.base(); ++__tmp)
00445           {
00446             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00447                                   _M_message(__gnu_debug::__msg_valid_range)
00448                                   ._M_iterator(__first, "first")
00449                                   ._M_iterator(__last, "last"));
00450             this->_M_invalidate_if(
00451                             [__tmp](_Base_const_iterator __it)
00452                             { return __it == __tmp; });
00453             this->_M_invalidate_local_if(
00454                             [__tmp](_Base_const_local_iterator __it)
00455                             { return __it._M_curr() == __tmp._M_cur; });
00456           }
00457         size_type __bucket_count = this->bucket_count();
00458         _Base_iterator __next = _Base::erase(__first.base(),
00459                                              __last.base());
00460         _M_check_rehashed(__bucket_count);
00461         return iterator(__next, this);
00462       }
00463 
00464       _Base&
00465       _M_base() noexcept { return *this; }
00466 
00467       const _Base&
00468       _M_base() const noexcept { return *this; }
00469 
00470     private:
00471       void
00472       _M_check_rehashed(size_type __prev_count)
00473       {
00474         if (__prev_count != this->bucket_count())
00475           this->_M_invalidate_locals();
00476       }
00477     };
00478 
00479   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00480     inline void
00481     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00482          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00483     noexcept(noexcept(__x.swap(__y)))
00484     { __x.swap(__y); }
00485 
00486   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00487     inline bool
00488     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00489                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00490     { return __x._M_base() == __y._M_base(); }
00491 
00492   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00493     inline bool
00494     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00495                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00496     { return !(__x == __y); }
00497 
00498 
00499   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
00500   template<typename _Value,
00501            typename _Hash = std::hash<_Value>,
00502            typename _Pred = std::equal_to<_Value>,
00503            typename _Alloc = std::allocator<_Value> >
00504     class unordered_multiset
00505     : public __gnu_debug::_Safe_container<
00506         unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
00507         __gnu_debug::_Safe_unordered_container>,
00508       public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
00509     {
00510       typedef _GLIBCXX_STD_C::unordered_multiset<
00511         _Value, _Hash, _Pred, _Alloc>                           _Base;
00512       typedef __gnu_debug::_Safe_container<unordered_multiset,
00513         _Alloc, __gnu_debug::_Safe_unordered_container>         _Safe;
00514       typedef typename _Base::const_iterator    _Base_const_iterator;
00515       typedef typename _Base::iterator          _Base_iterator;
00516       typedef typename _Base::const_local_iterator
00517                                                 _Base_const_local_iterator;
00518       typedef typename _Base::local_iterator    _Base_local_iterator;
00519 
00520     public:
00521       typedef typename _Base::size_type                 size_type;
00522       typedef typename _Base::hasher                    hasher;
00523       typedef typename _Base::key_equal                 key_equal;
00524       typedef typename _Base::allocator_type            allocator_type;
00525 
00526       typedef typename _Base::key_type                  key_type;
00527       typedef typename _Base::value_type                value_type;
00528 
00529       typedef __gnu_debug::_Safe_iterator<
00530         _Base_iterator, unordered_multiset>             iterator;
00531       typedef __gnu_debug::_Safe_iterator<
00532         _Base_const_iterator, unordered_multiset>       const_iterator;
00533       typedef __gnu_debug::_Safe_local_iterator<
00534         _Base_local_iterator, unordered_multiset>       local_iterator;
00535       typedef __gnu_debug::_Safe_local_iterator<
00536         _Base_const_local_iterator, unordered_multiset> const_local_iterator;
00537 
00538       unordered_multiset() = default;
00539 
00540       explicit
00541       unordered_multiset(size_type __n,
00542                          const hasher& __hf = hasher(),
00543                          const key_equal& __eql = key_equal(),
00544                          const allocator_type& __a = allocator_type())
00545       : _Base(__n, __hf, __eql, __a) { }
00546 
00547       template<typename _InputIterator>
00548         unordered_multiset(_InputIterator __first, _InputIterator __last,
00549                            size_type __n = 0,
00550                            const hasher& __hf = hasher(),
00551                            const key_equal& __eql = key_equal(),
00552                            const allocator_type& __a = allocator_type())
00553         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00554                                                                      __last)),
00555                 __gnu_debug::__base(__last), __n,
00556                 __hf, __eql, __a) { }
00557 
00558       unordered_multiset(const unordered_multiset&) = default;
00559 
00560       unordered_multiset(const _Base& __x)
00561       : _Base(__x) { }
00562 
00563       unordered_multiset(unordered_multiset&&) = default;
00564 
00565       explicit
00566       unordered_multiset(const allocator_type& __a)
00567       : _Base(__a) { }
00568 
00569       unordered_multiset(const unordered_multiset& __uset,
00570                          const allocator_type& __a)
00571       : _Base(__uset, __a) { }
00572 
00573       unordered_multiset(unordered_multiset&& __uset,
00574                          const allocator_type& __a)
00575       : _Safe(std::move(__uset._M_safe()), __a),
00576         _Base(std::move(__uset._M_base()), __a) { }
00577 
00578       unordered_multiset(initializer_list<value_type> __l,
00579                          size_type __n = 0,
00580                          const hasher& __hf = hasher(),
00581                          const key_equal& __eql = key_equal(),
00582                          const allocator_type& __a = allocator_type())
00583       : _Base(__l, __n, __hf, __eql, __a) { }
00584 
00585       unordered_multiset(size_type __n, const allocator_type& __a)
00586         : unordered_multiset(__n, hasher(), key_equal(), __a)
00587       { }
00588 
00589       unordered_multiset(size_type __n, const hasher& __hf,
00590                          const allocator_type& __a)
00591         : unordered_multiset(__n, __hf, key_equal(), __a)
00592       { }
00593 
00594       template<typename _InputIterator>
00595         unordered_multiset(_InputIterator __first, _InputIterator __last,
00596                            size_type __n,
00597                            const allocator_type& __a)
00598           : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
00599         { }
00600 
00601       template<typename _InputIterator>
00602         unordered_multiset(_InputIterator __first, _InputIterator __last,
00603                            size_type __n, const hasher& __hf,
00604                            const allocator_type& __a)
00605           : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
00606         { }
00607 
00608       unordered_multiset(initializer_list<value_type> __l,
00609                          size_type __n,
00610                          const allocator_type& __a)
00611         : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
00612       { }
00613 
00614       unordered_multiset(initializer_list<value_type> __l,
00615                          size_type __n, const hasher& __hf,
00616                          const allocator_type& __a)
00617         : unordered_multiset(__l, __n, __hf, key_equal(), __a)
00618       { }
00619 
00620       ~unordered_multiset() = default;
00621 
00622       unordered_multiset&
00623       operator=(const unordered_multiset&) = default;
00624 
00625       unordered_multiset&
00626       operator=(unordered_multiset&&) = default;
00627 
00628       unordered_multiset&
00629       operator=(initializer_list<value_type> __l)
00630       {
00631         this->_M_base() = __l;
00632         this->_M_invalidate_all();
00633         return *this;
00634       }
00635 
00636       void
00637       swap(unordered_multiset& __x)
00638         noexcept( noexcept(declval<_Base&>().swap(__x)) )
00639       {
00640         _Safe::_M_swap(__x);
00641         _Base::swap(__x);
00642       }
00643 
00644       void
00645       clear() noexcept
00646       {
00647         _Base::clear();
00648         this->_M_invalidate_all();
00649       }
00650 
00651       iterator
00652       begin() noexcept
00653       { return iterator(_Base::begin(), this); }
00654 
00655       const_iterator
00656       begin() const noexcept
00657       { return const_iterator(_Base::begin(), this); }
00658 
00659       iterator
00660       end() noexcept
00661       { return iterator(_Base::end(), this); }
00662 
00663       const_iterator
00664       end() const noexcept
00665       { return const_iterator(_Base::end(), this); }
00666 
00667       const_iterator
00668       cbegin() const noexcept
00669       { return const_iterator(_Base::begin(), this); }
00670 
00671       const_iterator
00672       cend() const noexcept
00673       { return const_iterator(_Base::end(), this); }
00674 
00675       // local versions
00676       local_iterator
00677       begin(size_type __b)
00678       {
00679         __glibcxx_check_bucket_index(__b);
00680         return local_iterator(_Base::begin(__b), this);
00681       }
00682 
00683       local_iterator
00684       end(size_type __b)
00685       {
00686         __glibcxx_check_bucket_index(__b);
00687         return local_iterator(_Base::end(__b), this);
00688       }
00689 
00690       const_local_iterator
00691       begin(size_type __b) const
00692       {
00693         __glibcxx_check_bucket_index(__b);
00694         return const_local_iterator(_Base::begin(__b), this);
00695       }
00696 
00697       const_local_iterator
00698       end(size_type __b) const
00699       {
00700         __glibcxx_check_bucket_index(__b);
00701         return const_local_iterator(_Base::end(__b), this);
00702       }
00703 
00704       const_local_iterator
00705       cbegin(size_type __b) const
00706       {
00707         __glibcxx_check_bucket_index(__b);
00708         return const_local_iterator(_Base::cbegin(__b), this);
00709       }
00710 
00711       const_local_iterator
00712       cend(size_type __b) const
00713       {
00714         __glibcxx_check_bucket_index(__b);
00715         return const_local_iterator(_Base::cend(__b), this);
00716       }
00717 
00718       size_type
00719       bucket_size(size_type __b) const
00720       {
00721         __glibcxx_check_bucket_index(__b);
00722         return _Base::bucket_size(__b);
00723       }
00724 
00725       float
00726       max_load_factor() const noexcept
00727       { return _Base::max_load_factor(); }
00728 
00729       void
00730       max_load_factor(float __f)
00731       {
00732         __glibcxx_check_max_load_factor(__f);
00733         _Base::max_load_factor(__f);
00734       }
00735 
00736       template<typename... _Args>
00737         iterator
00738         emplace(_Args&&... __args)
00739         {
00740           size_type __bucket_count = this->bucket_count();
00741           _Base_iterator __it
00742             = _Base::emplace(std::forward<_Args>(__args)...);
00743           _M_check_rehashed(__bucket_count);
00744           return iterator(__it, this);
00745         }
00746 
00747       template<typename... _Args>
00748         iterator
00749         emplace_hint(const_iterator __hint, _Args&&... __args)
00750         {
00751           __glibcxx_check_insert(__hint);
00752           size_type __bucket_count = this->bucket_count();
00753           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
00754                                         std::forward<_Args>(__args)...);
00755           _M_check_rehashed(__bucket_count);
00756           return iterator(__it, this);
00757         }
00758 
00759       iterator
00760       insert(const value_type& __obj)
00761       {
00762         size_type __bucket_count = this->bucket_count();
00763         _Base_iterator __it = _Base::insert(__obj);
00764         _M_check_rehashed(__bucket_count);
00765         return iterator(__it, this);
00766       }
00767 
00768       iterator
00769       insert(const_iterator __hint, const 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(), __obj);
00774         _M_check_rehashed(__bucket_count);
00775         return iterator(__it, this);
00776       }
00777 
00778       iterator
00779       insert(value_type&& __obj)
00780       {
00781         size_type __bucket_count = this->bucket_count();
00782         _Base_iterator __it = _Base::insert(std::move(__obj));
00783         _M_check_rehashed(__bucket_count);
00784         return iterator(__it, this);
00785       }
00786 
00787       iterator
00788       insert(const_iterator __hint, value_type&& __obj)
00789       {
00790         __glibcxx_check_insert(__hint);
00791         size_type __bucket_count = this->bucket_count();
00792         _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
00793         _M_check_rehashed(__bucket_count);
00794         return iterator(__it, this);
00795       }
00796 
00797       void
00798       insert(std::initializer_list<value_type> __l)
00799       {
00800         size_type __bucket_count = this->bucket_count();
00801         _Base::insert(__l);
00802         _M_check_rehashed(__bucket_count);
00803       }
00804 
00805       template<typename _InputIterator>
00806         void
00807         insert(_InputIterator __first, _InputIterator __last)
00808         {
00809           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00810           __glibcxx_check_valid_range2(__first, __last, __dist);
00811           size_type __bucket_count = this->bucket_count();
00812 
00813           if (__dist.second >= __gnu_debug::__dp_sign)
00814             _Base::insert(__gnu_debug::__unsafe(__first),
00815                           __gnu_debug::__unsafe(__last));
00816           else
00817             _Base::insert(__first, __last);
00818 
00819           _M_check_rehashed(__bucket_count);
00820         }
00821 
00822       iterator
00823       find(const key_type& __key)
00824       { return iterator(_Base::find(__key), this); }
00825 
00826       const_iterator
00827       find(const key_type& __key) const
00828       { return const_iterator(_Base::find(__key), this); }
00829 
00830       std::pair<iterator, iterator>
00831       equal_range(const key_type& __key)
00832       {
00833         std::pair<_Base_iterator, _Base_iterator> __res
00834           = _Base::equal_range(__key);
00835         return std::make_pair(iterator(__res.first, this),
00836                               iterator(__res.second, this));
00837       }
00838 
00839       std::pair<const_iterator, const_iterator>
00840       equal_range(const key_type& __key) const
00841       {
00842         std::pair<_Base_const_iterator, _Base_const_iterator>
00843           __res = _Base::equal_range(__key);
00844         return std::make_pair(const_iterator(__res.first, this),
00845                               const_iterator(__res.second, this));
00846       }
00847 
00848       size_type
00849       erase(const key_type& __key)
00850       {
00851         size_type __ret(0);
00852         std::pair<_Base_iterator, _Base_iterator> __pair =
00853           _Base::equal_range(__key);
00854         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
00855           {
00856             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00857                             { return __it == __victim; });
00858             this->_M_invalidate_local_if(
00859                             [__victim](_Base_const_local_iterator __it)
00860                             { return __it._M_curr() == __victim._M_cur; });
00861             _Base::erase(__victim++);
00862             ++__ret;
00863           }
00864         return __ret;
00865       }
00866 
00867       iterator
00868       erase(const_iterator __it)
00869       {
00870         __glibcxx_check_erase(__it);
00871         _Base_const_iterator __victim = __it.base();
00872         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00873                         { return __it == __victim; });
00874         this->_M_invalidate_local_if(
00875                         [__victim](_Base_const_local_iterator __it)
00876                         { return __it._M_curr() == __victim._M_cur; });
00877         return iterator(_Base::erase(__it.base()), this);
00878       }
00879 
00880       iterator
00881       erase(iterator __it)
00882       { return erase(const_iterator(__it)); }
00883 
00884       iterator
00885       erase(const_iterator __first, const_iterator __last)
00886       {
00887         __glibcxx_check_erase_range(__first, __last);
00888         for (_Base_const_iterator __tmp = __first.base();
00889              __tmp != __last.base(); ++__tmp)
00890           {
00891             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00892                                   _M_message(__gnu_debug::__msg_valid_range)
00893                                   ._M_iterator(__first, "first")
00894                                   ._M_iterator(__last, "last"));
00895             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
00896                             { return __it == __tmp; });
00897             this->_M_invalidate_local_if(
00898                             [__tmp](_Base_const_local_iterator __it)
00899                             { return __it._M_curr() == __tmp._M_cur; });
00900           }
00901         return iterator(_Base::erase(__first.base(),
00902                                      __last.base()), this);
00903       }
00904 
00905       _Base&
00906       _M_base() noexcept        { return *this; }
00907 
00908       const _Base&
00909       _M_base() const noexcept  { return *this; }
00910 
00911     private:
00912       void
00913       _M_check_rehashed(size_type __prev_count)
00914       {
00915         if (__prev_count != this->bucket_count())
00916           this->_M_invalidate_locals();
00917       }
00918     };
00919 
00920   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00921     inline void
00922     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00923          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00924     noexcept(noexcept(__x.swap(__y)))
00925     { __x.swap(__y); }
00926 
00927   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00928     inline bool
00929     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00930                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00931     { return __x._M_base() == __y._M_base(); }
00932 
00933   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00934     inline bool
00935     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00936                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00937     { return !(__x == __y); }
00938 
00939 } // namespace __debug
00940 } // namespace std
00941 
00942 #endif // C++11
00943 
00944 #endif