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