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