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