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_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_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_container<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_container<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       : _Base(std::move(__x)) { }
 108
 109       unordered_set(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_set() noexcept { }
 117
 118       unordered_set&
 119       operator=(const unordered_set& __x)
 120       {
 121         *static_cast<_Base*>(this) = __x;
 122         this->_M_invalidate_all();
 123         return *this;
 124       }
 125
 126       unordered_set&
 127       operator=(unordered_set&& __x)
 128       {
 129         // NB: DR 1204.
 130         // NB: DR 675.
 131         clear();
 132         swap(__x);
 133         return *this;
 134       }
 135
 136       unordered_set&
 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_set& __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       std::pair<iterator, bool>
 208       insert(const value_type& __obj)
 209       {
 210         size_type __bucket_count = this->bucket_count();
 211         typedef std::pair<_Base_iterator, bool> __pair_type;
 212           __pair_type __res = _Base::insert(__obj);
 213         _M_check_rehashed(__bucket_count);
 214         return std::make_pair(iterator(__res.first, this), __res.second);
 215       }
 216
 217       iterator
 218       insert(const_iterator __hint, const value_type& __obj)
 219       {
 220         __glibcxx_check_insert(__hint);
 221         size_type __bucket_count = this->bucket_count();
 222         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 223         _M_check_rehashed(__bucket_count);
 224         return iterator(__it, this);
 225       }
 226
 227       std::pair<iterator, bool>
 228       insert(value_type&& __obj)
 229       {
 230         size_type __bucket_count = this->bucket_count();
 231         typedef std::pair<typename _Base::iterator, bool> __pair_type;
 232           __pair_type __res = _Base::insert(std::move(__obj));
 233         _M_check_rehashed(__bucket_count);
 234         return std::make_pair(iterator(__res.first, this), __res.second);
 235       }
 236
 237       iterator
 238       insert(const_iterator __hint, value_type&& __obj)
 239       {
 240         __glibcxx_check_insert(__hint);
 241         size_type __bucket_count = this->bucket_count();
 242         _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
 243         _M_check_rehashed(__bucket_count);
 244         return iterator(__it, this);
 245       }
 246
 247       void
 248       insert(std::initializer_list<value_type> __l)
 249       {
 250         size_type __bucket_count = this->bucket_count();
 251         _Base::insert(__l);
 252         _M_check_rehashed(__bucket_count);
 253       }
 254
 255       template<typename _InputIterator>
 256         void
 257         insert(_InputIterator __first, _InputIterator __last)
 258         {
 259           __glibcxx_check_valid_range(__first, __last);
 260           size_type __bucket_count = this->bucket_count();
 261           _Base::insert(__gnu_debug::__base(__first),
 262                         __gnu_debug::__base(__last));
 263           _M_check_rehashed(__bucket_count);
 264         }
 265
 266       iterator
 267       find(const key_type& __key)
 268       { return iterator(_Base::find(__key), this); }
 269
 270       const_iterator
 271       find(const key_type& __key) const
 272       { return const_iterator(_Base::find(__key), this); }
 273
 274       std::pair<iterator, iterator>
 275       equal_range(const key_type& __key)
 276       {
 277         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 278         __pair_type __res = _Base::equal_range(__key);
 279         return std::make_pair(iterator(__res.first, this),
 280                               iterator(__res.second, this));
 281       }
 282
 283       std::pair<const_iterator, const_iterator>
 284       equal_range(const key_type& __key) const
 285       {
 286         std::pair<_Base_const_iterator, _Base_const_iterator>
 287           __res = _Base::equal_range(__key);
 288         return std::make_pair(const_iterator(__res.first, this),
 289                               const_iterator(__res.second, this));
 290       }
 291
 292       size_type
 293       erase(const key_type& __key)
 294       {
 295         size_type __ret(0);
 296         _Base_iterator __victim(_Base::find(__key));
 297         if (__victim != _Base::end())
 298           {
 299             this->_M_invalidate_if(
 300                             [__victim](_Base_const_iterator __it)
 301                             { return __it == __victim; });
 302             _Base_local_iterator __local_victim = _S_to_local(__victim);
 303             this->_M_invalidate_local_if(
 304                             [__local_victim](_Base_const_local_iterator __it)
 305                             { return __it == __local_victim; });
 306             size_type __bucket_count = this->bucket_count();
 307             _Base::erase(__victim);
 308             _M_check_rehashed(__bucket_count);
 309             __ret = 1;
 310           }
 311         return __ret;
 312       }
 313
 314       iterator
 315       erase(const_iterator __it)
 316       {
 317         __glibcxx_check_erase(__it);
 318         _Base_const_iterator __victim = __it.base();
 319         this->_M_invalidate_if(
 320                         [__victim](_Base_const_iterator __it)
 321                         { return __it == __victim; });
 322         _Base_const_local_iterator __local_victim = _S_to_local(__victim);
 323         this->_M_invalidate_local_if(
 324                         [__local_victim](_Base_const_local_iterator __it)
 325                         { return __it == __local_victim; });
 326         size_type __bucket_count = this->bucket_count();
 327         _Base_iterator __next = _Base::erase(__it.base());
 328         _M_check_rehashed(__bucket_count);
 329         return iterator(__next, this);
 330       }
 331
 332       iterator
 333       erase(iterator __it)
 334       { return erase(const_iterator(__it)); }
 335
 336       iterator
 337       erase(const_iterator __first, const_iterator __last)
 338       {
 339         __glibcxx_check_erase_range(__first, __last);
 340         for (_Base_const_iterator __tmp = __first.base();
 341              __tmp != __last.base(); ++__tmp)
 342           {
 343             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 344                                   _M_message(__gnu_debug::__msg_valid_range)
 345                                   ._M_iterator(__first, "first")
 346                                   ._M_iterator(__last, "last"));
 347             this->_M_invalidate_if(
 348                             [__tmp](_Base_const_iterator __it)
 349                             { return __it == __tmp; });
 350             _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
 351             this->_M_invalidate_local_if(
 352                             [__local_tmp](_Base_const_local_iterator __it)
 353                             { return __it == __local_tmp; });
 354           }
 355         size_type __bucket_count = this->bucket_count();
 356         _Base_iterator __next = _Base::erase(__first.base(),
 357                                              __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(
 383                         [__end](_Base_const_iterator __it)
 384                         { return __it != __end; });
 385         _M_invalidate_locals();
 386       }
 387
 388       void
 389       _M_check_rehashed(size_type __prev_count)
 390       {
 391         if (__prev_count != this->bucket_count())
 392           _M_invalidate_locals();
 393       }
 394
 395       static _Base_local_iterator
 396       _S_to_local(_Base_iterator __it)
 397       { return _Base_local_iterator(__it._M_cur_node); }
 398
 399       static _Base_const_local_iterator
 400       _S_to_local(_Base_const_iterator __it)
 401       { return _Base_const_local_iterator(__it._M_cur_node); }
 402     };
 403
 404   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 405     inline void
 406     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 407          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 408     { __x.swap(__y); }
 409
 410   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 411     inline bool
 412     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 413                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 414     { return __x._M_equal(__y); }
 415
 416   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 417     inline bool
 418     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 419                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 420     { return !(__x == __y); }
 421
 422
 423   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
 424   template<typename _Value,
 425            typename _Hash = std::hash<_Value>,
 426            typename _Pred = std::equal_to<_Value>,
 427            typename _Alloc = std::allocator<_Value> >
 428     class unordered_multiset
 429     : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
 430       public __gnu_debug::_Safe_unordered_container<
 431                 unordered_multiset<_Value, _Hash, _Pred, _Alloc> >
 432     {
 433       typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash,
 434                                                  _Pred, _Alloc> _Base;
 435       typedef __gnu_debug::_Safe_unordered_container<unordered_multiset>
 436                 _Safe_base;
 437       typedef typename _Base::const_iterator _Base_const_iterator;
 438       typedef typename _Base::iterator _Base_iterator;
 439       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
 440       typedef typename _Base::local_iterator _Base_local_iterator;
 441
 442     public:
 443       typedef typename _Base::size_type       size_type;
 444       typedef typename _Base::hasher          hasher;
 445       typedef typename _Base::key_equal       key_equal;
 446       typedef typename _Base::allocator_type  allocator_type;
 447
 448       typedef typename _Base::key_type        key_type;
 449       typedef typename _Base::value_type      value_type;
 450
 451       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
 452                                           unordered_multiset> iterator;
 453       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 454                                           unordered_multiset> const_iterator;
 455       typedef __gnu_debug::_Safe_local_iterator<
 456         _Base_local_iterator, unordered_multiset> local_iterator;
 457       typedef __gnu_debug::_Safe_local_iterator<
 458         _Base_const_local_iterator, unordered_multiset> const_local_iterator;
 459
 460       explicit
 461       unordered_multiset(size_type __n = 10,
 462                          const hasher& __hf = hasher(),
 463                          const key_equal& __eql = key_equal(),
 464                          const allocator_type& __a = allocator_type())
 465       : _Base(__n, __hf, __eql, __a) { }
 466
 467       template<typename _InputIterator>
 468         unordered_multiset(_InputIterator __first, _InputIterator __last,
 469                            size_type __n = 0,
 470                            const hasher& __hf = hasher(),
 471                            const key_equal& __eql = key_equal(),
 472                            const allocator_type& __a = allocator_type())
 473         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 474                                                                      __last)),
 475                 __gnu_debug::__base(__last), __n,
 476                 __hf, __eql, __a) { }
 477
 478       unordered_multiset(const unordered_multiset& __x)
 479       : _Base(__x) { }
 480
 481       unordered_multiset(const _Base& __x)
 482       : _Base(__x) { }
 483
 484       unordered_multiset(unordered_multiset&& __x)
 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(iterator __it)
 704       { return erase(const_iterator(__it)); }
 705
 706       iterator
 707       erase(const_iterator __first, const_iterator __last)
 708       {
 709         __glibcxx_check_erase_range(__first, __last);
 710         for (_Base_const_iterator __tmp = __first.base();
 711              __tmp != __last.base(); ++__tmp)
 712           {
 713             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 714                                   _M_message(__gnu_debug::__msg_valid_range)
 715                                   ._M_iterator(__first, "first")
 716                                   ._M_iterator(__last, "last"));
 717             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
 718                             { return __it == __tmp; });
 719             _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
 720             this->_M_invalidate_local_if(
 721                             [__local_tmp](_Base_const_local_iterator __it)
 722                             { return __it == __local_tmp; });
 723           }
 724         return iterator(_Base::erase(__first.base(),
 725                                      __last.base()), this);
 726       }
 727
 728       _Base&
 729       _M_base() noexcept       { return *this; }
 730
 731       const _Base&
 732       _M_base() const noexcept { return *this; }
 733
 734     private:
 735       void
 736       _M_invalidate_locals()
 737       {
 738         _Base_local_iterator __local_end = _Base::end(0);
 739         this->_M_invalidate_local_if(
 740                         [__local_end](_Base_const_local_iterator __it)
 741                         { return __it != __local_end; });
 742       }
 743
 744       void
 745       _M_invalidate_all()
 746       {
 747         _Base_iterator __end = _Base::end();
 748         this->_M_invalidate_if([__end](_Base_const_iterator __it)
 749                         { return __it != __end; });
 750         _M_invalidate_locals();
 751       }
 752
 753       void
 754       _M_check_rehashed(size_type __prev_count)
 755       {
 756         if (__prev_count != this->bucket_count())
 757           _M_invalidate_locals();
 758       }
 759
 760       static _Base_local_iterator
 761       _S_to_local(_Base_iterator __it)
 762       { return _Base_local_iterator(__it._M_cur_node); }
 763
 764       static _Base_const_local_iterator
 765       _S_to_local(_Base_const_iterator __it)
 766       { return _Base_const_local_iterator(__it._M_cur_node); }
 767     };
 768
 769   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 770     inline void
 771     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 772          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 773     { __x.swap(__y); }
 774
 775   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 776     inline bool
 777     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 778                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 779     { return __x._M_equal(__y); }
 780
 781   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 782     inline bool
 783     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 784                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 785     { return !(__x == __y); }
 786
 787 } // namespace __debug
 788 } // namespace std
 789
 790 #endif // __GXX_EXPERIMENTAL_CXX0X__
 791
 792 #endif