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