libstdc++-v3/include/debug/unordered_map

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