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     { __x.swap(__y); }
 490
 491   template<typename _Key, typename _Tp, typename _Hash,
 492            typename _Pred, typename _Alloc>
 493     inline bool
 494     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 495                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 496     { return __x._M_base() == __y._M_base(); }
 497
 498   template<typename _Key, typename _Tp, typename _Hash,
 499            typename _Pred, typename _Alloc>
 500     inline bool
 501     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 502                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 503     { return !(__x == __y); }
 504
 505
 506   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
 507   template<typename _Key, typename _Tp,
 508            typename _Hash = std::hash<_Key>,
 509            typename _Pred = std::equal_to<_Key>,
 510            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
 511     class unordered_multimap
 512       : public __gnu_debug::_Safe_container<
 513         unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
 514         __gnu_debug::_Safe_unordered_container>,
 515         public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
 516     {
 517       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
 518                                                  _Pred, _Alloc>         _Base;
 519       typedef __gnu_debug::_Safe_container<unordered_multimap,
 520         _Alloc, __gnu_debug::_Safe_unordered_container>                 _Safe;
 521       typedef typename _Base::const_iterator       _Base_const_iterator;
 522       typedef typename _Base::iterator             _Base_iterator;
 523       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
 524       typedef typename _Base::local_iterator       _Base_local_iterator;
 525
 526     public:
 527       typedef typename _Base::size_type                 size_type;
 528       typedef typename _Base::hasher                    hasher;
 529       typedef typename _Base::key_equal                 key_equal;
 530       typedef typename _Base::allocator_type            allocator_type;
 531
 532       typedef typename _Base::key_type                  key_type;
 533       typedef typename _Base::value_type                value_type;
 534
 535       typedef __gnu_debug::_Safe_iterator<
 536         _Base_iterator, unordered_multimap>             iterator;
 537       typedef __gnu_debug::_Safe_iterator<
 538         _Base_const_iterator, unordered_multimap>       const_iterator;
 539       typedef __gnu_debug::_Safe_local_iterator<
 540         _Base_local_iterator, unordered_multimap>       local_iterator;
 541       typedef __gnu_debug::_Safe_local_iterator<
 542         _Base_const_local_iterator, unordered_multimap> const_local_iterator;
 543
 544       unordered_multimap() = default;
 545
 546       explicit
 547       unordered_multimap(size_type __n,
 548                          const hasher& __hf = hasher(),
 549                          const key_equal& __eql = key_equal(),
 550                          const allocator_type& __a = allocator_type())
 551       : _Base(__n, __hf, __eql, __a) { }
 552
 553       template<typename _InputIterator>
 554         unordered_multimap(_InputIterator __first, _InputIterator __last,
 555                            size_type __n = 0,
 556                            const hasher& __hf = hasher(),
 557                            const key_equal& __eql = key_equal(),
 558                            const allocator_type& __a = allocator_type())
 559         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 560                                                                      __last)),
 561                 __gnu_debug::__base(__last), __n,
 562                 __hf, __eql, __a) { }
 563
 564       unordered_multimap(const unordered_multimap&) = default;
 565
 566       unordered_multimap(const _Base& __x)
 567       : _Base(__x) { }
 568
 569       unordered_multimap(unordered_multimap&&) = default;
 570
 571       explicit
 572       unordered_multimap(const allocator_type& __a)
 573       : _Base(__a) { }
 574
 575       unordered_multimap(const unordered_multimap& __umap,
 576                          const allocator_type& __a)
 577       : _Base(__umap, __a) { }
 578
 579       unordered_multimap(unordered_multimap&& __umap,
 580                          const allocator_type& __a)
 581       : _Safe(std::move(__umap._M_safe()), __a),
 582         _Base(std::move(__umap._M_base()), __a) { }
 583
 584       unordered_multimap(initializer_list<value_type> __l,
 585                          size_type __n = 0,
 586                          const hasher& __hf = hasher(),
 587                          const key_equal& __eql = key_equal(),
 588                          const allocator_type& __a = allocator_type())
 589       : _Base(__l, __n, __hf, __eql, __a) { }
 590
 591       unordered_multimap(size_type __n, const allocator_type& __a)
 592       : unordered_multimap(__n, hasher(), key_equal(), __a)
 593       { }
 594
 595       unordered_multimap(size_type __n, const hasher& __hf,
 596                          const allocator_type& __a)
 597       : unordered_multimap(__n, __hf, key_equal(), __a)
 598       { }
 599
 600       template<typename _InputIterator>
 601         unordered_multimap(_InputIterator __first, _InputIterator __last,
 602                            size_type __n,
 603                            const allocator_type& __a)
 604           : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
 605         { }
 606
 607       template<typename _InputIterator>
 608         unordered_multimap(_InputIterator __first, _InputIterator __last,
 609                            size_type __n, const hasher& __hf,
 610                            const allocator_type& __a)
 611           : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
 612         { }
 613
 614       unordered_multimap(initializer_list<value_type> __l,
 615                          size_type __n,
 616                          const allocator_type& __a)
 617         : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
 618       { }
 619
 620       unordered_multimap(initializer_list<value_type> __l,
 621                          size_type __n, const hasher& __hf,
 622                          const allocator_type& __a)
 623         : unordered_multimap(__l, __n, __hf, key_equal(), __a)
 624       { }
 625
 626       ~unordered_multimap() = default;
 627
 628       unordered_multimap&
 629       operator=(const unordered_multimap&) = default;
 630
 631       unordered_multimap&
 632       operator=(unordered_multimap&&) = default;
 633
 634       unordered_multimap&
 635       operator=(initializer_list<value_type> __l)
 636       {
 637         this->_M_base() = __l;
 638         this->_M_invalidate_all();
 639         return *this;
 640       }
 641
 642       void
 643       swap(unordered_multimap& __x)
 644         noexcept( noexcept(declval<_Base>().swap(__x)) )
 645       {
 646         _Safe::_M_swap(__x);
 647         _Base::swap(__x);
 648       }
 649
 650       void
 651       clear() noexcept
 652       {
 653         _Base::clear();
 654         this->_M_invalidate_all();
 655       }
 656
 657       iterator
 658       begin() noexcept
 659       { return iterator(_Base::begin(), this); }
 660
 661       const_iterator
 662       begin() const noexcept
 663       { return const_iterator(_Base::begin(), this); }
 664
 665       iterator
 666       end() noexcept
 667       { return iterator(_Base::end(), this); }
 668
 669       const_iterator
 670       end() const noexcept
 671       { return const_iterator(_Base::end(), this); }
 672
 673       const_iterator
 674       cbegin() const noexcept
 675       { return const_iterator(_Base::begin(), this); }
 676
 677       const_iterator
 678       cend() const noexcept
 679       { return const_iterator(_Base::end(), this); }
 680
 681       // local versions
 682       local_iterator
 683       begin(size_type __b)
 684       {
 685         __glibcxx_check_bucket_index(__b);
 686         return local_iterator(_Base::begin(__b), this);
 687       }
 688
 689       local_iterator
 690       end(size_type __b)
 691       {
 692         __glibcxx_check_bucket_index(__b);
 693         return local_iterator(_Base::end(__b), this);
 694       }
 695
 696       const_local_iterator
 697       begin(size_type __b) const
 698       {
 699         __glibcxx_check_bucket_index(__b);
 700         return const_local_iterator(_Base::begin(__b), this);
 701       }
 702
 703       const_local_iterator
 704       end(size_type __b) const
 705       {
 706         __glibcxx_check_bucket_index(__b);
 707         return const_local_iterator(_Base::end(__b), this);
 708       }
 709
 710       const_local_iterator
 711       cbegin(size_type __b) const
 712       {
 713         __glibcxx_check_bucket_index(__b);
 714         return const_local_iterator(_Base::cbegin(__b), this);
 715       }
 716
 717       const_local_iterator
 718       cend(size_type __b) const
 719       {
 720         __glibcxx_check_bucket_index(__b);
 721         return const_local_iterator(_Base::cend(__b), this);
 722       }
 723
 724       size_type
 725       bucket_size(size_type __b) const
 726       {
 727         __glibcxx_check_bucket_index(__b);
 728         return _Base::bucket_size(__b);
 729       }
 730
 731       float
 732       max_load_factor() const noexcept
 733       { return _Base::max_load_factor(); }
 734
 735       void
 736       max_load_factor(float __f)
 737       {
 738         __glibcxx_check_max_load_factor(__f);
 739         _Base::max_load_factor(__f);
 740       }
 741
 742       template<typename... _Args>
 743         iterator
 744         emplace(_Args&&... __args)
 745         {
 746           size_type __bucket_count = this->bucket_count();
 747           _Base_iterator __it
 748             = _Base::emplace(std::forward<_Args>(__args)...);
 749           _M_check_rehashed(__bucket_count);
 750           return iterator(__it, this);
 751         }
 752
 753       template<typename... _Args>
 754         iterator
 755         emplace_hint(const_iterator __hint, _Args&&... __args)
 756         {
 757           __glibcxx_check_insert(__hint);
 758           size_type __bucket_count = this->bucket_count();
 759           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 760                                         std::forward<_Args>(__args)...);
 761           _M_check_rehashed(__bucket_count);
 762           return iterator(__it, this);
 763         }
 764
 765       iterator
 766       insert(const value_type& __obj)
 767       {
 768         size_type __bucket_count = this->bucket_count();
 769         _Base_iterator __it = _Base::insert(__obj);
 770         _M_check_rehashed(__bucket_count);
 771         return iterator(__it, this);
 772       }
 773
 774       iterator
 775       insert(const_iterator __hint, const value_type& __obj)
 776       {
 777         __glibcxx_check_insert(__hint);
 778         size_type __bucket_count = this->bucket_count();
 779         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 780         _M_check_rehashed(__bucket_count);
 781         return iterator(__it, this);
 782       }
 783
 784       template<typename _Pair, typename = typename
 785                std::enable_if<std::is_constructible<value_type,
 786                                                     _Pair&&>::value>::type>
 787         iterator
 788         insert(_Pair&& __obj)
 789         {
 790           size_type __bucket_count = this->bucket_count();
 791           _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
 792           _M_check_rehashed(__bucket_count);
 793           return iterator(__it, this);
 794         }
 795
 796       template<typename _Pair, typename = typename
 797                std::enable_if<std::is_constructible<value_type,
 798                                                     _Pair&&>::value>::type>
 799         iterator
 800         insert(const_iterator __hint, _Pair&& __obj)
 801         {
 802           __glibcxx_check_insert(__hint);
 803           size_type __bucket_count = this->bucket_count();
 804           _Base_iterator __it =
 805             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
 806           _M_check_rehashed(__bucket_count);
 807           return iterator(__it, this);
 808         }
 809
 810       void
 811       insert(std::initializer_list<value_type> __l)
 812       { _Base::insert(__l); }
 813
 814       template<typename _InputIterator>
 815         void
 816         insert(_InputIterator __first, _InputIterator __last)
 817         {
 818           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 819           __glibcxx_check_valid_range2(__first, __last, __dist);
 820           size_type __bucket_count = this->bucket_count();
 821
 822           if (__dist.second >= __gnu_debug::__dp_sign)
 823             _Base::insert(__gnu_debug::__unsafe(__first),
 824                           __gnu_debug::__unsafe(__last));
 825           else
 826             _Base::insert(__first, __last);
 827
 828           _M_check_rehashed(__bucket_count);
 829         }
 830
 831       iterator
 832       find(const key_type& __key)
 833       { return iterator(_Base::find(__key), this); }
 834
 835       const_iterator
 836       find(const key_type& __key) const
 837       { return const_iterator(_Base::find(__key), this); }
 838
 839       std::pair<iterator, iterator>
 840       equal_range(const key_type& __key)
 841       {
 842         std::pair<_Base_iterator, _Base_iterator> __res =
 843           _Base::equal_range(__key);
 844         return std::make_pair(iterator(__res.first, this),
 845                               iterator(__res.second, this));
 846       }
 847
 848       std::pair<const_iterator, const_iterator>
 849       equal_range(const key_type& __key) const
 850       {
 851         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 852           _Base::equal_range(__key);
 853         return std::make_pair(const_iterator(__res.first, this),
 854                               const_iterator(__res.second, this));
 855       }
 856
 857       size_type
 858       erase(const key_type& __key)
 859       {
 860         size_type __ret(0);
 861         size_type __bucket_count = this->bucket_count();
 862         std::pair<_Base_iterator, _Base_iterator> __pair =
 863           _Base::equal_range(__key);
 864         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
 865           {
 866             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 867                             { return __it == __victim; });
 868             this->_M_invalidate_local_if(
 869                             [__victim](_Base_const_local_iterator __it)
 870                             { return __it._M_curr() == __victim._M_cur; });
 871             _Base::erase(__victim++);
 872             ++__ret;
 873           }
 874         _M_check_rehashed(__bucket_count);
 875         return __ret;
 876       }
 877
 878       iterator
 879       erase(const_iterator __it)
 880       {
 881         __glibcxx_check_erase(__it);
 882         _Base_const_iterator __victim = __it.base();
 883         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 884                         { return __it == __victim; });
 885         this->_M_invalidate_local_if(
 886                         [__victim](_Base_const_local_iterator __it)
 887                         { return __it._M_curr() == __victim._M_cur; });
 888         size_type __bucket_count = this->bucket_count();
 889         _Base_iterator __next = _Base::erase(__it.base());
 890         _M_check_rehashed(__bucket_count);
 891         return iterator(__next, this);
 892       }
 893
 894       iterator
 895       erase(iterator __it)
 896       { return erase(const_iterator(__it)); }
 897
 898       iterator
 899       erase(const_iterator __first, const_iterator __last)
 900       {
 901         __glibcxx_check_erase_range(__first, __last);
 902         for (_Base_const_iterator __tmp = __first.base();
 903              __tmp != __last.base(); ++__tmp)
 904           {
 905             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 906                                   _M_message(__gnu_debug::__msg_valid_range)
 907                                   ._M_iterator(__first, "first")
 908                                   ._M_iterator(__last, "last"));
 909             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
 910                             { return __it == __tmp; });
 911             this->_M_invalidate_local_if(
 912                             [__tmp](_Base_const_local_iterator __it)
 913                             { return __it._M_curr() == __tmp._M_cur; });
 914           }
 915         size_type __bucket_count = this->bucket_count();
 916         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
 917         _M_check_rehashed(__bucket_count);
 918         return iterator(__next, this);
 919       }
 920
 921       _Base&
 922       _M_base() noexcept { return *this; }
 923
 924       const _Base&
 925       _M_base() const noexcept { return *this; }
 926
 927     private:
 928       void
 929       _M_check_rehashed(size_type __prev_count)
 930       {
 931         if (__prev_count != this->bucket_count())
 932           this->_M_invalidate_locals();
 933       }
 934     };
 935
 936   template<typename _Key, typename _Tp, typename _Hash,
 937            typename _Pred, typename _Alloc>
 938     inline void
 939     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 940          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 941     { __x.swap(__y); }
 942
 943   template<typename _Key, typename _Tp, typename _Hash,
 944            typename _Pred, typename _Alloc>
 945     inline bool
 946     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 947                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 948     { return __x._M_base() == __y._M_base(); }
 949
 950   template<typename _Key, typename _Tp, typename _Hash,
 951            typename _Pred, typename _Alloc>
 952     inline bool
 953     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 954                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 955     { return !(__x == __y); }
 956
 957 } // namespace __debug
 958 } // namespace std
 959
 960 #endif // C++11
 961
 962 #endif