contrib/gcc-5.0/libstdc++-v3/include/debug/unordered_set

   1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2015 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file debug/unordered_set
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
  30 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
  31
  32 #if __cplusplus < 201103L
  33 # include <bits/c++0x_warning.h>
  34 #else
  35 # include <unordered_set>
  36
  37 #include <debug/safe_unordered_container.h>
  38 #include <debug/safe_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 __gnu_debug::_Safe_container<
  53         unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc,
  54         __gnu_debug::_Safe_unordered_container>,
  55       public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>
  56     {
  57       typedef _GLIBCXX_STD_C::unordered_set<
  58         _Value, _Hash, _Pred, _Alloc>                                   _Base;
  59       typedef __gnu_debug::_Safe_container<
  60         unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container>  _Safe;
  61
  62       typedef typename _Base::const_iterator       _Base_const_iterator;
  63       typedef typename _Base::iterator             _Base_iterator;
  64       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
  65       typedef typename _Base::local_iterator       _Base_local_iterator;
  66
  67     public:
  68       typedef typename _Base::size_type                 size_type;
  69       typedef typename _Base::hasher                    hasher;
  70       typedef typename _Base::key_equal                 key_equal;
  71       typedef typename _Base::allocator_type            allocator_type;
  72
  73       typedef typename _Base::key_type                  key_type;
  74       typedef typename _Base::value_type                value_type;
  75
  76       typedef __gnu_debug::_Safe_iterator<
  77         _Base_iterator, unordered_set>                  iterator;
  78       typedef __gnu_debug::_Safe_iterator<
  79         _Base_const_iterator, unordered_set>            const_iterator;
  80       typedef __gnu_debug::_Safe_local_iterator<
  81         _Base_local_iterator, unordered_set>            local_iterator;
  82       typedef __gnu_debug::_Safe_local_iterator<
  83         _Base_const_local_iterator, unordered_set>      const_local_iterator;
  84
  85       unordered_set() = default;
  86
  87       explicit
  88       unordered_set(size_type __n,
  89                     const hasher& __hf = hasher(),
  90                     const key_equal& __eql = key_equal(),
  91                     const allocator_type& __a = allocator_type())
  92       : _Base(__n, __hf, __eql, __a) { }
  93
  94       template<typename _InputIterator>
  95         unordered_set(_InputIterator __first, _InputIterator __last,
  96                       size_type __n = 0,
  97                       const hasher& __hf = hasher(),
  98                       const key_equal& __eql = key_equal(),
  99                       const allocator_type& __a = allocator_type())
 100         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 101                                                                      __last)),
 102                 __gnu_debug::__base(__last), __n,
 103                 __hf, __eql, __a) { }
 104
 105       unordered_set(const unordered_set&) = default;
 106
 107       unordered_set(const _Base& __x)
 108       : _Base(__x) { }
 109
 110       unordered_set(unordered_set&&) = default;
 111
 112       explicit
 113       unordered_set(const allocator_type& __a)
 114       : _Base(__a) { }
 115
 116       unordered_set(const unordered_set& __uset,
 117                     const allocator_type& __a)
 118       : _Base(__uset, __a) { }
 119
 120       unordered_set(unordered_set&& __uset,
 121                     const allocator_type& __a)
 122       : _Safe(std::move(__uset._M_safe()), __a),
 123         _Base(std::move(__uset._M_base()), __a) { }
 124
 125       unordered_set(initializer_list<value_type> __l,
 126                     size_type __n = 0,
 127                     const hasher& __hf = hasher(),
 128                     const key_equal& __eql = key_equal(),
 129                     const allocator_type& __a = allocator_type())
 130       : _Base(__l, __n, __hf, __eql, __a) { }
 131
 132       ~unordered_set() = default;
 133
 134       unordered_set&
 135       operator=(const unordered_set&) = default;
 136
 137       unordered_set&
 138       operator=(unordered_set&&) = default;
 139
 140       unordered_set&
 141       operator=(initializer_list<value_type> __l)
 142       {
 143         _M_base() = __l;
 144         this->_M_invalidate_all();
 145         return *this;
 146       }
 147
 148       void
 149       swap(unordered_set& __x)
 150         noexcept( noexcept(declval<_Base>().swap(__x)) )
 151       {
 152         _Safe::_M_swap(__x);
 153         _Base::swap(__x);
 154       }
 155
 156       void
 157       clear() noexcept
 158       {
 159         _Base::clear();
 160         this->_M_invalidate_all();
 161       }
 162
 163       iterator
 164       begin() noexcept
 165       { return iterator(_Base::begin(), this); }
 166
 167       const_iterator
 168       begin() const noexcept
 169       { return const_iterator(_Base::begin(), this); }
 170
 171       iterator
 172       end() noexcept
 173       { return iterator(_Base::end(), this); }
 174
 175       const_iterator
 176       end() const noexcept
 177       { return const_iterator(_Base::end(), this); }
 178
 179       const_iterator
 180       cbegin() const noexcept
 181       { return const_iterator(_Base::begin(), this); }
 182
 183       const_iterator
 184       cend() const noexcept
 185       { return const_iterator(_Base::end(), this); }
 186
 187       // local versions
 188       local_iterator
 189       begin(size_type __b)
 190       {
 191         __glibcxx_check_bucket_index(__b);
 192         return local_iterator(_Base::begin(__b), this);
 193       }
 194
 195       local_iterator
 196       end(size_type __b)
 197       {
 198         __glibcxx_check_bucket_index(__b);
 199         return local_iterator(_Base::end(__b), this);
 200       }
 201
 202       const_local_iterator
 203       begin(size_type __b) const
 204       {
 205         __glibcxx_check_bucket_index(__b);
 206         return const_local_iterator(_Base::begin(__b), this);
 207       }
 208
 209       const_local_iterator
 210       end(size_type __b) const
 211       {
 212         __glibcxx_check_bucket_index(__b);
 213         return const_local_iterator(_Base::end(__b), this);
 214       }
 215
 216       const_local_iterator
 217       cbegin(size_type __b) const
 218       {
 219         __glibcxx_check_bucket_index(__b);
 220         return const_local_iterator(_Base::cbegin(__b), this);
 221       }
 222
 223       const_local_iterator
 224       cend(size_type __b) const
 225       {
 226         __glibcxx_check_bucket_index(__b);
 227         return const_local_iterator(_Base::cend(__b), this);
 228       }
 229
 230       size_type
 231       bucket_size(size_type __b) const
 232       {
 233         __glibcxx_check_bucket_index(__b);
 234         return _Base::bucket_size(__b);
 235       }
 236
 237       float
 238       max_load_factor() const noexcept
 239       { return _Base::max_load_factor(); }
 240
 241       void
 242       max_load_factor(float __f)
 243       {
 244         __glibcxx_check_max_load_factor(__f);
 245         _Base::max_load_factor(__f);
 246       }
 247
 248       template<typename... _Args>
 249         std::pair<iterator, bool>
 250         emplace(_Args&&... __args)
 251         {
 252           size_type __bucket_count = this->bucket_count();
 253           std::pair<_Base_iterator, bool> __res
 254             = _Base::emplace(std::forward<_Args>(__args)...);
 255           _M_check_rehashed(__bucket_count);
 256           return std::make_pair(iterator(__res.first, this), __res.second);
 257         }
 258
 259       template<typename... _Args>
 260         iterator
 261         emplace_hint(const_iterator __hint, _Args&&... __args)
 262         {
 263           __glibcxx_check_insert(__hint);
 264           size_type __bucket_count = this->bucket_count();
 265           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 266                                         std::forward<_Args>(__args)...);
 267           _M_check_rehashed(__bucket_count);
 268           return iterator(__it, this);
 269         }
 270
 271       std::pair<iterator, bool>
 272       insert(const value_type& __obj)
 273       {
 274         size_type __bucket_count = this->bucket_count();
 275         std::pair<_Base_iterator, bool> __res
 276           = _Base::insert(__obj);
 277         _M_check_rehashed(__bucket_count);
 278         return std::make_pair(iterator(__res.first, this), __res.second);
 279       }
 280
 281       iterator
 282       insert(const_iterator __hint, const value_type& __obj)
 283       {
 284         __glibcxx_check_insert(__hint);
 285         size_type __bucket_count = this->bucket_count();
 286         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 287         _M_check_rehashed(__bucket_count);
 288         return iterator(__it, this);
 289       }
 290
 291       std::pair<iterator, bool>
 292       insert(value_type&& __obj)
 293       {
 294         size_type __bucket_count = this->bucket_count();
 295         std::pair<_Base_iterator, bool> __res
 296           = _Base::insert(std::move(__obj));
 297         _M_check_rehashed(__bucket_count);
 298         return std::make_pair(iterator(__res.first, this), __res.second);
 299       }
 300
 301       iterator
 302       insert(const_iterator __hint, value_type&& __obj)
 303       {
 304         __glibcxx_check_insert(__hint);
 305         size_type __bucket_count = this->bucket_count();
 306         _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
 307         _M_check_rehashed(__bucket_count);
 308         return iterator(__it, this);
 309       }
 310
 311       void
 312       insert(std::initializer_list<value_type> __l)
 313       {
 314         size_type __bucket_count = this->bucket_count();
 315         _Base::insert(__l);
 316         _M_check_rehashed(__bucket_count);
 317       }
 318
 319       template<typename _InputIterator>
 320         void
 321         insert(_InputIterator __first, _InputIterator __last)
 322         {
 323           __glibcxx_check_valid_range(__first, __last);
 324           size_type __bucket_count = this->bucket_count();
 325           _Base::insert(__gnu_debug::__base(__first),
 326                         __gnu_debug::__base(__last));
 327           _M_check_rehashed(__bucket_count);
 328         }
 329
 330       iterator
 331       find(const key_type& __key)
 332       { return iterator(_Base::find(__key), this); }
 333
 334       const_iterator
 335       find(const key_type& __key) const
 336       { return const_iterator(_Base::find(__key), this); }
 337
 338       std::pair<iterator, iterator>
 339       equal_range(const key_type& __key)
 340       {
 341         std::pair<_Base_iterator, _Base_iterator> __res
 342           = _Base::equal_range(__key);
 343         return std::make_pair(iterator(__res.first, this),
 344                               iterator(__res.second, this));
 345       }
 346
 347       std::pair<const_iterator, const_iterator>
 348       equal_range(const key_type& __key) const
 349       {
 350         std::pair<_Base_const_iterator, _Base_const_iterator>
 351           __res = _Base::equal_range(__key);
 352         return std::make_pair(const_iterator(__res.first, this),
 353                               const_iterator(__res.second, this));
 354       }
 355
 356       size_type
 357       erase(const key_type& __key)
 358       {
 359         size_type __ret(0);
 360         _Base_iterator __victim(_Base::find(__key));
 361         if (__victim != _Base::end())
 362           {
 363             this->_M_invalidate_if(
 364                             [__victim](_Base_const_iterator __it)
 365                             { return __it == __victim; });
 366             this->_M_invalidate_local_if(
 367                             [__victim](_Base_const_local_iterator __it)
 368                             { return __it._M_curr() == __victim._M_cur; });
 369             size_type __bucket_count = this->bucket_count();
 370             _Base::erase(__victim);
 371             _M_check_rehashed(__bucket_count);
 372             __ret = 1;
 373           }
 374         return __ret;
 375       }
 376
 377       iterator
 378       erase(const_iterator __it)
 379       {
 380         __glibcxx_check_erase(__it);
 381         _Base_const_iterator __victim = __it.base();
 382         this->_M_invalidate_if(
 383                         [__victim](_Base_const_iterator __it)
 384                         { return __it == __victim; });
 385         this->_M_invalidate_local_if(
 386                         [__victim](_Base_const_local_iterator __it)
 387                         { return __it._M_curr() == __victim._M_cur; });
 388         size_type __bucket_count = this->bucket_count();
 389         _Base_iterator __next = _Base::erase(__it.base());
 390         _M_check_rehashed(__bucket_count);
 391         return iterator(__next, this);
 392       }
 393
 394       iterator
 395       erase(iterator __it)
 396       { return erase(const_iterator(__it)); }
 397
 398       iterator
 399       erase(const_iterator __first, const_iterator __last)
 400       {
 401         __glibcxx_check_erase_range(__first, __last);
 402         for (_Base_const_iterator __tmp = __first.base();
 403              __tmp != __last.base(); ++__tmp)
 404           {
 405             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 406                                   _M_message(__gnu_debug::__msg_valid_range)
 407                                   ._M_iterator(__first, "first")
 408                                   ._M_iterator(__last, "last"));
 409             this->_M_invalidate_if(
 410                             [__tmp](_Base_const_iterator __it)
 411                             { return __it == __tmp; });
 412             this->_M_invalidate_local_if(
 413                             [__tmp](_Base_const_local_iterator __it)
 414                             { return __it._M_curr() == __tmp._M_cur; });
 415           }
 416         size_type __bucket_count = this->bucket_count();
 417         _Base_iterator __next = _Base::erase(__first.base(),
 418                                              __last.base());
 419         _M_check_rehashed(__bucket_count);
 420         return iterator(__next, this);
 421       }
 422
 423       _Base&
 424       _M_base() noexcept { return *this; }
 425
 426       const _Base&
 427       _M_base() const noexcept { return *this; }
 428
 429     private:
 430       void
 431       _M_check_rehashed(size_type __prev_count)
 432       {
 433         if (__prev_count != this->bucket_count())
 434           this->_M_invalidate_locals();
 435       }
 436     };
 437
 438   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 439     inline void
 440     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 441          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 442     { __x.swap(__y); }
 443
 444   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 445     inline bool
 446     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 447                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 448     { return __x._M_base() == __y._M_base(); }
 449
 450   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 451     inline bool
 452     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 453                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 454     { return !(__x == __y); }
 455
 456
 457   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
 458   template<typename _Value,
 459            typename _Hash = std::hash<_Value>,
 460            typename _Pred = std::equal_to<_Value>,
 461            typename _Alloc = std::allocator<_Value> >
 462     class unordered_multiset
 463     : public __gnu_debug::_Safe_container<
 464         unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
 465         __gnu_debug::_Safe_unordered_container>,
 466       public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
 467     {
 468       typedef _GLIBCXX_STD_C::unordered_multiset<
 469         _Value, _Hash, _Pred, _Alloc>                           _Base;
 470       typedef __gnu_debug::_Safe_container<unordered_multiset,
 471         _Alloc, __gnu_debug::_Safe_unordered_container>         _Safe;
 472       typedef typename _Base::const_iterator    _Base_const_iterator;
 473       typedef typename _Base::iterator          _Base_iterator;
 474       typedef typename _Base::const_local_iterator
 475                                                 _Base_const_local_iterator;
 476       typedef typename _Base::local_iterator    _Base_local_iterator;
 477
 478     public:
 479       typedef typename _Base::size_type                 size_type;
 480       typedef typename _Base::hasher                    hasher;
 481       typedef typename _Base::key_equal                 key_equal;
 482       typedef typename _Base::allocator_type            allocator_type;
 483
 484       typedef typename _Base::key_type                  key_type;
 485       typedef typename _Base::value_type                value_type;
 486
 487       typedef __gnu_debug::_Safe_iterator<
 488         _Base_iterator, unordered_multiset>             iterator;
 489       typedef __gnu_debug::_Safe_iterator<
 490         _Base_const_iterator, unordered_multiset>       const_iterator;
 491       typedef __gnu_debug::_Safe_local_iterator<
 492         _Base_local_iterator, unordered_multiset>       local_iterator;
 493       typedef __gnu_debug::_Safe_local_iterator<
 494         _Base_const_local_iterator, unordered_multiset> const_local_iterator;
 495
 496       unordered_multiset() = default;
 497
 498       explicit
 499       unordered_multiset(size_type __n,
 500                          const hasher& __hf = hasher(),
 501                          const key_equal& __eql = key_equal(),
 502                          const allocator_type& __a = allocator_type())
 503       : _Base(__n, __hf, __eql, __a) { }
 504
 505       template<typename _InputIterator>
 506         unordered_multiset(_InputIterator __first, _InputIterator __last,
 507                            size_type __n = 0,
 508                            const hasher& __hf = hasher(),
 509                            const key_equal& __eql = key_equal(),
 510                            const allocator_type& __a = allocator_type())
 511         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 512                                                                      __last)),
 513                 __gnu_debug::__base(__last), __n,
 514                 __hf, __eql, __a) { }
 515
 516       unordered_multiset(const unordered_multiset&) = default;
 517
 518       unordered_multiset(const _Base& __x)
 519       : _Base(__x) { }
 520
 521       unordered_multiset(unordered_multiset&&) = default;
 522
 523       explicit
 524       unordered_multiset(const allocator_type& __a)
 525       : _Base(__a) { }
 526
 527       unordered_multiset(const unordered_multiset& __uset,
 528                          const allocator_type& __a)
 529       : _Base(__uset, __a) { }
 530
 531       unordered_multiset(unordered_multiset&& __uset,
 532                          const allocator_type& __a)
 533       : _Safe(std::move(__uset._M_safe()), __a),
 534         _Base(std::move(__uset._M_base()), __a) { }
 535
 536       unordered_multiset(initializer_list<value_type> __l,
 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(__l, __n, __hf, __eql, __a) { }
 542
 543       ~unordered_multiset() = default;
 544
 545       unordered_multiset&
 546       operator=(const unordered_multiset&) = default;
 547
 548       unordered_multiset&
 549       operator=(unordered_multiset&&) = default;
 550
 551       unordered_multiset&
 552       operator=(initializer_list<value_type> __l)
 553       {
 554         this->_M_base() = __l;
 555         this->_M_invalidate_all();
 556         return *this;
 557       }
 558
 559       void
 560       swap(unordered_multiset& __x)
 561         noexcept( noexcept(declval<_Base>().swap(__x)) )
 562       {
 563         _Safe::_M_swap(__x);
 564         _Base::swap(__x);
 565       }
 566
 567       void
 568       clear() noexcept
 569       {
 570         _Base::clear();
 571         this->_M_invalidate_all();
 572       }
 573
 574       iterator
 575       begin() noexcept
 576       { return iterator(_Base::begin(), this); }
 577
 578       const_iterator
 579       begin() const noexcept
 580       { return const_iterator(_Base::begin(), this); }
 581
 582       iterator
 583       end() noexcept
 584       { return iterator(_Base::end(), this); }
 585
 586       const_iterator
 587       end() const noexcept
 588       { return const_iterator(_Base::end(), this); }
 589
 590       const_iterator
 591       cbegin() const noexcept
 592       { return const_iterator(_Base::begin(), this); }
 593
 594       const_iterator
 595       cend() const noexcept
 596       { return const_iterator(_Base::end(), this); }
 597
 598       // local versions
 599       local_iterator
 600       begin(size_type __b)
 601       {
 602         __glibcxx_check_bucket_index(__b);
 603         return local_iterator(_Base::begin(__b), this);
 604       }
 605
 606       local_iterator
 607       end(size_type __b)
 608       {
 609         __glibcxx_check_bucket_index(__b);
 610         return local_iterator(_Base::end(__b), this);
 611       }
 612
 613       const_local_iterator
 614       begin(size_type __b) const
 615       {
 616         __glibcxx_check_bucket_index(__b);
 617         return const_local_iterator(_Base::begin(__b), this);
 618       }
 619
 620       const_local_iterator
 621       end(size_type __b) const
 622       {
 623         __glibcxx_check_bucket_index(__b);
 624         return const_local_iterator(_Base::end(__b), this);
 625       }
 626
 627       const_local_iterator
 628       cbegin(size_type __b) const
 629       {
 630         __glibcxx_check_bucket_index(__b);
 631         return const_local_iterator(_Base::cbegin(__b), this);
 632       }
 633
 634       const_local_iterator
 635       cend(size_type __b) const
 636       {
 637         __glibcxx_check_bucket_index(__b);
 638         return const_local_iterator(_Base::cend(__b), this);
 639       }
 640
 641       size_type
 642       bucket_size(size_type __b) const
 643       {
 644         __glibcxx_check_bucket_index(__b);
 645         return _Base::bucket_size(__b);
 646       }
 647
 648       float
 649       max_load_factor() const noexcept
 650       { return _Base::max_load_factor(); }
 651
 652       void
 653       max_load_factor(float __f)
 654       {
 655         __glibcxx_check_max_load_factor(__f);
 656         _Base::max_load_factor(__f);
 657       }
 658
 659       template<typename... _Args>
 660         iterator
 661         emplace(_Args&&... __args)
 662         {
 663           size_type __bucket_count = this->bucket_count();
 664           _Base_iterator __it
 665             = _Base::emplace(std::forward<_Args>(__args)...);
 666           _M_check_rehashed(__bucket_count);
 667           return iterator(__it, this);
 668         }
 669
 670       template<typename... _Args>
 671         iterator
 672         emplace_hint(const_iterator __hint, _Args&&... __args)
 673         {
 674           __glibcxx_check_insert(__hint);
 675           size_type __bucket_count = this->bucket_count();
 676           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 677                                         std::forward<_Args>(__args)...);
 678           _M_check_rehashed(__bucket_count);
 679           return iterator(__it, this);
 680         }
 681
 682       iterator
 683       insert(const value_type& __obj)
 684       {
 685         size_type __bucket_count = this->bucket_count();
 686         _Base_iterator __it = _Base::insert(__obj);
 687         _M_check_rehashed(__bucket_count);
 688         return iterator(__it, this);
 689       }
 690
 691       iterator
 692       insert(const_iterator __hint, const value_type& __obj)
 693       {
 694         __glibcxx_check_insert(__hint);
 695         size_type __bucket_count = this->bucket_count();
 696         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 697         _M_check_rehashed(__bucket_count);
 698         return iterator(__it, this);
 699       }
 700
 701       iterator
 702       insert(value_type&& __obj)
 703       {
 704         size_type __bucket_count = this->bucket_count();
 705         _Base_iterator __it = _Base::insert(std::move(__obj));
 706         _M_check_rehashed(__bucket_count);
 707         return iterator(__it, this);
 708       }
 709
 710       iterator
 711       insert(const_iterator __hint, value_type&& __obj)
 712       {
 713         __glibcxx_check_insert(__hint);
 714         size_type __bucket_count = this->bucket_count();
 715         _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
 716         _M_check_rehashed(__bucket_count);
 717         return iterator(__it, this);
 718       }
 719
 720       void
 721       insert(std::initializer_list<value_type> __l)
 722       {
 723         size_type __bucket_count = this->bucket_count();
 724         _Base::insert(__l);
 725         _M_check_rehashed(__bucket_count);
 726       }
 727
 728       template<typename _InputIterator>
 729         void
 730         insert(_InputIterator __first, _InputIterator __last)
 731         {
 732           __glibcxx_check_valid_range(__first, __last);
 733           size_type __bucket_count = this->bucket_count();
 734           _Base::insert(__gnu_debug::__base(__first),
 735                         __gnu_debug::__base(__last));
 736           _M_check_rehashed(__bucket_count);
 737         }
 738
 739       iterator
 740       find(const key_type& __key)
 741       { return iterator(_Base::find(__key), this); }
 742
 743       const_iterator
 744       find(const key_type& __key) const
 745       { return const_iterator(_Base::find(__key), this); }
 746
 747       std::pair<iterator, iterator>
 748       equal_range(const key_type& __key)
 749       {
 750         std::pair<_Base_iterator, _Base_iterator> __res
 751           = _Base::equal_range(__key);
 752         return std::make_pair(iterator(__res.first, this),
 753                               iterator(__res.second, this));
 754       }
 755
 756       std::pair<const_iterator, const_iterator>
 757       equal_range(const key_type& __key) const
 758       {
 759         std::pair<_Base_const_iterator, _Base_const_iterator>
 760           __res = _Base::equal_range(__key);
 761         return std::make_pair(const_iterator(__res.first, this),
 762                               const_iterator(__res.second, this));
 763       }
 764
 765       size_type
 766       erase(const key_type& __key)
 767       {
 768         size_type __ret(0);
 769         std::pair<_Base_iterator, _Base_iterator> __pair =
 770           _Base::equal_range(__key);
 771         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
 772           {
 773             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 774                             { return __it == __victim; });
 775             this->_M_invalidate_local_if(
 776                             [__victim](_Base_const_local_iterator __it)
 777                             { return __it._M_curr() == __victim._M_cur; });
 778             _Base::erase(__victim++);
 779             ++__ret;
 780           }
 781         return __ret;
 782       }
 783
 784       iterator
 785       erase(const_iterator __it)
 786       {
 787         __glibcxx_check_erase(__it);
 788         _Base_const_iterator __victim = __it.base();
 789         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 790                         { return __it == __victim; });
 791         this->_M_invalidate_local_if(
 792                         [__victim](_Base_const_local_iterator __it)
 793                         { return __it._M_curr() == __victim._M_cur; });
 794         return iterator(_Base::erase(__it.base()), this);
 795       }
 796
 797       iterator
 798       erase(iterator __it)
 799       { return erase(const_iterator(__it)); }
 800
 801       iterator
 802       erase(const_iterator __first, const_iterator __last)
 803       {
 804         __glibcxx_check_erase_range(__first, __last);
 805         for (_Base_const_iterator __tmp = __first.base();
 806              __tmp != __last.base(); ++__tmp)
 807           {
 808             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 809                                   _M_message(__gnu_debug::__msg_valid_range)
 810                                   ._M_iterator(__first, "first")
 811                                   ._M_iterator(__last, "last"));
 812             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
 813                             { return __it == __tmp; });
 814             this->_M_invalidate_local_if(
 815                             [__tmp](_Base_const_local_iterator __it)
 816                             { return __it._M_curr() == __tmp._M_cur; });
 817           }
 818         return iterator(_Base::erase(__first.base(),
 819                                      __last.base()), this);
 820       }
 821
 822       _Base&
 823       _M_base() noexcept        { return *this; }
 824
 825       const _Base&
 826       _M_base() const noexcept  { return *this; }
 827
 828     private:
 829       void
 830       _M_check_rehashed(size_type __prev_count)
 831       {
 832         if (__prev_count != this->bucket_count())
 833           this->_M_invalidate_locals();
 834       }
 835     };
 836
 837   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 838     inline void
 839     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 840          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 841     { __x.swap(__y); }
 842
 843   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 844     inline bool
 845     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 846                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 847     { return __x._M_base() == __y._M_base(); }
 848
 849   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 850     inline bool
 851     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 852                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 853     { return !(__x == __y); }
 854
 855 } // namespace __debug
 856 } // namespace std
 857
 858 #endif // C++11
 859
 860 #endif