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