libstdc++-v3/include/debug/unordered_map

   1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2015 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 #if __cplusplus < 201103L
  33 # include <bits/c++0x_warning.h>
  34 #else
  35 # include <unordered_map>
  36
  37 #include <debug/safe_unordered_container.h>
  38 #include <debug/safe_container.h>
  39 #include <debug/safe_iterator.h>
  40 #include <debug/safe_local_iterator.h>
  41
  42 namespace std _GLIBCXX_VISIBILITY(default)
  43 {
  44 namespace __debug
  45 {
  46   /// Class std::unordered_map with safety/checking/debug instrumentation.
  47   template<typename _Key, typename _Tp,
  48            typename _Hash = std::hash<_Key>,
  49            typename _Pred = std::equal_to<_Key>,
  50            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
  51     class unordered_map
  52     : public __gnu_debug::_Safe_container<
  53         unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
  54         __gnu_debug::_Safe_unordered_container>,
  55       public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
  56     {
  57       typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
  58                                             _Pred, _Alloc>              _Base;
  59       typedef __gnu_debug::_Safe_container<unordered_map,
  60                    _Alloc, __gnu_debug::_Safe_unordered_container>      _Safe;
  61       typedef typename _Base::const_iterator    _Base_const_iterator;
  62       typedef typename _Base::iterator          _Base_iterator;
  63       typedef typename _Base::const_local_iterator
  64                                                 _Base_const_local_iterator;
  65       typedef typename _Base::local_iterator    _Base_local_iterator;
  66
  67     public:
  68       typedef typename _Base::size_type                 size_type;
  69       typedef typename _Base::hasher                    hasher;
  70       typedef typename _Base::key_equal                 key_equal;
  71       typedef typename _Base::allocator_type            allocator_type;
  72
  73       typedef typename _Base::key_type                  key_type;
  74       typedef typename _Base::value_type                value_type;
  75
  76       typedef __gnu_debug::_Safe_iterator<
  77         _Base_iterator, unordered_map>                  iterator;
  78       typedef __gnu_debug::_Safe_iterator<
  79         _Base_const_iterator, unordered_map>            const_iterator;
  80       typedef __gnu_debug::_Safe_local_iterator<
  81         _Base_local_iterator, unordered_map>            local_iterator;
  82       typedef __gnu_debug::_Safe_local_iterator<
  83         _Base_const_local_iterator, unordered_map>      const_local_iterator;
  84
  85       unordered_map() = default;
  86
  87       explicit
  88       unordered_map(size_type __n,
  89                     const hasher& __hf = hasher(),
  90                     const key_equal& __eql = key_equal(),
  91                     const allocator_type& __a = allocator_type())
  92       : _Base(__n, __hf, __eql, __a) { }
  93
  94       template<typename _InputIterator>
  95         unordered_map(_InputIterator __first, _InputIterator __last,
  96                       size_type __n = 0,
  97                       const hasher& __hf = hasher(),
  98                       const key_equal& __eql = key_equal(),
  99                       const allocator_type& __a = allocator_type())
 100         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 101                                                                      __last)),
 102                 __gnu_debug::__base(__last), __n,
 103                 __hf, __eql, __a) { }
 104
 105       unordered_map(const unordered_map&) = default;
 106
 107       unordered_map(const _Base& __x)
 108       : _Base(__x) { }
 109
 110       unordered_map(unordered_map&&) = default;
 111
 112       explicit
 113       unordered_map(const allocator_type& __a)
 114       : _Base(__a) { }
 115
 116       unordered_map(const unordered_map& __umap,
 117                     const allocator_type& __a)
 118       : _Base(__umap, __a) { }
 119
 120       unordered_map(unordered_map&& __umap,
 121                     const allocator_type& __a)
 122       : _Safe(std::move(__umap._M_safe()), __a),
 123         _Base(std::move(__umap._M_base()), __a) { }
 124
 125       unordered_map(initializer_list<value_type> __l,
 126                     size_type __n = 0,
 127                     const hasher& __hf = hasher(),
 128                     const key_equal& __eql = key_equal(),
 129                     const allocator_type& __a = allocator_type())
 130       : _Base(__l, __n, __hf, __eql, __a) { }
 131
 132       unordered_map(size_type __n, const allocator_type& __a)
 133       : unordered_map(__n, hasher(), key_equal(), __a)
 134       { }
 135
 136       unordered_map(size_type __n,
 137                     const hasher& __hf,
 138                     const allocator_type& __a)
 139       : unordered_map(__n, __hf, key_equal(), __a)
 140       { }
 141
 142       template<typename _InputIterator>
 143         unordered_map(_InputIterator __first, _InputIterator __last,
 144                       size_type __n,
 145                       const allocator_type& __a)
 146           : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
 147         { }
 148
 149       template<typename _InputIterator>
 150         unordered_map(_InputIterator __first, _InputIterator __last,
 151                       size_type __n,
 152                       const hasher& __hf,
 153                       const allocator_type& __a)
 154           : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
 155         { }
 156
 157       unordered_map(initializer_list<value_type> __l,
 158                     size_type __n,
 159                     const allocator_type& __a)
 160         : unordered_map(__l, __n, hasher(), key_equal(), __a)
 161       { }
 162
 163       unordered_map(initializer_list<value_type> __l,
 164                     size_type __n,
 165                     const hasher& __hf,
 166                     const allocator_type& __a)
 167         : unordered_map(__l, __n, __hf, key_equal(), __a)
 168       { }
 169
 170       ~unordered_map() = default;
 171
 172       unordered_map&
 173       operator=(const unordered_map&) = default;
 174
 175       unordered_map&
 176       operator=(unordered_map&&) = default;
 177
 178       unordered_map&
 179       operator=(initializer_list<value_type> __l)
 180       {
 181         _M_base() = __l;
 182         this->_M_invalidate_all();
 183         return *this;
 184       }
 185
 186       void
 187       swap(unordered_map& __x)
 188         noexcept( noexcept(declval<_Base&>().swap(__x)) )
 189       {
 190         _Safe::_M_swap(__x);
 191         _Base::swap(__x);
 192       }
 193
 194       void
 195       clear() noexcept
 196       {
 197         _Base::clear();
 198         this->_M_invalidate_all();
 199       }
 200
 201       iterator
 202       begin() noexcept
 203       { return iterator(_Base::begin(), this); }
 204
 205       const_iterator
 206       begin() const noexcept
 207       { return const_iterator(_Base::begin(), this); }
 208
 209       iterator
 210       end() noexcept
 211       { return iterator(_Base::end(), this); }
 212
 213       const_iterator
 214       end() const noexcept
 215       { return const_iterator(_Base::end(), this); }
 216
 217       const_iterator
 218       cbegin() const noexcept
 219       { return const_iterator(_Base::begin(), this); }
 220
 221       const_iterator
 222       cend() const noexcept
 223       { return const_iterator(_Base::end(), this); }
 224
 225       // local versions
 226       local_iterator
 227       begin(size_type __b)
 228       {
 229         __glibcxx_check_bucket_index(__b);
 230         return local_iterator(_Base::begin(__b), this);
 231       }
 232
 233       local_iterator
 234       end(size_type __b)
 235       {
 236         __glibcxx_check_bucket_index(__b);
 237         return local_iterator(_Base::end(__b), this);
 238       }
 239
 240       const_local_iterator
 241       begin(size_type __b) const
 242       {
 243         __glibcxx_check_bucket_index(__b);
 244         return const_local_iterator(_Base::begin(__b), this);
 245       }
 246
 247       const_local_iterator
 248       end(size_type __b) const
 249       {
 250         __glibcxx_check_bucket_index(__b);
 251         return const_local_iterator(_Base::end(__b), this);
 252       }
 253
 254       const_local_iterator
 255       cbegin(size_type __b) const
 256       {
 257         __glibcxx_check_bucket_index(__b);
 258         return const_local_iterator(_Base::cbegin(__b), this);
 259       }
 260
 261       const_local_iterator
 262       cend(size_type __b) const
 263       {
 264         __glibcxx_check_bucket_index(__b);
 265         return const_local_iterator(_Base::cend(__b), this);
 266       }
 267
 268       size_type
 269       bucket_size(size_type __b) const
 270       {
 271         __glibcxx_check_bucket_index(__b);
 272         return _Base::bucket_size(__b);
 273       }
 274
 275       float
 276       max_load_factor() const noexcept
 277       { return _Base::max_load_factor(); }
 278
 279       void
 280       max_load_factor(float __f)
 281       {
 282         __glibcxx_check_max_load_factor(__f);
 283         _Base::max_load_factor(__f);
 284       }
 285
 286       template<typename... _Args>
 287         std::pair<iterator, bool>
 288         emplace(_Args&&... __args)
 289         {
 290           size_type __bucket_count = this->bucket_count();
 291           std::pair<_Base_iterator, bool> __res
 292             = _Base::emplace(std::forward<_Args>(__args)...);
 293           _M_check_rehashed(__bucket_count);
 294           return std::make_pair(iterator(__res.first, this), __res.second);
 295         }
 296
 297       template<typename... _Args>
 298         iterator
 299         emplace_hint(const_iterator __hint, _Args&&... __args)
 300         {
 301           __glibcxx_check_insert(__hint);
 302           size_type __bucket_count = this->bucket_count();
 303           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 304                                         std::forward<_Args>(__args)...);
 305           _M_check_rehashed(__bucket_count);
 306           return iterator(__it, this);
 307         }
 308
 309       std::pair<iterator, bool>
 310       insert(const value_type& __obj)
 311       {
 312         size_type __bucket_count = this->bucket_count();
 313         std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
 314         _M_check_rehashed(__bucket_count);
 315         return std::make_pair(iterator(__res.first, this), __res.second);
 316       }
 317
 318       iterator
 319       insert(const_iterator __hint, const value_type& __obj)
 320       {
 321         __glibcxx_check_insert(__hint);
 322         size_type __bucket_count = this->bucket_count();
 323         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 324         _M_check_rehashed(__bucket_count);
 325         return iterator(__it, this);
 326       }
 327
 328       template<typename _Pair, typename = typename
 329                std::enable_if<std::is_constructible<value_type,
 330                                                     _Pair&&>::value>::type>
 331         std::pair<iterator, bool>
 332         insert(_Pair&& __obj)
 333         {
 334           size_type __bucket_count = this->bucket_count();
 335           std::pair<_Base_iterator, bool> __res =
 336             _Base::insert(std::forward<_Pair>(__obj));
 337           _M_check_rehashed(__bucket_count);
 338           return std::make_pair(iterator(__res.first, this), __res.second);
 339         }
 340
 341       template<typename _Pair, typename = typename
 342                std::enable_if<std::is_constructible<value_type,
 343                                                     _Pair&&>::value>::type>
 344         iterator
 345         insert(const_iterator __hint, _Pair&& __obj)
 346         {
 347           __glibcxx_check_insert(__hint);
 348           size_type __bucket_count = this->bucket_count();
 349           _Base_iterator __it =
 350             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
 351           _M_check_rehashed(__bucket_count);
 352           return iterator(__it, this);
 353         }
 354
 355       void
 356       insert(std::initializer_list<value_type> __l)
 357       {
 358         size_type __bucket_count = this->bucket_count();
 359         _Base::insert(__l);
 360         _M_check_rehashed(__bucket_count);
 361       }
 362
 363       template<typename _InputIterator>
 364         void
 365         insert(_InputIterator __first, _InputIterator __last)
 366         {
 367           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 368           __glibcxx_check_valid_range2(__first, __last, __dist);
 369           size_type __bucket_count = this->bucket_count();
 370
 371           if (__dist.second >= __gnu_debug::__dp_sign)
 372             _Base::insert(__gnu_debug::__unsafe(__first),
 373                           __gnu_debug::__unsafe(__last));
 374           else
 375             _Base::insert(__first, __last);
 376
 377           _M_check_rehashed(__bucket_count);
 378         }
 379
 380       iterator
 381       find(const key_type& __key)
 382       { return iterator(_Base::find(__key), this); }
 383
 384       const_iterator
 385       find(const key_type& __key) const
 386       { return const_iterator(_Base::find(__key), this); }
 387
 388       std::pair<iterator, iterator>
 389       equal_range(const key_type& __key)
 390       {
 391         std::pair<_Base_iterator, _Base_iterator> __res =
 392           _Base::equal_range(__key);
 393         return std::make_pair(iterator(__res.first, this),
 394                               iterator(__res.second, this));
 395       }
 396
 397       std::pair<const_iterator, const_iterator>
 398       equal_range(const key_type& __key) const
 399       {
 400         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 401           _Base::equal_range(__key);
 402         return std::make_pair(const_iterator(__res.first, this),
 403                               const_iterator(__res.second, this));
 404       }
 405
 406       size_type
 407       erase(const key_type& __key)
 408       {
 409         size_type __ret(0);
 410         _Base_iterator __victim(_Base::find(__key));
 411         if (__victim != _Base::end())
 412           {
 413             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 414                             { return __it == __victim; });
 415             this->_M_invalidate_local_if(
 416                             [__victim](_Base_const_local_iterator __it)
 417                             { return __it._M_curr() == __victim._M_cur; });
 418             size_type __bucket_count = this->bucket_count();
 419             _Base::erase(__victim);
 420             _M_check_rehashed(__bucket_count);
 421             __ret = 1;
 422           }
 423         return __ret;
 424       }
 425
 426       iterator
 427       erase(const_iterator __it)
 428       {
 429         __glibcxx_check_erase(__it);
 430         _Base_const_iterator __victim = __it.base();
 431         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 432                         { return __it == __victim; });
 433         this->_M_invalidate_local_if(
 434                         [__victim](_Base_const_local_iterator __it)
 435                         { return __it._M_curr() == __victim._M_cur; });
 436         size_type __bucket_count = this->bucket_count();
 437         _Base_iterator __next = _Base::erase(__it.base());
 438         _M_check_rehashed(__bucket_count);
 439         return iterator(__next, this);
 440       }
 441
 442       iterator
 443       erase(iterator __it)
 444       { return erase(const_iterator(__it)); }
 445
 446       iterator
 447       erase(const_iterator __first, const_iterator __last)
 448       {
 449         __glibcxx_check_erase_range(__first, __last);
 450         for (_Base_const_iterator __tmp = __first.base();
 451              __tmp != __last.base(); ++__tmp)
 452           {
 453             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 454                                   _M_message(__gnu_debug::__msg_valid_range)
 455                                   ._M_iterator(__first, "first")
 456                                   ._M_iterator(__last, "last"));
 457             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
 458                             { return __it == __tmp; });
 459             this->_M_invalidate_local_if(
 460                             [__tmp](_Base_const_local_iterator __it)
 461                             { return __it._M_curr() == __tmp._M_cur; });
 462           }
 463         size_type __bucket_count = this->bucket_count();
 464         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
 465         _M_check_rehashed(__bucket_count);
 466         return iterator(__next, this);
 467       }
 468
 469       _Base&
 470       _M_base() noexcept        { return *this; }
 471
 472       const _Base&
 473       _M_base() const noexcept  { return *this; }
 474
 475     private:
 476       void
 477       _M_check_rehashed(size_type __prev_count)
 478       {
 479         if (__prev_count != this->bucket_count())
 480           this->_M_invalidate_locals();
 481       }
 482     };
 483
 484   template<typename _Key, typename _Tp, typename _Hash,
 485            typename _Pred, typename _Alloc>
 486     inline void
 487     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 488          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 489     noexcept(noexcept(__x.swap(__y)))
 490     { __x.swap(__y); }
 491
 492   template<typename _Key, typename _Tp, typename _Hash,
 493            typename _Pred, typename _Alloc>
 494     inline bool
 495     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 496                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 497     { return __x._M_base() == __y._M_base(); }
 498
 499   template<typename _Key, typename _Tp, typename _Hash,
 500            typename _Pred, typename _Alloc>
 501     inline bool
 502     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 503                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 504     { return !(__x == __y); }
 505
 506
 507   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
 508   template<typename _Key, typename _Tp,
 509            typename _Hash = std::hash<_Key>,
 510            typename _Pred = std::equal_to<_Key>,
 511            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
 512     class unordered_multimap
 513       : public __gnu_debug::_Safe_container<
 514         unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
 515         __gnu_debug::_Safe_unordered_container>,
 516         public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
 517     {
 518       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
 519                                                  _Pred, _Alloc>         _Base;
 520       typedef __gnu_debug::_Safe_container<unordered_multimap,
 521         _Alloc, __gnu_debug::_Safe_unordered_container>                 _Safe;
 522       typedef typename _Base::const_iterator       _Base_const_iterator;
 523       typedef typename _Base::iterator             _Base_iterator;
 524       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
 525       typedef typename _Base::local_iterator       _Base_local_iterator;
 526
 527     public:
 528       typedef typename _Base::size_type                 size_type;
 529       typedef typename _Base::hasher                    hasher;
 530       typedef typename _Base::key_equal                 key_equal;
 531       typedef typename _Base::allocator_type            allocator_type;
 532
 533       typedef typename _Base::key_type                  key_type;
 534       typedef typename _Base::value_type                value_type;
 535
 536       typedef __gnu_debug::_Safe_iterator<
 537         _Base_iterator, unordered_multimap>             iterator;
 538       typedef __gnu_debug::_Safe_iterator<
 539         _Base_const_iterator, unordered_multimap>       const_iterator;
 540       typedef __gnu_debug::_Safe_local_iterator<
 541         _Base_local_iterator, unordered_multimap>       local_iterator;
 542       typedef __gnu_debug::_Safe_local_iterator<
 543         _Base_const_local_iterator, unordered_multimap> const_local_iterator;
 544
 545       unordered_multimap() = default;
 546
 547       explicit
 548       unordered_multimap(size_type __n,
 549                          const hasher& __hf = hasher(),
 550                          const key_equal& __eql = key_equal(),
 551                          const allocator_type& __a = allocator_type())
 552       : _Base(__n, __hf, __eql, __a) { }
 553
 554       template<typename _InputIterator>
 555         unordered_multimap(_InputIterator __first, _InputIterator __last,
 556                            size_type __n = 0,
 557                            const hasher& __hf = hasher(),
 558                            const key_equal& __eql = key_equal(),
 559                            const allocator_type& __a = allocator_type())
 560         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 561                                                                      __last)),
 562                 __gnu_debug::__base(__last), __n,
 563                 __hf, __eql, __a) { }
 564
 565       unordered_multimap(const unordered_multimap&) = default;
 566
 567       unordered_multimap(const _Base& __x)
 568       : _Base(__x) { }
 569
 570       unordered_multimap(unordered_multimap&&) = default;
 571
 572       explicit
 573       unordered_multimap(const allocator_type& __a)
 574       : _Base(__a) { }
 575
 576       unordered_multimap(const unordered_multimap& __umap,
 577                          const allocator_type& __a)
 578       : _Base(__umap, __a) { }
 579
 580       unordered_multimap(unordered_multimap&& __umap,
 581                          const allocator_type& __a)
 582       : _Safe(std::move(__umap._M_safe()), __a),
 583         _Base(std::move(__umap._M_base()), __a) { }
 584
 585       unordered_multimap(initializer_list<value_type> __l,
 586                          size_type __n = 0,
 587                          const hasher& __hf = hasher(),
 588                          const key_equal& __eql = key_equal(),
 589                          const allocator_type& __a = allocator_type())
 590       : _Base(__l, __n, __hf, __eql, __a) { }
 591
 592       unordered_multimap(size_type __n, const allocator_type& __a)
 593       : unordered_multimap(__n, hasher(), key_equal(), __a)
 594       { }
 595
 596       unordered_multimap(size_type __n, const hasher& __hf,
 597                          const allocator_type& __a)
 598       : unordered_multimap(__n, __hf, key_equal(), __a)
 599       { }
 600
 601       template<typename _InputIterator>
 602         unordered_multimap(_InputIterator __first, _InputIterator __last,
 603                            size_type __n,
 604                            const allocator_type& __a)
 605           : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
 606         { }
 607
 608       template<typename _InputIterator>
 609         unordered_multimap(_InputIterator __first, _InputIterator __last,
 610                            size_type __n, const hasher& __hf,
 611                            const allocator_type& __a)
 612           : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
 613         { }
 614
 615       unordered_multimap(initializer_list<value_type> __l,
 616                          size_type __n,
 617                          const allocator_type& __a)
 618         : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
 619       { }
 620
 621       unordered_multimap(initializer_list<value_type> __l,
 622                          size_type __n, const hasher& __hf,
 623                          const allocator_type& __a)
 624         : unordered_multimap(__l, __n, __hf, key_equal(), __a)
 625       { }
 626
 627       ~unordered_multimap() = default;
 628
 629       unordered_multimap&
 630       operator=(const unordered_multimap&) = default;
 631
 632       unordered_multimap&
 633       operator=(unordered_multimap&&) = default;
 634
 635       unordered_multimap&
 636       operator=(initializer_list<value_type> __l)
 637       {
 638         this->_M_base() = __l;
 639         this->_M_invalidate_all();
 640         return *this;
 641       }
 642
 643       void
 644       swap(unordered_multimap& __x)
 645         noexcept( noexcept(declval<_Base&>().swap(__x)) )
 646       {
 647         _Safe::_M_swap(__x);
 648         _Base::swap(__x);
 649       }
 650
 651       void
 652       clear() noexcept
 653       {
 654         _Base::clear();
 655         this->_M_invalidate_all();
 656       }
 657
 658       iterator
 659       begin() noexcept
 660       { return iterator(_Base::begin(), this); }
 661
 662       const_iterator
 663       begin() const noexcept
 664       { return const_iterator(_Base::begin(), this); }
 665
 666       iterator
 667       end() noexcept
 668       { return iterator(_Base::end(), this); }
 669
 670       const_iterator
 671       end() const noexcept
 672       { return const_iterator(_Base::end(), this); }
 673
 674       const_iterator
 675       cbegin() const noexcept
 676       { return const_iterator(_Base::begin(), this); }
 677
 678       const_iterator
 679       cend() const noexcept
 680       { return const_iterator(_Base::end(), this); }
 681
 682       // local versions
 683       local_iterator
 684       begin(size_type __b)
 685       {
 686         __glibcxx_check_bucket_index(__b);
 687         return local_iterator(_Base::begin(__b), this);
 688       }
 689
 690       local_iterator
 691       end(size_type __b)
 692       {
 693         __glibcxx_check_bucket_index(__b);
 694         return local_iterator(_Base::end(__b), this);
 695       }
 696
 697       const_local_iterator
 698       begin(size_type __b) const
 699       {
 700         __glibcxx_check_bucket_index(__b);
 701         return const_local_iterator(_Base::begin(__b), this);
 702       }
 703
 704       const_local_iterator
 705       end(size_type __b) const
 706       {
 707         __glibcxx_check_bucket_index(__b);
 708         return const_local_iterator(_Base::end(__b), this);
 709       }
 710
 711       const_local_iterator
 712       cbegin(size_type __b) const
 713       {
 714         __glibcxx_check_bucket_index(__b);
 715         return const_local_iterator(_Base::cbegin(__b), this);
 716       }
 717
 718       const_local_iterator
 719       cend(size_type __b) const
 720       {
 721         __glibcxx_check_bucket_index(__b);
 722         return const_local_iterator(_Base::cend(__b), this);
 723       }
 724
 725       size_type
 726       bucket_size(size_type __b) const
 727       {
 728         __glibcxx_check_bucket_index(__b);
 729         return _Base::bucket_size(__b);
 730       }
 731
 732       float
 733       max_load_factor() const noexcept
 734       { return _Base::max_load_factor(); }
 735
 736       void
 737       max_load_factor(float __f)
 738       {
 739         __glibcxx_check_max_load_factor(__f);
 740         _Base::max_load_factor(__f);
 741       }
 742
 743       template<typename... _Args>
 744         iterator
 745         emplace(_Args&&... __args)
 746         {
 747           size_type __bucket_count = this->bucket_count();
 748           _Base_iterator __it
 749             = _Base::emplace(std::forward<_Args>(__args)...);
 750           _M_check_rehashed(__bucket_count);
 751           return iterator(__it, this);
 752         }
 753
 754       template<typename... _Args>
 755         iterator
 756         emplace_hint(const_iterator __hint, _Args&&... __args)
 757         {
 758           __glibcxx_check_insert(__hint);
 759           size_type __bucket_count = this->bucket_count();
 760           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 761                                         std::forward<_Args>(__args)...);
 762           _M_check_rehashed(__bucket_count);
 763           return iterator(__it, this);
 764         }
 765
 766       iterator
 767       insert(const value_type& __obj)
 768       {
 769         size_type __bucket_count = this->bucket_count();
 770         _Base_iterator __it = _Base::insert(__obj);
 771         _M_check_rehashed(__bucket_count);
 772         return iterator(__it, this);
 773       }
 774
 775       iterator
 776       insert(const_iterator __hint, const value_type& __obj)
 777       {
 778         __glibcxx_check_insert(__hint);
 779         size_type __bucket_count = this->bucket_count();
 780         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 781         _M_check_rehashed(__bucket_count);
 782         return iterator(__it, this);
 783       }
 784
 785       template<typename _Pair, typename = typename
 786                std::enable_if<std::is_constructible<value_type,
 787                                                     _Pair&&>::value>::type>
 788         iterator
 789         insert(_Pair&& __obj)
 790         {
 791           size_type __bucket_count = this->bucket_count();
 792           _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
 793           _M_check_rehashed(__bucket_count);
 794           return iterator(__it, this);
 795         }
 796
 797       template<typename _Pair, typename = typename
 798                std::enable_if<std::is_constructible<value_type,
 799                                                     _Pair&&>::value>::type>
 800         iterator
 801         insert(const_iterator __hint, _Pair&& __obj)
 802         {
 803           __glibcxx_check_insert(__hint);
 804           size_type __bucket_count = this->bucket_count();
 805           _Base_iterator __it =
 806             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
 807           _M_check_rehashed(__bucket_count);
 808           return iterator(__it, this);
 809         }
 810
 811       void
 812       insert(std::initializer_list<value_type> __l)
 813       { _Base::insert(__l); }
 814
 815       template<typename _InputIterator>
 816         void
 817         insert(_InputIterator __first, _InputIterator __last)
 818         {
 819           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 820           __glibcxx_check_valid_range2(__first, __last, __dist);
 821           size_type __bucket_count = this->bucket_count();
 822
 823           if (__dist.second >= __gnu_debug::__dp_sign)
 824             _Base::insert(__gnu_debug::__unsafe(__first),
 825                           __gnu_debug::__unsafe(__last));
 826           else
 827             _Base::insert(__first, __last);
 828
 829           _M_check_rehashed(__bucket_count);
 830         }
 831
 832       iterator
 833       find(const key_type& __key)
 834       { return iterator(_Base::find(__key), this); }
 835
 836       const_iterator
 837       find(const key_type& __key) const
 838       { return const_iterator(_Base::find(__key), this); }
 839
 840       std::pair<iterator, iterator>
 841       equal_range(const key_type& __key)
 842       {
 843         std::pair<_Base_iterator, _Base_iterator> __res =
 844           _Base::equal_range(__key);
 845         return std::make_pair(iterator(__res.first, this),
 846                               iterator(__res.second, this));
 847       }
 848
 849       std::pair<const_iterator, const_iterator>
 850       equal_range(const key_type& __key) const
 851       {
 852         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 853           _Base::equal_range(__key);
 854         return std::make_pair(const_iterator(__res.first, this),
 855                               const_iterator(__res.second, this));
 856       }
 857
 858       size_type
 859       erase(const key_type& __key)
 860       {
 861         size_type __ret(0);
 862         size_type __bucket_count = this->bucket_count();
 863         std::pair<_Base_iterator, _Base_iterator> __pair =
 864           _Base::equal_range(__key);
 865         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
 866           {
 867             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 868                             { return __it == __victim; });
 869             this->_M_invalidate_local_if(
 870                             [__victim](_Base_const_local_iterator __it)
 871                             { return __it._M_curr() == __victim._M_cur; });
 872             _Base::erase(__victim++);
 873             ++__ret;
 874           }
 875         _M_check_rehashed(__bucket_count);
 876         return __ret;
 877       }
 878
 879       iterator
 880       erase(const_iterator __it)
 881       {
 882         __glibcxx_check_erase(__it);
 883         _Base_const_iterator __victim = __it.base();
 884         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 885                         { return __it == __victim; });
 886         this->_M_invalidate_local_if(
 887                         [__victim](_Base_const_local_iterator __it)
 888                         { return __it._M_curr() == __victim._M_cur; });
 889         size_type __bucket_count = this->bucket_count();
 890         _Base_iterator __next = _Base::erase(__it.base());
 891         _M_check_rehashed(__bucket_count);
 892         return iterator(__next, this);
 893       }
 894
 895       iterator
 896       erase(iterator __it)
 897       { return erase(const_iterator(__it)); }
 898
 899       iterator
 900       erase(const_iterator __first, const_iterator __last)
 901       {
 902         __glibcxx_check_erase_range(__first, __last);
 903         for (_Base_const_iterator __tmp = __first.base();
 904              __tmp != __last.base(); ++__tmp)
 905           {
 906             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 907                                   _M_message(__gnu_debug::__msg_valid_range)
 908                                   ._M_iterator(__first, "first")
 909                                   ._M_iterator(__last, "last"));
 910             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
 911                             { return __it == __tmp; });
 912             this->_M_invalidate_local_if(
 913                             [__tmp](_Base_const_local_iterator __it)
 914                             { return __it._M_curr() == __tmp._M_cur; });
 915           }
 916         size_type __bucket_count = this->bucket_count();
 917         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
 918         _M_check_rehashed(__bucket_count);
 919         return iterator(__next, this);
 920       }
 921
 922       _Base&
 923       _M_base() noexcept { return *this; }
 924
 925       const _Base&
 926       _M_base() const noexcept { return *this; }
 927
 928     private:
 929       void
 930       _M_check_rehashed(size_type __prev_count)
 931       {
 932         if (__prev_count != this->bucket_count())
 933           this->_M_invalidate_locals();
 934       }
 935     };
 936
 937   template<typename _Key, typename _Tp, typename _Hash,
 938            typename _Pred, typename _Alloc>
 939     inline void
 940     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 941          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 942     noexcept(noexcept(__x.swap(__y)))
 943     { __x.swap(__y); }
 944
 945   template<typename _Key, typename _Tp, typename _Hash,
 946            typename _Pred, typename _Alloc>
 947     inline bool
 948     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 949                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 950     { return __x._M_base() == __y._M_base(); }
 951
 952   template<typename _Key, typename _Tp, typename _Hash,
 953            typename _Pred, typename _Alloc>
 954     inline bool
 955     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 956                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 957     { return !(__x == __y); }
 958
 959 } // namespace __debug
 960 } // namespace std
 961
 962 #endif // C++11
 963
 964 #endif