libstdc++-v3/include/debug/unordered_map

   1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2024 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_map
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
  30 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
  31
  32 #pragma GCC system_header
  33
  34 #if __cplusplus < 201103L
  35 # include <bits/c++0x_warning.h>
  36 #else
  37 # include <bits/c++config.h>
  38 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
  39   template<typename _Key, typename _Tp, typename _Hash, typename _Pred,
  40            typename _Allocator>
  41     class unordered_map;
  42   template<typename _Key, typename _Tp, typename _Hash, typename _Pred,
  43            typename _Allocator>
  44     class unordered_multimap;
  45 } } // namespace std::__debug
  46
  47 # include <unordered_map>
  48
  49 #include <debug/safe_unordered_container.h>
  50 #include <debug/safe_container.h>
  51 #include <debug/safe_iterator.h>
  52 #include <debug/safe_local_iterator.h>
  53
  54 namespace std _GLIBCXX_VISIBILITY(default)
  55 {
  56 namespace __debug
  57 {
  58   /// Class std::unordered_map with safety/checking/debug instrumentation.
  59   template<typename _Key, typename _Tp,
  60            typename _Hash = std::hash<_Key>,
  61            typename _Pred = std::equal_to<_Key>,
  62            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
  63     class unordered_map
  64     : public __gnu_debug::_Safe_container<
  65         unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
  66         __gnu_debug::_Safe_unordered_container>,
  67       public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
  68     {
  69       typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
  70                                             _Pred, _Alloc>              _Base;
  71       typedef __gnu_debug::_Safe_container<unordered_map,
  72                    _Alloc, __gnu_debug::_Safe_unordered_container>      _Safe;
  73       typedef typename _Base::const_iterator    _Base_const_iterator;
  74       typedef typename _Base::iterator          _Base_iterator;
  75       typedef typename _Base::const_local_iterator
  76                                                 _Base_const_local_iterator;
  77       typedef typename _Base::local_iterator    _Base_local_iterator;
  78
  79       template<typename _ItT, typename _SeqT, typename _CatT>
  80         friend class ::__gnu_debug::_Safe_iterator;
  81       template<typename _ItT, typename _SeqT>
  82         friend class ::__gnu_debug::_Safe_local_iterator;
  83
  84       // Reference wrapper for base class. See PR libstdc++/90102.
  85       struct _Base_ref
  86       {
  87         _Base_ref(const _Base& __r) : _M_ref(__r) { }
  88
  89         const _Base& _M_ref;
  90       };
  91
  92     public:
  93       typedef typename _Base::size_type                 size_type;
  94       typedef typename _Base::hasher                    hasher;
  95       typedef typename _Base::key_equal                 key_equal;
  96       typedef typename _Base::allocator_type            allocator_type;
  97
  98       typedef typename _Base::key_type                  key_type;
  99       typedef typename _Base::value_type                value_type;
 100       typedef typename _Base::mapped_type               mapped_type;
 101
 102       typedef typename _Base::pointer                   pointer;
 103       typedef typename _Base::const_pointer             const_pointer;
 104       typedef typename _Base::reference                 reference;
 105       typedef typename _Base::const_reference           const_reference;
 106       typedef __gnu_debug::_Safe_iterator<
 107         _Base_iterator, unordered_map>                  iterator;
 108       typedef __gnu_debug::_Safe_iterator<
 109         _Base_const_iterator, unordered_map>            const_iterator;
 110       typedef __gnu_debug::_Safe_local_iterator<
 111         _Base_local_iterator, unordered_map>            local_iterator;
 112       typedef __gnu_debug::_Safe_local_iterator<
 113         _Base_const_local_iterator, unordered_map>      const_local_iterator;
 114       typedef typename _Base::difference_type           difference_type;
 115
 116       unordered_map() = default;
 117
 118       explicit
 119       unordered_map(size_type __n,
 120                     const hasher& __hf = hasher(),
 121                     const key_equal& __eql = key_equal(),
 122                     const allocator_type& __a = allocator_type())
 123       : _Base(__n, __hf, __eql, __a) { }
 124
 125       template<typename _InputIterator>
 126         unordered_map(_InputIterator __first, _InputIterator __last,
 127                       size_type __n = 0,
 128                       const hasher& __hf = hasher(),
 129                       const key_equal& __eql = key_equal(),
 130                       const allocator_type& __a = allocator_type())
 131         : _Base(__gnu_debug::__base(
 132                   __glibcxx_check_valid_constructor_range(__first, __last)),
 133                 __gnu_debug::__base(__last), __n,
 134                 __hf, __eql, __a) { }
 135
 136       unordered_map(const unordered_map&) = default;
 137
 138       unordered_map(_Base_ref __x)
 139       : _Base(__x._M_ref) { }
 140
 141       unordered_map(unordered_map&&) = default;
 142
 143       explicit
 144       unordered_map(const allocator_type& __a)
 145       : _Base(__a) { }
 146
 147       unordered_map(const unordered_map& __umap,
 148                     const allocator_type& __a)
 149       : _Base(__umap, __a) { }
 150
 151       unordered_map(unordered_map&& __umap,
 152                     const allocator_type& __a)
 153       noexcept( noexcept(_Base(std::move(__umap), __a)) )
 154       : _Safe(std::move(__umap), __a),
 155         _Base(std::move(__umap), __a) { }
 156
 157       unordered_map(initializer_list<value_type> __l,
 158                     size_type __n = 0,
 159                     const hasher& __hf = hasher(),
 160                     const key_equal& __eql = key_equal(),
 161                     const allocator_type& __a = allocator_type())
 162       : _Base(__l, __n, __hf, __eql, __a) { }
 163
 164       unordered_map(size_type __n, const allocator_type& __a)
 165       : unordered_map(__n, hasher(), key_equal(), __a)
 166       { }
 167
 168       unordered_map(size_type __n,
 169                     const hasher& __hf,
 170                     const allocator_type& __a)
 171       : unordered_map(__n, __hf, key_equal(), __a)
 172       { }
 173
 174       template<typename _InputIterator>
 175         unordered_map(_InputIterator __first, _InputIterator __last,
 176                       size_type __n,
 177                       const allocator_type& __a)
 178         : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
 179         { }
 180
 181       template<typename _InputIterator>
 182         unordered_map(_InputIterator __first, _InputIterator __last,
 183                       size_type __n,
 184                       const hasher& __hf,
 185                       const allocator_type& __a)
 186         : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
 187         { }
 188
 189       unordered_map(initializer_list<value_type> __l,
 190                     size_type __n,
 191                     const allocator_type& __a)
 192       : unordered_map(__l, __n, hasher(), key_equal(), __a)
 193       { }
 194
 195       unordered_map(initializer_list<value_type> __l,
 196                     size_type __n,
 197                     const hasher& __hf,
 198                     const allocator_type& __a)
 199       : unordered_map(__l, __n, __hf, key_equal(), __a)
 200       { }
 201
 202       ~unordered_map() = default;
 203
 204       unordered_map&
 205       operator=(const unordered_map&) = default;
 206
 207       unordered_map&
 208       operator=(unordered_map&&) = default;
 209
 210       unordered_map&
 211       operator=(initializer_list<value_type> __l)
 212       {
 213         _Base::operator=(__l);
 214         this->_M_invalidate_all();
 215         return *this;
 216       }
 217
 218       using _Base::get_allocator;
 219       using _Base::empty;
 220       using _Base::size;
 221       using _Base::max_size;
 222
 223       void
 224       swap(unordered_map& __x)
 225         noexcept( noexcept(declval<_Base&>().swap(__x)) )
 226       {
 227         _Safe::_M_swap(__x);
 228         _Base::swap(__x);
 229       }
 230
 231       void
 232       clear() noexcept
 233       {
 234         _Base::clear();
 235         this->_M_invalidate_all();
 236       }
 237
 238       iterator
 239       begin() noexcept
 240       { return { _Base::begin(), this }; }
 241
 242       const_iterator
 243       begin() const noexcept
 244       { return { _Base::begin(), this }; }
 245
 246       iterator
 247       end() noexcept
 248       { return { _Base::end(), this }; }
 249
 250       const_iterator
 251       end() const noexcept
 252       { return { _Base::end(), this }; }
 253
 254       const_iterator
 255       cbegin() const noexcept
 256       { return { _Base::cbegin(), this }; }
 257
 258       const_iterator
 259       cend() const noexcept
 260       { return { _Base::cend(), this }; }
 261
 262       // local versions
 263       local_iterator
 264       begin(size_type __b)
 265       {
 266         __glibcxx_check_bucket_index(__b);
 267         return { _Base::begin(__b), this };
 268       }
 269
 270       local_iterator
 271       end(size_type __b)
 272       {
 273         __glibcxx_check_bucket_index(__b);
 274         return { _Base::end(__b), this };
 275       }
 276
 277       const_local_iterator
 278       begin(size_type __b) const
 279       {
 280         __glibcxx_check_bucket_index(__b);
 281         return { _Base::begin(__b), this };
 282       }
 283
 284       const_local_iterator
 285       end(size_type __b) const
 286       {
 287         __glibcxx_check_bucket_index(__b);
 288         return { _Base::end(__b), this };
 289       }
 290
 291       const_local_iterator
 292       cbegin(size_type __b) const
 293       {
 294         __glibcxx_check_bucket_index(__b);
 295         return { _Base::cbegin(__b), this };
 296       }
 297
 298       const_local_iterator
 299       cend(size_type __b) const
 300       {
 301         __glibcxx_check_bucket_index(__b);
 302         return { _Base::cend(__b), this };
 303       }
 304
 305       using _Base::bucket_count;
 306       using _Base::max_bucket_count;
 307       using _Base::bucket;
 308
 309       size_type
 310       bucket_size(size_type __b) const
 311       {
 312         __glibcxx_check_bucket_index(__b);
 313         return _Base::bucket_size(__b);
 314       }
 315
 316       using _Base::load_factor;
 317
 318       float
 319       max_load_factor() const noexcept
 320       { return _Base::max_load_factor(); }
 321
 322       void
 323       max_load_factor(float __f)
 324       {
 325         __glibcxx_check_max_load_factor(__f);
 326         _Base::max_load_factor(__f);
 327       }
 328
 329       template<typename... _Args>
 330         std::pair<iterator, bool>
 331         emplace(_Args&&... __args)
 332         {
 333           size_type __bucket_count = this->bucket_count();
 334           auto __res = _Base::emplace(std::forward<_Args>(__args)...);
 335           _M_check_rehashed(__bucket_count);
 336           return { { __res.first, this }, __res.second };
 337         }
 338
 339       template<typename... _Args>
 340         iterator
 341         emplace_hint(const_iterator __hint, _Args&&... __args)
 342         {
 343           __glibcxx_check_insert(__hint);
 344           size_type __bucket_count = this->bucket_count();
 345           auto __it = _Base::emplace_hint(__hint.base(),
 346                                           std::forward<_Args>(__args)...);
 347           _M_check_rehashed(__bucket_count);
 348           return { __it, this };
 349         }
 350
 351       std::pair<iterator, bool>
 352       insert(const value_type& __obj)
 353       {
 354         size_type __bucket_count = this->bucket_count();
 355         auto __res = _Base::insert(__obj);
 356         _M_check_rehashed(__bucket_count);
 357         return { { __res.first, this }, __res.second };
 358       }
 359
 360       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 361       // 2354. Unnecessary copying when inserting into maps with braced-init
 362       std::pair<iterator, bool>
 363       insert(value_type&& __x)
 364       {
 365         size_type __bucket_count = this->bucket_count();
 366         auto __res = _Base::insert(std::move(__x));
 367         _M_check_rehashed(__bucket_count);
 368         return { { __res.first, this }, __res.second };
 369       }
 370
 371       template<typename _Pair, typename = typename
 372                std::enable_if<std::is_constructible<value_type,
 373                                                     _Pair&&>::value>::type>
 374         std::pair<iterator, bool>
 375         insert(_Pair&& __obj)
 376         {
 377           size_type __bucket_count = this->bucket_count();
 378           auto __res = _Base::insert(std::forward<_Pair>(__obj));
 379           _M_check_rehashed(__bucket_count);
 380           return { { __res.first, this }, __res.second };
 381         }
 382
 383       iterator
 384       insert(const_iterator __hint, const value_type& __obj)
 385       {
 386         __glibcxx_check_insert(__hint);
 387         size_type __bucket_count = this->bucket_count();
 388         auto __it = _Base::insert(__hint.base(), __obj);
 389         _M_check_rehashed(__bucket_count);
 390         return { __it, this };
 391       }
 392
 393       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 394       // 2354. Unnecessary copying when inserting into maps with braced-init
 395       iterator
 396       insert(const_iterator __hint, value_type&& __x)
 397       {
 398         __glibcxx_check_insert(__hint);
 399         size_type __bucket_count = this->bucket_count();
 400         auto __it = _Base::insert(__hint.base(), std::move(__x));
 401         _M_check_rehashed(__bucket_count);
 402         return { __it, this };
 403       }
 404
 405       template<typename _Pair, typename = typename
 406                std::enable_if<std::is_constructible<value_type,
 407                                                     _Pair&&>::value>::type>
 408         iterator
 409         insert(const_iterator __hint, _Pair&& __obj)
 410         {
 411           __glibcxx_check_insert(__hint);
 412           size_type __bucket_count = this->bucket_count();
 413           auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
 414           _M_check_rehashed(__bucket_count);
 415           return { __it, this };
 416         }
 417
 418       void
 419       insert(std::initializer_list<value_type> __l)
 420       {
 421         size_type __bucket_count = this->bucket_count();
 422         _Base::insert(__l);
 423         _M_check_rehashed(__bucket_count);
 424       }
 425
 426       template<typename _InputIterator>
 427         void
 428         insert(_InputIterator __first, _InputIterator __last)
 429         {
 430           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 431           __glibcxx_check_valid_range2(__first, __last, __dist);
 432           size_type __bucket_count = this->bucket_count();
 433
 434           if (__dist.second >= __gnu_debug::__dp_sign)
 435             _Base::insert(__gnu_debug::__unsafe(__first),
 436                           __gnu_debug::__unsafe(__last));
 437           else
 438             _Base::insert(__first, __last);
 439
 440           _M_check_rehashed(__bucket_count);
 441         }
 442
 443 #if __cplusplus > 201402L
 444       template <typename... _Args>
 445         pair<iterator, bool>
 446         try_emplace(const key_type& __k, _Args&&... __args)
 447         {
 448           auto __res = _Base::try_emplace(__k,
 449                                           std::forward<_Args>(__args)...);
 450           return { { __res.first, this }, __res.second };
 451         }
 452
 453       template <typename... _Args>
 454         pair<iterator, bool>
 455         try_emplace(key_type&& __k, _Args&&... __args)
 456         {
 457           auto __res = _Base::try_emplace(std::move(__k),
 458                                           std::forward<_Args>(__args)...);
 459           return { { __res.first, this }, __res.second };
 460         }
 461
 462       template <typename... _Args>
 463         iterator
 464         try_emplace(const_iterator __hint, const key_type& __k,
 465                     _Args&&... __args)
 466         {
 467           __glibcxx_check_insert(__hint);
 468           return { _Base::try_emplace(__hint.base(), __k,
 469                                       std::forward<_Args>(__args)...),
 470                    this };
 471         }
 472
 473       template <typename... _Args>
 474         iterator
 475         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
 476         {
 477           __glibcxx_check_insert(__hint);
 478           return { _Base::try_emplace(__hint.base(), std::move(__k),
 479                                       std::forward<_Args>(__args)...),
 480                    this };
 481         }
 482
 483       template <typename _Obj>
 484         pair<iterator, bool>
 485         insert_or_assign(const key_type& __k, _Obj&& __obj)
 486         {
 487           auto __res = _Base::insert_or_assign(__k,
 488                                                std::forward<_Obj>(__obj));
 489           return { { __res.first, this }, __res.second };
 490         }
 491
 492       template <typename _Obj>
 493         pair<iterator, bool>
 494         insert_or_assign(key_type&& __k, _Obj&& __obj)
 495         {
 496           auto __res = _Base::insert_or_assign(std::move(__k),
 497                                                std::forward<_Obj>(__obj));
 498           return { { __res.first, this }, __res.second };
 499         }
 500
 501       template <typename _Obj>
 502         iterator
 503         insert_or_assign(const_iterator __hint, const key_type& __k,
 504                          _Obj&& __obj)
 505         {
 506           __glibcxx_check_insert(__hint);
 507           return { _Base::insert_or_assign(__hint.base(), __k,
 508                                            std::forward<_Obj>(__obj)),
 509                    this };
 510         }
 511
 512       template <typename _Obj>
 513         iterator
 514         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
 515         {
 516           __glibcxx_check_insert(__hint);
 517           return { _Base::insert_or_assign(__hint.base(), std::move(__k),
 518                                            std::forward<_Obj>(__obj)),
 519                    this };
 520         }
 521 #endif // C++17
 522
 523 #if __cplusplus > 201402L
 524       using node_type = typename _Base::node_type;
 525       using insert_return_type = _Node_insert_return<iterator, node_type>;
 526
 527       node_type
 528       extract(const_iterator __position)
 529       {
 530         __glibcxx_check_erase(__position);
 531         return _M_extract(__position.base());
 532       }
 533
 534       node_type
 535       extract(const key_type& __key)
 536       {
 537         const auto __position = _Base::find(__key);
 538         if (__position != _Base::end())
 539           return _M_extract(__position);
 540         return {};
 541       }
 542
 543       insert_return_type
 544       insert(node_type&& __nh)
 545       {
 546         auto __ret = _Base::insert(std::move(__nh));
 547         return
 548           { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
 549       }
 550
 551       iterator
 552       insert(const_iterator __hint, node_type&& __nh)
 553       {
 554         __glibcxx_check_insert(__hint);
 555         return { _Base::insert(__hint.base(), std::move(__nh)), this };
 556       }
 557
 558       template<typename _H2, typename _P2>
 559         void
 560         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
 561         {
 562           auto __guard
 563             = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
 564           _Base::merge(__source);
 565         }
 566
 567       template<typename _H2, typename _P2>
 568         void
 569         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
 570         { merge(__source); }
 571
 572       template<typename _H2, typename _P2>
 573         void
 574         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
 575         {
 576           auto __guard
 577             = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
 578           _Base::merge(__source);
 579         }
 580
 581       template<typename _H2, typename _P2>
 582         void
 583         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
 584         { merge(__source); }
 585 #endif // C++17
 586
 587       using _Base::hash_function;
 588       using _Base::key_eq;
 589
 590       iterator
 591       find(const key_type& __key)
 592       { return { _Base::find(__key), this }; }
 593
 594 #if __cplusplus > 201703L
 595       template<typename _Kt,
 596                typename = std::__has_is_transparent_t<_Hash, _Kt>,
 597                typename = std::__has_is_transparent_t<_Pred, _Kt>>
 598         iterator
 599         find(const _Kt& __k)
 600         { return { _Base::find(__k), this }; }
 601 #endif
 602
 603       const_iterator
 604       find(const key_type& __key) const
 605       { return { _Base::find(__key), this }; }
 606
 607 #if __cplusplus > 201703L
 608       template<typename _Kt,
 609                typename = std::__has_is_transparent_t<_Hash, _Kt>,
 610                typename = std::__has_is_transparent_t<_Pred, _Kt>>
 611         const_iterator
 612         find(const _Kt& __k) const
 613         { return { _Base::find(__k), this }; }
 614 #endif
 615
 616       using _Base::count;
 617 #if __cplusplus > 201703L
 618       using _Base::contains;
 619 #endif
 620
 621       std::pair<iterator, iterator>
 622       equal_range(const key_type& __key)
 623       {
 624         auto __res = _Base::equal_range(__key);
 625         return { { __res.first, this }, { __res.second, this } };
 626       }
 627
 628 #if __cplusplus > 201703L
 629       template<typename _Kt,
 630                typename = std::__has_is_transparent_t<_Hash, _Kt>,
 631                typename = std::__has_is_transparent_t<_Pred, _Kt>>
 632         std::pair<iterator, iterator>
 633         equal_range(const _Kt& __k)
 634         {
 635           auto __res = _Base::equal_range(__k);
 636           return { { __res.first, this }, { __res.second, this } };
 637         }
 638 #endif
 639
 640       std::pair<const_iterator, const_iterator>
 641       equal_range(const key_type& __key) const
 642       {
 643         auto __res = _Base::equal_range(__key);
 644         return { { __res.first, this }, { __res.second, this } };
 645       }
 646
 647 #if __cplusplus > 201703L
 648       template<typename _Kt,
 649                typename = std::__has_is_transparent_t<_Hash, _Kt>,
 650                typename = std::__has_is_transparent_t<_Pred, _Kt>>
 651         std::pair<const_iterator, const_iterator>
 652         equal_range(const _Kt& __k) const
 653         {
 654           auto __res = _Base::equal_range(__k);
 655           return { { __res.first, this }, { __res.second, this } };
 656         }
 657 #endif
 658
 659       using _Base::operator[];
 660       using _Base::at;
 661
 662       size_type
 663       erase(const key_type& __key)
 664       {
 665         size_type __ret(0);
 666         auto __victim = _Base::find(__key);
 667         if (__victim != _Base::end())
 668           {
 669             _M_erase(__victim);
 670             __ret = 1;
 671           }
 672         return __ret;
 673       }
 674
 675       iterator
 676       erase(const_iterator __it)
 677       {
 678         __glibcxx_check_erase(__it);
 679         return { _M_erase(__it.base()), this };
 680       }
 681
 682       _Base_iterator
 683       erase(_Base_const_iterator __it)
 684       {
 685         __glibcxx_check_erase2(__it);
 686         return _M_erase(__it);
 687       }
 688
 689       iterator
 690       erase(iterator __it)
 691       {
 692         __glibcxx_check_erase(__it);
 693         return { _M_erase(__it.base()), this };
 694       }
 695
 696       iterator
 697       erase(const_iterator __first, const_iterator __last)
 698       {
 699         __glibcxx_check_erase_range(__first, __last);
 700         for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
 701           {
 702             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
 703                                   _M_message(__gnu_debug::__msg_valid_range)
 704                                   ._M_iterator(__first, "first")
 705                                   ._M_iterator(__last, "last"));
 706             _M_invalidate(__tmp);
 707           }
 708
 709         size_type __bucket_count = this->bucket_count();
 710         auto __next = _Base::erase(__first.base(), __last.base());
 711         _M_check_rehashed(__bucket_count);
 712         return { __next, this };
 713       }
 714
 715       using _Base::rehash;
 716       using _Base::reserve;
 717
 718       _Base&
 719       _M_base() noexcept        { return *this; }
 720
 721       const _Base&
 722       _M_base() const noexcept  { return *this; }
 723
 724     private:
 725       void
 726       _M_check_rehashed(size_type __prev_count)
 727       {
 728         if (__prev_count != this->bucket_count())
 729           this->_M_invalidate_all();
 730       }
 731
 732       void
 733       _M_invalidate(_Base_const_iterator __victim)
 734       {
 735         this->_M_invalidate_if(
 736           [__victim](_Base_const_iterator __it) { return __it == __victim; });
 737         this->_M_invalidate_local_if(
 738           [__victim](_Base_const_local_iterator __it)
 739           { return __it == __victim; });
 740       }
 741
 742       _Base_iterator
 743       _M_erase(_Base_const_iterator __victim)
 744       {
 745         _M_invalidate(__victim);
 746         size_type __bucket_count = this->bucket_count();
 747         _Base_iterator __next = _Base::erase(__victim);
 748         _M_check_rehashed(__bucket_count);
 749         return __next;
 750       }
 751
 752 #if __cplusplus > 201402L
 753       node_type
 754       _M_extract(_Base_const_iterator __victim)
 755       {
 756         _M_invalidate(__victim);
 757         return _Base::extract(__victim);
 758       }
 759 #endif
 760     };
 761
 762 #if __cpp_deduction_guides >= 201606
 763
 764   template<typename _InputIterator,
 765            typename _Hash = hash<__iter_key_t<_InputIterator>>,
 766            typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
 767            typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
 768            typename = _RequireInputIter<_InputIterator>,
 769            typename = _RequireNotAllocatorOrIntegral<_Hash>,
 770            typename = _RequireNotAllocator<_Pred>,
 771            typename = _RequireAllocator<_Allocator>>
 772     unordered_map(_InputIterator, _InputIterator,
 773                   typename unordered_map<int, int>::size_type = {},
 774                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
 775     -> unordered_map<__iter_key_t<_InputIterator>,
 776                      __iter_val_t<_InputIterator>,
 777                      _Hash, _Pred, _Allocator>;
 778
 779   template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
 780            typename _Pred = equal_to<_Key>,
 781            typename _Allocator = allocator<pair<const _Key, _Tp>>,
 782            typename = _RequireNotAllocatorOrIntegral<_Hash>,
 783            typename = _RequireNotAllocator<_Pred>,
 784            typename = _RequireAllocator<_Allocator>>
 785     unordered_map(initializer_list<pair<_Key, _Tp>>,
 786                   typename unordered_map<int, int>::size_type = {},
 787                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
 788     -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
 789
 790   template<typename _InputIterator, typename _Allocator,
 791            typename = _RequireInputIter<_InputIterator>,
 792            typename = _RequireAllocator<_Allocator>>
 793     unordered_map(_InputIterator, _InputIterator,
 794                   typename unordered_map<int, int>::size_type, _Allocator)
 795     -> unordered_map<__iter_key_t<_InputIterator>,
 796                      __iter_val_t<_InputIterator>,
 797                      hash<__iter_key_t<_InputIterator>>,
 798                      equal_to<__iter_key_t<_InputIterator>>,
 799                      _Allocator>;
 800
 801   template<typename _InputIterator, typename _Allocator,
 802            typename = _RequireInputIter<_InputIterator>,
 803            typename = _RequireAllocator<_Allocator>>
 804     unordered_map(_InputIterator, _InputIterator, _Allocator)
 805     -> unordered_map<__iter_key_t<_InputIterator>,
 806                      __iter_val_t<_InputIterator>,
 807                      hash<__iter_key_t<_InputIterator>>,
 808                      equal_to<__iter_key_t<_InputIterator>>,
 809                      _Allocator>;
 810
 811   template<typename _InputIterator, typename _Hash, typename _Allocator,
 812            typename = _RequireInputIter<_InputIterator>,
 813            typename = _RequireNotAllocatorOrIntegral<_Hash>,
 814            typename = _RequireAllocator<_Allocator>>
 815     unordered_map(_InputIterator, _InputIterator,
 816                   typename unordered_map<int, int>::size_type,
 817                   _Hash, _Allocator)
 818     -> unordered_map<__iter_key_t<_InputIterator>,
 819                      __iter_val_t<_InputIterator>, _Hash,
 820                      equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
 821
 822   template<typename _Key, typename _Tp, typename _Allocator,
 823            typename = _RequireAllocator<_Allocator>>
 824     unordered_map(initializer_list<pair<_Key, _Tp>>,
 825                   typename unordered_map<int, int>::size_type,
 826                   _Allocator)
 827     -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
 828
 829   template<typename _Key, typename _Tp, typename _Allocator,
 830            typename = _RequireAllocator<_Allocator>>
 831     unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
 832     -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
 833
 834   template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
 835            typename = _RequireNotAllocatorOrIntegral<_Hash>,
 836            typename = _RequireAllocator<_Allocator>>
 837     unordered_map(initializer_list<pair<_Key, _Tp>>,
 838                   typename unordered_map<int, int>::size_type,
 839                   _Hash, _Allocator)
 840     -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
 841
 842 #endif
 843
 844   template<typename _Key, typename _Tp, typename _Hash,
 845            typename _Pred, typename _Alloc>
 846     inline void
 847     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 848          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 849     noexcept(noexcept(__x.swap(__y)))
 850     { __x.swap(__y); }
 851
 852   template<typename _Key, typename _Tp, typename _Hash,
 853            typename _Pred, typename _Alloc>
 854     inline bool
 855     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 856                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 857     { return __x._M_base() == __y._M_base(); }
 858
 859 #if __cpp_impl_three_way_comparison < 201907L
 860   template<typename _Key, typename _Tp, typename _Hash,
 861            typename _Pred, typename _Alloc>
 862     inline bool
 863     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 864                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 865     { return !(__x == __y); }
 866 #endif
 867
 868   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
 869   template<typename _Key, typename _Tp,
 870            typename _Hash = std::hash<_Key>,
 871            typename _Pred = std::equal_to<_Key>,
 872            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
 873     class unordered_multimap
 874       : public __gnu_debug::_Safe_container<
 875         unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
 876         __gnu_debug::_Safe_unordered_container>,
 877         public _GLIBCXX_STD_C::unordered_multimap<
 878         _Key, _Tp, _Hash, _Pred, _Alloc>
 879     {
 880       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
 881                                                  _Pred, _Alloc>         _Base;
 882       typedef __gnu_debug::_Safe_container<unordered_multimap,
 883         _Alloc, __gnu_debug::_Safe_unordered_container>                 _Safe;
 884       typedef typename _Base::const_iterator       _Base_const_iterator;
 885       typedef typename _Base::iterator             _Base_iterator;
 886       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
 887       typedef typename _Base::local_iterator       _Base_local_iterator;
 888
 889       template<typename _ItT, typename _SeqT, typename _CatT>
 890         friend class ::__gnu_debug::_Safe_iterator;
 891       template<typename _ItT, typename _SeqT>
 892         friend class ::__gnu_debug::_Safe_local_iterator;
 893
 894       // Reference wrapper for base class. See PR libstdc++/90102.
 895       struct _Base_ref
 896       {
 897         _Base_ref(const _Base& __r) : _M_ref(__r) { }
 898
 899         const _Base& _M_ref;
 900       };
 901
 902     public:
 903       typedef typename _Base::size_type                 size_type;
 904       typedef typename _Base::hasher                    hasher;
 905       typedef typename _Base::key_equal                 key_equal;
 906       typedef typename _Base::allocator_type            allocator_type;
 907
 908       typedef typename _Base::key_type                  key_type;
 909       typedef typename _Base::value_type                value_type;
 910       typedef typename _Base::mapped_type               mapped_type;
 911
 912       typedef typename _Base::pointer                   pointer;
 913       typedef typename _Base::const_pointer             const_pointer;
 914       typedef typename _Base::reference                 reference;
 915       typedef typename _Base::const_reference           const_reference;
 916       typedef __gnu_debug::_Safe_iterator<
 917         _Base_iterator, unordered_multimap>             iterator;
 918       typedef __gnu_debug::_Safe_iterator<
 919         _Base_const_iterator, unordered_multimap>       const_iterator;
 920       typedef __gnu_debug::_Safe_local_iterator<
 921         _Base_local_iterator, unordered_multimap>       local_iterator;
 922       typedef __gnu_debug::_Safe_local_iterator<
 923         _Base_const_local_iterator, unordered_multimap> const_local_iterator;
 924       typedef typename _Base::difference_type           difference_type;
 925
 926       unordered_multimap() = default;
 927
 928       explicit
 929       unordered_multimap(size_type __n,
 930                          const hasher& __hf = hasher(),
 931                          const key_equal& __eql = key_equal(),
 932                          const allocator_type& __a = allocator_type())
 933       : _Base(__n, __hf, __eql, __a) { }
 934
 935       template<typename _InputIterator>
 936         unordered_multimap(_InputIterator __first, _InputIterator __last,
 937                            size_type __n = 0,
 938                            const hasher& __hf = hasher(),
 939                            const key_equal& __eql = key_equal(),
 940                            const allocator_type& __a = allocator_type())
 941         : _Base(__gnu_debug::__base(
 942                   __glibcxx_check_valid_constructor_range(__first, __last)),
 943                 __gnu_debug::__base(__last), __n,
 944                 __hf, __eql, __a) { }
 945
 946       unordered_multimap(const unordered_multimap&) = default;
 947
 948       unordered_multimap(_Base_ref __x)
 949       : _Base(__x._M_ref) { }
 950
 951       unordered_multimap(unordered_multimap&&) = default;
 952
 953       explicit
 954       unordered_multimap(const allocator_type& __a)
 955       : _Base(__a) { }
 956
 957       unordered_multimap(const unordered_multimap& __umap,
 958                          const allocator_type& __a)
 959       : _Base(__umap, __a) { }
 960
 961       unordered_multimap(unordered_multimap&& __umap,
 962                          const allocator_type& __a)
 963       noexcept( noexcept(_Base(std::move(__umap), __a)) )
 964       : _Safe(std::move(__umap), __a),
 965         _Base(std::move(__umap), __a) { }
 966
 967       unordered_multimap(initializer_list<value_type> __l,
 968                          size_type __n = 0,
 969                          const hasher& __hf = hasher(),
 970                          const key_equal& __eql = key_equal(),
 971                          const allocator_type& __a = allocator_type())
 972       : _Base(__l, __n, __hf, __eql, __a) { }
 973
 974       unordered_multimap(size_type __n, const allocator_type& __a)
 975       : unordered_multimap(__n, hasher(), key_equal(), __a)
 976       { }
 977
 978       unordered_multimap(size_type __n, const hasher& __hf,
 979                          const allocator_type& __a)
 980       : unordered_multimap(__n, __hf, key_equal(), __a)
 981       { }
 982
 983       template<typename _InputIterator>
 984         unordered_multimap(_InputIterator __first, _InputIterator __last,
 985                            size_type __n,
 986                            const allocator_type& __a)
 987         : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
 988         { }
 989
 990       template<typename _InputIterator>
 991         unordered_multimap(_InputIterator __first, _InputIterator __last,
 992                            size_type __n, const hasher& __hf,
 993                            const allocator_type& __a)
 994         : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
 995         { }
 996
 997       unordered_multimap(initializer_list<value_type> __l,
 998                          size_type __n,
 999                          const allocator_type& __a)
1000       : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1001       { }
1002
1003       unordered_multimap(initializer_list<value_type> __l,
1004                          size_type __n, const hasher& __hf,
1005                          const allocator_type& __a)
1006       : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1007       { }
1008
1009       ~unordered_multimap() = default;
1010
1011       unordered_multimap&
1012       operator=(const unordered_multimap&) = default;
1013
1014       unordered_multimap&
1015       operator=(unordered_multimap&&) = default;
1016
1017       unordered_multimap&
1018       operator=(initializer_list<value_type> __l)
1019       {
1020         _Base::operator=(__l);
1021         this->_M_invalidate_all();
1022         return *this;
1023       }
1024
1025       using _Base::get_allocator;
1026       using _Base::empty;
1027       using _Base::size;
1028       using _Base::max_size;
1029
1030       void
1031       swap(unordered_multimap& __x)
1032         noexcept( noexcept(declval<_Base&>().swap(__x)) )
1033       {
1034         _Safe::_M_swap(__x);
1035         _Base::swap(__x);
1036       }
1037
1038       void
1039       clear() noexcept
1040       {
1041         _Base::clear();
1042         this->_M_invalidate_all();
1043       }
1044
1045       iterator
1046       begin() noexcept
1047       { return { _Base::begin(), this }; }
1048
1049       const_iterator
1050       begin() const noexcept
1051       { return { _Base::begin(), this }; }
1052
1053       iterator
1054       end() noexcept
1055       { return { _Base::end(), this }; }
1056
1057       const_iterator
1058       end() const noexcept
1059       { return { _Base::end(), this }; }
1060
1061       const_iterator
1062       cbegin() const noexcept
1063       { return { _Base::cbegin(), this }; }
1064
1065       const_iterator
1066       cend() const noexcept
1067       { return { _Base::cend(), this }; }
1068
1069       // local versions
1070       local_iterator
1071       begin(size_type __b)
1072       {
1073         __glibcxx_check_bucket_index(__b);
1074         return { _Base::begin(__b), this };
1075       }
1076
1077       local_iterator
1078       end(size_type __b)
1079       {
1080         __glibcxx_check_bucket_index(__b);
1081         return { _Base::end(__b), this };
1082       }
1083
1084       const_local_iterator
1085       begin(size_type __b) const
1086       {
1087         __glibcxx_check_bucket_index(__b);
1088         return { _Base::begin(__b), this };
1089       }
1090
1091       const_local_iterator
1092       end(size_type __b) const
1093       {
1094         __glibcxx_check_bucket_index(__b);
1095         return { _Base::end(__b), this };
1096       }
1097
1098       const_local_iterator
1099       cbegin(size_type __b) const
1100       {
1101         __glibcxx_check_bucket_index(__b);
1102         return { _Base::cbegin(__b), this };
1103       }
1104
1105       const_local_iterator
1106       cend(size_type __b) const
1107       {
1108         __glibcxx_check_bucket_index(__b);
1109         return { _Base::cend(__b), this };
1110       }
1111
1112       using _Base::bucket_count;
1113       using _Base::max_bucket_count;
1114       using _Base::bucket;
1115
1116       size_type
1117       bucket_size(size_type __b) const
1118       {
1119         __glibcxx_check_bucket_index(__b);
1120         return _Base::bucket_size(__b);
1121       }
1122
1123       float
1124       max_load_factor() const noexcept
1125       { return _Base::max_load_factor(); }
1126
1127       void
1128       max_load_factor(float __f)
1129       {
1130         __glibcxx_check_max_load_factor(__f);
1131         _Base::max_load_factor(__f);
1132       }
1133
1134       template<typename... _Args>
1135         iterator
1136         emplace(_Args&&... __args)
1137         {
1138           size_type __bucket_count = this->bucket_count();
1139           auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1140           _M_check_rehashed(__bucket_count);
1141           return { __it, this };
1142         }
1143
1144       template<typename... _Args>
1145         iterator
1146         emplace_hint(const_iterator __hint, _Args&&... __args)
1147         {
1148           __glibcxx_check_insert(__hint);
1149           size_type __bucket_count = this->bucket_count();
1150           auto __it = _Base::emplace_hint(__hint.base(),
1151                                           std::forward<_Args>(__args)...);
1152           _M_check_rehashed(__bucket_count);
1153           return { __it, this };
1154         }
1155
1156       iterator
1157       insert(const value_type& __obj)
1158       {
1159         size_type __bucket_count = this->bucket_count();
1160         auto __it = _Base::insert(__obj);
1161         _M_check_rehashed(__bucket_count);
1162         return { __it, this };
1163       }
1164
1165       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1166       // 2354. Unnecessary copying when inserting into maps with braced-init
1167       iterator
1168       insert(value_type&& __x)
1169       {
1170         size_type __bucket_count = this->bucket_count();
1171         auto __it = _Base::insert(std::move(__x));
1172         _M_check_rehashed(__bucket_count);
1173         return { __it, this };
1174       }
1175
1176       iterator
1177       insert(const_iterator __hint, const value_type& __obj)
1178       {
1179         __glibcxx_check_insert(__hint);
1180         size_type __bucket_count = this->bucket_count();
1181         auto __it = _Base::insert(__hint.base(), __obj);
1182         _M_check_rehashed(__bucket_count);
1183         return { __it, this };
1184       }
1185
1186       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1187       // 2354. Unnecessary copying when inserting into maps with braced-init
1188       iterator
1189       insert(const_iterator __hint, value_type&& __x)
1190       {
1191         __glibcxx_check_insert(__hint);
1192         size_type __bucket_count = this->bucket_count();
1193         auto __it = _Base::insert(__hint.base(), std::move(__x));
1194         _M_check_rehashed(__bucket_count);
1195         return { __it, this };
1196       }
1197
1198       template<typename _Pair, typename = typename
1199                std::enable_if<std::is_constructible<value_type,
1200                                                     _Pair&&>::value>::type>
1201         iterator
1202         insert(_Pair&& __obj)
1203         {
1204           size_type __bucket_count = this->bucket_count();
1205           auto __it = _Base::insert(std::forward<_Pair>(__obj));
1206           _M_check_rehashed(__bucket_count);
1207           return { __it, this };
1208         }
1209
1210       template<typename _Pair, typename = typename
1211                std::enable_if<std::is_constructible<value_type,
1212                                                     _Pair&&>::value>::type>
1213         iterator
1214         insert(const_iterator __hint, _Pair&& __obj)
1215         {
1216           __glibcxx_check_insert(__hint);
1217           size_type __bucket_count = this->bucket_count();
1218           auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1219           _M_check_rehashed(__bucket_count);
1220           return { __it, this };
1221         }
1222
1223       void
1224       insert(std::initializer_list<value_type> __l)
1225       { _Base::insert(__l); }
1226
1227       template<typename _InputIterator>
1228         void
1229         insert(_InputIterator __first, _InputIterator __last)
1230         {
1231           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1232           __glibcxx_check_valid_range2(__first, __last, __dist);
1233           size_type __bucket_count = this->bucket_count();
1234
1235           if (__dist.second >= __gnu_debug::__dp_sign)
1236             _Base::insert(__gnu_debug::__unsafe(__first),
1237                           __gnu_debug::__unsafe(__last));
1238           else
1239             _Base::insert(__first, __last);
1240
1241           _M_check_rehashed(__bucket_count);
1242         }
1243
1244 #if __cplusplus > 201402L
1245       using node_type = typename _Base::node_type;
1246
1247       node_type
1248       extract(const_iterator __position)
1249       {
1250         __glibcxx_check_erase(__position);
1251         return _M_extract(__position.base());
1252       }
1253
1254       node_type
1255       extract(const key_type& __key)
1256       {
1257         const auto __position = _Base::find(__key);
1258         if (__position != _Base::end())
1259           return _M_extract(__position);
1260         return {};
1261       }
1262
1263       iterator
1264       insert(node_type&& __nh)
1265       { return { _Base::insert(std::move(__nh)), this }; }
1266
1267       iterator
1268       insert(const_iterator __hint, node_type&& __nh)
1269       {
1270         __glibcxx_check_insert(__hint);
1271         return { _Base::insert(__hint.base(), std::move(__nh)), this };
1272       }
1273
1274       template<typename _H2, typename _P2>
1275         void
1276         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1277         {
1278           auto __guard
1279             = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1280           _Base::merge(__source);
1281         }
1282
1283       template<typename _H2, typename _P2>
1284         void
1285         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1286         { merge(__source); }
1287
1288       template<typename _H2, typename _P2>
1289         void
1290         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1291         {
1292           auto __guard
1293             = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1294           _Base::merge(__source);
1295         }
1296
1297       template<typename _H2, typename _P2>
1298         void
1299         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1300         { merge(__source); }
1301 #endif // C++17
1302
1303       using _Base::hash_function;
1304       using _Base::key_eq;
1305
1306       iterator
1307       find(const key_type& __key)
1308       { return { _Base::find(__key), this }; }
1309
1310 #if __cplusplus > 201703L
1311       template<typename _Kt,
1312                typename = std::__has_is_transparent_t<_Hash, _Kt>,
1313                typename = std::__has_is_transparent_t<_Pred, _Kt>>
1314         iterator
1315         find(const _Kt& __k)
1316         { return { _Base::find(__k), this }; }
1317 #endif
1318
1319       const_iterator
1320       find(const key_type& __key) const
1321       { return { _Base::find(__key), this }; }
1322
1323 #if __cplusplus > 201703L
1324       template<typename _Kt,
1325                typename = std::__has_is_transparent_t<_Hash, _Kt>,
1326                typename = std::__has_is_transparent_t<_Pred, _Kt>>
1327         const_iterator
1328         find(const _Kt& __k) const
1329         { return { _Base::find(__k), this }; }
1330 #endif
1331
1332       using _Base::count;
1333 #if __cplusplus > 201703L
1334       using _Base::contains;
1335 #endif
1336
1337       std::pair<iterator, iterator>
1338       equal_range(const key_type& __key)
1339       {
1340         auto __res = _Base::equal_range(__key);
1341         return { { __res.first, this }, { __res.second, this } };
1342       }
1343
1344 #if __cplusplus > 201703L
1345       template<typename _Kt,
1346                typename = std::__has_is_transparent_t<_Hash, _Kt>,
1347                typename = std::__has_is_transparent_t<_Pred, _Kt>>
1348         std::pair<iterator, iterator>
1349         equal_range(const _Kt& __k)
1350         {
1351           auto __res = _Base::equal_range(__k);
1352           return { { __res.first, this }, { __res.second, this } };
1353         }
1354 #endif
1355
1356       std::pair<const_iterator, const_iterator>
1357       equal_range(const key_type& __key) const
1358       {
1359         auto __res = _Base::equal_range(__key);
1360         return { { __res.first, this }, { __res.second, this } };
1361       }
1362
1363 #if __cplusplus > 201703L
1364       template<typename _Kt,
1365                typename = std::__has_is_transparent_t<_Hash, _Kt>,
1366                typename = std::__has_is_transparent_t<_Pred, _Kt>>
1367         std::pair<const_iterator, const_iterator>
1368         equal_range(const _Kt& __k) const
1369         {
1370           auto __res = _Base::equal_range(__k);
1371           return { { __res.first, this }, { __res.second, this } };
1372         }
1373 #endif
1374
1375       size_type
1376       erase(const key_type& __key)
1377       {
1378         size_type __ret(0);
1379         size_type __bucket_count = this->bucket_count();
1380         auto __pair = _Base::equal_range(__key);
1381         for (auto __victim = __pair.first; __victim != __pair.second;)
1382           {
1383             _M_invalidate(__victim);
1384             __victim = _Base::erase(__victim);
1385             ++__ret;
1386           }
1387
1388         _M_check_rehashed(__bucket_count);
1389         return __ret;
1390       }
1391
1392       iterator
1393       erase(const_iterator __it)
1394       {
1395         __glibcxx_check_erase(__it);
1396         return { _M_erase(__it.base()), this };
1397       }
1398
1399       _Base_iterator
1400       erase(_Base_const_iterator __it)
1401       {
1402         __glibcxx_check_erase2(__it);
1403         return _M_erase(__it);
1404       }
1405
1406       iterator
1407       erase(iterator __it)
1408       {
1409         __glibcxx_check_erase(__it);
1410         return { _M_erase(__it.base()), this };
1411       }
1412
1413       iterator
1414       erase(const_iterator __first, const_iterator __last)
1415       {
1416         __glibcxx_check_erase_range(__first, __last);
1417         for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1418           {
1419             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1420                                   _M_message(__gnu_debug::__msg_valid_range)
1421                                   ._M_iterator(__first, "first")
1422                                   ._M_iterator(__last, "last"));
1423             _M_invalidate(__tmp);
1424           }
1425
1426         size_type __bucket_count = this->bucket_count();
1427         auto __next = _Base::erase(__first.base(), __last.base());
1428         _M_check_rehashed(__bucket_count);
1429         return { __next, this };
1430       }
1431
1432       using _Base::rehash;
1433       using _Base::reserve;
1434
1435       _Base&
1436       _M_base() noexcept { return *this; }
1437
1438       const _Base&
1439       _M_base() const noexcept { return *this; }
1440
1441     private:
1442       void
1443       _M_check_rehashed(size_type __prev_count)
1444       {
1445         if (__prev_count != this->bucket_count())
1446           this->_M_invalidate_all();
1447       }
1448
1449       void
1450       _M_invalidate(_Base_const_iterator __victim)
1451       {
1452         this->_M_invalidate_if(
1453           [__victim](_Base_const_iterator __it) { return __it == __victim; });
1454         this->_M_invalidate_local_if(
1455           [__victim](_Base_const_local_iterator __it)
1456           { return __it == __victim; });
1457       }
1458
1459       _Base_iterator
1460       _M_erase(_Base_const_iterator __victim)
1461       {
1462         _M_invalidate(__victim);
1463         size_type __bucket_count = this->bucket_count();
1464         _Base_iterator __next = _Base::erase(__victim);
1465         _M_check_rehashed(__bucket_count);
1466         return __next;
1467       }
1468
1469 #if __cplusplus > 201402L
1470       node_type
1471       _M_extract(_Base_const_iterator __victim)
1472       {
1473         _M_invalidate(__victim);
1474         return _Base::extract(__victim);
1475       }
1476 #endif
1477     };
1478
1479 #if __cpp_deduction_guides >= 201606
1480
1481   template<typename _InputIterator,
1482            typename _Hash = hash<__iter_key_t<_InputIterator>>,
1483            typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1484            typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1485            typename = _RequireInputIter<_InputIterator>,
1486            typename = _RequireNotAllocatorOrIntegral<_Hash>,
1487            typename = _RequireNotAllocator<_Pred>,
1488            typename = _RequireAllocator<_Allocator>>
1489     unordered_multimap(_InputIterator, _InputIterator,
1490                        unordered_multimap<int, int>::size_type = {},
1491                        _Hash = _Hash(), _Pred = _Pred(),
1492                        _Allocator = _Allocator())
1493     -> unordered_multimap<__iter_key_t<_InputIterator>,
1494                           __iter_val_t<_InputIterator>, _Hash, _Pred,
1495                           _Allocator>;
1496
1497   template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1498            typename _Pred = equal_to<_Key>,
1499            typename _Allocator = allocator<pair<const _Key, _Tp>>,
1500            typename = _RequireNotAllocatorOrIntegral<_Hash>,
1501            typename = _RequireNotAllocator<_Pred>,
1502            typename = _RequireAllocator<_Allocator>>
1503     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1504                        unordered_multimap<int, int>::size_type = {},
1505                        _Hash = _Hash(), _Pred = _Pred(),
1506                        _Allocator = _Allocator())
1507     -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1508
1509   template<typename _InputIterator, typename _Allocator,
1510            typename = _RequireInputIter<_InputIterator>,
1511            typename = _RequireAllocator<_Allocator>>
1512     unordered_multimap(_InputIterator, _InputIterator,
1513                        unordered_multimap<int, int>::size_type, _Allocator)
1514     -> unordered_multimap<__iter_key_t<_InputIterator>,
1515                           __iter_val_t<_InputIterator>,
1516                           hash<__iter_key_t<_InputIterator>>,
1517                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1518
1519   template<typename _InputIterator, typename _Allocator,
1520            typename = _RequireInputIter<_InputIterator>,
1521            typename = _RequireAllocator<_Allocator>>
1522     unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1523     -> unordered_multimap<__iter_key_t<_InputIterator>,
1524                           __iter_val_t<_InputIterator>,
1525                           hash<__iter_key_t<_InputIterator>>,
1526                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1527
1528   template<typename _InputIterator, typename _Hash, typename _Allocator,
1529            typename = _RequireInputIter<_InputIterator>,
1530            typename = _RequireNotAllocatorOrIntegral<_Hash>,
1531            typename = _RequireAllocator<_Allocator>>
1532     unordered_multimap(_InputIterator, _InputIterator,
1533                        unordered_multimap<int, int>::size_type, _Hash,
1534                        _Allocator)
1535     -> unordered_multimap<__iter_key_t<_InputIterator>,
1536                           __iter_val_t<_InputIterator>, _Hash,
1537                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1538
1539   template<typename _Key, typename _Tp, typename _Allocator,
1540            typename = _RequireAllocator<_Allocator>>
1541     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1542                        unordered_multimap<int, int>::size_type,
1543                        _Allocator)
1544     -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1545
1546   template<typename _Key, typename _Tp, typename _Allocator,
1547            typename = _RequireAllocator<_Allocator>>
1548     unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1549     -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1550
1551   template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1552            typename = _RequireNotAllocatorOrIntegral<_Hash>,
1553            typename = _RequireAllocator<_Allocator>>
1554     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1555                        unordered_multimap<int, int>::size_type,
1556                        _Hash, _Allocator)
1557     -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1558
1559 #endif
1560
1561   template<typename _Key, typename _Tp, typename _Hash,
1562            typename _Pred, typename _Alloc>
1563     inline void
1564     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1565          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1566     noexcept(noexcept(__x.swap(__y)))
1567     { __x.swap(__y); }
1568
1569   template<typename _Key, typename _Tp, typename _Hash,
1570            typename _Pred, typename _Alloc>
1571     inline bool
1572     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1573                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1574     { return __x._M_base() == __y._M_base(); }
1575
1576 #if __cpp_impl_three_way_comparison < 201907L
1577   template<typename _Key, typename _Tp, typename _Hash,
1578            typename _Pred, typename _Alloc>
1579     inline bool
1580     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1581                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1582     { return !(__x == __y); }
1583 #endif
1584
1585 } // namespace __debug
1586 } // namespace std
1587
1588 #endif // C++11
1589
1590 #endif