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