libstdc++-v3/include/debug/unordered_map

   1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /** @file debug/unordered_map
  27  *  This file is a GNU debug extension to the Standard C++ Library.
  28  */
  29
  30 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
  31 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
  32
  33 #ifndef __GXX_EXPERIMENTAL_CXX0X__
  34 # include <bits/c++0x_warning.h>
  35 #else
  36 # include <unordered_map>
  37
  38 #include <debug/safe_unordered_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<_Key> >
  51     class unordered_map
  52     : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
  53       public __gnu_debug::_Safe_unordered_container<unordered_map<_Key, _Tp,
  54                                                         _Hash, _Pred, _Alloc> >
  55     {
  56       typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
  57                                             _Pred, _Alloc> _Base;
  58       typedef __gnu_debug::_Safe_unordered_container<unordered_map> _Safe_base;
  59       typedef typename _Base::const_iterator _Base_const_iterator;
  60       typedef typename _Base::iterator _Base_iterator;
  61       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
  62       typedef typename _Base::local_iterator _Base_local_iterator;
  63
  64     public:
  65       typedef typename _Base::size_type       size_type;
  66       typedef typename _Base::hasher          hasher;
  67       typedef typename _Base::key_equal       key_equal;
  68       typedef typename _Base::allocator_type  allocator_type;
  69
  70       typedef typename _Base::key_type        key_type;
  71       typedef typename _Base::value_type      value_type;
  72
  73       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
  74                                           unordered_map> iterator;
  75       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  76                                           unordered_map> const_iterator;
  77       typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
  78                                           unordered_map> local_iterator;
  79       typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
  80                                           unordered_map> const_local_iterator;
  81
  82       explicit
  83       unordered_map(size_type __n = 10,
  84                     const hasher& __hf = hasher(),
  85                     const key_equal& __eql = key_equal(),
  86                     const allocator_type& __a = allocator_type())
  87       : _Base(__n, __hf, __eql, __a) { }
  88
  89       template<typename _InputIterator>
  90         unordered_map(_InputIterator __first, _InputIterator __last,
  91                       size_type __n = 0,
  92                       const hasher& __hf = hasher(),
  93                       const key_equal& __eql = key_equal(),
  94                       const allocator_type& __a = allocator_type())
  95         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  96                                                                      __last)),
  97                 __gnu_debug::__base(__last), __n,
  98                 __hf, __eql, __a) { }
  99
 100       unordered_map(const unordered_map& __x)
 101       : _Base(__x) { }
 102
 103       unordered_map(const _Base& __x)
 104       : _Base(__x) { }
 105
 106       unordered_map(unordered_map&& __x)
 107       : _Base(std::move(__x)) { }
 108
 109       unordered_map(initializer_list<value_type> __l,
 110                     size_type __n = 0,
 111                     const hasher& __hf = hasher(),
 112                     const key_equal& __eql = key_equal(),
 113                     const allocator_type& __a = allocator_type())
 114       : _Base(__l, __n, __hf, __eql, __a) { }
 115
 116       ~unordered_map() noexcept { }
 117
 118       unordered_map&
 119       operator=(const unordered_map& __x)
 120       {
 121         *static_cast<_Base*>(this) = __x;
 122         this->_M_invalidate_all();
 123         return *this;
 124       }
 125
 126       unordered_map&
 127       operator=(unordered_map&& __x)
 128       {
 129         // NB: DR 1204.
 130         // NB: DR 675.
 131         __glibcxx_check_self_move_assign(__x);
 132         clear();
 133         swap(__x);
 134         return *this;
 135       }
 136
 137       unordered_map&
 138       operator=(initializer_list<value_type> __l)
 139       {
 140         this->clear();
 141         this->insert(__l);
 142         return *this;
 143       }
 144
 145       void
 146       swap(unordered_map& __x)
 147       {
 148         _Base::swap(__x);
 149         _Safe_base::_M_swap(__x);
 150       }
 151
 152       void
 153       clear() noexcept
 154       {
 155         _Base::clear();
 156         this->_M_invalidate_all();
 157       }
 158
 159       iterator
 160       begin() noexcept
 161       { return iterator(_Base::begin(), this); }
 162
 163       const_iterator
 164       begin() const noexcept
 165       { return const_iterator(_Base::begin(), this); }
 166
 167       iterator
 168       end() noexcept
 169       { return iterator(_Base::end(), this); }
 170
 171       const_iterator
 172       end() const noexcept
 173       { return const_iterator(_Base::end(), this); }
 174
 175       const_iterator
 176       cbegin() const noexcept
 177       { return const_iterator(_Base::begin(), this); }
 178
 179       const_iterator
 180       cend() const noexcept
 181       { return const_iterator(_Base::end(), this); }
 182
 183       // local versions
 184       local_iterator
 185       begin(size_type __b)
 186       { return local_iterator(_Base::begin(__b), __b, this); }
 187
 188       local_iterator
 189       end(size_type __b)
 190       { return local_iterator(_Base::end(__b), __b, this); }
 191
 192       const_local_iterator
 193       begin(size_type __b) const
 194       { return const_local_iterator(_Base::begin(__b), __b, this); }
 195
 196       const_local_iterator
 197       end(size_type __b) const
 198       { return const_local_iterator(_Base::end(__b), __b, this); }
 199
 200       const_local_iterator
 201       cbegin(size_type __b) const
 202       { return const_local_iterator(_Base::cbegin(__b), __b, this); }
 203
 204       const_local_iterator
 205       cend(size_type __b) const
 206       { return const_local_iterator(_Base::cend(__b), __b, this); }
 207
 208       template<typename... _Args>
 209         std::pair<iterator, bool>
 210         emplace(_Args&&... __args)
 211         {
 212           size_type __bucket_count = this->bucket_count();
 213           std::pair<_Base_iterator, bool> __res
 214             = _Base::emplace(std::forward<_Args>(__args)...);
 215           _M_check_rehashed(__bucket_count);
 216           return std::make_pair(iterator(__res.first, this), __res.second);
 217         }
 218
 219       template<typename... _Args>
 220         iterator
 221         emplace_hint(const_iterator __hint, _Args&&... __args)
 222         {
 223           __glibcxx_check_insert(__hint);
 224           size_type __bucket_count = this->bucket_count();
 225           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 226                                         std::forward<_Args>(__args)...);
 227           _M_check_rehashed(__bucket_count);
 228           return iterator(__it, this);
 229         }
 230
 231       std::pair<iterator, bool>
 232       insert(const value_type& __obj)
 233       {
 234         size_type __bucket_count = this->bucket_count();
 235         std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
 236         _M_check_rehashed(__bucket_count);
 237         return std::make_pair(iterator(__res.first, this), __res.second);
 238       }
 239
 240       iterator
 241       insert(const_iterator __hint, const value_type& __obj)
 242       {
 243         __glibcxx_check_insert(__hint);
 244         size_type __bucket_count = this->bucket_count();
 245         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 246         _M_check_rehashed(__bucket_count);
 247         return iterator(__it, this);
 248       }
 249
 250       template<typename _Pair, typename = typename
 251                std::enable_if<std::is_convertible<_Pair,
 252                                                   value_type>::value>::type>
 253         std::pair<iterator, bool>
 254         insert(_Pair&& __obj)
 255         {
 256           size_type __bucket_count = this->bucket_count();
 257           std::pair<_Base_iterator, bool> __res =
 258             _Base::insert(std::forward<_Pair>(__obj));
 259           _M_check_rehashed(__bucket_count);
 260           return std::make_pair(iterator(__res.first, this), __res.second);
 261         }
 262
 263       template<typename _Pair, typename = typename
 264                std::enable_if<std::is_convertible<_Pair,
 265                                                   value_type>::value>::type>
 266         iterator
 267         insert(const_iterator __hint, _Pair&& __obj)
 268         {
 269           __glibcxx_check_insert(__hint);
 270           size_type __bucket_count = this->bucket_count();
 271           _Base_iterator __it =
 272             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
 273           _M_check_rehashed(__bucket_count);
 274           return iterator(__it, this);
 275         }
 276
 277       void
 278       insert(std::initializer_list<value_type> __l)
 279       {
 280         size_type __bucket_count = this->bucket_count();
 281         _Base::insert(__l);
 282         _M_check_rehashed(__bucket_count);
 283       }
 284
 285       template<typename _InputIterator>
 286         void
 287         insert(_InputIterator __first, _InputIterator __last)
 288         {
 289           __glibcxx_check_valid_range(__first, __last);
 290           size_type __bucket_count = this->bucket_count();
 291           _Base::insert(__gnu_debug::__base(__first),
 292                         __gnu_debug::__base(__last));
 293           _M_check_rehashed(__bucket_count);
 294         }
 295
 296       iterator
 297       find(const key_type& __key)
 298       { return iterator(_Base::find(__key), this); }
 299
 300       const_iterator
 301       find(const key_type& __key) const
 302       { return const_iterator(_Base::find(__key), this); }
 303
 304       std::pair<iterator, iterator>
 305       equal_range(const key_type& __key)
 306       {
 307         std::pair<_Base_iterator, _Base_iterator> __res =
 308           _Base::equal_range(__key);
 309         return std::make_pair(iterator(__res.first, this),
 310                               iterator(__res.second, this));
 311       }
 312
 313       std::pair<const_iterator, const_iterator>
 314       equal_range(const key_type& __key) const
 315       {
 316         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 317           _Base::equal_range(__key);
 318         return std::make_pair(const_iterator(__res.first, this),
 319                               const_iterator(__res.second, this));
 320       }
 321
 322       size_type
 323       erase(const key_type& __key)
 324       {
 325         size_type __ret(0);
 326         _Base_iterator __victim(_Base::find(__key));
 327         if (__victim != _Base::end())
 328           {
 329             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 330                             { return __it == __victim; });
 331             _Base_local_iterator __local_victim = _S_to_local(__victim);
 332             this->_M_invalidate_local_if(
 333                             [__local_victim](_Base_const_local_iterator __it)
 334                             { return __it == __local_victim; });
 335             size_type __bucket_count = this->bucket_count();
 336             _Base::erase(__victim);
 337             _M_check_rehashed(__bucket_count);
 338             __ret = 1;
 339           }
 340         return __ret;
 341       }
 342
 343       iterator
 344       erase(const_iterator __it)
 345       {
 346         __glibcxx_check_erase(__it);
 347         _Base_const_iterator __victim = __it.base();
 348         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 349                         { return __it == __victim; });
 350         _Base_const_local_iterator __local_victim = _S_to_local(__victim);
 351         this->_M_invalidate_local_if(
 352                         [__local_victim](_Base_const_local_iterator __it)
 353                         { return __it == __local_victim; });
 354         size_type __bucket_count = this->bucket_count();
 355         _Base_iterator __next = _Base::erase(__it.base());
 356         _M_check_rehashed(__bucket_count);
 357         return iterator(__next, this);
 358       }
 359
 360       iterator
 361       erase(iterator __it)
 362       { return erase(const_iterator(__it)); }
 363
 364       iterator
 365       erase(const_iterator __first, const_iterator __last)
 366       {
 367         __glibcxx_check_erase_range(__first, __last);
 368         for (_Base_const_iterator __tmp = __first.base();
 369              __tmp != __last.base(); ++__tmp)
 370           {
 371             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 372                                   _M_message(__gnu_debug::__msg_valid_range)
 373                                   ._M_iterator(__first, "first")
 374                                   ._M_iterator(__last, "last"));
 375             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
 376                             { return __it == __tmp; });
 377             _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
 378             this->_M_invalidate_local_if(
 379                             [__local_tmp](_Base_const_local_iterator __it)
 380                             { return __it == __local_tmp; });
 381           }
 382         size_type __bucket_count = this->bucket_count();
 383         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
 384         _M_check_rehashed(__bucket_count);
 385         return iterator(__next, this);
 386       }
 387
 388       _Base&
 389       _M_base() noexcept       { return *this; }
 390
 391       const _Base&
 392       _M_base() const noexcept { return *this; }
 393
 394     private:
 395       void
 396       _M_invalidate_locals()
 397       {
 398         _Base_local_iterator __local_end = _Base::end(0);
 399         this->_M_invalidate_local_if(
 400                         [__local_end](_Base_const_local_iterator __it)
 401                         { return __it != __local_end; });
 402       }
 403
 404       void
 405       _M_invalidate_all()
 406       {
 407         _Base_iterator __end = _Base::end();
 408         this->_M_invalidate_if([__end](_Base_const_iterator __it)
 409                         { return __it != __end; });
 410         _M_invalidate_locals();
 411       }
 412
 413       void
 414       _M_check_rehashed(size_type __prev_count)
 415       {
 416         if (__prev_count != this->bucket_count())
 417           _M_invalidate_locals();
 418       }
 419
 420       static _Base_local_iterator
 421       _S_to_local(_Base_iterator __it)
 422       {
 423         // The returned local iterator will not be incremented so we don't
 424         // need to compute __it's node bucket
 425         return _Base_local_iterator(__it._M_cur, 0, 0);
 426       }
 427
 428       static _Base_const_local_iterator
 429       _S_to_local(_Base_const_iterator __it)
 430       {
 431         // The returned local iterator will not be incremented so we don't
 432         // need to compute __it's node bucket
 433         return _Base_const_local_iterator(__it._M_cur, 0, 0);
 434       }
 435     };
 436
 437   template<typename _Key, typename _Tp, typename _Hash,
 438            typename _Pred, typename _Alloc>
 439     inline void
 440     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 441          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 442     { __x.swap(__y); }
 443
 444   template<typename _Key, typename _Tp, typename _Hash,
 445            typename _Pred, typename _Alloc>
 446     inline bool
 447     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 448                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 449     { return __x._M_equal(__y); }
 450
 451   template<typename _Key, typename _Tp, typename _Hash,
 452            typename _Pred, typename _Alloc>
 453     inline bool
 454     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 455                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 456     { return !(__x == __y); }
 457
 458
 459   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
 460   template<typename _Key, typename _Tp,
 461            typename _Hash = std::hash<_Key>,
 462            typename _Pred = std::equal_to<_Key>,
 463            typename _Alloc = std::allocator<_Key> >
 464     class unordered_multimap
 465     : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
 466                                                 _Pred, _Alloc>,
 467       public __gnu_debug::_Safe_unordered_container<unordered_multimap<_Key,
 468                                                 _Tp, _Hash, _Pred, _Alloc> >
 469     {
 470       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
 471                                                  _Pred, _Alloc> _Base;
 472       typedef __gnu_debug::_Safe_unordered_container<unordered_multimap>
 473         _Safe_base;
 474       typedef typename _Base::const_iterator _Base_const_iterator;
 475       typedef typename _Base::iterator _Base_iterator;
 476       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
 477       typedef typename _Base::local_iterator _Base_local_iterator;
 478
 479     public:
 480       typedef typename _Base::size_type       size_type;
 481       typedef typename _Base::hasher          hasher;
 482       typedef typename _Base::key_equal       key_equal;
 483       typedef typename _Base::allocator_type  allocator_type;
 484
 485       typedef typename _Base::key_type        key_type;
 486       typedef typename _Base::value_type      value_type;
 487
 488       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
 489                                           unordered_multimap> iterator;
 490       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 491                                           unordered_multimap> const_iterator;
 492       typedef __gnu_debug::_Safe_local_iterator<
 493         _Base_local_iterator, unordered_multimap> local_iterator;
 494       typedef __gnu_debug::_Safe_local_iterator<
 495         _Base_const_local_iterator, unordered_multimap> const_local_iterator;
 496
 497       explicit
 498       unordered_multimap(size_type __n = 10,
 499                          const hasher& __hf = hasher(),
 500                          const key_equal& __eql = key_equal(),
 501                          const allocator_type& __a = allocator_type())
 502       : _Base(__n, __hf, __eql, __a) { }
 503
 504       template<typename _InputIterator>
 505         unordered_multimap(_InputIterator __first, _InputIterator __last,
 506                            size_type __n = 0,
 507                            const hasher& __hf = hasher(),
 508                            const key_equal& __eql = key_equal(),
 509                            const allocator_type& __a = allocator_type())
 510         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 511                                                                      __last)),
 512                 __gnu_debug::__base(__last), __n,
 513                 __hf, __eql, __a) { }
 514
 515       unordered_multimap(const unordered_multimap& __x)
 516       : _Base(__x) { }
 517
 518       unordered_multimap(const _Base& __x)
 519       : _Base(__x) { }
 520
 521       unordered_multimap(unordered_multimap&& __x)
 522       : _Base(std::move(__x)) { }
 523
 524       unordered_multimap(initializer_list<value_type> __l,
 525                          size_type __n = 0,
 526                          const hasher& __hf = hasher(),
 527                          const key_equal& __eql = key_equal(),
 528                          const allocator_type& __a = allocator_type())
 529       : _Base(__l, __n, __hf, __eql, __a) { }
 530
 531       ~unordered_multimap() noexcept { }
 532
 533       unordered_multimap&
 534       operator=(const unordered_multimap& __x)
 535       {
 536         *static_cast<_Base*>(this) = __x;
 537         this->_M_invalidate_all();
 538         return *this;
 539       }
 540
 541       unordered_multimap&
 542       operator=(unordered_multimap&& __x)
 543       {
 544         // NB: DR 1204.
 545         // NB: DR 675.
 546         __glibcxx_check_self_move_assign(__x);
 547         clear();
 548         swap(__x);
 549         return *this;
 550       }
 551
 552       unordered_multimap&
 553       operator=(initializer_list<value_type> __l)
 554       {
 555         this->clear();
 556         this->insert(__l);
 557         return *this;
 558       }
 559
 560       void
 561       swap(unordered_multimap& __x)
 562       {
 563         _Base::swap(__x);
 564         _Safe_base::_M_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       { return local_iterator(_Base::begin(__b), __b, this); }
 602
 603       local_iterator
 604       end(size_type __b)
 605       { return local_iterator(_Base::end(__b), __b, this); }
 606
 607       const_local_iterator
 608       begin(size_type __b) const
 609       { return const_local_iterator(_Base::begin(__b), __b, this); }
 610
 611       const_local_iterator
 612       end(size_type __b) const
 613       { return const_local_iterator(_Base::end(__b), __b, this); }
 614
 615       const_local_iterator
 616       cbegin(size_type __b) const
 617       { return const_local_iterator(_Base::cbegin(__b), __b, this); }
 618
 619       const_local_iterator
 620       cend(size_type __b) const
 621       { return const_local_iterator(_Base::cend(__b), __b, this); }
 622
 623       template<typename... _Args>
 624         iterator
 625         emplace(_Args&&... __args)
 626         {
 627           size_type __bucket_count = this->bucket_count();
 628           _Base_iterator __it
 629             = _Base::emplace(std::forward<_Args>(__args)...);
 630           _M_check_rehashed(__bucket_count);
 631           return iterator(__it, this);
 632         }
 633
 634       template<typename... _Args>
 635         iterator
 636         emplace_hint(const_iterator __hint, _Args&&... __args)
 637         {
 638           __glibcxx_check_insert(__hint);
 639           size_type __bucket_count = this->bucket_count();
 640           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 641                                         std::forward<_Args>(__args)...);
 642           _M_check_rehashed(__bucket_count);
 643           return iterator(__it, this);
 644         }
 645
 646       iterator
 647       insert(const value_type& __obj)
 648       {
 649         size_type __bucket_count = this->bucket_count();
 650         _Base_iterator __it = _Base::insert(__obj);
 651         _M_check_rehashed(__bucket_count);
 652         return iterator(__it, this);
 653       }
 654
 655       iterator
 656       insert(const_iterator __hint, const value_type& __obj)
 657       {
 658         __glibcxx_check_insert(__hint);
 659         size_type __bucket_count = this->bucket_count();
 660         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 661         _M_check_rehashed(__bucket_count);
 662         return iterator(__it, this);
 663       }
 664
 665       template<typename _Pair, typename = typename
 666                std::enable_if<std::is_convertible<_Pair,
 667                                                   value_type>::value>::type>
 668         iterator
 669         insert(_Pair&& __obj)
 670         {
 671           size_type __bucket_count = this->bucket_count();
 672           _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
 673           _M_check_rehashed(__bucket_count);
 674           return iterator(__it, this);
 675         }
 676
 677       template<typename _Pair, typename = typename
 678                std::enable_if<std::is_convertible<_Pair,
 679                                                   value_type>::value>::type>
 680         iterator
 681         insert(const_iterator __hint, _Pair&& __obj)
 682         {
 683           __glibcxx_check_insert(__hint);
 684           size_type __bucket_count = this->bucket_count();
 685           _Base_iterator __it =
 686             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
 687           _M_check_rehashed(__bucket_count);
 688           return iterator(__it, this);
 689         }
 690
 691       void
 692       insert(std::initializer_list<value_type> __l)
 693       { _Base::insert(__l); }
 694
 695       template<typename _InputIterator>
 696         void
 697         insert(_InputIterator __first, _InputIterator __last)
 698         {
 699           __glibcxx_check_valid_range(__first, __last);
 700           size_type __bucket_count = this->bucket_count();
 701           _Base::insert(__gnu_debug::__base(__first),
 702                         __gnu_debug::__base(__last));
 703           _M_check_rehashed(__bucket_count);
 704         }
 705
 706       iterator
 707       find(const key_type& __key)
 708       { return iterator(_Base::find(__key), this); }
 709
 710       const_iterator
 711       find(const key_type& __key) const
 712       { return const_iterator(_Base::find(__key), this); }
 713
 714       std::pair<iterator, iterator>
 715       equal_range(const key_type& __key)
 716       {
 717         std::pair<_Base_iterator, _Base_iterator> __res =
 718           _Base::equal_range(__key);
 719         return std::make_pair(iterator(__res.first, this),
 720                               iterator(__res.second, this));
 721       }
 722
 723       std::pair<const_iterator, const_iterator>
 724       equal_range(const key_type& __key) const
 725       {
 726         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 727           _Base::equal_range(__key);
 728         return std::make_pair(const_iterator(__res.first, this),
 729                               const_iterator(__res.second, this));
 730       }
 731
 732       size_type
 733       erase(const key_type& __key)
 734       {
 735         size_type __ret(0);
 736         size_type __bucket_count = this->bucket_count();
 737         std::pair<_Base_iterator, _Base_iterator> __pair =
 738           _Base::equal_range(__key);
 739         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
 740           {
 741             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 742                             { return __it == __victim; });
 743             _Base_local_iterator __local_victim = _S_to_local(__victim);
 744             this->_M_invalidate_local_if(
 745                             [__local_victim](_Base_const_local_iterator __it)
 746                             { return __it == __local_victim; });
 747             _Base::erase(__victim++);
 748             ++__ret;
 749           }
 750         _M_check_rehashed(__bucket_count);
 751         return __ret;
 752       }
 753
 754       iterator
 755       erase(const_iterator __it)
 756       {
 757         __glibcxx_check_erase(__it);
 758         _Base_const_iterator __victim = __it.base();
 759         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 760                         { return __it == __victim; });
 761         _Base_const_local_iterator __local_victim = _S_to_local(__victim);
 762         this->_M_invalidate_local_if(
 763                         [__local_victim](_Base_const_local_iterator __it)
 764                         { return __it == __local_victim; });
 765         size_type __bucket_count = this->bucket_count();
 766         _Base_iterator __next = _Base::erase(__it.base());
 767         _M_check_rehashed(__bucket_count);
 768         return iterator(__next, this);
 769       }
 770
 771       iterator
 772       erase(iterator __it)
 773       { return erase(const_iterator(__it)); }
 774
 775       iterator
 776       erase(const_iterator __first, const_iterator __last)
 777       {
 778         __glibcxx_check_erase_range(__first, __last);
 779         for (_Base_const_iterator __tmp = __first.base();
 780              __tmp != __last.base(); ++__tmp)
 781           {
 782             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 783                                   _M_message(__gnu_debug::__msg_valid_range)
 784                                   ._M_iterator(__first, "first")
 785                                   ._M_iterator(__last, "last"));
 786             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
 787                             { return __it == __tmp; });
 788             _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
 789             this->_M_invalidate_local_if(
 790                             [__local_tmp](_Base_const_local_iterator __it)
 791                             { return __it == __local_tmp; });
 792           }
 793         size_type __bucket_count = this->bucket_count();
 794         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
 795         _M_check_rehashed(__bucket_count);
 796         return iterator(__next, this);
 797       }
 798
 799       _Base&
 800       _M_base() noexcept       { return *this; }
 801
 802       const _Base&
 803       _M_base() const noexcept { return *this; }
 804
 805     private:
 806       void
 807       _M_invalidate_locals()
 808       {
 809         _Base_local_iterator __local_end = _Base::end(0);
 810         this->_M_invalidate_local_if(
 811                         [__local_end](_Base_const_local_iterator __it)
 812                         { return __it != __local_end; });
 813       }
 814
 815       void
 816       _M_invalidate_all()
 817       {
 818         _Base_iterator __end = _Base::end();
 819         this->_M_invalidate_if([__end](_Base_const_iterator __it)
 820                         { return __it != __end; });
 821         _M_invalidate_locals();
 822       }
 823
 824       void
 825       _M_check_rehashed(size_type __prev_count)
 826       {
 827         if (__prev_count != this->bucket_count())
 828           _M_invalidate_locals();
 829       }
 830
 831       static _Base_local_iterator
 832       _S_to_local(_Base_iterator __it)
 833       {
 834         // The returned local iterator will not be incremented so we don't
 835         // need to compute __it's node bucket
 836         return _Base_local_iterator(__it._M_cur, 0, 0);
 837       }
 838
 839       static _Base_const_local_iterator
 840       _S_to_local(_Base_const_iterator __it)
 841       {
 842         // The returned local iterator will not be incremented so we don't
 843         // need to compute __it's node bucket
 844         return _Base_const_local_iterator(__it._M_cur, 0, 0);
 845       }
 846     };
 847
 848   template<typename _Key, typename _Tp, typename _Hash,
 849            typename _Pred, typename _Alloc>
 850     inline void
 851     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 852          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 853     { __x.swap(__y); }
 854
 855   template<typename _Key, typename _Tp, typename _Hash,
 856            typename _Pred, typename _Alloc>
 857     inline bool
 858     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 859                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 860     { return __x._M_equal(__y); }
 861
 862   template<typename _Key, typename _Tp, typename _Hash,
 863            typename _Pred, typename _Alloc>
 864     inline bool
 865     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 866                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 867     { return !(__x == __y); }
 868
 869 } // namespace __debug
 870 } // namespace std
 871
 872 #endif // __GXX_EXPERIMENTAL_CXX0X__
 873
 874 #endif