contrib/gcc-8.0/libstdc++-v3/include/debug/unordered_set

   1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2018 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file debug/unordered_set
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
  30 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
  31
  32 #pragma GCC system_header
  33
  34 #if __cplusplus < 201103L
  35 # include <bits/c++0x_warning.h>
  36 #else
  37 # include <unordered_set>
  38
  39 #include <debug/safe_unordered_container.h>
  40 #include <debug/safe_container.h>
  41 #include <debug/safe_iterator.h>
  42 #include <debug/safe_local_iterator.h>
  43
  44 namespace std _GLIBCXX_VISIBILITY(default)
  45 {
  46 namespace __debug
  47 {
  48   /// Class std::unordered_set with safety/checking/debug instrumentation.
  49   template<typename _Value,
  50            typename _Hash = std::hash<_Value>,
  51            typename _Pred = std::equal_to<_Value>,
  52            typename _Alloc = std::allocator<_Value> >
  53     class unordered_set
  54     : public __gnu_debug::_Safe_container<
  55         unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc,
  56         __gnu_debug::_Safe_unordered_container>,
  57       public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>
  58     {
  59       typedef _GLIBCXX_STD_C::unordered_set<
  60         _Value, _Hash, _Pred, _Alloc>                                   _Base;
  61       typedef __gnu_debug::_Safe_container<
  62         unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container>  _Safe;
  63
  64       typedef typename _Base::const_iterator       _Base_const_iterator;
  65       typedef typename _Base::iterator             _Base_iterator;
  66       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
  67       typedef typename _Base::local_iterator       _Base_local_iterator;
  68
  69     public:
  70       typedef typename _Base::size_type                 size_type;
  71       typedef typename _Base::hasher                    hasher;
  72       typedef typename _Base::key_equal                 key_equal;
  73       typedef typename _Base::allocator_type            allocator_type;
  74
  75       typedef typename _Base::key_type                  key_type;
  76       typedef typename _Base::value_type                value_type;
  77
  78       typedef __gnu_debug::_Safe_iterator<
  79         _Base_iterator, unordered_set>                  iterator;
  80       typedef __gnu_debug::_Safe_iterator<
  81         _Base_const_iterator, unordered_set>            const_iterator;
  82       typedef __gnu_debug::_Safe_local_iterator<
  83         _Base_local_iterator, unordered_set>            local_iterator;
  84       typedef __gnu_debug::_Safe_local_iterator<
  85         _Base_const_local_iterator, unordered_set>      const_local_iterator;
  86
  87       unordered_set() = default;
  88
  89       explicit
  90       unordered_set(size_type __n,
  91                     const hasher& __hf = hasher(),
  92                     const key_equal& __eql = key_equal(),
  93                     const allocator_type& __a = allocator_type())
  94       : _Base(__n, __hf, __eql, __a) { }
  95
  96       template<typename _InputIterator>
  97         unordered_set(_InputIterator __first, _InputIterator __last,
  98                       size_type __n = 0,
  99                       const hasher& __hf = hasher(),
 100                       const key_equal& __eql = key_equal(),
 101                       const allocator_type& __a = allocator_type())
 102         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 103                                                                      __last)),
 104                 __gnu_debug::__base(__last), __n,
 105                 __hf, __eql, __a) { }
 106
 107       unordered_set(const unordered_set&) = default;
 108
 109       unordered_set(const _Base& __x)
 110       : _Base(__x) { }
 111
 112       unordered_set(unordered_set&&) = default;
 113
 114       explicit
 115       unordered_set(const allocator_type& __a)
 116       : _Base(__a) { }
 117
 118       unordered_set(const unordered_set& __uset,
 119                     const allocator_type& __a)
 120       : _Base(__uset, __a) { }
 121
 122       unordered_set(unordered_set&& __uset,
 123                     const allocator_type& __a)
 124       : _Safe(std::move(__uset._M_safe()), __a),
 125         _Base(std::move(__uset._M_base()), __a) { }
 126
 127       unordered_set(initializer_list<value_type> __l,
 128                     size_type __n = 0,
 129                     const hasher& __hf = hasher(),
 130                     const key_equal& __eql = key_equal(),
 131                     const allocator_type& __a = allocator_type())
 132       : _Base(__l, __n, __hf, __eql, __a) { }
 133
 134       unordered_set(size_type __n, const allocator_type& __a)
 135         : unordered_set(__n, hasher(), key_equal(), __a)
 136       { }
 137
 138       unordered_set(size_type __n, const hasher& __hf,
 139                     const allocator_type& __a)
 140         : unordered_set(__n, __hf, key_equal(), __a)
 141       { }
 142
 143       template<typename _InputIterator>
 144         unordered_set(_InputIterator __first, _InputIterator __last,
 145                       size_type __n,
 146                       const allocator_type& __a)
 147           : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
 148         { }
 149
 150       template<typename _InputIterator>
 151         unordered_set(_InputIterator __first, _InputIterator __last,
 152                       size_type __n, const hasher& __hf,
 153                       const allocator_type& __a)
 154           : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
 155         { }
 156
 157       unordered_set(initializer_list<value_type> __l,
 158                     size_type __n,
 159                     const allocator_type& __a)
 160         : unordered_set(__l, __n, hasher(), key_equal(), __a)
 161       { }
 162
 163       unordered_set(initializer_list<value_type> __l,
 164                     size_type __n, const hasher& __hf,
 165                     const allocator_type& __a)
 166         : unordered_set(__l, __n, __hf, key_equal(), __a)
 167       { }
 168
 169       ~unordered_set() = default;
 170
 171       unordered_set&
 172       operator=(const unordered_set&) = default;
 173
 174       unordered_set&
 175       operator=(unordered_set&&) = default;
 176
 177       unordered_set&
 178       operator=(initializer_list<value_type> __l)
 179       {
 180         _M_base() = __l;
 181         this->_M_invalidate_all();
 182         return *this;
 183       }
 184
 185       void
 186       swap(unordered_set& __x)
 187         noexcept( noexcept(declval<_Base&>().swap(__x)) )
 188       {
 189         _Safe::_M_swap(__x);
 190         _Base::swap(__x);
 191       }
 192
 193       void
 194       clear() noexcept
 195       {
 196         _Base::clear();
 197         this->_M_invalidate_all();
 198       }
 199
 200       iterator
 201       begin() noexcept
 202       { return iterator(_Base::begin(), this); }
 203
 204       const_iterator
 205       begin() const noexcept
 206       { return const_iterator(_Base::begin(), this); }
 207
 208       iterator
 209       end() noexcept
 210       { return iterator(_Base::end(), this); }
 211
 212       const_iterator
 213       end() const noexcept
 214       { return const_iterator(_Base::end(), this); }
 215
 216       const_iterator
 217       cbegin() const noexcept
 218       { return const_iterator(_Base::begin(), this); }
 219
 220       const_iterator
 221       cend() const noexcept
 222       { return const_iterator(_Base::end(), this); }
 223
 224       // local versions
 225       local_iterator
 226       begin(size_type __b)
 227       {
 228         __glibcxx_check_bucket_index(__b);
 229         return local_iterator(_Base::begin(__b), this);
 230       }
 231
 232       local_iterator
 233       end(size_type __b)
 234       {
 235         __glibcxx_check_bucket_index(__b);
 236         return local_iterator(_Base::end(__b), this);
 237       }
 238
 239       const_local_iterator
 240       begin(size_type __b) const
 241       {
 242         __glibcxx_check_bucket_index(__b);
 243         return const_local_iterator(_Base::begin(__b), this);
 244       }
 245
 246       const_local_iterator
 247       end(size_type __b) const
 248       {
 249         __glibcxx_check_bucket_index(__b);
 250         return const_local_iterator(_Base::end(__b), this);
 251       }
 252
 253       const_local_iterator
 254       cbegin(size_type __b) const
 255       {
 256         __glibcxx_check_bucket_index(__b);
 257         return const_local_iterator(_Base::cbegin(__b), this);
 258       }
 259
 260       const_local_iterator
 261       cend(size_type __b) const
 262       {
 263         __glibcxx_check_bucket_index(__b);
 264         return const_local_iterator(_Base::cend(__b), this);
 265       }
 266
 267       size_type
 268       bucket_size(size_type __b) const
 269       {
 270         __glibcxx_check_bucket_index(__b);
 271         return _Base::bucket_size(__b);
 272       }
 273
 274       float
 275       max_load_factor() const noexcept
 276       { return _Base::max_load_factor(); }
 277
 278       void
 279       max_load_factor(float __f)
 280       {
 281         __glibcxx_check_max_load_factor(__f);
 282         _Base::max_load_factor(__f);
 283       }
 284
 285       template<typename... _Args>
 286         std::pair<iterator, bool>
 287         emplace(_Args&&... __args)
 288         {
 289           size_type __bucket_count = this->bucket_count();
 290           std::pair<_Base_iterator, bool> __res
 291             = _Base::emplace(std::forward<_Args>(__args)...);
 292           _M_check_rehashed(__bucket_count);
 293           return std::make_pair(iterator(__res.first, this), __res.second);
 294         }
 295
 296       template<typename... _Args>
 297         iterator
 298         emplace_hint(const_iterator __hint, _Args&&... __args)
 299         {
 300           __glibcxx_check_insert(__hint);
 301           size_type __bucket_count = this->bucket_count();
 302           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 303                                         std::forward<_Args>(__args)...);
 304           _M_check_rehashed(__bucket_count);
 305           return iterator(__it, this);
 306         }
 307
 308       std::pair<iterator, bool>
 309       insert(const value_type& __obj)
 310       {
 311         size_type __bucket_count = this->bucket_count();
 312         std::pair<_Base_iterator, bool> __res
 313           = _Base::insert(__obj);
 314         _M_check_rehashed(__bucket_count);
 315         return std::make_pair(iterator(__res.first, this), __res.second);
 316       }
 317
 318       iterator
 319       insert(const_iterator __hint, const value_type& __obj)
 320       {
 321         __glibcxx_check_insert(__hint);
 322         size_type __bucket_count = this->bucket_count();
 323         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 324         _M_check_rehashed(__bucket_count);
 325         return iterator(__it, this);
 326       }
 327
 328       std::pair<iterator, bool>
 329       insert(value_type&& __obj)
 330       {
 331         size_type __bucket_count = this->bucket_count();
 332         std::pair<_Base_iterator, bool> __res
 333           = _Base::insert(std::move(__obj));
 334         _M_check_rehashed(__bucket_count);
 335         return std::make_pair(iterator(__res.first, this), __res.second);
 336       }
 337
 338       iterator
 339       insert(const_iterator __hint, value_type&& __obj)
 340       {
 341         __glibcxx_check_insert(__hint);
 342         size_type __bucket_count = this->bucket_count();
 343         _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
 344         _M_check_rehashed(__bucket_count);
 345         return iterator(__it, this);
 346       }
 347
 348       void
 349       insert(std::initializer_list<value_type> __l)
 350       {
 351         size_type __bucket_count = this->bucket_count();
 352         _Base::insert(__l);
 353         _M_check_rehashed(__bucket_count);
 354       }
 355
 356       template<typename _InputIterator>
 357         void
 358         insert(_InputIterator __first, _InputIterator __last)
 359         {
 360           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 361           __glibcxx_check_valid_range2(__first, __last, __dist);
 362           size_type __bucket_count = this->bucket_count();
 363
 364           if (__dist.second >= __gnu_debug::__dp_sign)
 365             _Base::insert(__gnu_debug::__unsafe(__first),
 366                           __gnu_debug::__unsafe(__last));
 367           else
 368             _Base::insert(__first, __last);
 369
 370           _M_check_rehashed(__bucket_count);
 371         }
 372
 373 #if __cplusplus > 201402L
 374       using node_type = typename _Base::node_type;
 375       using insert_return_type = _Node_insert_return<iterator, node_type>;
 376
 377       node_type
 378       extract(const_iterator __position)
 379       {
 380         __glibcxx_check_erase(__position);
 381         _Base_const_iterator __victim = __position.base();
 382         this->_M_invalidate_if(
 383             [__victim](_Base_const_iterator __it) { return __it == __victim; }
 384             );
 385         this->_M_invalidate_local_if(
 386             [__victim](_Base_const_local_iterator __it) {
 387                 return __it._M_curr() == __victim._M_cur;
 388             });
 389         return _Base::extract(__position.base());
 390       }
 391
 392       node_type
 393       extract(const key_type& __key)
 394       {
 395         const auto __position = find(__key);
 396         if (__position != end())
 397           return extract(__position);
 398         return {};
 399       }
 400
 401       insert_return_type
 402       insert(node_type&& __nh)
 403       {
 404         auto __ret = _Base::insert(std::move(__nh));
 405         iterator __pos = iterator(__ret.position, this);
 406         return { __pos, __ret.inserted, std::move(__ret.node) };
 407       }
 408
 409       iterator
 410       insert(const_iterator __hint, node_type&& __nh)
 411       {
 412         __glibcxx_check_insert(__hint);
 413         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
 414       }
 415
 416       using _Base::merge;
 417 #endif // C++17
 418
 419       iterator
 420       find(const key_type& __key)
 421       { return iterator(_Base::find(__key), this); }
 422
 423       const_iterator
 424       find(const key_type& __key) const
 425       { return const_iterator(_Base::find(__key), this); }
 426
 427       std::pair<iterator, iterator>
 428       equal_range(const key_type& __key)
 429       {
 430         std::pair<_Base_iterator, _Base_iterator> __res
 431           = _Base::equal_range(__key);
 432         return std::make_pair(iterator(__res.first, this),
 433                               iterator(__res.second, this));
 434       }
 435
 436       std::pair<const_iterator, const_iterator>
 437       equal_range(const key_type& __key) const
 438       {
 439         std::pair<_Base_const_iterator, _Base_const_iterator>
 440           __res = _Base::equal_range(__key);
 441         return std::make_pair(const_iterator(__res.first, this),
 442                               const_iterator(__res.second, this));
 443       }
 444
 445       size_type
 446       erase(const key_type& __key)
 447       {
 448         size_type __ret(0);
 449         _Base_iterator __victim(_Base::find(__key));
 450         if (__victim != _Base::end())
 451           {
 452             this->_M_invalidate_if(
 453                             [__victim](_Base_const_iterator __it)
 454                             { return __it == __victim; });
 455             this->_M_invalidate_local_if(
 456                             [__victim](_Base_const_local_iterator __it)
 457                             { return __it._M_curr() == __victim._M_cur; });
 458             size_type __bucket_count = this->bucket_count();
 459             _Base::erase(__victim);
 460             _M_check_rehashed(__bucket_count);
 461             __ret = 1;
 462           }
 463         return __ret;
 464       }
 465
 466       iterator
 467       erase(const_iterator __it)
 468       {
 469         __glibcxx_check_erase(__it);
 470         _Base_const_iterator __victim = __it.base();
 471         this->_M_invalidate_if(
 472                         [__victim](_Base_const_iterator __it)
 473                         { return __it == __victim; });
 474         this->_M_invalidate_local_if(
 475                         [__victim](_Base_const_local_iterator __it)
 476                         { return __it._M_curr() == __victim._M_cur; });
 477         size_type __bucket_count = this->bucket_count();
 478         _Base_iterator __next = _Base::erase(__it.base());
 479         _M_check_rehashed(__bucket_count);
 480         return iterator(__next, this);
 481       }
 482
 483       iterator
 484       erase(iterator __it)
 485       { return erase(const_iterator(__it)); }
 486
 487       iterator
 488       erase(const_iterator __first, const_iterator __last)
 489       {
 490         __glibcxx_check_erase_range(__first, __last);
 491         for (_Base_const_iterator __tmp = __first.base();
 492              __tmp != __last.base(); ++__tmp)
 493           {
 494             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 495                                   _M_message(__gnu_debug::__msg_valid_range)
 496                                   ._M_iterator(__first, "first")
 497                                   ._M_iterator(__last, "last"));
 498             this->_M_invalidate_if(
 499                             [__tmp](_Base_const_iterator __it)
 500                             { return __it == __tmp; });
 501             this->_M_invalidate_local_if(
 502                             [__tmp](_Base_const_local_iterator __it)
 503                             { return __it._M_curr() == __tmp._M_cur; });
 504           }
 505         size_type __bucket_count = this->bucket_count();
 506         _Base_iterator __next = _Base::erase(__first.base(),
 507                                              __last.base());
 508         _M_check_rehashed(__bucket_count);
 509         return iterator(__next, this);
 510       }
 511
 512       _Base&
 513       _M_base() noexcept { return *this; }
 514
 515       const _Base&
 516       _M_base() const noexcept { return *this; }
 517
 518     private:
 519       void
 520       _M_check_rehashed(size_type __prev_count)
 521       {
 522         if (__prev_count != this->bucket_count())
 523           this->_M_invalidate_locals();
 524       }
 525     };
 526
 527 #if __cpp_deduction_guides >= 201606
 528
 529   template<typename _InputIterator,
 530            typename _Hash =
 531            hash<typename iterator_traits<_InputIterator>::value_type>,
 532            typename _Pred =
 533            equal_to<typename iterator_traits<_InputIterator>::value_type>,
 534            typename _Allocator =
 535            allocator<typename iterator_traits<_InputIterator>::value_type>,
 536            typename = _RequireInputIter<_InputIterator>,
 537            typename = _RequireAllocator<_Allocator>>
 538     unordered_set(_InputIterator, _InputIterator,
 539                   unordered_set<int>::size_type = {},
 540                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
 541     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
 542                      _Hash, _Pred, _Allocator>;
 543
 544   template<typename _Tp, typename _Hash = hash<_Tp>,
 545            typename _Pred = equal_to<_Tp>,
 546            typename _Allocator = allocator<_Tp>,
 547            typename = _RequireAllocator<_Allocator>>
 548     unordered_set(initializer_list<_Tp>,
 549                   unordered_set<int>::size_type = {},
 550                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
 551     -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
 552
 553   template<typename _InputIterator, typename _Allocator,
 554            typename = _RequireInputIter<_InputIterator>,
 555            typename = _RequireAllocator<_Allocator>>
 556     unordered_set(_InputIterator, _InputIterator,
 557                   unordered_set<int>::size_type, _Allocator)
 558     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
 559                      hash<
 560                        typename iterator_traits<_InputIterator>::value_type>,
 561                      equal_to<
 562                        typename iterator_traits<_InputIterator>::value_type>,
 563                      _Allocator>;
 564
 565   template<typename _InputIterator, typename _Hash, typename _Allocator,
 566            typename = _RequireInputIter<_InputIterator>,
 567            typename = _RequireAllocator<_Allocator>>
 568     unordered_set(_InputIterator, _InputIterator,
 569                   unordered_set<int>::size_type,
 570                   _Hash, _Allocator)
 571     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
 572                      _Hash,
 573                      equal_to<
 574                        typename iterator_traits<_InputIterator>::value_type>,
 575                      _Allocator>;
 576
 577   template<typename _Tp, typename _Allocator,
 578            typename = _RequireAllocator<_Allocator>>
 579     unordered_set(initializer_list<_Tp>,
 580                   unordered_set<int>::size_type, _Allocator)
 581     -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
 582
 583   template<typename _Tp, typename _Hash, typename _Allocator,
 584            typename = _RequireAllocator<_Allocator>>
 585     unordered_set(initializer_list<_Tp>,
 586                   unordered_set<int>::size_type, _Hash, _Allocator)
 587     -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
 588
 589 #endif
 590
 591   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 592     inline void
 593     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 594          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 595     noexcept(noexcept(__x.swap(__y)))
 596     { __x.swap(__y); }
 597
 598   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 599     inline bool
 600     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 601                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 602     { return __x._M_base() == __y._M_base(); }
 603
 604   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 605     inline bool
 606     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 607                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 608     { return !(__x == __y); }
 609
 610
 611   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
 612   template<typename _Value,
 613            typename _Hash = std::hash<_Value>,
 614            typename _Pred = std::equal_to<_Value>,
 615            typename _Alloc = std::allocator<_Value> >
 616     class unordered_multiset
 617     : public __gnu_debug::_Safe_container<
 618         unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
 619         __gnu_debug::_Safe_unordered_container>,
 620       public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
 621     {
 622       typedef _GLIBCXX_STD_C::unordered_multiset<
 623         _Value, _Hash, _Pred, _Alloc>                           _Base;
 624       typedef __gnu_debug::_Safe_container<unordered_multiset,
 625         _Alloc, __gnu_debug::_Safe_unordered_container>         _Safe;
 626       typedef typename _Base::const_iterator    _Base_const_iterator;
 627       typedef typename _Base::iterator          _Base_iterator;
 628       typedef typename _Base::const_local_iterator
 629                                                 _Base_const_local_iterator;
 630       typedef typename _Base::local_iterator    _Base_local_iterator;
 631
 632     public:
 633       typedef typename _Base::size_type                 size_type;
 634       typedef typename _Base::hasher                    hasher;
 635       typedef typename _Base::key_equal                 key_equal;
 636       typedef typename _Base::allocator_type            allocator_type;
 637
 638       typedef typename _Base::key_type                  key_type;
 639       typedef typename _Base::value_type                value_type;
 640
 641       typedef __gnu_debug::_Safe_iterator<
 642         _Base_iterator, unordered_multiset>             iterator;
 643       typedef __gnu_debug::_Safe_iterator<
 644         _Base_const_iterator, unordered_multiset>       const_iterator;
 645       typedef __gnu_debug::_Safe_local_iterator<
 646         _Base_local_iterator, unordered_multiset>       local_iterator;
 647       typedef __gnu_debug::_Safe_local_iterator<
 648         _Base_const_local_iterator, unordered_multiset> const_local_iterator;
 649
 650       unordered_multiset() = default;
 651
 652       explicit
 653       unordered_multiset(size_type __n,
 654                          const hasher& __hf = hasher(),
 655                          const key_equal& __eql = key_equal(),
 656                          const allocator_type& __a = allocator_type())
 657       : _Base(__n, __hf, __eql, __a) { }
 658
 659       template<typename _InputIterator>
 660         unordered_multiset(_InputIterator __first, _InputIterator __last,
 661                            size_type __n = 0,
 662                            const hasher& __hf = hasher(),
 663                            const key_equal& __eql = key_equal(),
 664                            const allocator_type& __a = allocator_type())
 665         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 666                                                                      __last)),
 667                 __gnu_debug::__base(__last), __n,
 668                 __hf, __eql, __a) { }
 669
 670       unordered_multiset(const unordered_multiset&) = default;
 671
 672       unordered_multiset(const _Base& __x)
 673       : _Base(__x) { }
 674
 675       unordered_multiset(unordered_multiset&&) = default;
 676
 677       explicit
 678       unordered_multiset(const allocator_type& __a)
 679       : _Base(__a) { }
 680
 681       unordered_multiset(const unordered_multiset& __uset,
 682                          const allocator_type& __a)
 683       : _Base(__uset, __a) { }
 684
 685       unordered_multiset(unordered_multiset&& __uset,
 686                          const allocator_type& __a)
 687       : _Safe(std::move(__uset._M_safe()), __a),
 688         _Base(std::move(__uset._M_base()), __a) { }
 689
 690       unordered_multiset(initializer_list<value_type> __l,
 691                          size_type __n = 0,
 692                          const hasher& __hf = hasher(),
 693                          const key_equal& __eql = key_equal(),
 694                          const allocator_type& __a = allocator_type())
 695       : _Base(__l, __n, __hf, __eql, __a) { }
 696
 697       unordered_multiset(size_type __n, const allocator_type& __a)
 698         : unordered_multiset(__n, hasher(), key_equal(), __a)
 699       { }
 700
 701       unordered_multiset(size_type __n, const hasher& __hf,
 702                          const allocator_type& __a)
 703         : unordered_multiset(__n, __hf, key_equal(), __a)
 704       { }
 705
 706       template<typename _InputIterator>
 707         unordered_multiset(_InputIterator __first, _InputIterator __last,
 708                            size_type __n,
 709                            const allocator_type& __a)
 710           : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
 711         { }
 712
 713       template<typename _InputIterator>
 714         unordered_multiset(_InputIterator __first, _InputIterator __last,
 715                            size_type __n, const hasher& __hf,
 716                            const allocator_type& __a)
 717           : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
 718         { }
 719
 720       unordered_multiset(initializer_list<value_type> __l,
 721                          size_type __n,
 722                          const allocator_type& __a)
 723         : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
 724       { }
 725
 726       unordered_multiset(initializer_list<value_type> __l,
 727                          size_type __n, const hasher& __hf,
 728                          const allocator_type& __a)
 729         : unordered_multiset(__l, __n, __hf, key_equal(), __a)
 730       { }
 731
 732       ~unordered_multiset() = default;
 733
 734       unordered_multiset&
 735       operator=(const unordered_multiset&) = default;
 736
 737       unordered_multiset&
 738       operator=(unordered_multiset&&) = default;
 739
 740       unordered_multiset&
 741       operator=(initializer_list<value_type> __l)
 742       {
 743         this->_M_base() = __l;
 744         this->_M_invalidate_all();
 745         return *this;
 746       }
 747
 748       void
 749       swap(unordered_multiset& __x)
 750         noexcept( noexcept(declval<_Base&>().swap(__x)) )
 751       {
 752         _Safe::_M_swap(__x);
 753         _Base::swap(__x);
 754       }
 755
 756       void
 757       clear() noexcept
 758       {
 759         _Base::clear();
 760         this->_M_invalidate_all();
 761       }
 762
 763       iterator
 764       begin() noexcept
 765       { return iterator(_Base::begin(), this); }
 766
 767       const_iterator
 768       begin() const noexcept
 769       { return const_iterator(_Base::begin(), this); }
 770
 771       iterator
 772       end() noexcept
 773       { return iterator(_Base::end(), this); }
 774
 775       const_iterator
 776       end() const noexcept
 777       { return const_iterator(_Base::end(), this); }
 778
 779       const_iterator
 780       cbegin() const noexcept
 781       { return const_iterator(_Base::begin(), this); }
 782
 783       const_iterator
 784       cend() const noexcept
 785       { return const_iterator(_Base::end(), this); }
 786
 787       // local versions
 788       local_iterator
 789       begin(size_type __b)
 790       {
 791         __glibcxx_check_bucket_index(__b);
 792         return local_iterator(_Base::begin(__b), this);
 793       }
 794
 795       local_iterator
 796       end(size_type __b)
 797       {
 798         __glibcxx_check_bucket_index(__b);
 799         return local_iterator(_Base::end(__b), this);
 800       }
 801
 802       const_local_iterator
 803       begin(size_type __b) const
 804       {
 805         __glibcxx_check_bucket_index(__b);
 806         return const_local_iterator(_Base::begin(__b), this);
 807       }
 808
 809       const_local_iterator
 810       end(size_type __b) const
 811       {
 812         __glibcxx_check_bucket_index(__b);
 813         return const_local_iterator(_Base::end(__b), this);
 814       }
 815
 816       const_local_iterator
 817       cbegin(size_type __b) const
 818       {
 819         __glibcxx_check_bucket_index(__b);
 820         return const_local_iterator(_Base::cbegin(__b), this);
 821       }
 822
 823       const_local_iterator
 824       cend(size_type __b) const
 825       {
 826         __glibcxx_check_bucket_index(__b);
 827         return const_local_iterator(_Base::cend(__b), this);
 828       }
 829
 830       size_type
 831       bucket_size(size_type __b) const
 832       {
 833         __glibcxx_check_bucket_index(__b);
 834         return _Base::bucket_size(__b);
 835       }
 836
 837       float
 838       max_load_factor() const noexcept
 839       { return _Base::max_load_factor(); }
 840
 841       void
 842       max_load_factor(float __f)
 843       {
 844         __glibcxx_check_max_load_factor(__f);
 845         _Base::max_load_factor(__f);
 846       }
 847
 848       template<typename... _Args>
 849         iterator
 850         emplace(_Args&&... __args)
 851         {
 852           size_type __bucket_count = this->bucket_count();
 853           _Base_iterator __it
 854             = _Base::emplace(std::forward<_Args>(__args)...);
 855           _M_check_rehashed(__bucket_count);
 856           return iterator(__it, this);
 857         }
 858
 859       template<typename... _Args>
 860         iterator
 861         emplace_hint(const_iterator __hint, _Args&&... __args)
 862         {
 863           __glibcxx_check_insert(__hint);
 864           size_type __bucket_count = this->bucket_count();
 865           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 866                                         std::forward<_Args>(__args)...);
 867           _M_check_rehashed(__bucket_count);
 868           return iterator(__it, this);
 869         }
 870
 871       iterator
 872       insert(const value_type& __obj)
 873       {
 874         size_type __bucket_count = this->bucket_count();
 875         _Base_iterator __it = _Base::insert(__obj);
 876         _M_check_rehashed(__bucket_count);
 877         return iterator(__it, this);
 878       }
 879
 880       iterator
 881       insert(const_iterator __hint, const value_type& __obj)
 882       {
 883         __glibcxx_check_insert(__hint);
 884         size_type __bucket_count = this->bucket_count();
 885         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 886         _M_check_rehashed(__bucket_count);
 887         return iterator(__it, this);
 888       }
 889
 890       iterator
 891       insert(value_type&& __obj)
 892       {
 893         size_type __bucket_count = this->bucket_count();
 894         _Base_iterator __it = _Base::insert(std::move(__obj));
 895         _M_check_rehashed(__bucket_count);
 896         return iterator(__it, this);
 897       }
 898
 899       iterator
 900       insert(const_iterator __hint, value_type&& __obj)
 901       {
 902         __glibcxx_check_insert(__hint);
 903         size_type __bucket_count = this->bucket_count();
 904         _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
 905         _M_check_rehashed(__bucket_count);
 906         return iterator(__it, this);
 907       }
 908
 909       void
 910       insert(std::initializer_list<value_type> __l)
 911       {
 912         size_type __bucket_count = this->bucket_count();
 913         _Base::insert(__l);
 914         _M_check_rehashed(__bucket_count);
 915       }
 916
 917       template<typename _InputIterator>
 918         void
 919         insert(_InputIterator __first, _InputIterator __last)
 920         {
 921           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 922           __glibcxx_check_valid_range2(__first, __last, __dist);
 923           size_type __bucket_count = this->bucket_count();
 924
 925           if (__dist.second >= __gnu_debug::__dp_sign)
 926             _Base::insert(__gnu_debug::__unsafe(__first),
 927                           __gnu_debug::__unsafe(__last));
 928           else
 929             _Base::insert(__first, __last);
 930
 931           _M_check_rehashed(__bucket_count);
 932         }
 933
 934 #if __cplusplus > 201402L
 935       using node_type = typename _Base::node_type;
 936
 937       node_type
 938       extract(const_iterator __position)
 939       {
 940         __glibcxx_check_erase(__position);
 941         _Base_const_iterator __victim = __position.base();
 942         this->_M_invalidate_if(
 943             [__victim](_Base_const_iterator __it) { return __it == __victim; }
 944             );
 945         this->_M_invalidate_local_if(
 946             [__victim](_Base_const_local_iterator __it) {
 947                 return __it._M_curr() == __victim._M_cur;
 948             });
 949         return _Base::extract(__position.base());
 950       }
 951
 952       node_type
 953       extract(const key_type& __key)
 954       {
 955         const auto __position = find(__key);
 956         if (__position != end())
 957           return extract(__position);
 958         return {};
 959       }
 960
 961       iterator
 962       insert(node_type&& __nh)
 963       { return iterator(_Base::insert(std::move(__nh)), this); }
 964
 965       iterator
 966       insert(const_iterator __hint, node_type&& __nh)
 967       {
 968         __glibcxx_check_insert(__hint);
 969         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
 970       }
 971
 972       using _Base::merge;
 973 #endif // C++17
 974
 975       iterator
 976       find(const key_type& __key)
 977       { return iterator(_Base::find(__key), this); }
 978
 979       const_iterator
 980       find(const key_type& __key) const
 981       { return const_iterator(_Base::find(__key), this); }
 982
 983       std::pair<iterator, iterator>
 984       equal_range(const key_type& __key)
 985       {
 986         std::pair<_Base_iterator, _Base_iterator> __res
 987           = _Base::equal_range(__key);
 988         return std::make_pair(iterator(__res.first, this),
 989                               iterator(__res.second, this));
 990       }
 991
 992       std::pair<const_iterator, const_iterator>
 993       equal_range(const key_type& __key) const
 994       {
 995         std::pair<_Base_const_iterator, _Base_const_iterator>
 996           __res = _Base::equal_range(__key);
 997         return std::make_pair(const_iterator(__res.first, this),
 998                               const_iterator(__res.second, this));
 999       }
1000
1001       size_type
1002       erase(const key_type& __key)
1003       {
1004         size_type __ret(0);
1005         std::pair<_Base_iterator, _Base_iterator> __pair =
1006           _Base::equal_range(__key);
1007         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
1008           {
1009             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
1010                             { return __it == __victim; });
1011             this->_M_invalidate_local_if(
1012                             [__victim](_Base_const_local_iterator __it)
1013                             { return __it._M_curr() == __victim._M_cur; });
1014             _Base::erase(__victim++);
1015             ++__ret;
1016           }
1017         return __ret;
1018       }
1019
1020       iterator
1021       erase(const_iterator __it)
1022       {
1023         __glibcxx_check_erase(__it);
1024         _Base_const_iterator __victim = __it.base();
1025         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
1026                         { return __it == __victim; });
1027         this->_M_invalidate_local_if(
1028                         [__victim](_Base_const_local_iterator __it)
1029                         { return __it._M_curr() == __victim._M_cur; });
1030         return iterator(_Base::erase(__it.base()), this);
1031       }
1032
1033       iterator
1034       erase(iterator __it)
1035       { return erase(const_iterator(__it)); }
1036
1037       iterator
1038       erase(const_iterator __first, const_iterator __last)
1039       {
1040         __glibcxx_check_erase_range(__first, __last);
1041         for (_Base_const_iterator __tmp = __first.base();
1042              __tmp != __last.base(); ++__tmp)
1043           {
1044             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
1045                                   _M_message(__gnu_debug::__msg_valid_range)
1046                                   ._M_iterator(__first, "first")
1047                                   ._M_iterator(__last, "last"));
1048             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
1049                             { return __it == __tmp; });
1050             this->_M_invalidate_local_if(
1051                             [__tmp](_Base_const_local_iterator __it)
1052                             { return __it._M_curr() == __tmp._M_cur; });
1053           }
1054         return iterator(_Base::erase(__first.base(),
1055                                      __last.base()), this);
1056       }
1057
1058       _Base&
1059       _M_base() noexcept        { return *this; }
1060
1061       const _Base&
1062       _M_base() const noexcept  { return *this; }
1063
1064     private:
1065       void
1066       _M_check_rehashed(size_type __prev_count)
1067       {
1068         if (__prev_count != this->bucket_count())
1069           this->_M_invalidate_locals();
1070       }
1071     };
1072
1073 #if __cpp_deduction_guides >= 201606
1074
1075   template<typename _InputIterator,
1076            typename _Hash =
1077            hash<typename iterator_traits<_InputIterator>::value_type>,
1078            typename _Pred =
1079            equal_to<typename iterator_traits<_InputIterator>::value_type>,
1080            typename _Allocator =
1081            allocator<typename iterator_traits<_InputIterator>::value_type>,
1082            typename = _RequireInputIter<_InputIterator>,
1083            typename = _RequireAllocator<_Allocator>>
1084     unordered_multiset(_InputIterator, _InputIterator,
1085                        unordered_multiset<int>::size_type = {},
1086                        _Hash = _Hash(), _Pred = _Pred(),
1087                        _Allocator = _Allocator())
1088     -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1089                           _Hash, _Pred, _Allocator>;
1090
1091   template<typename _Tp, typename _Hash = hash<_Tp>,
1092            typename _Pred = equal_to<_Tp>,
1093            typename _Allocator = allocator<_Tp>,
1094            typename = _RequireAllocator<_Allocator>>
1095     unordered_multiset(initializer_list<_Tp>,
1096                        unordered_multiset<int>::size_type = {},
1097                        _Hash = _Hash(), _Pred = _Pred(),
1098                        _Allocator = _Allocator())
1099     -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1100
1101   template<typename _InputIterator, typename _Allocator,
1102            typename = _RequireInputIter<_InputIterator>,
1103            typename = _RequireAllocator<_Allocator>>
1104     unordered_multiset(_InputIterator, _InputIterator,
1105                        unordered_multiset<int>::size_type, _Allocator)
1106     -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1107                           hash<typename
1108                                iterator_traits<_InputIterator>::value_type>,
1109                           equal_to<typename
1110                                    iterator_traits<_InputIterator>::value_type>,
1111                           _Allocator>;
1112
1113   template<typename _InputIterator, typename _Hash, typename _Allocator,
1114            typename = _RequireInputIter<_InputIterator>,
1115            typename = _RequireAllocator<_Allocator>>
1116     unordered_multiset(_InputIterator, _InputIterator,
1117                        unordered_multiset<int>::size_type,
1118                        _Hash, _Allocator)
1119     -> unordered_multiset<typename
1120                           iterator_traits<_InputIterator>::value_type,
1121                           _Hash,
1122                           equal_to<
1123                             typename
1124                             iterator_traits<_InputIterator>::value_type>,
1125                           _Allocator>;
1126
1127   template<typename _Tp, typename _Allocator,
1128            typename = _RequireAllocator<_Allocator>>
1129     unordered_multiset(initializer_list<_Tp>,
1130                        unordered_multiset<int>::size_type, _Allocator)
1131     -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1132
1133   template<typename _Tp, typename _Hash, typename _Allocator,
1134            typename = _RequireAllocator<_Allocator>>
1135     unordered_multiset(initializer_list<_Tp>,
1136                        unordered_multiset<int>::size_type, _Hash, _Allocator)
1137     -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1138
1139 #endif
1140
1141   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1142     inline void
1143     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1144          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1145     noexcept(noexcept(__x.swap(__y)))
1146     { __x.swap(__y); }
1147
1148   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1149     inline bool
1150     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1151                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1152     { return __x._M_base() == __y._M_base(); }
1153
1154   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1155     inline bool
1156     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1157                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1158     { return !(__x == __y); }
1159
1160 } // namespace __debug
1161 } // namespace std
1162
1163 #endif // C++11
1164
1165 #endif