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