libstdc++-v3/include/debug/unordered_set

   1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2016 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 #pragma GCC system_header
  33
  34 #if __cplusplus < 201103L
  35 # include <bits/c++0x_warning.h>
  36 #else
  37 # include <unordered_set>
  38
  39 #include <debug/safe_unordered_container.h>
  40 #include <debug/safe_container.h>
  41 #include <debug/safe_iterator.h>
  42 #include <debug/safe_local_iterator.h>
  43
  44 namespace std _GLIBCXX_VISIBILITY(default)
  45 {
  46 namespace __debug
  47 {
  48   /// Class std::unordered_set with safety/checking/debug instrumentation.
  49   template<typename _Value,
  50            typename _Hash = std::hash<_Value>,
  51            typename _Pred = std::equal_to<_Value>,
  52            typename _Alloc = std::allocator<_Value> >
  53     class unordered_set
  54     : public __gnu_debug::_Safe_container<
  55         unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc,
  56         __gnu_debug::_Safe_unordered_container>,
  57       public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>
  58     {
  59       typedef _GLIBCXX_STD_C::unordered_set<
  60         _Value, _Hash, _Pred, _Alloc>                                   _Base;
  61       typedef __gnu_debug::_Safe_container<
  62         unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container>  _Safe;
  63
  64       typedef typename _Base::const_iterator       _Base_const_iterator;
  65       typedef typename _Base::iterator             _Base_iterator;
  66       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
  67       typedef typename _Base::local_iterator       _Base_local_iterator;
  68
  69     public:
  70       typedef typename _Base::size_type                 size_type;
  71       typedef typename _Base::hasher                    hasher;
  72       typedef typename _Base::key_equal                 key_equal;
  73       typedef typename _Base::allocator_type            allocator_type;
  74
  75       typedef typename _Base::key_type                  key_type;
  76       typedef typename _Base::value_type                value_type;
  77
  78       typedef __gnu_debug::_Safe_iterator<
  79         _Base_iterator, unordered_set>                  iterator;
  80       typedef __gnu_debug::_Safe_iterator<
  81         _Base_const_iterator, unordered_set>            const_iterator;
  82       typedef __gnu_debug::_Safe_local_iterator<
  83         _Base_local_iterator, unordered_set>            local_iterator;
  84       typedef __gnu_debug::_Safe_local_iterator<
  85         _Base_const_local_iterator, unordered_set>      const_local_iterator;
  86
  87       unordered_set() = default;
  88
  89       explicit
  90       unordered_set(size_type __n,
  91                     const hasher& __hf = hasher(),
  92                     const key_equal& __eql = key_equal(),
  93                     const allocator_type& __a = allocator_type())
  94       : _Base(__n, __hf, __eql, __a) { }
  95
  96       template<typename _InputIterator>
  97         unordered_set(_InputIterator __first, _InputIterator __last,
  98                       size_type __n = 0,
  99                       const hasher& __hf = hasher(),
 100                       const key_equal& __eql = key_equal(),
 101                       const allocator_type& __a = allocator_type())
 102         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 103                                                                      __last)),
 104                 __gnu_debug::__base(__last), __n,
 105                 __hf, __eql, __a) { }
 106
 107       unordered_set(const unordered_set&) = default;
 108
 109       unordered_set(const _Base& __x)
 110       : _Base(__x) { }
 111
 112       unordered_set(unordered_set&&) = default;
 113
 114       explicit
 115       unordered_set(const allocator_type& __a)
 116       : _Base(__a) { }
 117
 118       unordered_set(const unordered_set& __uset,
 119                     const allocator_type& __a)
 120       : _Base(__uset, __a) { }
 121
 122       unordered_set(unordered_set&& __uset,
 123                     const allocator_type& __a)
 124       : _Safe(std::move(__uset._M_safe()), __a),
 125         _Base(std::move(__uset._M_base()), __a) { }
 126
 127       unordered_set(initializer_list<value_type> __l,
 128                     size_type __n = 0,
 129                     const hasher& __hf = hasher(),
 130                     const key_equal& __eql = key_equal(),
 131                     const allocator_type& __a = allocator_type())
 132       : _Base(__l, __n, __hf, __eql, __a) { }
 133
 134       unordered_set(size_type __n, const allocator_type& __a)
 135         : unordered_set(__n, hasher(), key_equal(), __a)
 136       { }
 137
 138       unordered_set(size_type __n, const hasher& __hf,
 139                     const allocator_type& __a)
 140         : unordered_set(__n, __hf, key_equal(), __a)
 141       { }
 142
 143       template<typename _InputIterator>
 144         unordered_set(_InputIterator __first, _InputIterator __last,
 145                       size_type __n,
 146                       const allocator_type& __a)
 147           : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
 148         { }
 149
 150       template<typename _InputIterator>
 151         unordered_set(_InputIterator __first, _InputIterator __last,
 152                       size_type __n, const hasher& __hf,
 153                       const allocator_type& __a)
 154           : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
 155         { }
 156
 157       unordered_set(initializer_list<value_type> __l,
 158                     size_type __n,
 159                     const allocator_type& __a)
 160         : unordered_set(__l, __n, hasher(), key_equal(), __a)
 161       { }
 162
 163       unordered_set(initializer_list<value_type> __l,
 164                     size_type __n, const hasher& __hf,
 165                     const allocator_type& __a)
 166         : unordered_set(__l, __n, __hf, key_equal(), __a)
 167       { }
 168
 169       ~unordered_set() = default;
 170
 171       unordered_set&
 172       operator=(const unordered_set&) = default;
 173
 174       unordered_set&
 175       operator=(unordered_set&&) = default;
 176
 177       unordered_set&
 178       operator=(initializer_list<value_type> __l)
 179       {
 180         _M_base() = __l;
 181         this->_M_invalidate_all();
 182         return *this;
 183       }
 184
 185       void
 186       swap(unordered_set& __x)
 187         noexcept( noexcept(declval<_Base&>().swap(__x)) )
 188       {
 189         _Safe::_M_swap(__x);
 190         _Base::swap(__x);
 191       }
 192
 193       void
 194       clear() noexcept
 195       {
 196         _Base::clear();
 197         this->_M_invalidate_all();
 198       }
 199
 200       iterator
 201       begin() noexcept
 202       { return iterator(_Base::begin(), this); }
 203
 204       const_iterator
 205       begin() const noexcept
 206       { return const_iterator(_Base::begin(), this); }
 207
 208       iterator
 209       end() noexcept
 210       { return iterator(_Base::end(), this); }
 211
 212       const_iterator
 213       end() const noexcept
 214       { return const_iterator(_Base::end(), this); }
 215
 216       const_iterator
 217       cbegin() const noexcept
 218       { return const_iterator(_Base::begin(), this); }
 219
 220       const_iterator
 221       cend() const noexcept
 222       { return const_iterator(_Base::end(), this); }
 223
 224       // local versions
 225       local_iterator
 226       begin(size_type __b)
 227       {
 228         __glibcxx_check_bucket_index(__b);
 229         return local_iterator(_Base::begin(__b), this);
 230       }
 231
 232       local_iterator
 233       end(size_type __b)
 234       {
 235         __glibcxx_check_bucket_index(__b);
 236         return local_iterator(_Base::end(__b), this);
 237       }
 238
 239       const_local_iterator
 240       begin(size_type __b) const
 241       {
 242         __glibcxx_check_bucket_index(__b);
 243         return const_local_iterator(_Base::begin(__b), this);
 244       }
 245
 246       const_local_iterator
 247       end(size_type __b) const
 248       {
 249         __glibcxx_check_bucket_index(__b);
 250         return const_local_iterator(_Base::end(__b), this);
 251       }
 252
 253       const_local_iterator
 254       cbegin(size_type __b) const
 255       {
 256         __glibcxx_check_bucket_index(__b);
 257         return const_local_iterator(_Base::cbegin(__b), this);
 258       }
 259
 260       const_local_iterator
 261       cend(size_type __b) const
 262       {
 263         __glibcxx_check_bucket_index(__b);
 264         return const_local_iterator(_Base::cend(__b), this);
 265       }
 266
 267       size_type
 268       bucket_size(size_type __b) const
 269       {
 270         __glibcxx_check_bucket_index(__b);
 271         return _Base::bucket_size(__b);
 272       }
 273
 274       float
 275       max_load_factor() const noexcept
 276       { return _Base::max_load_factor(); }
 277
 278       void
 279       max_load_factor(float __f)
 280       {
 281         __glibcxx_check_max_load_factor(__f);
 282         _Base::max_load_factor(__f);
 283       }
 284
 285       template<typename... _Args>
 286         std::pair<iterator, bool>
 287         emplace(_Args&&... __args)
 288         {
 289           size_type __bucket_count = this->bucket_count();
 290           std::pair<_Base_iterator, bool> __res
 291             = _Base::emplace(std::forward<_Args>(__args)...);
 292           _M_check_rehashed(__bucket_count);
 293           return std::make_pair(iterator(__res.first, this), __res.second);
 294         }
 295
 296       template<typename... _Args>
 297         iterator
 298         emplace_hint(const_iterator __hint, _Args&&... __args)
 299         {
 300           __glibcxx_check_insert(__hint);
 301           size_type __bucket_count = this->bucket_count();
 302           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 303                                         std::forward<_Args>(__args)...);
 304           _M_check_rehashed(__bucket_count);
 305           return iterator(__it, this);
 306         }
 307
 308       std::pair<iterator, bool>
 309       insert(const value_type& __obj)
 310       {
 311         size_type __bucket_count = this->bucket_count();
 312         std::pair<_Base_iterator, bool> __res
 313           = _Base::insert(__obj);
 314         _M_check_rehashed(__bucket_count);
 315         return std::make_pair(iterator(__res.first, this), __res.second);
 316       }
 317
 318       iterator
 319       insert(const_iterator __hint, const value_type& __obj)
 320       {
 321         __glibcxx_check_insert(__hint);
 322         size_type __bucket_count = this->bucket_count();
 323         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 324         _M_check_rehashed(__bucket_count);
 325         return iterator(__it, this);
 326       }
 327
 328       std::pair<iterator, bool>
 329       insert(value_type&& __obj)
 330       {
 331         size_type __bucket_count = this->bucket_count();
 332         std::pair<_Base_iterator, bool> __res
 333           = _Base::insert(std::move(__obj));
 334         _M_check_rehashed(__bucket_count);
 335         return std::make_pair(iterator(__res.first, this), __res.second);
 336       }
 337
 338       iterator
 339       insert(const_iterator __hint, value_type&& __obj)
 340       {
 341         __glibcxx_check_insert(__hint);
 342         size_type __bucket_count = this->bucket_count();
 343         _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
 344         _M_check_rehashed(__bucket_count);
 345         return iterator(__it, this);
 346       }
 347
 348       void
 349       insert(std::initializer_list<value_type> __l)
 350       {
 351         size_type __bucket_count = this->bucket_count();
 352         _Base::insert(__l);
 353         _M_check_rehashed(__bucket_count);
 354       }
 355
 356       template<typename _InputIterator>
 357         void
 358         insert(_InputIterator __first, _InputIterator __last)
 359         {
 360           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 361           __glibcxx_check_valid_range2(__first, __last, __dist);
 362           size_type __bucket_count = this->bucket_count();
 363
 364           if (__dist.second >= __gnu_debug::__dp_sign)
 365             _Base::insert(__gnu_debug::__unsafe(__first),
 366                           __gnu_debug::__unsafe(__last));
 367           else
 368             _Base::insert(__first, __last);
 369
 370           _M_check_rehashed(__bucket_count);
 371         }
 372
 373 #if __cplusplus > 201402L
 374       using node_type = typename _Base::node_type;
 375
 376       struct insert_return_type
 377       {
 378         bool inserted;
 379         iterator position;
 380         node_type node;
 381       };
 382
 383       node_type
 384       extract(const_iterator __position)
 385       {
 386         __glibcxx_check_erase(__position);
 387         _Base_const_iterator __victim = __position.base();
 388         this->_M_invalidate_if(
 389             [__victim](_Base_const_iterator __it) { return __it == __victim; }
 390             );
 391         this->_M_invalidate_local_if(
 392             [__victim](_Base_const_local_iterator __it) {
 393                 return __it._M_curr() == __victim._M_cur;
 394             });
 395         return _Base::extract(__position.base());
 396       }
 397
 398       node_type
 399       extract(const key_type& __key)
 400       {
 401         const auto __position = find(__key);
 402         if (__position != end())
 403           return extract(__position);
 404         return {};
 405       }
 406
 407       insert_return_type
 408       insert(node_type&& __nh)
 409       {
 410         auto __ret = _Base::insert(std::move(__nh));
 411         iterator __pos = iterator(__ret.position, this);
 412         return { __ret.inserted, __pos, std::move(__ret.node) };
 413       }
 414
 415       iterator
 416       insert(const_iterator __hint, node_type&& __nh)
 417       {
 418         __glibcxx_check_insert(__hint);
 419         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
 420       }
 421
 422       using _Base::merge;
 423 #endif // C++17
 424
 425       iterator
 426       find(const key_type& __key)
 427       { return iterator(_Base::find(__key), this); }
 428
 429       const_iterator
 430       find(const key_type& __key) const
 431       { return const_iterator(_Base::find(__key), this); }
 432
 433       std::pair<iterator, iterator>
 434       equal_range(const key_type& __key)
 435       {
 436         std::pair<_Base_iterator, _Base_iterator> __res
 437           = _Base::equal_range(__key);
 438         return std::make_pair(iterator(__res.first, this),
 439                               iterator(__res.second, this));
 440       }
 441
 442       std::pair<const_iterator, const_iterator>
 443       equal_range(const key_type& __key) const
 444       {
 445         std::pair<_Base_const_iterator, _Base_const_iterator>
 446           __res = _Base::equal_range(__key);
 447         return std::make_pair(const_iterator(__res.first, this),
 448                               const_iterator(__res.second, this));
 449       }
 450
 451       size_type
 452       erase(const key_type& __key)
 453       {
 454         size_type __ret(0);
 455         _Base_iterator __victim(_Base::find(__key));
 456         if (__victim != _Base::end())
 457           {
 458             this->_M_invalidate_if(
 459                             [__victim](_Base_const_iterator __it)
 460                             { return __it == __victim; });
 461             this->_M_invalidate_local_if(
 462                             [__victim](_Base_const_local_iterator __it)
 463                             { return __it._M_curr() == __victim._M_cur; });
 464             size_type __bucket_count = this->bucket_count();
 465             _Base::erase(__victim);
 466             _M_check_rehashed(__bucket_count);
 467             __ret = 1;
 468           }
 469         return __ret;
 470       }
 471
 472       iterator
 473       erase(const_iterator __it)
 474       {
 475         __glibcxx_check_erase(__it);
 476         _Base_const_iterator __victim = __it.base();
 477         this->_M_invalidate_if(
 478                         [__victim](_Base_const_iterator __it)
 479                         { return __it == __victim; });
 480         this->_M_invalidate_local_if(
 481                         [__victim](_Base_const_local_iterator __it)
 482                         { return __it._M_curr() == __victim._M_cur; });
 483         size_type __bucket_count = this->bucket_count();
 484         _Base_iterator __next = _Base::erase(__it.base());
 485         _M_check_rehashed(__bucket_count);
 486         return iterator(__next, this);
 487       }
 488
 489       iterator
 490       erase(iterator __it)
 491       { return erase(const_iterator(__it)); }
 492
 493       iterator
 494       erase(const_iterator __first, const_iterator __last)
 495       {
 496         __glibcxx_check_erase_range(__first, __last);
 497         for (_Base_const_iterator __tmp = __first.base();
 498              __tmp != __last.base(); ++__tmp)
 499           {
 500             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 501                                   _M_message(__gnu_debug::__msg_valid_range)
 502                                   ._M_iterator(__first, "first")
 503                                   ._M_iterator(__last, "last"));
 504             this->_M_invalidate_if(
 505                             [__tmp](_Base_const_iterator __it)
 506                             { return __it == __tmp; });
 507             this->_M_invalidate_local_if(
 508                             [__tmp](_Base_const_local_iterator __it)
 509                             { return __it._M_curr() == __tmp._M_cur; });
 510           }
 511         size_type __bucket_count = this->bucket_count();
 512         _Base_iterator __next = _Base::erase(__first.base(),
 513                                              __last.base());
 514         _M_check_rehashed(__bucket_count);
 515         return iterator(__next, this);
 516       }
 517
 518       _Base&
 519       _M_base() noexcept { return *this; }
 520
 521       const _Base&
 522       _M_base() const noexcept { return *this; }
 523
 524     private:
 525       void
 526       _M_check_rehashed(size_type __prev_count)
 527       {
 528         if (__prev_count != this->bucket_count())
 529           this->_M_invalidate_locals();
 530       }
 531     };
 532
 533   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 534     inline void
 535     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 536          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 537     noexcept(noexcept(__x.swap(__y)))
 538     { __x.swap(__y); }
 539
 540   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 541     inline bool
 542     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 543                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 544     { return __x._M_base() == __y._M_base(); }
 545
 546   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 547     inline bool
 548     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 549                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 550     { return !(__x == __y); }
 551
 552
 553   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
 554   template<typename _Value,
 555            typename _Hash = std::hash<_Value>,
 556            typename _Pred = std::equal_to<_Value>,
 557            typename _Alloc = std::allocator<_Value> >
 558     class unordered_multiset
 559     : public __gnu_debug::_Safe_container<
 560         unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
 561         __gnu_debug::_Safe_unordered_container>,
 562       public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
 563     {
 564       typedef _GLIBCXX_STD_C::unordered_multiset<
 565         _Value, _Hash, _Pred, _Alloc>                           _Base;
 566       typedef __gnu_debug::_Safe_container<unordered_multiset,
 567         _Alloc, __gnu_debug::_Safe_unordered_container>         _Safe;
 568       typedef typename _Base::const_iterator    _Base_const_iterator;
 569       typedef typename _Base::iterator          _Base_iterator;
 570       typedef typename _Base::const_local_iterator
 571                                                 _Base_const_local_iterator;
 572       typedef typename _Base::local_iterator    _Base_local_iterator;
 573
 574     public:
 575       typedef typename _Base::size_type                 size_type;
 576       typedef typename _Base::hasher                    hasher;
 577       typedef typename _Base::key_equal                 key_equal;
 578       typedef typename _Base::allocator_type            allocator_type;
 579
 580       typedef typename _Base::key_type                  key_type;
 581       typedef typename _Base::value_type                value_type;
 582
 583       typedef __gnu_debug::_Safe_iterator<
 584         _Base_iterator, unordered_multiset>             iterator;
 585       typedef __gnu_debug::_Safe_iterator<
 586         _Base_const_iterator, unordered_multiset>       const_iterator;
 587       typedef __gnu_debug::_Safe_local_iterator<
 588         _Base_local_iterator, unordered_multiset>       local_iterator;
 589       typedef __gnu_debug::_Safe_local_iterator<
 590         _Base_const_local_iterator, unordered_multiset> const_local_iterator;
 591
 592       unordered_multiset() = default;
 593
 594       explicit
 595       unordered_multiset(size_type __n,
 596                          const hasher& __hf = hasher(),
 597                          const key_equal& __eql = key_equal(),
 598                          const allocator_type& __a = allocator_type())
 599       : _Base(__n, __hf, __eql, __a) { }
 600
 601       template<typename _InputIterator>
 602         unordered_multiset(_InputIterator __first, _InputIterator __last,
 603                            size_type __n = 0,
 604                            const hasher& __hf = hasher(),
 605                            const key_equal& __eql = key_equal(),
 606                            const allocator_type& __a = allocator_type())
 607         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 608                                                                      __last)),
 609                 __gnu_debug::__base(__last), __n,
 610                 __hf, __eql, __a) { }
 611
 612       unordered_multiset(const unordered_multiset&) = default;
 613
 614       unordered_multiset(const _Base& __x)
 615       : _Base(__x) { }
 616
 617       unordered_multiset(unordered_multiset&&) = default;
 618
 619       explicit
 620       unordered_multiset(const allocator_type& __a)
 621       : _Base(__a) { }
 622
 623       unordered_multiset(const unordered_multiset& __uset,
 624                          const allocator_type& __a)
 625       : _Base(__uset, __a) { }
 626
 627       unordered_multiset(unordered_multiset&& __uset,
 628                          const allocator_type& __a)
 629       : _Safe(std::move(__uset._M_safe()), __a),
 630         _Base(std::move(__uset._M_base()), __a) { }
 631
 632       unordered_multiset(initializer_list<value_type> __l,
 633                          size_type __n = 0,
 634                          const hasher& __hf = hasher(),
 635                          const key_equal& __eql = key_equal(),
 636                          const allocator_type& __a = allocator_type())
 637       : _Base(__l, __n, __hf, __eql, __a) { }
 638
 639       unordered_multiset(size_type __n, const allocator_type& __a)
 640         : unordered_multiset(__n, hasher(), key_equal(), __a)
 641       { }
 642
 643       unordered_multiset(size_type __n, const hasher& __hf,
 644                          const allocator_type& __a)
 645         : unordered_multiset(__n, __hf, key_equal(), __a)
 646       { }
 647
 648       template<typename _InputIterator>
 649         unordered_multiset(_InputIterator __first, _InputIterator __last,
 650                            size_type __n,
 651                            const allocator_type& __a)
 652           : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
 653         { }
 654
 655       template<typename _InputIterator>
 656         unordered_multiset(_InputIterator __first, _InputIterator __last,
 657                            size_type __n, const hasher& __hf,
 658                            const allocator_type& __a)
 659           : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
 660         { }
 661
 662       unordered_multiset(initializer_list<value_type> __l,
 663                          size_type __n,
 664                          const allocator_type& __a)
 665         : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
 666       { }
 667
 668       unordered_multiset(initializer_list<value_type> __l,
 669                          size_type __n, const hasher& __hf,
 670                          const allocator_type& __a)
 671         : unordered_multiset(__l, __n, __hf, key_equal(), __a)
 672       { }
 673
 674       ~unordered_multiset() = default;
 675
 676       unordered_multiset&
 677       operator=(const unordered_multiset&) = default;
 678
 679       unordered_multiset&
 680       operator=(unordered_multiset&&) = default;
 681
 682       unordered_multiset&
 683       operator=(initializer_list<value_type> __l)
 684       {
 685         this->_M_base() = __l;
 686         this->_M_invalidate_all();
 687         return *this;
 688       }
 689
 690       void
 691       swap(unordered_multiset& __x)
 692         noexcept( noexcept(declval<_Base&>().swap(__x)) )
 693       {
 694         _Safe::_M_swap(__x);
 695         _Base::swap(__x);
 696       }
 697
 698       void
 699       clear() noexcept
 700       {
 701         _Base::clear();
 702         this->_M_invalidate_all();
 703       }
 704
 705       iterator
 706       begin() noexcept
 707       { return iterator(_Base::begin(), this); }
 708
 709       const_iterator
 710       begin() const noexcept
 711       { return const_iterator(_Base::begin(), this); }
 712
 713       iterator
 714       end() noexcept
 715       { return iterator(_Base::end(), this); }
 716
 717       const_iterator
 718       end() const noexcept
 719       { return const_iterator(_Base::end(), this); }
 720
 721       const_iterator
 722       cbegin() const noexcept
 723       { return const_iterator(_Base::begin(), this); }
 724
 725       const_iterator
 726       cend() const noexcept
 727       { return const_iterator(_Base::end(), this); }
 728
 729       // local versions
 730       local_iterator
 731       begin(size_type __b)
 732       {
 733         __glibcxx_check_bucket_index(__b);
 734         return local_iterator(_Base::begin(__b), this);
 735       }
 736
 737       local_iterator
 738       end(size_type __b)
 739       {
 740         __glibcxx_check_bucket_index(__b);
 741         return local_iterator(_Base::end(__b), this);
 742       }
 743
 744       const_local_iterator
 745       begin(size_type __b) const
 746       {
 747         __glibcxx_check_bucket_index(__b);
 748         return const_local_iterator(_Base::begin(__b), this);
 749       }
 750
 751       const_local_iterator
 752       end(size_type __b) const
 753       {
 754         __glibcxx_check_bucket_index(__b);
 755         return const_local_iterator(_Base::end(__b), this);
 756       }
 757
 758       const_local_iterator
 759       cbegin(size_type __b) const
 760       {
 761         __glibcxx_check_bucket_index(__b);
 762         return const_local_iterator(_Base::cbegin(__b), this);
 763       }
 764
 765       const_local_iterator
 766       cend(size_type __b) const
 767       {
 768         __glibcxx_check_bucket_index(__b);
 769         return const_local_iterator(_Base::cend(__b), this);
 770       }
 771
 772       size_type
 773       bucket_size(size_type __b) const
 774       {
 775         __glibcxx_check_bucket_index(__b);
 776         return _Base::bucket_size(__b);
 777       }
 778
 779       float
 780       max_load_factor() const noexcept
 781       { return _Base::max_load_factor(); }
 782
 783       void
 784       max_load_factor(float __f)
 785       {
 786         __glibcxx_check_max_load_factor(__f);
 787         _Base::max_load_factor(__f);
 788       }
 789
 790       template<typename... _Args>
 791         iterator
 792         emplace(_Args&&... __args)
 793         {
 794           size_type __bucket_count = this->bucket_count();
 795           _Base_iterator __it
 796             = _Base::emplace(std::forward<_Args>(__args)...);
 797           _M_check_rehashed(__bucket_count);
 798           return iterator(__it, this);
 799         }
 800
 801       template<typename... _Args>
 802         iterator
 803         emplace_hint(const_iterator __hint, _Args&&... __args)
 804         {
 805           __glibcxx_check_insert(__hint);
 806           size_type __bucket_count = this->bucket_count();
 807           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 808                                         std::forward<_Args>(__args)...);
 809           _M_check_rehashed(__bucket_count);
 810           return iterator(__it, this);
 811         }
 812
 813       iterator
 814       insert(const value_type& __obj)
 815       {
 816         size_type __bucket_count = this->bucket_count();
 817         _Base_iterator __it = _Base::insert(__obj);
 818         _M_check_rehashed(__bucket_count);
 819         return iterator(__it, this);
 820       }
 821
 822       iterator
 823       insert(const_iterator __hint, const value_type& __obj)
 824       {
 825         __glibcxx_check_insert(__hint);
 826         size_type __bucket_count = this->bucket_count();
 827         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 828         _M_check_rehashed(__bucket_count);
 829         return iterator(__it, this);
 830       }
 831
 832       iterator
 833       insert(value_type&& __obj)
 834       {
 835         size_type __bucket_count = this->bucket_count();
 836         _Base_iterator __it = _Base::insert(std::move(__obj));
 837         _M_check_rehashed(__bucket_count);
 838         return iterator(__it, this);
 839       }
 840
 841       iterator
 842       insert(const_iterator __hint, value_type&& __obj)
 843       {
 844         __glibcxx_check_insert(__hint);
 845         size_type __bucket_count = this->bucket_count();
 846         _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
 847         _M_check_rehashed(__bucket_count);
 848         return iterator(__it, this);
 849       }
 850
 851       void
 852       insert(std::initializer_list<value_type> __l)
 853       {
 854         size_type __bucket_count = this->bucket_count();
 855         _Base::insert(__l);
 856         _M_check_rehashed(__bucket_count);
 857       }
 858
 859       template<typename _InputIterator>
 860         void
 861         insert(_InputIterator __first, _InputIterator __last)
 862         {
 863           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 864           __glibcxx_check_valid_range2(__first, __last, __dist);
 865           size_type __bucket_count = this->bucket_count();
 866
 867           if (__dist.second >= __gnu_debug::__dp_sign)
 868             _Base::insert(__gnu_debug::__unsafe(__first),
 869                           __gnu_debug::__unsafe(__last));
 870           else
 871             _Base::insert(__first, __last);
 872
 873           _M_check_rehashed(__bucket_count);
 874         }
 875
 876 #if __cplusplus > 201402L
 877       using node_type = typename _Base::node_type;
 878
 879       node_type
 880       extract(const_iterator __position)
 881       {
 882         __glibcxx_check_erase(__position);
 883         _Base_const_iterator __victim = __position.base();
 884         this->_M_invalidate_if(
 885             [__victim](_Base_const_iterator __it) { return __it == __victim; }
 886             );
 887         this->_M_invalidate_local_if(
 888             [__victim](_Base_const_local_iterator __it) {
 889                 return __it._M_curr() == __victim._M_cur;
 890             });
 891         return _Base::extract(__position.base());
 892       }
 893
 894       node_type
 895       extract(const key_type& __key)
 896       {
 897         const auto __position = find(__key);
 898         if (__position != end())
 899           return extract(__position);
 900         return {};
 901       }
 902
 903       iterator
 904       insert(node_type&& __nh)
 905       { return iterator(_Base::insert(std::move(__nh)), this); }
 906
 907       iterator
 908       insert(const_iterator __hint, node_type&& __nh)
 909       {
 910         __glibcxx_check_insert(__hint);
 911         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
 912       }
 913
 914       using _Base::merge;
 915 #endif // C++17
 916
 917       iterator
 918       find(const key_type& __key)
 919       { return iterator(_Base::find(__key), this); }
 920
 921       const_iterator
 922       find(const key_type& __key) const
 923       { return const_iterator(_Base::find(__key), this); }
 924
 925       std::pair<iterator, iterator>
 926       equal_range(const key_type& __key)
 927       {
 928         std::pair<_Base_iterator, _Base_iterator> __res
 929           = _Base::equal_range(__key);
 930         return std::make_pair(iterator(__res.first, this),
 931                               iterator(__res.second, this));
 932       }
 933
 934       std::pair<const_iterator, const_iterator>
 935       equal_range(const key_type& __key) const
 936       {
 937         std::pair<_Base_const_iterator, _Base_const_iterator>
 938           __res = _Base::equal_range(__key);
 939         return std::make_pair(const_iterator(__res.first, this),
 940                               const_iterator(__res.second, this));
 941       }
 942
 943       size_type
 944       erase(const key_type& __key)
 945       {
 946         size_type __ret(0);
 947         std::pair<_Base_iterator, _Base_iterator> __pair =
 948           _Base::equal_range(__key);
 949         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
 950           {
 951             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 952                             { return __it == __victim; });
 953             this->_M_invalidate_local_if(
 954                             [__victim](_Base_const_local_iterator __it)
 955                             { return __it._M_curr() == __victim._M_cur; });
 956             _Base::erase(__victim++);
 957             ++__ret;
 958           }
 959         return __ret;
 960       }
 961
 962       iterator
 963       erase(const_iterator __it)
 964       {
 965         __glibcxx_check_erase(__it);
 966         _Base_const_iterator __victim = __it.base();
 967         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 968                         { return __it == __victim; });
 969         this->_M_invalidate_local_if(
 970                         [__victim](_Base_const_local_iterator __it)
 971                         { return __it._M_curr() == __victim._M_cur; });
 972         return iterator(_Base::erase(__it.base()), this);
 973       }
 974
 975       iterator
 976       erase(iterator __it)
 977       { return erase(const_iterator(__it)); }
 978
 979       iterator
 980       erase(const_iterator __first, const_iterator __last)
 981       {
 982         __glibcxx_check_erase_range(__first, __last);
 983         for (_Base_const_iterator __tmp = __first.base();
 984              __tmp != __last.base(); ++__tmp)
 985           {
 986             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 987                                   _M_message(__gnu_debug::__msg_valid_range)
 988                                   ._M_iterator(__first, "first")
 989                                   ._M_iterator(__last, "last"));
 990             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
 991                             { return __it == __tmp; });
 992             this->_M_invalidate_local_if(
 993                             [__tmp](_Base_const_local_iterator __it)
 994                             { return __it._M_curr() == __tmp._M_cur; });
 995           }
 996         return iterator(_Base::erase(__first.base(),
 997                                      __last.base()), this);
 998       }
 999
1000       _Base&
1001       _M_base() noexcept        { return *this; }
1002
1003       const _Base&
1004       _M_base() const noexcept  { return *this; }
1005
1006     private:
1007       void
1008       _M_check_rehashed(size_type __prev_count)
1009       {
1010         if (__prev_count != this->bucket_count())
1011           this->_M_invalidate_locals();
1012       }
1013     };
1014
1015   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1016     inline void
1017     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1018          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1019     noexcept(noexcept(__x.swap(__y)))
1020     { __x.swap(__y); }
1021
1022   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1023     inline bool
1024     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1025                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1026     { return __x._M_base() == __y._M_base(); }
1027
1028   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1029     inline bool
1030     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1031                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1032     { return !(__x == __y); }
1033
1034 } // namespace __debug
1035 } // namespace std
1036
1037 #endif // C++11
1038
1039 #endif