libstdc++-v3/include/debug/unordered_map

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