l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.7/include/debug/unordered_map

   1 // Debugging unordered_map/unordered_multimap 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_map
  27  *  This file is a GNU debug extension to the Standard C++ Library.
  28  */
  29
  30 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
  31 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
  32
  33 #ifndef __GXX_EXPERIMENTAL_CXX0X__
  34 # include <bits/c++0x_warning.h>
  35 #else
  36 # include <unordered_map>
  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_map with safety/checking/debug instrumentation.
  47   template<typename _Key, typename _Tp,
  48            typename _Hash = std::hash<_Key>,
  49            typename _Pred = std::equal_to<_Key>,
  50            typename _Alloc = std::allocator<_Key> >
  51     class unordered_map
  52     : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
  53       public __gnu_debug::_Safe_unordered_container<unordered_map<_Key, _Tp,
  54                                                         _Hash, _Pred, _Alloc> >
  55     {
  56       typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
  57                                             _Pred, _Alloc> _Base;
  58       typedef __gnu_debug::_Safe_unordered_container<unordered_map> _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_map> iterator;
  75       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  76                                           unordered_map> const_iterator;
  77       typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
  78                                           unordered_map> local_iterator;
  79       typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
  80                                           unordered_map> const_local_iterator;
  81
  82       explicit
  83       unordered_map(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_map(_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_map(const unordered_map& __x) = default;
 101
 102       unordered_map(const _Base& __x)
 103       : _Base(__x) { }
 104
 105       unordered_map(unordered_map&& __x) = default;
 106
 107       unordered_map(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_map() noexcept { }
 115
 116       unordered_map&
 117       operator=(const unordered_map& __x)
 118       {
 119         *static_cast<_Base*>(this) = __x;
 120         this->_M_invalidate_all();
 121         return *this;
 122       }
 123
 124       unordered_map&
 125       operator=(unordered_map&& __x)
 126       {
 127         // NB: DR 1204.
 128         // NB: DR 675.
 129         clear();
 130         swap(__x);
 131         return *this;
 132       }
 133
 134       unordered_map&
 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_map& __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         std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
 233         _M_check_rehashed(__bucket_count);
 234         return std::make_pair(iterator(__res.first, this), __res.second);
 235       }
 236
 237       iterator
 238       insert(const_iterator __hint, const value_type& __obj)
 239       {
 240         __glibcxx_check_insert(__hint);
 241         size_type __bucket_count = this->bucket_count();
 242         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 243         _M_check_rehashed(__bucket_count);
 244         return iterator(__it, this);
 245       }
 246
 247       template<typename _Pair, typename = typename
 248                std::enable_if<std::is_constructible<value_type,
 249                                                     _Pair&&>::value>::type>
 250         std::pair<iterator, bool>
 251         insert(_Pair&& __obj)
 252         {
 253           size_type __bucket_count = this->bucket_count();
 254           std::pair<_Base_iterator, bool> __res =
 255             _Base::insert(std::forward<_Pair>(__obj));
 256           _M_check_rehashed(__bucket_count);
 257           return std::make_pair(iterator(__res.first, this), __res.second);
 258         }
 259
 260       template<typename _Pair, typename = typename
 261                std::enable_if<std::is_constructible<value_type,
 262                                                     _Pair&&>::value>::type>
 263         iterator
 264         insert(const_iterator __hint, _Pair&& __obj)
 265         {
 266           __glibcxx_check_insert(__hint);
 267           size_type __bucket_count = this->bucket_count();
 268           _Base_iterator __it =
 269             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
 270           _M_check_rehashed(__bucket_count);
 271           return iterator(__it, this);
 272         }
 273
 274       void
 275       insert(std::initializer_list<value_type> __l)
 276       {
 277         size_type __bucket_count = this->bucket_count();
 278         _Base::insert(__l);
 279         _M_check_rehashed(__bucket_count);
 280       }
 281
 282       template<typename _InputIterator>
 283         void
 284         insert(_InputIterator __first, _InputIterator __last)
 285         {
 286           __glibcxx_check_valid_range(__first, __last);
 287           size_type __bucket_count = this->bucket_count();
 288           _Base::insert(__gnu_debug::__base(__first),
 289                         __gnu_debug::__base(__last));
 290           _M_check_rehashed(__bucket_count);
 291         }
 292
 293       iterator
 294       find(const key_type& __key)
 295       { return iterator(_Base::find(__key), this); }
 296
 297       const_iterator
 298       find(const key_type& __key) const
 299       { return const_iterator(_Base::find(__key), this); }
 300
 301       std::pair<iterator, iterator>
 302       equal_range(const key_type& __key)
 303       {
 304         std::pair<_Base_iterator, _Base_iterator> __res =
 305           _Base::equal_range(__key);
 306         return std::make_pair(iterator(__res.first, this),
 307                               iterator(__res.second, this));
 308       }
 309
 310       std::pair<const_iterator, const_iterator>
 311       equal_range(const key_type& __key) const
 312       {
 313         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 314           _Base::equal_range(__key);
 315         return std::make_pair(const_iterator(__res.first, this),
 316                               const_iterator(__res.second, this));
 317       }
 318
 319       size_type
 320       erase(const key_type& __key)
 321       {
 322         size_type __ret(0);
 323         _Base_iterator __victim(_Base::find(__key));
 324         if (__victim != _Base::end())
 325           {
 326             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 327                             { return __it == __victim; });
 328             _Base_local_iterator __local_victim = _S_to_local(__victim);
 329             this->_M_invalidate_local_if(
 330                             [__local_victim](_Base_const_local_iterator __it)
 331                             { return __it == __local_victim; });
 332             size_type __bucket_count = this->bucket_count();
 333             _Base::erase(__victim);
 334             _M_check_rehashed(__bucket_count);
 335             __ret = 1;
 336           }
 337         return __ret;
 338       }
 339
 340       iterator
 341       erase(const_iterator __it)
 342       {
 343         __glibcxx_check_erase(__it);
 344         _Base_const_iterator __victim = __it.base();
 345         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 346                         { return __it == __victim; });
 347         _Base_const_local_iterator __local_victim = _S_to_local(__victim);
 348         this->_M_invalidate_local_if(
 349                         [__local_victim](_Base_const_local_iterator __it)
 350                         { return __it == __local_victim; });
 351         size_type __bucket_count = this->bucket_count();
 352         _Base_iterator __next = _Base::erase(__it.base());
 353         _M_check_rehashed(__bucket_count);
 354         return iterator(__next, this);
 355       }
 356
 357       iterator
 358       erase(iterator __it)
 359       { return erase(const_iterator(__it)); }
 360
 361       iterator
 362       erase(const_iterator __first, const_iterator __last)
 363       {
 364         __glibcxx_check_erase_range(__first, __last);
 365         for (_Base_const_iterator __tmp = __first.base();
 366              __tmp != __last.base(); ++__tmp)
 367           {
 368             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 369                                   _M_message(__gnu_debug::__msg_valid_range)
 370                                   ._M_iterator(__first, "first")
 371                                   ._M_iterator(__last, "last"));
 372             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
 373                             { return __it == __tmp; });
 374             _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
 375             this->_M_invalidate_local_if(
 376                             [__local_tmp](_Base_const_local_iterator __it)
 377                             { return __it == __local_tmp; });
 378           }
 379         size_type __bucket_count = this->bucket_count();
 380         _Base_iterator __next = _Base::erase(__first.base(), __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([__end](_Base_const_iterator __it)
 406                         { return __it != __end; });
 407         _M_invalidate_locals();
 408       }
 409
 410       void
 411       _M_check_rehashed(size_type __prev_count)
 412       {
 413         if (__prev_count != this->bucket_count())
 414           _M_invalidate_locals();
 415       }
 416
 417       static _Base_local_iterator
 418       _S_to_local(_Base_iterator __it)
 419       {
 420         // The returned local iterator will not be incremented so we don't
 421         // need to compute __it's node bucket
 422         return _Base_local_iterator(__it._M_cur, 0, 0);
 423       }
 424
 425       static _Base_const_local_iterator
 426       _S_to_local(_Base_const_iterator __it)
 427       {
 428         // The returned local iterator will not be incremented so we don't
 429         // need to compute __it's node bucket
 430         return _Base_const_local_iterator(__it._M_cur, 0, 0);
 431       }
 432     };
 433
 434   template<typename _Key, typename _Tp, typename _Hash,
 435            typename _Pred, typename _Alloc>
 436     inline void
 437     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 438          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 439     { __x.swap(__y); }
 440
 441   template<typename _Key, typename _Tp, typename _Hash,
 442            typename _Pred, typename _Alloc>
 443     inline bool
 444     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 445                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 446     { return __x._M_equal(__y); }
 447
 448   template<typename _Key, typename _Tp, typename _Hash,
 449            typename _Pred, typename _Alloc>
 450     inline bool
 451     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 452                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 453     { return !(__x == __y); }
 454
 455
 456   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
 457   template<typename _Key, typename _Tp,
 458            typename _Hash = std::hash<_Key>,
 459            typename _Pred = std::equal_to<_Key>,
 460            typename _Alloc = std::allocator<_Key> >
 461     class unordered_multimap
 462     : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
 463                                                 _Pred, _Alloc>,
 464       public __gnu_debug::_Safe_unordered_container<unordered_multimap<_Key,
 465                                                 _Tp, _Hash, _Pred, _Alloc> >
 466     {
 467       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
 468                                                  _Pred, _Alloc> _Base;
 469       typedef __gnu_debug::_Safe_unordered_container<unordered_multimap>
 470         _Safe_base;
 471       typedef typename _Base::const_iterator _Base_const_iterator;
 472       typedef typename _Base::iterator _Base_iterator;
 473       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
 474       typedef typename _Base::local_iterator _Base_local_iterator;
 475
 476     public:
 477       typedef typename _Base::size_type       size_type;
 478       typedef typename _Base::hasher          hasher;
 479       typedef typename _Base::key_equal       key_equal;
 480       typedef typename _Base::allocator_type  allocator_type;
 481
 482       typedef typename _Base::key_type        key_type;
 483       typedef typename _Base::value_type      value_type;
 484
 485       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
 486                                           unordered_multimap> iterator;
 487       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 488                                           unordered_multimap> const_iterator;
 489       typedef __gnu_debug::_Safe_local_iterator<
 490         _Base_local_iterator, unordered_multimap> local_iterator;
 491       typedef __gnu_debug::_Safe_local_iterator<
 492         _Base_const_local_iterator, unordered_multimap> const_local_iterator;
 493
 494       explicit
 495       unordered_multimap(size_type __n = 10,
 496                          const hasher& __hf = hasher(),
 497                          const key_equal& __eql = key_equal(),
 498                          const allocator_type& __a = allocator_type())
 499       : _Base(__n, __hf, __eql, __a) { }
 500
 501       template<typename _InputIterator>
 502         unordered_multimap(_InputIterator __first, _InputIterator __last,
 503                            size_type __n = 0,
 504                            const hasher& __hf = hasher(),
 505                            const key_equal& __eql = key_equal(),
 506                            const allocator_type& __a = allocator_type())
 507         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 508                                                                      __last)),
 509                 __gnu_debug::__base(__last), __n,
 510                 __hf, __eql, __a) { }
 511
 512       unordered_multimap(const unordered_multimap& __x) = default;
 513
 514       unordered_multimap(const _Base& __x)
 515       : _Base(__x) { }
 516
 517       unordered_multimap(unordered_multimap&& __x) = default;
 518
 519       unordered_multimap(initializer_list<value_type> __l,
 520                          size_type __n = 0,
 521                          const hasher& __hf = hasher(),
 522                          const key_equal& __eql = key_equal(),
 523                          const allocator_type& __a = allocator_type())
 524       : _Base(__l, __n, __hf, __eql, __a) { }
 525
 526       ~unordered_multimap() noexcept { }
 527
 528       unordered_multimap&
 529       operator=(const unordered_multimap& __x)
 530       {
 531         *static_cast<_Base*>(this) = __x;
 532         this->_M_invalidate_all();
 533         return *this;
 534       }
 535
 536       unordered_multimap&
 537       operator=(unordered_multimap&& __x)
 538       {
 539         // NB: DR 1204.
 540         // NB: DR 675.
 541         clear();
 542         swap(__x);
 543         return *this;
 544       }
 545
 546       unordered_multimap&
 547       operator=(initializer_list<value_type> __l)
 548       {
 549         this->clear();
 550         this->insert(__l);
 551         return *this;
 552       }
 553
 554       void
 555       swap(unordered_multimap& __x)
 556       {
 557         _Base::swap(__x);
 558         _Safe_base::_M_swap(__x);
 559       }
 560
 561       void
 562       clear() noexcept
 563       {
 564         _Base::clear();
 565         this->_M_invalidate_all();
 566       }
 567
 568       iterator
 569       begin() noexcept
 570       { return iterator(_Base::begin(), this); }
 571
 572       const_iterator
 573       begin() const noexcept
 574       { return const_iterator(_Base::begin(), this); }
 575
 576       iterator
 577       end() noexcept
 578       { return iterator(_Base::end(), this); }
 579
 580       const_iterator
 581       end() const noexcept
 582       { return const_iterator(_Base::end(), this); }
 583
 584       const_iterator
 585       cbegin() const noexcept
 586       { return const_iterator(_Base::begin(), this); }
 587
 588       const_iterator
 589       cend() const noexcept
 590       { return const_iterator(_Base::end(), this); }
 591
 592       // local versions
 593       local_iterator
 594       begin(size_type __b)
 595       { return local_iterator(_Base::begin(__b), __b, this); }
 596
 597       local_iterator
 598       end(size_type __b)
 599       { return local_iterator(_Base::end(__b), __b, this); }
 600
 601       const_local_iterator
 602       begin(size_type __b) const
 603       { return const_local_iterator(_Base::begin(__b), __b, this); }
 604
 605       const_local_iterator
 606       end(size_type __b) const
 607       { return const_local_iterator(_Base::end(__b), __b, this); }
 608
 609       const_local_iterator
 610       cbegin(size_type __b) const
 611       { return const_local_iterator(_Base::cbegin(__b), __b, this); }
 612
 613       const_local_iterator
 614       cend(size_type __b) const
 615       { return const_local_iterator(_Base::cend(__b), __b, this); }
 616
 617       template<typename... _Args>
 618         iterator
 619         emplace(_Args&&... __args)
 620         {
 621           size_type __bucket_count = this->bucket_count();
 622           _Base_iterator __it
 623             = _Base::emplace(std::forward<_Args>(__args)...);
 624           _M_check_rehashed(__bucket_count);
 625           return iterator(__it, this);
 626         }
 627
 628       template<typename... _Args>
 629         iterator
 630         emplace_hint(const_iterator __hint, _Args&&... __args)
 631         {
 632           __glibcxx_check_insert(__hint);
 633           size_type __bucket_count = this->bucket_count();
 634           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 635                                         std::forward<_Args>(__args)...);
 636           _M_check_rehashed(__bucket_count);
 637           return iterator(__it, this);
 638         }
 639
 640       iterator
 641       insert(const value_type& __obj)
 642       {
 643         size_type __bucket_count = this->bucket_count();
 644         _Base_iterator __it = _Base::insert(__obj);
 645         _M_check_rehashed(__bucket_count);
 646         return iterator(__it, this);
 647       }
 648
 649       iterator
 650       insert(const_iterator __hint, const value_type& __obj)
 651       {
 652         __glibcxx_check_insert(__hint);
 653         size_type __bucket_count = this->bucket_count();
 654         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 655         _M_check_rehashed(__bucket_count);
 656         return iterator(__it, this);
 657       }
 658
 659       template<typename _Pair, typename = typename
 660                std::enable_if<std::is_constructible<value_type,
 661                                                     _Pair&&>::value>::type>
 662         iterator
 663         insert(_Pair&& __obj)
 664         {
 665           size_type __bucket_count = this->bucket_count();
 666           _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
 667           _M_check_rehashed(__bucket_count);
 668           return iterator(__it, this);
 669         }
 670
 671       template<typename _Pair, typename = typename
 672                std::enable_if<std::is_constructible<value_type,
 673                                                     _Pair&&>::value>::type>
 674         iterator
 675         insert(const_iterator __hint, _Pair&& __obj)
 676         {
 677           __glibcxx_check_insert(__hint);
 678           size_type __bucket_count = this->bucket_count();
 679           _Base_iterator __it =
 680             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
 681           _M_check_rehashed(__bucket_count);
 682           return iterator(__it, this);
 683         }
 684
 685       void
 686       insert(std::initializer_list<value_type> __l)
 687       { _Base::insert(__l); }
 688
 689       template<typename _InputIterator>
 690         void
 691         insert(_InputIterator __first, _InputIterator __last)
 692         {
 693           __glibcxx_check_valid_range(__first, __last);
 694           size_type __bucket_count = this->bucket_count();
 695           _Base::insert(__gnu_debug::__base(__first),
 696                         __gnu_debug::__base(__last));
 697           _M_check_rehashed(__bucket_count);
 698         }
 699
 700       iterator
 701       find(const key_type& __key)
 702       { return iterator(_Base::find(__key), this); }
 703
 704       const_iterator
 705       find(const key_type& __key) const
 706       { return const_iterator(_Base::find(__key), this); }
 707
 708       std::pair<iterator, iterator>
 709       equal_range(const key_type& __key)
 710       {
 711         std::pair<_Base_iterator, _Base_iterator> __res =
 712           _Base::equal_range(__key);
 713         return std::make_pair(iterator(__res.first, this),
 714                               iterator(__res.second, this));
 715       }
 716
 717       std::pair<const_iterator, const_iterator>
 718       equal_range(const key_type& __key) const
 719       {
 720         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 721           _Base::equal_range(__key);
 722         return std::make_pair(const_iterator(__res.first, this),
 723                               const_iterator(__res.second, this));
 724       }
 725
 726       size_type
 727       erase(const key_type& __key)
 728       {
 729         size_type __ret(0);
 730         size_type __bucket_count = this->bucket_count();
 731         std::pair<_Base_iterator, _Base_iterator> __pair =
 732           _Base::equal_range(__key);
 733         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
 734           {
 735             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 736                             { return __it == __victim; });
 737             _Base_local_iterator __local_victim = _S_to_local(__victim);
 738             this->_M_invalidate_local_if(
 739                             [__local_victim](_Base_const_local_iterator __it)
 740                             { return __it == __local_victim; });
 741             _Base::erase(__victim++);
 742             ++__ret;
 743           }
 744         _M_check_rehashed(__bucket_count);
 745         return __ret;
 746       }
 747
 748       iterator
 749       erase(const_iterator __it)
 750       {
 751         __glibcxx_check_erase(__it);
 752         _Base_const_iterator __victim = __it.base();
 753         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 754                         { return __it == __victim; });
 755         _Base_const_local_iterator __local_victim = _S_to_local(__victim);
 756         this->_M_invalidate_local_if(
 757                         [__local_victim](_Base_const_local_iterator __it)
 758                         { return __it == __local_victim; });
 759         size_type __bucket_count = this->bucket_count();
 760         _Base_iterator __next = _Base::erase(__it.base());
 761         _M_check_rehashed(__bucket_count);
 762         return iterator(__next, this);
 763       }
 764
 765       iterator
 766       erase(iterator __it)
 767       { return erase(const_iterator(__it)); }
 768
 769       iterator
 770       erase(const_iterator __first, const_iterator __last)
 771       {
 772         __glibcxx_check_erase_range(__first, __last);
 773         for (_Base_const_iterator __tmp = __first.base();
 774              __tmp != __last.base(); ++__tmp)
 775           {
 776             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 777                                   _M_message(__gnu_debug::__msg_valid_range)
 778                                   ._M_iterator(__first, "first")
 779                                   ._M_iterator(__last, "last"));
 780             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
 781                             { return __it == __tmp; });
 782             _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
 783             this->_M_invalidate_local_if(
 784                             [__local_tmp](_Base_const_local_iterator __it)
 785                             { return __it == __local_tmp; });
 786           }
 787         size_type __bucket_count = this->bucket_count();
 788         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
 789         _M_check_rehashed(__bucket_count);
 790         return iterator(__next, this);
 791       }
 792
 793       _Base&
 794       _M_base() noexcept       { return *this; }
 795
 796       const _Base&
 797       _M_base() const noexcept { return *this; }
 798
 799     private:
 800       void
 801       _M_invalidate_locals()
 802       {
 803         _Base_local_iterator __local_end = _Base::end(0);
 804         this->_M_invalidate_local_if(
 805                         [__local_end](_Base_const_local_iterator __it)
 806                         { return __it != __local_end; });
 807       }
 808
 809       void
 810       _M_invalidate_all()
 811       {
 812         _Base_iterator __end = _Base::end();
 813         this->_M_invalidate_if([__end](_Base_const_iterator __it)
 814                         { return __it != __end; });
 815         _M_invalidate_locals();
 816       }
 817
 818       void
 819       _M_check_rehashed(size_type __prev_count)
 820       {
 821         if (__prev_count != this->bucket_count())
 822           _M_invalidate_locals();
 823       }
 824
 825       static _Base_local_iterator
 826       _S_to_local(_Base_iterator __it)
 827       {
 828         // The returned local iterator will not be incremented so we don't
 829         // need to compute __it's node bucket
 830         return _Base_local_iterator(__it._M_cur, 0, 0);
 831       }
 832
 833       static _Base_const_local_iterator
 834       _S_to_local(_Base_const_iterator __it)
 835       {
 836         // The returned local iterator will not be incremented so we don't
 837         // need to compute __it's node bucket
 838         return _Base_const_local_iterator(__it._M_cur, 0, 0);
 839       }
 840     };
 841
 842   template<typename _Key, typename _Tp, typename _Hash,
 843            typename _Pred, typename _Alloc>
 844     inline void
 845     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 846          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 847     { __x.swap(__y); }
 848
 849   template<typename _Key, typename _Tp, typename _Hash,
 850            typename _Pred, typename _Alloc>
 851     inline bool
 852     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 853                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 854     { return __x._M_equal(__y); }
 855
 856   template<typename _Key, typename _Tp, typename _Hash,
 857            typename _Pred, typename _Alloc>
 858     inline bool
 859     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 860                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 861     { return !(__x == __y); }
 862
 863 } // namespace __debug
 864 } // namespace std
 865
 866 #endif // __GXX_EXPERIMENTAL_CXX0X__
 867
 868 #endif