libstdc++
unordered_set
Go to the documentation of this file.
00001 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2019 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 #pragma GCC system_header
00033 
00034 #if __cplusplus < 201103L
00035 # include <bits/c++0x_warning.h>
00036 #else
00037 # include <bits/c++config.h>
00038 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
00039   template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
00040     class unordered_set;
00041   template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
00042     class unordered_multiset;
00043 } } // namespace std::__debug
00044 # include <unordered_set>
00045 
00046 #include <debug/safe_unordered_container.h>
00047 #include <debug/safe_container.h>
00048 #include <debug/safe_iterator.h>
00049 #include <debug/safe_local_iterator.h>
00050 
00051 namespace std _GLIBCXX_VISIBILITY(default)
00052 {
00053 namespace __debug
00054 {
00055   /// Class std::unordered_set with safety/checking/debug instrumentation.
00056   template<typename _Value,
00057            typename _Hash = std::hash<_Value>,
00058            typename _Pred = std::equal_to<_Value>,
00059            typename _Alloc = std::allocator<_Value> >
00060     class unordered_set
00061     : public __gnu_debug::_Safe_container<
00062         unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc,
00063         __gnu_debug::_Safe_unordered_container>,
00064       public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>
00065     {
00066       typedef _GLIBCXX_STD_C::unordered_set<
00067         _Value, _Hash, _Pred, _Alloc>                                   _Base;
00068       typedef __gnu_debug::_Safe_container<
00069         unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container>  _Safe;
00070 
00071       typedef typename _Base::const_iterator       _Base_const_iterator;
00072       typedef typename _Base::iterator             _Base_iterator;
00073       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
00074       typedef typename _Base::local_iterator       _Base_local_iterator;
00075 
00076       template<typename _ItT, typename _SeqT, typename _CatT>
00077         friend class ::__gnu_debug::_Safe_iterator;
00078       template<typename _ItT, typename _SeqT>
00079         friend class ::__gnu_debug::_Safe_local_iterator;
00080 
00081     public:
00082       typedef typename _Base::size_type                 size_type;
00083       typedef typename _Base::hasher                    hasher;
00084       typedef typename _Base::key_equal                 key_equal;
00085       typedef typename _Base::allocator_type            allocator_type;
00086 
00087       typedef typename _Base::key_type                  key_type;
00088       typedef typename _Base::value_type                value_type;
00089 
00090       typedef __gnu_debug::_Safe_iterator<
00091         _Base_iterator, unordered_set>                  iterator;
00092       typedef __gnu_debug::_Safe_iterator<
00093         _Base_const_iterator, unordered_set>            const_iterator;
00094       typedef __gnu_debug::_Safe_local_iterator<
00095         _Base_local_iterator, unordered_set>            local_iterator;
00096       typedef __gnu_debug::_Safe_local_iterator<
00097         _Base_const_local_iterator, unordered_set>      const_local_iterator;
00098 
00099       unordered_set() = default;
00100 
00101       explicit
00102       unordered_set(size_type __n,
00103                     const hasher& __hf = hasher(),
00104                     const key_equal& __eql = key_equal(),
00105                     const allocator_type& __a = allocator_type())
00106       : _Base(__n, __hf, __eql, __a) { }
00107 
00108       template<typename _InputIterator>
00109         unordered_set(_InputIterator __first, _InputIterator __last,
00110                       size_type __n = 0,
00111                       const hasher& __hf = hasher(),
00112                       const key_equal& __eql = key_equal(),
00113                       const allocator_type& __a = allocator_type())
00114         : _Base(__gnu_debug::__base(
00115                   __glibcxx_check_valid_constructor_range(__first, __last)),
00116                 __gnu_debug::__base(__last), __n,
00117                 __hf, __eql, __a) { }
00118 
00119       unordered_set(const unordered_set&) = default;
00120 
00121       unordered_set(const _Base& __x)
00122       : _Base(__x) { }
00123 
00124       unordered_set(unordered_set&&) = default;
00125 
00126       explicit
00127       unordered_set(const allocator_type& __a)
00128       : _Base(__a) { }
00129 
00130       unordered_set(const unordered_set& __uset,
00131                     const allocator_type& __a)
00132       : _Base(__uset, __a) { }
00133 
00134       unordered_set(unordered_set&& __uset,
00135                     const allocator_type& __a)
00136       : _Safe(std::move(__uset._M_safe()), __a),
00137         _Base(std::move(__uset._M_base()), __a) { }
00138 
00139       unordered_set(initializer_list<value_type> __l,
00140                     size_type __n = 0,
00141                     const hasher& __hf = hasher(),
00142                     const key_equal& __eql = key_equal(),
00143                     const allocator_type& __a = allocator_type())
00144       : _Base(__l, __n, __hf, __eql, __a) { }
00145 
00146       unordered_set(size_type __n, const allocator_type& __a)
00147         : unordered_set(__n, hasher(), key_equal(), __a)
00148       { }
00149 
00150       unordered_set(size_type __n, const hasher& __hf,
00151                     const allocator_type& __a)
00152         : unordered_set(__n, __hf, key_equal(), __a)
00153       { }
00154 
00155       template<typename _InputIterator>
00156         unordered_set(_InputIterator __first, _InputIterator __last,
00157                       size_type __n,
00158                       const allocator_type& __a)
00159           : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
00160         { }
00161 
00162       template<typename _InputIterator>
00163         unordered_set(_InputIterator __first, _InputIterator __last,
00164                       size_type __n, const hasher& __hf,
00165                       const allocator_type& __a)
00166           : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
00167         { }
00168 
00169       unordered_set(initializer_list<value_type> __l,
00170                     size_type __n,
00171                     const allocator_type& __a)
00172         : unordered_set(__l, __n, hasher(), key_equal(), __a)
00173       { }
00174 
00175       unordered_set(initializer_list<value_type> __l,
00176                     size_type __n, const hasher& __hf,
00177                     const allocator_type& __a)
00178         : unordered_set(__l, __n, __hf, key_equal(), __a)
00179       { }
00180 
00181       ~unordered_set() = default;
00182 
00183       unordered_set&
00184       operator=(const unordered_set&) = default;
00185 
00186       unordered_set&
00187       operator=(unordered_set&&) = default;
00188 
00189       unordered_set&
00190       operator=(initializer_list<value_type> __l)
00191       {
00192         _M_base() = __l;
00193         this->_M_invalidate_all();
00194         return *this;
00195       }
00196 
00197       void
00198       swap(unordered_set& __x)
00199         noexcept( noexcept(declval<_Base&>().swap(__x)) )
00200       {
00201         _Safe::_M_swap(__x);
00202         _Base::swap(__x);
00203       }
00204 
00205       void
00206       clear() noexcept
00207       {
00208         _Base::clear();
00209         this->_M_invalidate_all();
00210       }
00211 
00212       iterator
00213       begin() noexcept
00214       { return { _Base::begin(), this }; }
00215 
00216       const_iterator
00217       begin() const noexcept
00218       { return { _Base::begin(), this }; }
00219 
00220       iterator
00221       end() noexcept
00222       { return { _Base::end(), this }; }
00223 
00224       const_iterator
00225       end() const noexcept
00226       { return { _Base::end(), this }; }
00227 
00228       const_iterator
00229       cbegin() const noexcept
00230       { return { _Base::cbegin(), this }; }
00231 
00232       const_iterator
00233       cend() const noexcept
00234       { return { _Base::cend(), this }; }
00235 
00236       // local versions
00237       local_iterator
00238       begin(size_type __b)
00239       {
00240         __glibcxx_check_bucket_index(__b);
00241         return { _Base::begin(__b), this };
00242       }
00243 
00244       local_iterator
00245       end(size_type __b)
00246       {
00247         __glibcxx_check_bucket_index(__b);
00248         return { _Base::end(__b), this };
00249       }
00250 
00251       const_local_iterator
00252       begin(size_type __b) const
00253       {
00254         __glibcxx_check_bucket_index(__b);
00255         return { _Base::begin(__b), this };
00256       }
00257 
00258       const_local_iterator
00259       end(size_type __b) const
00260       {
00261         __glibcxx_check_bucket_index(__b);
00262         return { _Base::end(__b), this };
00263       }
00264 
00265       const_local_iterator
00266       cbegin(size_type __b) const
00267       {
00268         __glibcxx_check_bucket_index(__b);
00269         return { _Base::cbegin(__b), this };
00270       }
00271 
00272       const_local_iterator
00273       cend(size_type __b) const
00274       {
00275         __glibcxx_check_bucket_index(__b);
00276         return { _Base::cend(__b), this };
00277       }
00278 
00279       size_type
00280       bucket_size(size_type __b) const
00281       {
00282         __glibcxx_check_bucket_index(__b);
00283         return _Base::bucket_size(__b);
00284       }
00285 
00286       float
00287       max_load_factor() const noexcept
00288       { return _Base::max_load_factor(); }
00289 
00290       void
00291       max_load_factor(float __f)
00292       {
00293         __glibcxx_check_max_load_factor(__f);
00294         _Base::max_load_factor(__f);
00295       }
00296 
00297       template<typename... _Args>
00298         std::pair<iterator, bool>
00299         emplace(_Args&&... __args)
00300         {
00301           size_type __bucket_count = this->bucket_count();
00302           auto __res = _Base::emplace(std::forward<_Args>(__args)...);
00303           _M_check_rehashed(__bucket_count);
00304           return { { __res.first, this }, __res.second };
00305         }
00306 
00307       template<typename... _Args>
00308         iterator
00309         emplace_hint(const_iterator __hint, _Args&&... __args)
00310         {
00311           __glibcxx_check_insert(__hint);
00312           size_type __bucket_count = this->bucket_count();
00313           auto __it = _Base::emplace_hint(__hint.base(),
00314                                           std::forward<_Args>(__args)...);
00315           _M_check_rehashed(__bucket_count);
00316           return { __it, this };
00317         }
00318 
00319       std::pair<iterator, bool>
00320       insert(const value_type& __obj)
00321       {
00322         size_type __bucket_count = this->bucket_count();
00323         auto __res = _Base::insert(__obj);
00324         _M_check_rehashed(__bucket_count);
00325         return { { __res.first, this }, __res.second };
00326       }
00327 
00328       iterator
00329       insert(const_iterator __hint, const value_type& __obj)
00330       {
00331         __glibcxx_check_insert(__hint);
00332         size_type __bucket_count = this->bucket_count();
00333         auto __it = _Base::insert(__hint.base(), __obj);
00334         _M_check_rehashed(__bucket_count);
00335         return { __it, this };
00336       }
00337 
00338       std::pair<iterator, bool>
00339       insert(value_type&& __obj)
00340       {
00341         size_type __bucket_count = this->bucket_count();
00342         auto __res = _Base::insert(std::move(__obj));
00343         _M_check_rehashed(__bucket_count);
00344         return { { __res.first, this }, __res.second };
00345       }
00346 
00347       iterator
00348       insert(const_iterator __hint, value_type&& __obj)
00349       {
00350         __glibcxx_check_insert(__hint);
00351         size_type __bucket_count = this->bucket_count();
00352         auto __it = _Base::insert(__hint.base(), std::move(__obj));
00353         _M_check_rehashed(__bucket_count);
00354         return { __it, this };
00355       }
00356 
00357       void
00358       insert(std::initializer_list<value_type> __l)
00359       {
00360         size_type __bucket_count = this->bucket_count();
00361         _Base::insert(__l);
00362         _M_check_rehashed(__bucket_count);
00363       }
00364 
00365       template<typename _InputIterator>
00366         void
00367         insert(_InputIterator __first, _InputIterator __last)
00368         {
00369           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00370           __glibcxx_check_valid_range2(__first, __last, __dist);
00371           size_type __bucket_count = this->bucket_count();
00372 
00373           if (__dist.second >= __gnu_debug::__dp_sign)
00374             _Base::insert(__gnu_debug::__unsafe(__first),
00375                           __gnu_debug::__unsafe(__last));
00376           else
00377             _Base::insert(__first, __last);
00378 
00379           _M_check_rehashed(__bucket_count);
00380         }
00381 
00382 #if __cplusplus > 201402L
00383       using node_type = typename _Base::node_type;
00384       using insert_return_type = _Node_insert_return<iterator, node_type>;
00385 
00386       node_type
00387       extract(const_iterator __position)
00388       {
00389         __glibcxx_check_erase(__position);
00390         return _M_extract(__position.base());
00391       }
00392 
00393       node_type
00394       extract(const key_type& __key)
00395       {
00396         const auto __position = _Base::find(__key);
00397         if (__position != _Base::end())
00398           return _M_extract(__position);
00399         return {};
00400       }
00401 
00402       insert_return_type
00403       insert(node_type&& __nh)
00404       {
00405         auto __ret = _Base::insert(std::move(__nh));
00406         return
00407           { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
00408       }
00409 
00410       iterator
00411       insert(const_iterator __hint, node_type&& __nh)
00412       {
00413         __glibcxx_check_insert(__hint);
00414         return { _Base::insert(__hint.base(), std::move(__nh)), this };
00415       }
00416 
00417       using _Base::merge;
00418 #endif // C++17
00419 
00420       iterator
00421       find(const key_type& __key)
00422       { return { _Base::find(__key), this }; }
00423 
00424       const_iterator
00425       find(const key_type& __key) const
00426       { return { _Base::find(__key), this }; }
00427 
00428       std::pair<iterator, iterator>
00429       equal_range(const key_type& __key)
00430       {
00431         auto __res = _Base::equal_range(__key);
00432         return { { __res.first, this }, { __res.second, this } };
00433       }
00434 
00435       std::pair<const_iterator, const_iterator>
00436       equal_range(const key_type& __key) const
00437       {
00438         auto __res = _Base::equal_range(__key);
00439         return { { __res.first, this }, { __res.second, this } };
00440       }
00441 
00442       size_type
00443       erase(const key_type& __key)
00444       {
00445         size_type __ret(0);
00446         auto __victim = _Base::find(__key);
00447         if (__victim != _Base::end())
00448           {
00449             _M_erase(__victim);
00450             __ret = 1;
00451           }
00452         return __ret;
00453       }
00454 
00455       iterator
00456       erase(const_iterator __it)
00457       {
00458         __glibcxx_check_erase(__it);
00459         return { _M_erase(__it.base()), this };
00460       }
00461 
00462       iterator
00463       erase(iterator __it)
00464       {
00465         __glibcxx_check_erase(__it);
00466         return { _M_erase(__it.base()), this };
00467       }
00468 
00469       iterator
00470       erase(const_iterator __first, const_iterator __last)
00471       {
00472         __glibcxx_check_erase_range(__first, __last);
00473         for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
00474           {
00475             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
00476                                   _M_message(__gnu_debug::__msg_valid_range)
00477                                   ._M_iterator(__first, "first")
00478                                   ._M_iterator(__last, "last"));
00479             _M_invalidate(__tmp);
00480           }
00481 
00482         size_type __bucket_count = this->bucket_count();
00483         auto __next = _Base::erase(__first.base(), __last.base());
00484         _M_check_rehashed(__bucket_count);
00485         return { __next, this };
00486       }
00487 
00488       _Base&
00489       _M_base() noexcept { return *this; }
00490 
00491       const _Base&
00492       _M_base() const noexcept { return *this; }
00493 
00494     private:
00495       void
00496       _M_check_rehashed(size_type __prev_count)
00497       {
00498         if (__prev_count != this->bucket_count())
00499           this->_M_invalidate_all();
00500       }
00501 
00502       void
00503       _M_invalidate(_Base_const_iterator __victim)
00504       {
00505         this->_M_invalidate_if(
00506           [__victim](_Base_const_iterator __it) { return __it == __victim; });
00507         this->_M_invalidate_local_if(
00508           [__victim](_Base_const_local_iterator __it)
00509           { return __it._M_curr() == __victim._M_cur; });
00510       }
00511 
00512       _Base_iterator
00513       _M_erase(_Base_const_iterator __victim)
00514       {
00515         _M_invalidate(__victim);
00516         size_type __bucket_count = this->bucket_count();
00517         _Base_iterator __next = _Base::erase(__victim);
00518         _M_check_rehashed(__bucket_count);
00519         return __next;
00520       }
00521 
00522 #if __cplusplus > 201402L
00523       node_type
00524       _M_extract(_Base_const_iterator __victim)
00525       {
00526         _M_invalidate(__victim);
00527         return _Base::extract(__victim);
00528       }
00529 #endif
00530     };
00531 
00532 #if __cpp_deduction_guides >= 201606
00533 
00534   template<typename _InputIterator,
00535            typename _Hash =
00536              hash<typename iterator_traits<_InputIterator>::value_type>,
00537            typename _Pred =
00538              equal_to<typename iterator_traits<_InputIterator>::value_type>,
00539            typename _Allocator =
00540              allocator<typename iterator_traits<_InputIterator>::value_type>,
00541            typename = _RequireInputIter<_InputIterator>,
00542            typename = _RequireNotAllocatorOrIntegral<_Hash>,
00543            typename = _RequireNotAllocator<_Pred>,
00544            typename = _RequireAllocator<_Allocator>>
00545     unordered_set(_InputIterator, _InputIterator,
00546                   unordered_set<int>::size_type = {},
00547                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
00548     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
00549                      _Hash, _Pred, _Allocator>;
00550 
00551   template<typename _Tp, typename _Hash = hash<_Tp>,
00552            typename _Pred = equal_to<_Tp>,
00553            typename _Allocator = allocator<_Tp>,
00554            typename = _RequireNotAllocatorOrIntegral<_Hash>,
00555            typename = _RequireNotAllocator<_Pred>,
00556            typename = _RequireAllocator<_Allocator>>
00557     unordered_set(initializer_list<_Tp>,
00558                   unordered_set<int>::size_type = {},
00559                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
00560     -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
00561 
00562   template<typename _InputIterator, typename _Allocator,
00563            typename = _RequireInputIter<_InputIterator>,
00564            typename = _RequireAllocator<_Allocator>>
00565     unordered_set(_InputIterator, _InputIterator,
00566                   unordered_set<int>::size_type, _Allocator)
00567     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
00568                      hash<
00569                        typename iterator_traits<_InputIterator>::value_type>,
00570                      equal_to<
00571                        typename iterator_traits<_InputIterator>::value_type>,
00572                      _Allocator>;
00573 
00574   template<typename _InputIterator, typename _Hash, typename _Allocator,
00575            typename = _RequireInputIter<_InputIterator>,
00576            typename = _RequireNotAllocatorOrIntegral<_Hash>,
00577            typename = _RequireAllocator<_Allocator>>
00578     unordered_set(_InputIterator, _InputIterator,
00579                   unordered_set<int>::size_type,
00580                   _Hash, _Allocator)
00581     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
00582                      _Hash,
00583                      equal_to<
00584                        typename iterator_traits<_InputIterator>::value_type>,
00585                      _Allocator>;
00586 
00587   template<typename _Tp, typename _Allocator,
00588            typename = _RequireAllocator<_Allocator>>
00589     unordered_set(initializer_list<_Tp>,
00590                   unordered_set<int>::size_type, _Allocator)
00591     -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
00592 
00593   template<typename _Tp, typename _Hash, typename _Allocator,
00594            typename = _RequireNotAllocatorOrIntegral<_Hash>,
00595            typename = _RequireAllocator<_Allocator>>
00596     unordered_set(initializer_list<_Tp>,
00597                   unordered_set<int>::size_type, _Hash, _Allocator)
00598     -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
00599 
00600 #endif
00601 
00602   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00603     inline void
00604     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00605          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00606     noexcept(noexcept(__x.swap(__y)))
00607     { __x.swap(__y); }
00608 
00609   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00610     inline bool
00611     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00612                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00613     { return __x._M_base() == __y._M_base(); }
00614 
00615   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00616     inline bool
00617     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00618                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00619     { return !(__x == __y); }
00620 
00621 
00622   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
00623   template<typename _Value,
00624            typename _Hash = std::hash<_Value>,
00625            typename _Pred = std::equal_to<_Value>,
00626            typename _Alloc = std::allocator<_Value> >
00627     class unordered_multiset
00628     : public __gnu_debug::_Safe_container<
00629         unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
00630         __gnu_debug::_Safe_unordered_container>,
00631       public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
00632     {
00633       typedef _GLIBCXX_STD_C::unordered_multiset<
00634         _Value, _Hash, _Pred, _Alloc>                           _Base;
00635       typedef __gnu_debug::_Safe_container<unordered_multiset,
00636         _Alloc, __gnu_debug::_Safe_unordered_container>         _Safe;
00637       typedef typename _Base::const_iterator    _Base_const_iterator;
00638       typedef typename _Base::iterator          _Base_iterator;
00639       typedef typename _Base::const_local_iterator
00640                                                 _Base_const_local_iterator;
00641       typedef typename _Base::local_iterator    _Base_local_iterator;
00642 
00643       template<typename _ItT, typename _SeqT, typename _CatT>
00644         friend class ::__gnu_debug::_Safe_iterator;
00645       template<typename _ItT, typename _SeqT>
00646         friend class ::__gnu_debug::_Safe_local_iterator;
00647 
00648     public:
00649       typedef typename _Base::size_type                 size_type;
00650       typedef typename _Base::hasher                    hasher;
00651       typedef typename _Base::key_equal                 key_equal;
00652       typedef typename _Base::allocator_type            allocator_type;
00653 
00654       typedef typename _Base::key_type                  key_type;
00655       typedef typename _Base::value_type                value_type;
00656 
00657       typedef __gnu_debug::_Safe_iterator<
00658         _Base_iterator, unordered_multiset>             iterator;
00659       typedef __gnu_debug::_Safe_iterator<
00660         _Base_const_iterator, unordered_multiset>       const_iterator;
00661       typedef __gnu_debug::_Safe_local_iterator<
00662         _Base_local_iterator, unordered_multiset>       local_iterator;
00663       typedef __gnu_debug::_Safe_local_iterator<
00664         _Base_const_local_iterator, unordered_multiset> const_local_iterator;
00665 
00666       unordered_multiset() = default;
00667 
00668       explicit
00669       unordered_multiset(size_type __n,
00670                          const hasher& __hf = hasher(),
00671                          const key_equal& __eql = key_equal(),
00672                          const allocator_type& __a = allocator_type())
00673       : _Base(__n, __hf, __eql, __a) { }
00674 
00675       template<typename _InputIterator>
00676         unordered_multiset(_InputIterator __first, _InputIterator __last,
00677                            size_type __n = 0,
00678                            const hasher& __hf = hasher(),
00679                            const key_equal& __eql = key_equal(),
00680                            const allocator_type& __a = allocator_type())
00681         : _Base(__gnu_debug::__base(
00682                   __glibcxx_check_valid_constructor_range(__first, __last)),
00683                 __gnu_debug::__base(__last), __n,
00684                 __hf, __eql, __a) { }
00685 
00686       unordered_multiset(const unordered_multiset&) = default;
00687 
00688       unordered_multiset(const _Base& __x)
00689       : _Base(__x) { }
00690 
00691       unordered_multiset(unordered_multiset&&) = default;
00692 
00693       explicit
00694       unordered_multiset(const allocator_type& __a)
00695       : _Base(__a) { }
00696 
00697       unordered_multiset(const unordered_multiset& __uset,
00698                          const allocator_type& __a)
00699       : _Base(__uset, __a) { }
00700 
00701       unordered_multiset(unordered_multiset&& __uset,
00702                          const allocator_type& __a)
00703       : _Safe(std::move(__uset._M_safe()), __a),
00704         _Base(std::move(__uset._M_base()), __a) { }
00705 
00706       unordered_multiset(initializer_list<value_type> __l,
00707                          size_type __n = 0,
00708                          const hasher& __hf = hasher(),
00709                          const key_equal& __eql = key_equal(),
00710                          const allocator_type& __a = allocator_type())
00711       : _Base(__l, __n, __hf, __eql, __a) { }
00712 
00713       unordered_multiset(size_type __n, const allocator_type& __a)
00714         : unordered_multiset(__n, hasher(), key_equal(), __a)
00715       { }
00716 
00717       unordered_multiset(size_type __n, const hasher& __hf,
00718                          const allocator_type& __a)
00719         : unordered_multiset(__n, __hf, key_equal(), __a)
00720       { }
00721 
00722       template<typename _InputIterator>
00723         unordered_multiset(_InputIterator __first, _InputIterator __last,
00724                            size_type __n,
00725                            const allocator_type& __a)
00726           : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
00727         { }
00728 
00729       template<typename _InputIterator>
00730         unordered_multiset(_InputIterator __first, _InputIterator __last,
00731                            size_type __n, const hasher& __hf,
00732                            const allocator_type& __a)
00733           : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
00734         { }
00735 
00736       unordered_multiset(initializer_list<value_type> __l,
00737                          size_type __n,
00738                          const allocator_type& __a)
00739         : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
00740       { }
00741 
00742       unordered_multiset(initializer_list<value_type> __l,
00743                          size_type __n, const hasher& __hf,
00744                          const allocator_type& __a)
00745         : unordered_multiset(__l, __n, __hf, key_equal(), __a)
00746       { }
00747 
00748       ~unordered_multiset() = default;
00749 
00750       unordered_multiset&
00751       operator=(const unordered_multiset&) = default;
00752 
00753       unordered_multiset&
00754       operator=(unordered_multiset&&) = default;
00755 
00756       unordered_multiset&
00757       operator=(initializer_list<value_type> __l)
00758       {
00759         this->_M_base() = __l;
00760         this->_M_invalidate_all();
00761         return *this;
00762       }
00763 
00764       void
00765       swap(unordered_multiset& __x)
00766         noexcept( noexcept(declval<_Base&>().swap(__x)) )
00767       {
00768         _Safe::_M_swap(__x);
00769         _Base::swap(__x);
00770       }
00771 
00772       void
00773       clear() noexcept
00774       {
00775         _Base::clear();
00776         this->_M_invalidate_all();
00777       }
00778 
00779       iterator
00780       begin() noexcept
00781       { return { _Base::begin(), this }; }
00782 
00783       const_iterator
00784       begin() const noexcept
00785       { return { _Base::begin(), this }; }
00786 
00787       iterator
00788       end() noexcept
00789       { return { _Base::end(), this }; }
00790 
00791       const_iterator
00792       end() const noexcept
00793       { return { _Base::end(), this }; }
00794 
00795       const_iterator
00796       cbegin() const noexcept
00797       { return { _Base::cbegin(), this }; }
00798 
00799       const_iterator
00800       cend() const noexcept
00801       { return { _Base::cend(), this }; }
00802 
00803       // local versions
00804       local_iterator
00805       begin(size_type __b)
00806       {
00807         __glibcxx_check_bucket_index(__b);
00808         return { _Base::begin(__b), this };
00809       }
00810 
00811       local_iterator
00812       end(size_type __b)
00813       {
00814         __glibcxx_check_bucket_index(__b);
00815         return { _Base::end(__b), this };
00816       }
00817 
00818       const_local_iterator
00819       begin(size_type __b) const
00820       {
00821         __glibcxx_check_bucket_index(__b);
00822         return { _Base::begin(__b), this };
00823       }
00824 
00825       const_local_iterator
00826       end(size_type __b) const
00827       {
00828         __glibcxx_check_bucket_index(__b);
00829         return { _Base::end(__b), this };
00830       }
00831 
00832       const_local_iterator
00833       cbegin(size_type __b) const
00834       {
00835         __glibcxx_check_bucket_index(__b);
00836         return { _Base::cbegin(__b), this };
00837       }
00838 
00839       const_local_iterator
00840       cend(size_type __b) const
00841       {
00842         __glibcxx_check_bucket_index(__b);
00843         return { _Base::cend(__b), this };
00844       }
00845 
00846       size_type
00847       bucket_size(size_type __b) const
00848       {
00849         __glibcxx_check_bucket_index(__b);
00850         return _Base::bucket_size(__b);
00851       }
00852 
00853       float
00854       max_load_factor() const noexcept
00855       { return _Base::max_load_factor(); }
00856 
00857       void
00858       max_load_factor(float __f)
00859       {
00860         __glibcxx_check_max_load_factor(__f);
00861         _Base::max_load_factor(__f);
00862       }
00863 
00864       template<typename... _Args>
00865         iterator
00866         emplace(_Args&&... __args)
00867         {
00868           size_type __bucket_count = this->bucket_count();
00869           auto __it = _Base::emplace(std::forward<_Args>(__args)...);
00870           _M_check_rehashed(__bucket_count);
00871           return { __it, this };
00872         }
00873 
00874       template<typename... _Args>
00875         iterator
00876         emplace_hint(const_iterator __hint, _Args&&... __args)
00877         {
00878           __glibcxx_check_insert(__hint);
00879           size_type __bucket_count = this->bucket_count();
00880           auto __it = _Base::emplace_hint(__hint.base(),
00881                                           std::forward<_Args>(__args)...);
00882           _M_check_rehashed(__bucket_count);
00883           return { __it, this };
00884         }
00885 
00886       iterator
00887       insert(const value_type& __obj)
00888       {
00889         size_type __bucket_count = this->bucket_count();
00890         auto __it = _Base::insert(__obj);
00891         _M_check_rehashed(__bucket_count);
00892         return { __it, this };
00893       }
00894 
00895       iterator
00896       insert(const_iterator __hint, const value_type& __obj)
00897       {
00898         __glibcxx_check_insert(__hint);
00899         size_type __bucket_count = this->bucket_count();
00900         auto __it = _Base::insert(__hint.base(), __obj);
00901         _M_check_rehashed(__bucket_count);
00902         return { __it, this };
00903       }
00904 
00905       iterator
00906       insert(value_type&& __obj)
00907       {
00908         size_type __bucket_count = this->bucket_count();
00909         auto __it = _Base::insert(std::move(__obj));
00910         _M_check_rehashed(__bucket_count);
00911         return { __it, this };
00912       }
00913 
00914       iterator
00915       insert(const_iterator __hint, value_type&& __obj)
00916       {
00917         __glibcxx_check_insert(__hint);
00918         size_type __bucket_count = this->bucket_count();
00919         auto __it = _Base::insert(__hint.base(), std::move(__obj));
00920         _M_check_rehashed(__bucket_count);
00921         return { __it, this };
00922       }
00923 
00924       void
00925       insert(std::initializer_list<value_type> __l)
00926       {
00927         size_type __bucket_count = this->bucket_count();
00928         _Base::insert(__l);
00929         _M_check_rehashed(__bucket_count);
00930       }
00931 
00932       template<typename _InputIterator>
00933         void
00934         insert(_InputIterator __first, _InputIterator __last)
00935         {
00936           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00937           __glibcxx_check_valid_range2(__first, __last, __dist);
00938           size_type __bucket_count = this->bucket_count();
00939 
00940           if (__dist.second >= __gnu_debug::__dp_sign)
00941             _Base::insert(__gnu_debug::__unsafe(__first),
00942                           __gnu_debug::__unsafe(__last));
00943           else
00944             _Base::insert(__first, __last);
00945 
00946           _M_check_rehashed(__bucket_count);
00947         }
00948 
00949 #if __cplusplus > 201402L
00950       using node_type = typename _Base::node_type;
00951 
00952       node_type
00953       extract(const_iterator __position)
00954       {
00955         __glibcxx_check_erase(__position);
00956         return _M_extract(__position.base());
00957       }
00958 
00959       node_type
00960       extract(const key_type& __key)
00961       {
00962         const auto __position = _Base::find(__key);
00963         if (__position != _Base::end())
00964           return _M_extract(__position);
00965         return {};
00966       }
00967 
00968       iterator
00969       insert(node_type&& __nh)
00970       { return { _Base::insert(std::move(__nh)), this }; }
00971 
00972       iterator
00973       insert(const_iterator __hint, node_type&& __nh)
00974       {
00975         __glibcxx_check_insert(__hint);
00976         return { _Base::insert(__hint.base(), std::move(__nh)), this };
00977       }
00978 
00979       using _Base::merge;
00980 #endif // C++17
00981 
00982       iterator
00983       find(const key_type& __key)
00984       { return { _Base::find(__key), this }; }
00985 
00986       const_iterator
00987       find(const key_type& __key) const
00988       { return { _Base::find(__key), this }; }
00989 
00990       std::pair<iterator, iterator>
00991       equal_range(const key_type& __key)
00992       {
00993         auto __res = _Base::equal_range(__key);
00994         return { { __res.first, this }, { __res.second, this } };
00995       }
00996 
00997       std::pair<const_iterator, const_iterator>
00998       equal_range(const key_type& __key) const
00999       {
01000         auto __res = _Base::equal_range(__key);
01001         return { { __res.first, this }, { __res.second, this } };
01002       }
01003 
01004       size_type
01005       erase(const key_type& __key)
01006       {
01007         size_type __ret(0);
01008         auto __pair = _Base::equal_range(__key);
01009         for (auto __victim = __pair.first; __victim != __pair.second;)
01010           {
01011             _M_invalidate(__victim);
01012             __victim = _Base::erase(__victim);
01013             ++__ret;
01014           }
01015 
01016         return __ret;
01017       }
01018 
01019       iterator
01020       erase(const_iterator __it)
01021       {
01022         __glibcxx_check_erase(__it);
01023         return { _M_erase(__it.base()), this };
01024       }
01025 
01026       iterator
01027       erase(iterator __it)
01028       {
01029         __glibcxx_check_erase(__it);
01030         return { _M_erase(__it.base()), this };
01031       }
01032 
01033       iterator
01034       erase(const_iterator __first, const_iterator __last)
01035       {
01036         __glibcxx_check_erase_range(__first, __last);
01037         for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
01038           {
01039             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
01040                                   _M_message(__gnu_debug::__msg_valid_range)
01041                                   ._M_iterator(__first, "first")
01042                                   ._M_iterator(__last, "last"));
01043             _M_invalidate(__tmp);
01044           }
01045         return { _Base::erase(__first.base(), __last.base()), this };
01046       }
01047 
01048       _Base&
01049       _M_base() noexcept        { return *this; }
01050 
01051       const _Base&
01052       _M_base() const noexcept  { return *this; }
01053 
01054     private:
01055       void
01056       _M_check_rehashed(size_type __prev_count)
01057       {
01058         if (__prev_count != this->bucket_count())
01059           this->_M_invalidate_all();
01060       }
01061 
01062       void
01063       _M_invalidate(_Base_const_iterator __victim)
01064       {
01065         this->_M_invalidate_if(
01066           [__victim](_Base_const_iterator __it) { return __it == __victim; });
01067         this->_M_invalidate_local_if(
01068           [__victim](_Base_const_local_iterator __it)
01069           { return __it._M_curr() == __victim._M_cur; });
01070       }
01071 
01072       _Base_iterator
01073       _M_erase(_Base_const_iterator __victim)
01074       {
01075         _M_invalidate(__victim);
01076         size_type __bucket_count = this->bucket_count();
01077         _Base_iterator __next = _Base::erase(__victim);
01078         _M_check_rehashed(__bucket_count);
01079         return __next;
01080       }
01081 
01082 #if __cplusplus > 201402L
01083       node_type
01084       _M_extract(_Base_const_iterator __victim)
01085       {
01086         _M_invalidate(__victim);
01087         return _Base::extract(__victim);
01088       }
01089 #endif
01090     };
01091 
01092 #if __cpp_deduction_guides >= 201606
01093 
01094   template<typename _InputIterator,
01095            typename _Hash =
01096              hash<typename iterator_traits<_InputIterator>::value_type>,
01097            typename _Pred =
01098              equal_to<typename iterator_traits<_InputIterator>::value_type>,
01099            typename _Allocator =
01100              allocator<typename iterator_traits<_InputIterator>::value_type>,
01101            typename = _RequireInputIter<_InputIterator>,
01102            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01103            typename = _RequireNotAllocator<_Pred>,
01104            typename = _RequireAllocator<_Allocator>>
01105     unordered_multiset(_InputIterator, _InputIterator,
01106                        unordered_multiset<int>::size_type = {},
01107                        _Hash = _Hash(), _Pred = _Pred(),
01108                        _Allocator = _Allocator())
01109     -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
01110                           _Hash, _Pred, _Allocator>;
01111 
01112   template<typename _Tp, typename _Hash = hash<_Tp>,
01113            typename _Pred = equal_to<_Tp>,
01114            typename _Allocator = allocator<_Tp>,
01115            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01116            typename = _RequireNotAllocator<_Pred>,
01117            typename = _RequireAllocator<_Allocator>>
01118     unordered_multiset(initializer_list<_Tp>,
01119                        unordered_multiset<int>::size_type = {},
01120                        _Hash = _Hash(), _Pred = _Pred(),
01121                        _Allocator = _Allocator())
01122     -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
01123 
01124   template<typename _InputIterator, typename _Allocator,
01125            typename = _RequireInputIter<_InputIterator>,
01126            typename = _RequireAllocator<_Allocator>>
01127     unordered_multiset(_InputIterator, _InputIterator,
01128                        unordered_multiset<int>::size_type, _Allocator)
01129     -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
01130                           hash<typename
01131                                iterator_traits<_InputIterator>::value_type>,
01132                           equal_to<typename
01133                                    iterator_traits<_InputIterator>::value_type>,
01134                           _Allocator>;
01135 
01136   template<typename _InputIterator, typename _Hash, typename _Allocator,
01137            typename = _RequireInputIter<_InputIterator>,
01138            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01139            typename = _RequireAllocator<_Allocator>>
01140     unordered_multiset(_InputIterator, _InputIterator,
01141                        unordered_multiset<int>::size_type,
01142                        _Hash, _Allocator)
01143     -> unordered_multiset<typename
01144                           iterator_traits<_InputIterator>::value_type,
01145                           _Hash,
01146                           equal_to<
01147                             typename
01148                             iterator_traits<_InputIterator>::value_type>,
01149                           _Allocator>;
01150 
01151   template<typename _Tp, typename _Allocator,
01152            typename = _RequireAllocator<_Allocator>>
01153     unordered_multiset(initializer_list<_Tp>,
01154                        unordered_multiset<int>::size_type, _Allocator)
01155     -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
01156 
01157   template<typename _Tp, typename _Hash, typename _Allocator,
01158            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01159            typename = _RequireAllocator<_Allocator>>
01160     unordered_multiset(initializer_list<_Tp>,
01161                        unordered_multiset<int>::size_type, _Hash, _Allocator)
01162     -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
01163 
01164 #endif
01165 
01166   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
01167     inline void
01168     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01169          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01170     noexcept(noexcept(__x.swap(__y)))
01171     { __x.swap(__y); }
01172 
01173   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
01174     inline bool
01175     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01176                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01177     { return __x._M_base() == __y._M_base(); }
01178 
01179   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
01180     inline bool
01181     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01182                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01183     { return !(__x == __y); }
01184 
01185 } // namespace __debug
01186 } // namespace std
01187 
01188 #endif // C++11
01189 
01190 #endif