contrib/gcc-5.0/libstdc++-v3/include/debug/unordered_map

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