libstdc++-v3/include/debug/unordered_set

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