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