libstdc++-v3/include/debug/unordered_map

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