i686-linux-gnu-4.7/usr/include/c++/4.7/debug/unordered_set

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