libstdc++
unordered_set
Go to the documentation of this file.
00001 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2018 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       using insert_return_type = _Node_insert_return<iterator, node_type>;
00376 
00377       node_type
00378       extract(const_iterator __position)
00379       {
00380         __glibcxx_check_erase(__position);
00381         _Base_const_iterator __victim = __position.base();
00382         this->_M_invalidate_if(
00383             [__victim](_Base_const_iterator __it) { return __it == __victim; }
00384             );
00385         this->_M_invalidate_local_if(
00386             [__victim](_Base_const_local_iterator __it) {
00387                 return __it._M_curr() == __victim._M_cur;
00388             });
00389         return _Base::extract(__position.base());
00390       }
00391 
00392       node_type
00393       extract(const key_type& __key)
00394       {
00395         const auto __position = find(__key);
00396         if (__position != end())
00397           return extract(__position);
00398         return {};
00399       }
00400 
00401       insert_return_type
00402       insert(node_type&& __nh)
00403       {
00404         auto __ret = _Base::insert(std::move(__nh));
00405         iterator __pos = iterator(__ret.position, this);
00406         return { __pos, __ret.inserted, std::move(__ret.node) };
00407       }
00408 
00409       iterator
00410       insert(const_iterator __hint, node_type&& __nh)
00411       {
00412         __glibcxx_check_insert(__hint);
00413         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
00414       }
00415 
00416       using _Base::merge;
00417 #endif // C++17
00418 
00419       iterator
00420       find(const key_type& __key)
00421       { return iterator(_Base::find(__key), this); }
00422 
00423       const_iterator
00424       find(const key_type& __key) const
00425       { return const_iterator(_Base::find(__key), this); }
00426 
00427       std::pair<iterator, iterator>
00428       equal_range(const key_type& __key)
00429       {
00430         std::pair<_Base_iterator, _Base_iterator> __res
00431           = _Base::equal_range(__key);
00432         return std::make_pair(iterator(__res.first, this),
00433                               iterator(__res.second, this));
00434       }
00435 
00436       std::pair<const_iterator, const_iterator>
00437       equal_range(const key_type& __key) const
00438       {
00439         std::pair<_Base_const_iterator, _Base_const_iterator>
00440           __res = _Base::equal_range(__key);
00441         return std::make_pair(const_iterator(__res.first, this),
00442                               const_iterator(__res.second, this));
00443       }
00444 
00445       size_type
00446       erase(const key_type& __key)
00447       {
00448         size_type __ret(0);
00449         _Base_iterator __victim(_Base::find(__key));
00450         if (__victim != _Base::end())
00451           {
00452             this->_M_invalidate_if(
00453                             [__victim](_Base_const_iterator __it)
00454                             { return __it == __victim; });
00455             this->_M_invalidate_local_if(
00456                             [__victim](_Base_const_local_iterator __it)
00457                             { return __it._M_curr() == __victim._M_cur; });
00458             size_type __bucket_count = this->bucket_count();
00459             _Base::erase(__victim);
00460             _M_check_rehashed(__bucket_count);
00461             __ret = 1;
00462           }
00463         return __ret;
00464       }
00465 
00466       iterator
00467       erase(const_iterator __it)
00468       {
00469         __glibcxx_check_erase(__it);
00470         _Base_const_iterator __victim = __it.base();
00471         this->_M_invalidate_if(
00472                         [__victim](_Base_const_iterator __it)
00473                         { return __it == __victim; });
00474         this->_M_invalidate_local_if(
00475                         [__victim](_Base_const_local_iterator __it)
00476                         { return __it._M_curr() == __victim._M_cur; });
00477         size_type __bucket_count = this->bucket_count();
00478         _Base_iterator __next = _Base::erase(__it.base());
00479         _M_check_rehashed(__bucket_count);
00480         return iterator(__next, this);
00481       }
00482 
00483       iterator
00484       erase(iterator __it)
00485       { return erase(const_iterator(__it)); }
00486 
00487       iterator
00488       erase(const_iterator __first, const_iterator __last)
00489       {
00490         __glibcxx_check_erase_range(__first, __last);
00491         for (_Base_const_iterator __tmp = __first.base();
00492              __tmp != __last.base(); ++__tmp)
00493           {
00494             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00495                                   _M_message(__gnu_debug::__msg_valid_range)
00496                                   ._M_iterator(__first, "first")
00497                                   ._M_iterator(__last, "last"));
00498             this->_M_invalidate_if(
00499                             [__tmp](_Base_const_iterator __it)
00500                             { return __it == __tmp; });
00501             this->_M_invalidate_local_if(
00502                             [__tmp](_Base_const_local_iterator __it)
00503                             { return __it._M_curr() == __tmp._M_cur; });
00504           }
00505         size_type __bucket_count = this->bucket_count();
00506         _Base_iterator __next = _Base::erase(__first.base(),
00507                                              __last.base());
00508         _M_check_rehashed(__bucket_count);
00509         return iterator(__next, this);
00510       }
00511 
00512       _Base&
00513       _M_base() noexcept { return *this; }
00514 
00515       const _Base&
00516       _M_base() const noexcept { return *this; }
00517 
00518     private:
00519       void
00520       _M_check_rehashed(size_type __prev_count)
00521       {
00522         if (__prev_count != this->bucket_count())
00523           this->_M_invalidate_locals();
00524       }
00525     };
00526 
00527 #if __cpp_deduction_guides >= 201606
00528 
00529   template<typename _InputIterator,
00530            typename _Hash =
00531            hash<typename iterator_traits<_InputIterator>::value_type>,
00532            typename _Pred =
00533            equal_to<typename iterator_traits<_InputIterator>::value_type>,
00534            typename _Allocator =
00535            allocator<typename iterator_traits<_InputIterator>::value_type>,
00536            typename = _RequireInputIter<_InputIterator>,
00537            typename = _RequireAllocator<_Allocator>>
00538     unordered_set(_InputIterator, _InputIterator,
00539                   unordered_set<int>::size_type = {},
00540                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
00541     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
00542                      _Hash, _Pred, _Allocator>;
00543 
00544   template<typename _Tp, typename _Hash = hash<_Tp>,
00545            typename _Pred = equal_to<_Tp>,
00546            typename _Allocator = allocator<_Tp>,
00547            typename = _RequireAllocator<_Allocator>>
00548     unordered_set(initializer_list<_Tp>,
00549                   unordered_set<int>::size_type = {},
00550                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
00551     -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
00552 
00553   template<typename _InputIterator, typename _Allocator,
00554            typename = _RequireInputIter<_InputIterator>,
00555            typename = _RequireAllocator<_Allocator>>
00556     unordered_set(_InputIterator, _InputIterator,
00557                   unordered_set<int>::size_type, _Allocator)
00558     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
00559                      hash<
00560                        typename iterator_traits<_InputIterator>::value_type>,
00561                      equal_to<
00562                        typename iterator_traits<_InputIterator>::value_type>,
00563                      _Allocator>;
00564 
00565   template<typename _InputIterator, typename _Hash, typename _Allocator,
00566            typename = _RequireInputIter<_InputIterator>,
00567            typename = _RequireAllocator<_Allocator>>
00568     unordered_set(_InputIterator, _InputIterator,
00569                   unordered_set<int>::size_type,
00570                   _Hash, _Allocator)
00571     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
00572                      _Hash,
00573                      equal_to<
00574                        typename iterator_traits<_InputIterator>::value_type>,
00575                      _Allocator>;
00576 
00577   template<typename _Tp, typename _Allocator,
00578            typename = _RequireAllocator<_Allocator>>
00579     unordered_set(initializer_list<_Tp>,
00580                   unordered_set<int>::size_type, _Allocator)
00581     -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
00582 
00583   template<typename _Tp, typename _Hash, typename _Allocator,
00584            typename = _RequireAllocator<_Allocator>>
00585     unordered_set(initializer_list<_Tp>,
00586                   unordered_set<int>::size_type, _Hash, _Allocator)
00587     -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
00588 
00589 #endif
00590 
00591   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00592     inline void
00593     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00594          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00595     noexcept(noexcept(__x.swap(__y)))
00596     { __x.swap(__y); }
00597 
00598   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00599     inline bool
00600     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00601                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00602     { return __x._M_base() == __y._M_base(); }
00603 
00604   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00605     inline bool
00606     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00607                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00608     { return !(__x == __y); }
00609 
00610 
00611   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
00612   template<typename _Value,
00613            typename _Hash = std::hash<_Value>,
00614            typename _Pred = std::equal_to<_Value>,
00615            typename _Alloc = std::allocator<_Value> >
00616     class unordered_multiset
00617     : public __gnu_debug::_Safe_container<
00618         unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
00619         __gnu_debug::_Safe_unordered_container>,
00620       public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
00621     {
00622       typedef _GLIBCXX_STD_C::unordered_multiset<
00623         _Value, _Hash, _Pred, _Alloc>                           _Base;
00624       typedef __gnu_debug::_Safe_container<unordered_multiset,
00625         _Alloc, __gnu_debug::_Safe_unordered_container>         _Safe;
00626       typedef typename _Base::const_iterator    _Base_const_iterator;
00627       typedef typename _Base::iterator          _Base_iterator;
00628       typedef typename _Base::const_local_iterator
00629                                                 _Base_const_local_iterator;
00630       typedef typename _Base::local_iterator    _Base_local_iterator;
00631 
00632     public:
00633       typedef typename _Base::size_type                 size_type;
00634       typedef typename _Base::hasher                    hasher;
00635       typedef typename _Base::key_equal                 key_equal;
00636       typedef typename _Base::allocator_type            allocator_type;
00637 
00638       typedef typename _Base::key_type                  key_type;
00639       typedef typename _Base::value_type                value_type;
00640 
00641       typedef __gnu_debug::_Safe_iterator<
00642         _Base_iterator, unordered_multiset>             iterator;
00643       typedef __gnu_debug::_Safe_iterator<
00644         _Base_const_iterator, unordered_multiset>       const_iterator;
00645       typedef __gnu_debug::_Safe_local_iterator<
00646         _Base_local_iterator, unordered_multiset>       local_iterator;
00647       typedef __gnu_debug::_Safe_local_iterator<
00648         _Base_const_local_iterator, unordered_multiset> const_local_iterator;
00649 
00650       unordered_multiset() = default;
00651 
00652       explicit
00653       unordered_multiset(size_type __n,
00654                          const hasher& __hf = hasher(),
00655                          const key_equal& __eql = key_equal(),
00656                          const allocator_type& __a = allocator_type())
00657       : _Base(__n, __hf, __eql, __a) { }
00658 
00659       template<typename _InputIterator>
00660         unordered_multiset(_InputIterator __first, _InputIterator __last,
00661                            size_type __n = 0,
00662                            const hasher& __hf = hasher(),
00663                            const key_equal& __eql = key_equal(),
00664                            const allocator_type& __a = allocator_type())
00665         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00666                                                                      __last)),
00667                 __gnu_debug::__base(__last), __n,
00668                 __hf, __eql, __a) { }
00669 
00670       unordered_multiset(const unordered_multiset&) = default;
00671 
00672       unordered_multiset(const _Base& __x)
00673       : _Base(__x) { }
00674 
00675       unordered_multiset(unordered_multiset&&) = default;
00676 
00677       explicit
00678       unordered_multiset(const allocator_type& __a)
00679       : _Base(__a) { }
00680 
00681       unordered_multiset(const unordered_multiset& __uset,
00682                          const allocator_type& __a)
00683       : _Base(__uset, __a) { }
00684 
00685       unordered_multiset(unordered_multiset&& __uset,
00686                          const allocator_type& __a)
00687       : _Safe(std::move(__uset._M_safe()), __a),
00688         _Base(std::move(__uset._M_base()), __a) { }
00689 
00690       unordered_multiset(initializer_list<value_type> __l,
00691                          size_type __n = 0,
00692                          const hasher& __hf = hasher(),
00693                          const key_equal& __eql = key_equal(),
00694                          const allocator_type& __a = allocator_type())
00695       : _Base(__l, __n, __hf, __eql, __a) { }
00696 
00697       unordered_multiset(size_type __n, const allocator_type& __a)
00698         : unordered_multiset(__n, hasher(), key_equal(), __a)
00699       { }
00700 
00701       unordered_multiset(size_type __n, const hasher& __hf,
00702                          const allocator_type& __a)
00703         : unordered_multiset(__n, __hf, key_equal(), __a)
00704       { }
00705 
00706       template<typename _InputIterator>
00707         unordered_multiset(_InputIterator __first, _InputIterator __last,
00708                            size_type __n,
00709                            const allocator_type& __a)
00710           : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
00711         { }
00712 
00713       template<typename _InputIterator>
00714         unordered_multiset(_InputIterator __first, _InputIterator __last,
00715                            size_type __n, const hasher& __hf,
00716                            const allocator_type& __a)
00717           : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
00718         { }
00719 
00720       unordered_multiset(initializer_list<value_type> __l,
00721                          size_type __n,
00722                          const allocator_type& __a)
00723         : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
00724       { }
00725 
00726       unordered_multiset(initializer_list<value_type> __l,
00727                          size_type __n, const hasher& __hf,
00728                          const allocator_type& __a)
00729         : unordered_multiset(__l, __n, __hf, key_equal(), __a)
00730       { }
00731 
00732       ~unordered_multiset() = default;
00733 
00734       unordered_multiset&
00735       operator=(const unordered_multiset&) = default;
00736 
00737       unordered_multiset&
00738       operator=(unordered_multiset&&) = default;
00739 
00740       unordered_multiset&
00741       operator=(initializer_list<value_type> __l)
00742       {
00743         this->_M_base() = __l;
00744         this->_M_invalidate_all();
00745         return *this;
00746       }
00747 
00748       void
00749       swap(unordered_multiset& __x)
00750         noexcept( noexcept(declval<_Base&>().swap(__x)) )
00751       {
00752         _Safe::_M_swap(__x);
00753         _Base::swap(__x);
00754       }
00755 
00756       void
00757       clear() noexcept
00758       {
00759         _Base::clear();
00760         this->_M_invalidate_all();
00761       }
00762 
00763       iterator
00764       begin() noexcept
00765       { return iterator(_Base::begin(), this); }
00766 
00767       const_iterator
00768       begin() const noexcept
00769       { return const_iterator(_Base::begin(), this); }
00770 
00771       iterator
00772       end() noexcept
00773       { return iterator(_Base::end(), this); }
00774 
00775       const_iterator
00776       end() const noexcept
00777       { return const_iterator(_Base::end(), this); }
00778 
00779       const_iterator
00780       cbegin() const noexcept
00781       { return const_iterator(_Base::begin(), this); }
00782 
00783       const_iterator
00784       cend() const noexcept
00785       { return const_iterator(_Base::end(), this); }
00786 
00787       // local versions
00788       local_iterator
00789       begin(size_type __b)
00790       {
00791         __glibcxx_check_bucket_index(__b);
00792         return local_iterator(_Base::begin(__b), this);
00793       }
00794 
00795       local_iterator
00796       end(size_type __b)
00797       {
00798         __glibcxx_check_bucket_index(__b);
00799         return local_iterator(_Base::end(__b), this);
00800       }
00801 
00802       const_local_iterator
00803       begin(size_type __b) const
00804       {
00805         __glibcxx_check_bucket_index(__b);
00806         return const_local_iterator(_Base::begin(__b), this);
00807       }
00808 
00809       const_local_iterator
00810       end(size_type __b) const
00811       {
00812         __glibcxx_check_bucket_index(__b);
00813         return const_local_iterator(_Base::end(__b), this);
00814       }
00815 
00816       const_local_iterator
00817       cbegin(size_type __b) const
00818       {
00819         __glibcxx_check_bucket_index(__b);
00820         return const_local_iterator(_Base::cbegin(__b), this);
00821       }
00822 
00823       const_local_iterator
00824       cend(size_type __b) const
00825       {
00826         __glibcxx_check_bucket_index(__b);
00827         return const_local_iterator(_Base::cend(__b), this);
00828       }
00829 
00830       size_type
00831       bucket_size(size_type __b) const
00832       {
00833         __glibcxx_check_bucket_index(__b);
00834         return _Base::bucket_size(__b);
00835       }
00836 
00837       float
00838       max_load_factor() const noexcept
00839       { return _Base::max_load_factor(); }
00840 
00841       void
00842       max_load_factor(float __f)
00843       {
00844         __glibcxx_check_max_load_factor(__f);
00845         _Base::max_load_factor(__f);
00846       }
00847 
00848       template<typename... _Args>
00849         iterator
00850         emplace(_Args&&... __args)
00851         {
00852           size_type __bucket_count = this->bucket_count();
00853           _Base_iterator __it
00854             = _Base::emplace(std::forward<_Args>(__args)...);
00855           _M_check_rehashed(__bucket_count);
00856           return iterator(__it, this);
00857         }
00858 
00859       template<typename... _Args>
00860         iterator
00861         emplace_hint(const_iterator __hint, _Args&&... __args)
00862         {
00863           __glibcxx_check_insert(__hint);
00864           size_type __bucket_count = this->bucket_count();
00865           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
00866                                         std::forward<_Args>(__args)...);
00867           _M_check_rehashed(__bucket_count);
00868           return iterator(__it, this);
00869         }
00870 
00871       iterator
00872       insert(const value_type& __obj)
00873       {
00874         size_type __bucket_count = this->bucket_count();
00875         _Base_iterator __it = _Base::insert(__obj);
00876         _M_check_rehashed(__bucket_count);
00877         return iterator(__it, this);
00878       }
00879 
00880       iterator
00881       insert(const_iterator __hint, const value_type& __obj)
00882       {
00883         __glibcxx_check_insert(__hint);
00884         size_type __bucket_count = this->bucket_count();
00885         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
00886         _M_check_rehashed(__bucket_count);
00887         return iterator(__it, this);
00888       }
00889 
00890       iterator
00891       insert(value_type&& __obj)
00892       {
00893         size_type __bucket_count = this->bucket_count();
00894         _Base_iterator __it = _Base::insert(std::move(__obj));
00895         _M_check_rehashed(__bucket_count);
00896         return iterator(__it, this);
00897       }
00898 
00899       iterator
00900       insert(const_iterator __hint, value_type&& __obj)
00901       {
00902         __glibcxx_check_insert(__hint);
00903         size_type __bucket_count = this->bucket_count();
00904         _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
00905         _M_check_rehashed(__bucket_count);
00906         return iterator(__it, this);
00907       }
00908 
00909       void
00910       insert(std::initializer_list<value_type> __l)
00911       {
00912         size_type __bucket_count = this->bucket_count();
00913         _Base::insert(__l);
00914         _M_check_rehashed(__bucket_count);
00915       }
00916 
00917       template<typename _InputIterator>
00918         void
00919         insert(_InputIterator __first, _InputIterator __last)
00920         {
00921           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00922           __glibcxx_check_valid_range2(__first, __last, __dist);
00923           size_type __bucket_count = this->bucket_count();
00924 
00925           if (__dist.second >= __gnu_debug::__dp_sign)
00926             _Base::insert(__gnu_debug::__unsafe(__first),
00927                           __gnu_debug::__unsafe(__last));
00928           else
00929             _Base::insert(__first, __last);
00930 
00931           _M_check_rehashed(__bucket_count);
00932         }
00933 
00934 #if __cplusplus > 201402L
00935       using node_type = typename _Base::node_type;
00936 
00937       node_type
00938       extract(const_iterator __position)
00939       {
00940         __glibcxx_check_erase(__position);
00941         _Base_const_iterator __victim = __position.base();
00942         this->_M_invalidate_if(
00943             [__victim](_Base_const_iterator __it) { return __it == __victim; }
00944             );
00945         this->_M_invalidate_local_if(
00946             [__victim](_Base_const_local_iterator __it) {
00947                 return __it._M_curr() == __victim._M_cur;
00948             });
00949         return _Base::extract(__position.base());
00950       }
00951 
00952       node_type
00953       extract(const key_type& __key)
00954       {
00955         const auto __position = find(__key);
00956         if (__position != end())
00957           return extract(__position);
00958         return {};
00959       }
00960 
00961       iterator
00962       insert(node_type&& __nh)
00963       { return iterator(_Base::insert(std::move(__nh)), this); }
00964 
00965       iterator
00966       insert(const_iterator __hint, node_type&& __nh)
00967       {
00968         __glibcxx_check_insert(__hint);
00969         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
00970       }
00971 
00972       using _Base::merge;
00973 #endif // C++17
00974 
00975       iterator
00976       find(const key_type& __key)
00977       { return iterator(_Base::find(__key), this); }
00978 
00979       const_iterator
00980       find(const key_type& __key) const
00981       { return const_iterator(_Base::find(__key), this); }
00982 
00983       std::pair<iterator, iterator>
00984       equal_range(const key_type& __key)
00985       {
00986         std::pair<_Base_iterator, _Base_iterator> __res
00987           = _Base::equal_range(__key);
00988         return std::make_pair(iterator(__res.first, this),
00989                               iterator(__res.second, this));
00990       }
00991 
00992       std::pair<const_iterator, const_iterator>
00993       equal_range(const key_type& __key) const
00994       {
00995         std::pair<_Base_const_iterator, _Base_const_iterator>
00996           __res = _Base::equal_range(__key);
00997         return std::make_pair(const_iterator(__res.first, this),
00998                               const_iterator(__res.second, this));
00999       }
01000 
01001       size_type
01002       erase(const key_type& __key)
01003       {
01004         size_type __ret(0);
01005         std::pair<_Base_iterator, _Base_iterator> __pair =
01006           _Base::equal_range(__key);
01007         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
01008           {
01009             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
01010                             { return __it == __victim; });
01011             this->_M_invalidate_local_if(
01012                             [__victim](_Base_const_local_iterator __it)
01013                             { return __it._M_curr() == __victim._M_cur; });
01014             _Base::erase(__victim++);
01015             ++__ret;
01016           }
01017         return __ret;
01018       }
01019 
01020       iterator
01021       erase(const_iterator __it)
01022       {
01023         __glibcxx_check_erase(__it);
01024         _Base_const_iterator __victim = __it.base();
01025         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
01026                         { return __it == __victim; });
01027         this->_M_invalidate_local_if(
01028                         [__victim](_Base_const_local_iterator __it)
01029                         { return __it._M_curr() == __victim._M_cur; });
01030         return iterator(_Base::erase(__it.base()), this);
01031       }
01032 
01033       iterator
01034       erase(iterator __it)
01035       { return erase(const_iterator(__it)); }
01036 
01037       iterator
01038       erase(const_iterator __first, const_iterator __last)
01039       {
01040         __glibcxx_check_erase_range(__first, __last);
01041         for (_Base_const_iterator __tmp = __first.base();
01042              __tmp != __last.base(); ++__tmp)
01043           {
01044             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
01045                                   _M_message(__gnu_debug::__msg_valid_range)
01046                                   ._M_iterator(__first, "first")
01047                                   ._M_iterator(__last, "last"));
01048             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
01049                             { return __it == __tmp; });
01050             this->_M_invalidate_local_if(
01051                             [__tmp](_Base_const_local_iterator __it)
01052                             { return __it._M_curr() == __tmp._M_cur; });
01053           }
01054         return iterator(_Base::erase(__first.base(),
01055                                      __last.base()), this);
01056       }
01057 
01058       _Base&
01059       _M_base() noexcept        { return *this; }
01060 
01061       const _Base&
01062       _M_base() const noexcept  { return *this; }
01063 
01064     private:
01065       void
01066       _M_check_rehashed(size_type __prev_count)
01067       {
01068         if (__prev_count != this->bucket_count())
01069           this->_M_invalidate_locals();
01070       }
01071     };
01072 
01073 #if __cpp_deduction_guides >= 201606
01074 
01075   template<typename _InputIterator,
01076            typename _Hash =
01077            hash<typename iterator_traits<_InputIterator>::value_type>,
01078            typename _Pred =
01079            equal_to<typename iterator_traits<_InputIterator>::value_type>,
01080            typename _Allocator =
01081            allocator<typename iterator_traits<_InputIterator>::value_type>,
01082            typename = _RequireInputIter<_InputIterator>,
01083            typename = _RequireAllocator<_Allocator>>
01084     unordered_multiset(_InputIterator, _InputIterator,
01085                        unordered_multiset<int>::size_type = {},
01086                        _Hash = _Hash(), _Pred = _Pred(),
01087                        _Allocator = _Allocator())
01088     -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
01089                           _Hash, _Pred, _Allocator>;
01090 
01091   template<typename _Tp, typename _Hash = hash<_Tp>,
01092            typename _Pred = equal_to<_Tp>,
01093            typename _Allocator = allocator<_Tp>,
01094            typename = _RequireAllocator<_Allocator>>
01095     unordered_multiset(initializer_list<_Tp>,
01096                        unordered_multiset<int>::size_type = {},
01097                        _Hash = _Hash(), _Pred = _Pred(),
01098                        _Allocator = _Allocator())
01099     -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
01100 
01101   template<typename _InputIterator, typename _Allocator,
01102            typename = _RequireInputIter<_InputIterator>,
01103            typename = _RequireAllocator<_Allocator>>
01104     unordered_multiset(_InputIterator, _InputIterator,
01105                        unordered_multiset<int>::size_type, _Allocator)
01106     -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
01107                           hash<typename
01108                                iterator_traits<_InputIterator>::value_type>,
01109                           equal_to<typename
01110                                    iterator_traits<_InputIterator>::value_type>,
01111                           _Allocator>;
01112 
01113   template<typename _InputIterator, typename _Hash, typename _Allocator,
01114            typename = _RequireInputIter<_InputIterator>,
01115            typename = _RequireAllocator<_Allocator>>
01116     unordered_multiset(_InputIterator, _InputIterator,
01117                        unordered_multiset<int>::size_type,
01118                        _Hash, _Allocator)
01119     -> unordered_multiset<typename
01120                           iterator_traits<_InputIterator>::value_type,
01121                           _Hash,
01122                           equal_to<
01123                             typename
01124                             iterator_traits<_InputIterator>::value_type>,
01125                           _Allocator>;
01126 
01127   template<typename _Tp, typename _Allocator,
01128            typename = _RequireAllocator<_Allocator>>
01129     unordered_multiset(initializer_list<_Tp>,
01130                        unordered_multiset<int>::size_type, _Allocator)
01131     -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
01132 
01133   template<typename _Tp, typename _Hash, typename _Allocator,
01134            typename = _RequireAllocator<_Allocator>>
01135     unordered_multiset(initializer_list<_Tp>,
01136                        unordered_multiset<int>::size_type, _Hash, _Allocator)
01137     -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
01138 
01139 #endif
01140 
01141   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
01142     inline void
01143     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01144          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01145     noexcept(noexcept(__x.swap(__y)))
01146     { __x.swap(__y); }
01147 
01148   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
01149     inline bool
01150     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01151                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01152     { return __x._M_base() == __y._M_base(); }
01153 
01154   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
01155     inline bool
01156     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01157                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01158     { return !(__x == __y); }
01159 
01160 } // namespace __debug
01161 } // namespace std
01162 
01163 #endif // C++11
01164 
01165 #endif