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