libstdc++-v3/include/debug/unordered_set

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