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