libstdc++-v3/include/debug/unordered_set

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