libstdc++-v3/include/debug/unordered_map

   1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2016 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 #pragma GCC system_header
  33
  34 #if __cplusplus < 201103L
  35 # include <bits/c++0x_warning.h>
  36 #else
  37 # include <unordered_map>
  38
  39 #include <debug/safe_unordered_container.h>
  40 #include <debug/safe_container.h>
  41 #include <debug/safe_iterator.h>
  42 #include <debug/safe_local_iterator.h>
  43
  44 namespace std _GLIBCXX_VISIBILITY(default)
  45 {
  46 namespace __debug
  47 {
  48   /// Class std::unordered_map with safety/checking/debug instrumentation.
  49   template<typename _Key, typename _Tp,
  50            typename _Hash = std::hash<_Key>,
  51            typename _Pred = std::equal_to<_Key>,
  52            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
  53     class unordered_map
  54     : public __gnu_debug::_Safe_container<
  55         unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
  56         __gnu_debug::_Safe_unordered_container>,
  57       public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
  58     {
  59       typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
  60                                             _Pred, _Alloc>              _Base;
  61       typedef __gnu_debug::_Safe_container<unordered_map,
  62                    _Alloc, __gnu_debug::_Safe_unordered_container>      _Safe;
  63       typedef typename _Base::const_iterator    _Base_const_iterator;
  64       typedef typename _Base::iterator          _Base_iterator;
  65       typedef typename _Base::const_local_iterator
  66                                                 _Base_const_local_iterator;
  67       typedef typename _Base::local_iterator    _Base_local_iterator;
  68
  69     public:
  70       typedef typename _Base::size_type                 size_type;
  71       typedef typename _Base::hasher                    hasher;
  72       typedef typename _Base::key_equal                 key_equal;
  73       typedef typename _Base::allocator_type            allocator_type;
  74
  75       typedef typename _Base::key_type                  key_type;
  76       typedef typename _Base::value_type                value_type;
  77
  78       typedef __gnu_debug::_Safe_iterator<
  79         _Base_iterator, unordered_map>                  iterator;
  80       typedef __gnu_debug::_Safe_iterator<
  81         _Base_const_iterator, unordered_map>            const_iterator;
  82       typedef __gnu_debug::_Safe_local_iterator<
  83         _Base_local_iterator, unordered_map>            local_iterator;
  84       typedef __gnu_debug::_Safe_local_iterator<
  85         _Base_const_local_iterator, unordered_map>      const_local_iterator;
  86
  87       unordered_map() = default;
  88
  89       explicit
  90       unordered_map(size_type __n,
  91                     const hasher& __hf = hasher(),
  92                     const key_equal& __eql = key_equal(),
  93                     const allocator_type& __a = allocator_type())
  94       : _Base(__n, __hf, __eql, __a) { }
  95
  96       template<typename _InputIterator>
  97         unordered_map(_InputIterator __first, _InputIterator __last,
  98                       size_type __n = 0,
  99                       const hasher& __hf = hasher(),
 100                       const key_equal& __eql = key_equal(),
 101                       const allocator_type& __a = allocator_type())
 102         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 103                                                                      __last)),
 104                 __gnu_debug::__base(__last), __n,
 105                 __hf, __eql, __a) { }
 106
 107       unordered_map(const unordered_map&) = default;
 108
 109       unordered_map(const _Base& __x)
 110       : _Base(__x) { }
 111
 112       unordered_map(unordered_map&&) = default;
 113
 114       explicit
 115       unordered_map(const allocator_type& __a)
 116       : _Base(__a) { }
 117
 118       unordered_map(const unordered_map& __umap,
 119                     const allocator_type& __a)
 120       : _Base(__umap, __a) { }
 121
 122       unordered_map(unordered_map&& __umap,
 123                     const allocator_type& __a)
 124       : _Safe(std::move(__umap._M_safe()), __a),
 125         _Base(std::move(__umap._M_base()), __a) { }
 126
 127       unordered_map(initializer_list<value_type> __l,
 128                     size_type __n = 0,
 129                     const hasher& __hf = hasher(),
 130                     const key_equal& __eql = key_equal(),
 131                     const allocator_type& __a = allocator_type())
 132       : _Base(__l, __n, __hf, __eql, __a) { }
 133
 134       unordered_map(size_type __n, const allocator_type& __a)
 135       : unordered_map(__n, hasher(), key_equal(), __a)
 136       { }
 137
 138       unordered_map(size_type __n,
 139                     const hasher& __hf,
 140                     const allocator_type& __a)
 141       : unordered_map(__n, __hf, key_equal(), __a)
 142       { }
 143
 144       template<typename _InputIterator>
 145         unordered_map(_InputIterator __first, _InputIterator __last,
 146                       size_type __n,
 147                       const allocator_type& __a)
 148           : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
 149         { }
 150
 151       template<typename _InputIterator>
 152         unordered_map(_InputIterator __first, _InputIterator __last,
 153                       size_type __n,
 154                       const hasher& __hf,
 155                       const allocator_type& __a)
 156           : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
 157         { }
 158
 159       unordered_map(initializer_list<value_type> __l,
 160                     size_type __n,
 161                     const allocator_type& __a)
 162         : unordered_map(__l, __n, hasher(), key_equal(), __a)
 163       { }
 164
 165       unordered_map(initializer_list<value_type> __l,
 166                     size_type __n,
 167                     const hasher& __hf,
 168                     const allocator_type& __a)
 169         : unordered_map(__l, __n, __hf, key_equal(), __a)
 170       { }
 171
 172       ~unordered_map() = default;
 173
 174       unordered_map&
 175       operator=(const unordered_map&) = default;
 176
 177       unordered_map&
 178       operator=(unordered_map&&) = default;
 179
 180       unordered_map&
 181       operator=(initializer_list<value_type> __l)
 182       {
 183         _M_base() = __l;
 184         this->_M_invalidate_all();
 185         return *this;
 186       }
 187
 188       void
 189       swap(unordered_map& __x)
 190         noexcept( noexcept(declval<_Base&>().swap(__x)) )
 191       {
 192         _Safe::_M_swap(__x);
 193         _Base::swap(__x);
 194       }
 195
 196       void
 197       clear() noexcept
 198       {
 199         _Base::clear();
 200         this->_M_invalidate_all();
 201       }
 202
 203       iterator
 204       begin() noexcept
 205       { return iterator(_Base::begin(), this); }
 206
 207       const_iterator
 208       begin() const noexcept
 209       { return const_iterator(_Base::begin(), this); }
 210
 211       iterator
 212       end() noexcept
 213       { return iterator(_Base::end(), this); }
 214
 215       const_iterator
 216       end() const noexcept
 217       { return const_iterator(_Base::end(), this); }
 218
 219       const_iterator
 220       cbegin() const noexcept
 221       { return const_iterator(_Base::begin(), this); }
 222
 223       const_iterator
 224       cend() const noexcept
 225       { return const_iterator(_Base::end(), this); }
 226
 227       // local versions
 228       local_iterator
 229       begin(size_type __b)
 230       {
 231         __glibcxx_check_bucket_index(__b);
 232         return local_iterator(_Base::begin(__b), this);
 233       }
 234
 235       local_iterator
 236       end(size_type __b)
 237       {
 238         __glibcxx_check_bucket_index(__b);
 239         return local_iterator(_Base::end(__b), this);
 240       }
 241
 242       const_local_iterator
 243       begin(size_type __b) const
 244       {
 245         __glibcxx_check_bucket_index(__b);
 246         return const_local_iterator(_Base::begin(__b), this);
 247       }
 248
 249       const_local_iterator
 250       end(size_type __b) const
 251       {
 252         __glibcxx_check_bucket_index(__b);
 253         return const_local_iterator(_Base::end(__b), this);
 254       }
 255
 256       const_local_iterator
 257       cbegin(size_type __b) const
 258       {
 259         __glibcxx_check_bucket_index(__b);
 260         return const_local_iterator(_Base::cbegin(__b), this);
 261       }
 262
 263       const_local_iterator
 264       cend(size_type __b) const
 265       {
 266         __glibcxx_check_bucket_index(__b);
 267         return const_local_iterator(_Base::cend(__b), this);
 268       }
 269
 270       size_type
 271       bucket_size(size_type __b) const
 272       {
 273         __glibcxx_check_bucket_index(__b);
 274         return _Base::bucket_size(__b);
 275       }
 276
 277       float
 278       max_load_factor() const noexcept
 279       { return _Base::max_load_factor(); }
 280
 281       void
 282       max_load_factor(float __f)
 283       {
 284         __glibcxx_check_max_load_factor(__f);
 285         _Base::max_load_factor(__f);
 286       }
 287
 288       template<typename... _Args>
 289         std::pair<iterator, bool>
 290         emplace(_Args&&... __args)
 291         {
 292           size_type __bucket_count = this->bucket_count();
 293           std::pair<_Base_iterator, bool> __res
 294             = _Base::emplace(std::forward<_Args>(__args)...);
 295           _M_check_rehashed(__bucket_count);
 296           return std::make_pair(iterator(__res.first, this), __res.second);
 297         }
 298
 299       template<typename... _Args>
 300         iterator
 301         emplace_hint(const_iterator __hint, _Args&&... __args)
 302         {
 303           __glibcxx_check_insert(__hint);
 304           size_type __bucket_count = this->bucket_count();
 305           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 306                                         std::forward<_Args>(__args)...);
 307           _M_check_rehashed(__bucket_count);
 308           return iterator(__it, this);
 309         }
 310
 311       std::pair<iterator, bool>
 312       insert(const value_type& __obj)
 313       {
 314         size_type __bucket_count = this->bucket_count();
 315         std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
 316         _M_check_rehashed(__bucket_count);
 317         return std::make_pair(iterator(__res.first, this), __res.second);
 318       }
 319
 320       iterator
 321       insert(const_iterator __hint, const value_type& __obj)
 322       {
 323         __glibcxx_check_insert(__hint);
 324         size_type __bucket_count = this->bucket_count();
 325         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 326         _M_check_rehashed(__bucket_count);
 327         return iterator(__it, this);
 328       }
 329
 330       template<typename _Pair, typename = typename
 331                std::enable_if<std::is_constructible<value_type,
 332                                                     _Pair&&>::value>::type>
 333         std::pair<iterator, bool>
 334         insert(_Pair&& __obj)
 335         {
 336           size_type __bucket_count = this->bucket_count();
 337           std::pair<_Base_iterator, bool> __res =
 338             _Base::insert(std::forward<_Pair>(__obj));
 339           _M_check_rehashed(__bucket_count);
 340           return std::make_pair(iterator(__res.first, this), __res.second);
 341         }
 342
 343       template<typename _Pair, typename = typename
 344                std::enable_if<std::is_constructible<value_type,
 345                                                     _Pair&&>::value>::type>
 346         iterator
 347         insert(const_iterator __hint, _Pair&& __obj)
 348         {
 349           __glibcxx_check_insert(__hint);
 350           size_type __bucket_count = this->bucket_count();
 351           _Base_iterator __it =
 352             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
 353           _M_check_rehashed(__bucket_count);
 354           return iterator(__it, this);
 355         }
 356
 357       void
 358       insert(std::initializer_list<value_type> __l)
 359       {
 360         size_type __bucket_count = this->bucket_count();
 361         _Base::insert(__l);
 362         _M_check_rehashed(__bucket_count);
 363       }
 364
 365       template<typename _InputIterator>
 366         void
 367         insert(_InputIterator __first, _InputIterator __last)
 368         {
 369           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 370           __glibcxx_check_valid_range2(__first, __last, __dist);
 371           size_type __bucket_count = this->bucket_count();
 372
 373           if (__dist.second >= __gnu_debug::__dp_sign)
 374             _Base::insert(__gnu_debug::__unsafe(__first),
 375                           __gnu_debug::__unsafe(__last));
 376           else
 377             _Base::insert(__first, __last);
 378
 379           _M_check_rehashed(__bucket_count);
 380         }
 381
 382 #if __cplusplus > 201402L
 383       template <typename... _Args>
 384         pair<iterator, bool>
 385         try_emplace(const key_type& __k, _Args&&... __args)
 386         {
 387           auto __res = _Base::try_emplace(__k,
 388                                           std::forward<_Args>(__args)...);
 389           return { iterator(__res.first, this), __res.second };
 390         }
 391
 392       template <typename... _Args>
 393         pair<iterator, bool>
 394         try_emplace(key_type&& __k, _Args&&... __args)
 395         {
 396           auto __res = _Base::try_emplace(std::move(__k),
 397                                           std::forward<_Args>(__args)...);
 398           return { iterator(__res.first, this), __res.second };
 399         }
 400
 401       template <typename... _Args>
 402         iterator
 403         try_emplace(const_iterator __hint, const key_type& __k,
 404                     _Args&&... __args)
 405         {
 406           __glibcxx_check_insert(__hint);
 407           return iterator(_Base::try_emplace(__hint.base(), __k,
 408                                              std::forward<_Args>(__args)...),
 409                           this);
 410         }
 411
 412       template <typename... _Args>
 413         iterator
 414         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
 415         {
 416           __glibcxx_check_insert(__hint);
 417           return iterator(_Base::try_emplace(__hint.base(), std::move(__k),
 418                                              std::forward<_Args>(__args)...),
 419                           this);
 420         }
 421
 422       template <typename _Obj>
 423         pair<iterator, bool>
 424         insert_or_assign(const key_type& __k, _Obj&& __obj)
 425         {
 426           auto __res = _Base::insert_or_assign(__k,
 427                                                std::forward<_Obj>(__obj));
 428           return { iterator(__res.first, this), __res.second };
 429         }
 430
 431       template <typename _Obj>
 432         pair<iterator, bool>
 433         insert_or_assign(key_type&& __k, _Obj&& __obj)
 434         {
 435           auto __res = _Base::insert_or_assign(std::move(__k),
 436                                                std::forward<_Obj>(__obj));
 437           return { iterator(__res.first, this), __res.second };
 438         }
 439
 440       template <typename _Obj>
 441         iterator
 442         insert_or_assign(const_iterator __hint, const key_type& __k,
 443                          _Obj&& __obj)
 444         {
 445           __glibcxx_check_insert(__hint);
 446           return iterator(_Base::insert_or_assign(__hint.base(), __k,
 447                                                   std::forward<_Obj>(__obj)),
 448                           this);
 449         }
 450
 451       template <typename _Obj>
 452         iterator
 453         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
 454         {
 455           __glibcxx_check_insert(__hint);
 456           return iterator(_Base::insert_or_assign(__hint.base(),
 457                                                   std::move(__k),
 458                                                   std::forward<_Obj>(__obj)),
 459                           this);
 460         }
 461 #endif // C++17
 462
 463 #if __cplusplus > 201402L
 464       using node_type = typename _Base::node_type;
 465
 466       struct insert_return_type
 467       {
 468         bool inserted;
 469         iterator position;
 470         node_type node;
 471       };
 472
 473       node_type
 474       extract(const_iterator __position)
 475       {
 476         __glibcxx_check_erase(__position);
 477         _Base_const_iterator __victim = __position.base();
 478         this->_M_invalidate_if(
 479             [__victim](_Base_const_iterator __it) { return __it == __victim; }
 480             );
 481         this->_M_invalidate_local_if(
 482             [__victim](_Base_const_local_iterator __it) {
 483                 return __it._M_curr() == __victim._M_cur;
 484             });
 485         return _Base::extract(__position.base());
 486       }
 487
 488       node_type
 489       extract(const key_type& __key)
 490       {
 491         const auto __position = find(__key);
 492         if (__position != end())
 493           return extract(__position);
 494         return {};
 495       }
 496
 497       insert_return_type
 498       insert(node_type&& __nh)
 499       {
 500         auto __ret = _Base::insert(std::move(__nh));
 501         iterator __pos = iterator(__ret.position, this);
 502         return { __ret.inserted, __pos, std::move(__ret.node) };
 503       }
 504
 505       iterator
 506       insert(const_iterator __hint, node_type&& __nh)
 507       {
 508         __glibcxx_check_insert(__hint);
 509         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
 510       }
 511
 512       using _Base::merge;
 513 #endif // C++17
 514
 515       iterator
 516       find(const key_type& __key)
 517       { return iterator(_Base::find(__key), this); }
 518
 519       const_iterator
 520       find(const key_type& __key) const
 521       { return const_iterator(_Base::find(__key), this); }
 522
 523       std::pair<iterator, iterator>
 524       equal_range(const key_type& __key)
 525       {
 526         std::pair<_Base_iterator, _Base_iterator> __res =
 527           _Base::equal_range(__key);
 528         return std::make_pair(iterator(__res.first, this),
 529                               iterator(__res.second, this));
 530       }
 531
 532       std::pair<const_iterator, const_iterator>
 533       equal_range(const key_type& __key) const
 534       {
 535         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 536           _Base::equal_range(__key);
 537         return std::make_pair(const_iterator(__res.first, this),
 538                               const_iterator(__res.second, this));
 539       }
 540
 541       size_type
 542       erase(const key_type& __key)
 543       {
 544         size_type __ret(0);
 545         _Base_iterator __victim(_Base::find(__key));
 546         if (__victim != _Base::end())
 547           {
 548             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 549                             { return __it == __victim; });
 550             this->_M_invalidate_local_if(
 551                             [__victim](_Base_const_local_iterator __it)
 552                             { return __it._M_curr() == __victim._M_cur; });
 553             size_type __bucket_count = this->bucket_count();
 554             _Base::erase(__victim);
 555             _M_check_rehashed(__bucket_count);
 556             __ret = 1;
 557           }
 558         return __ret;
 559       }
 560
 561       iterator
 562       erase(const_iterator __it)
 563       {
 564         __glibcxx_check_erase(__it);
 565         _Base_const_iterator __victim = __it.base();
 566         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 567                         { return __it == __victim; });
 568         this->_M_invalidate_local_if(
 569                         [__victim](_Base_const_local_iterator __it)
 570                         { return __it._M_curr() == __victim._M_cur; });
 571         size_type __bucket_count = this->bucket_count();
 572         _Base_iterator __next = _Base::erase(__it.base());
 573         _M_check_rehashed(__bucket_count);
 574         return iterator(__next, this);
 575       }
 576
 577       iterator
 578       erase(iterator __it)
 579       { return erase(const_iterator(__it)); }
 580
 581       iterator
 582       erase(const_iterator __first, const_iterator __last)
 583       {
 584         __glibcxx_check_erase_range(__first, __last);
 585         for (_Base_const_iterator __tmp = __first.base();
 586              __tmp != __last.base(); ++__tmp)
 587           {
 588             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 589                                   _M_message(__gnu_debug::__msg_valid_range)
 590                                   ._M_iterator(__first, "first")
 591                                   ._M_iterator(__last, "last"));
 592             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
 593                             { return __it == __tmp; });
 594             this->_M_invalidate_local_if(
 595                             [__tmp](_Base_const_local_iterator __it)
 596                             { return __it._M_curr() == __tmp._M_cur; });
 597           }
 598         size_type __bucket_count = this->bucket_count();
 599         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
 600         _M_check_rehashed(__bucket_count);
 601         return iterator(__next, this);
 602       }
 603
 604       _Base&
 605       _M_base() noexcept        { return *this; }
 606
 607       const _Base&
 608       _M_base() const noexcept  { return *this; }
 609
 610     private:
 611       void
 612       _M_check_rehashed(size_type __prev_count)
 613       {
 614         if (__prev_count != this->bucket_count())
 615           this->_M_invalidate_locals();
 616       }
 617     };
 618
 619   template<typename _Key, typename _Tp, typename _Hash,
 620            typename _Pred, typename _Alloc>
 621     inline void
 622     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 623          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 624     noexcept(noexcept(__x.swap(__y)))
 625     { __x.swap(__y); }
 626
 627   template<typename _Key, typename _Tp, typename _Hash,
 628            typename _Pred, typename _Alloc>
 629     inline bool
 630     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 631                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 632     { return __x._M_base() == __y._M_base(); }
 633
 634   template<typename _Key, typename _Tp, typename _Hash,
 635            typename _Pred, typename _Alloc>
 636     inline bool
 637     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 638                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 639     { return !(__x == __y); }
 640
 641
 642   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
 643   template<typename _Key, typename _Tp,
 644            typename _Hash = std::hash<_Key>,
 645            typename _Pred = std::equal_to<_Key>,
 646            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
 647     class unordered_multimap
 648       : public __gnu_debug::_Safe_container<
 649         unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
 650         __gnu_debug::_Safe_unordered_container>,
 651         public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
 652     {
 653       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
 654                                                  _Pred, _Alloc>         _Base;
 655       typedef __gnu_debug::_Safe_container<unordered_multimap,
 656         _Alloc, __gnu_debug::_Safe_unordered_container>                 _Safe;
 657       typedef typename _Base::const_iterator       _Base_const_iterator;
 658       typedef typename _Base::iterator             _Base_iterator;
 659       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
 660       typedef typename _Base::local_iterator       _Base_local_iterator;
 661
 662     public:
 663       typedef typename _Base::size_type                 size_type;
 664       typedef typename _Base::hasher                    hasher;
 665       typedef typename _Base::key_equal                 key_equal;
 666       typedef typename _Base::allocator_type            allocator_type;
 667
 668       typedef typename _Base::key_type                  key_type;
 669       typedef typename _Base::value_type                value_type;
 670
 671       typedef __gnu_debug::_Safe_iterator<
 672         _Base_iterator, unordered_multimap>             iterator;
 673       typedef __gnu_debug::_Safe_iterator<
 674         _Base_const_iterator, unordered_multimap>       const_iterator;
 675       typedef __gnu_debug::_Safe_local_iterator<
 676         _Base_local_iterator, unordered_multimap>       local_iterator;
 677       typedef __gnu_debug::_Safe_local_iterator<
 678         _Base_const_local_iterator, unordered_multimap> const_local_iterator;
 679
 680       unordered_multimap() = default;
 681
 682       explicit
 683       unordered_multimap(size_type __n,
 684                          const hasher& __hf = hasher(),
 685                          const key_equal& __eql = key_equal(),
 686                          const allocator_type& __a = allocator_type())
 687       : _Base(__n, __hf, __eql, __a) { }
 688
 689       template<typename _InputIterator>
 690         unordered_multimap(_InputIterator __first, _InputIterator __last,
 691                            size_type __n = 0,
 692                            const hasher& __hf = hasher(),
 693                            const key_equal& __eql = key_equal(),
 694                            const allocator_type& __a = allocator_type())
 695         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 696                                                                      __last)),
 697                 __gnu_debug::__base(__last), __n,
 698                 __hf, __eql, __a) { }
 699
 700       unordered_multimap(const unordered_multimap&) = default;
 701
 702       unordered_multimap(const _Base& __x)
 703       : _Base(__x) { }
 704
 705       unordered_multimap(unordered_multimap&&) = default;
 706
 707       explicit
 708       unordered_multimap(const allocator_type& __a)
 709       : _Base(__a) { }
 710
 711       unordered_multimap(const unordered_multimap& __umap,
 712                          const allocator_type& __a)
 713       : _Base(__umap, __a) { }
 714
 715       unordered_multimap(unordered_multimap&& __umap,
 716                          const allocator_type& __a)
 717       : _Safe(std::move(__umap._M_safe()), __a),
 718         _Base(std::move(__umap._M_base()), __a) { }
 719
 720       unordered_multimap(initializer_list<value_type> __l,
 721                          size_type __n = 0,
 722                          const hasher& __hf = hasher(),
 723                          const key_equal& __eql = key_equal(),
 724                          const allocator_type& __a = allocator_type())
 725       : _Base(__l, __n, __hf, __eql, __a) { }
 726
 727       unordered_multimap(size_type __n, const allocator_type& __a)
 728       : unordered_multimap(__n, hasher(), key_equal(), __a)
 729       { }
 730
 731       unordered_multimap(size_type __n, const hasher& __hf,
 732                          const allocator_type& __a)
 733       : unordered_multimap(__n, __hf, key_equal(), __a)
 734       { }
 735
 736       template<typename _InputIterator>
 737         unordered_multimap(_InputIterator __first, _InputIterator __last,
 738                            size_type __n,
 739                            const allocator_type& __a)
 740           : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
 741         { }
 742
 743       template<typename _InputIterator>
 744         unordered_multimap(_InputIterator __first, _InputIterator __last,
 745                            size_type __n, const hasher& __hf,
 746                            const allocator_type& __a)
 747           : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
 748         { }
 749
 750       unordered_multimap(initializer_list<value_type> __l,
 751                          size_type __n,
 752                          const allocator_type& __a)
 753         : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
 754       { }
 755
 756       unordered_multimap(initializer_list<value_type> __l,
 757                          size_type __n, const hasher& __hf,
 758                          const allocator_type& __a)
 759         : unordered_multimap(__l, __n, __hf, key_equal(), __a)
 760       { }
 761
 762       ~unordered_multimap() = default;
 763
 764       unordered_multimap&
 765       operator=(const unordered_multimap&) = default;
 766
 767       unordered_multimap&
 768       operator=(unordered_multimap&&) = default;
 769
 770       unordered_multimap&
 771       operator=(initializer_list<value_type> __l)
 772       {
 773         this->_M_base() = __l;
 774         this->_M_invalidate_all();
 775         return *this;
 776       }
 777
 778       void
 779       swap(unordered_multimap& __x)
 780         noexcept( noexcept(declval<_Base&>().swap(__x)) )
 781       {
 782         _Safe::_M_swap(__x);
 783         _Base::swap(__x);
 784       }
 785
 786       void
 787       clear() noexcept
 788       {
 789         _Base::clear();
 790         this->_M_invalidate_all();
 791       }
 792
 793       iterator
 794       begin() noexcept
 795       { return iterator(_Base::begin(), this); }
 796
 797       const_iterator
 798       begin() const noexcept
 799       { return const_iterator(_Base::begin(), this); }
 800
 801       iterator
 802       end() noexcept
 803       { return iterator(_Base::end(), this); }
 804
 805       const_iterator
 806       end() const noexcept
 807       { return const_iterator(_Base::end(), this); }
 808
 809       const_iterator
 810       cbegin() const noexcept
 811       { return const_iterator(_Base::begin(), this); }
 812
 813       const_iterator
 814       cend() const noexcept
 815       { return const_iterator(_Base::end(), this); }
 816
 817       // local versions
 818       local_iterator
 819       begin(size_type __b)
 820       {
 821         __glibcxx_check_bucket_index(__b);
 822         return local_iterator(_Base::begin(__b), this);
 823       }
 824
 825       local_iterator
 826       end(size_type __b)
 827       {
 828         __glibcxx_check_bucket_index(__b);
 829         return local_iterator(_Base::end(__b), this);
 830       }
 831
 832       const_local_iterator
 833       begin(size_type __b) const
 834       {
 835         __glibcxx_check_bucket_index(__b);
 836         return const_local_iterator(_Base::begin(__b), this);
 837       }
 838
 839       const_local_iterator
 840       end(size_type __b) const
 841       {
 842         __glibcxx_check_bucket_index(__b);
 843         return const_local_iterator(_Base::end(__b), this);
 844       }
 845
 846       const_local_iterator
 847       cbegin(size_type __b) const
 848       {
 849         __glibcxx_check_bucket_index(__b);
 850         return const_local_iterator(_Base::cbegin(__b), this);
 851       }
 852
 853       const_local_iterator
 854       cend(size_type __b) const
 855       {
 856         __glibcxx_check_bucket_index(__b);
 857         return const_local_iterator(_Base::cend(__b), this);
 858       }
 859
 860       size_type
 861       bucket_size(size_type __b) const
 862       {
 863         __glibcxx_check_bucket_index(__b);
 864         return _Base::bucket_size(__b);
 865       }
 866
 867       float
 868       max_load_factor() const noexcept
 869       { return _Base::max_load_factor(); }
 870
 871       void
 872       max_load_factor(float __f)
 873       {
 874         __glibcxx_check_max_load_factor(__f);
 875         _Base::max_load_factor(__f);
 876       }
 877
 878       template<typename... _Args>
 879         iterator
 880         emplace(_Args&&... __args)
 881         {
 882           size_type __bucket_count = this->bucket_count();
 883           _Base_iterator __it
 884             = _Base::emplace(std::forward<_Args>(__args)...);
 885           _M_check_rehashed(__bucket_count);
 886           return iterator(__it, this);
 887         }
 888
 889       template<typename... _Args>
 890         iterator
 891         emplace_hint(const_iterator __hint, _Args&&... __args)
 892         {
 893           __glibcxx_check_insert(__hint);
 894           size_type __bucket_count = this->bucket_count();
 895           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
 896                                         std::forward<_Args>(__args)...);
 897           _M_check_rehashed(__bucket_count);
 898           return iterator(__it, this);
 899         }
 900
 901       iterator
 902       insert(const value_type& __obj)
 903       {
 904         size_type __bucket_count = this->bucket_count();
 905         _Base_iterator __it = _Base::insert(__obj);
 906         _M_check_rehashed(__bucket_count);
 907         return iterator(__it, this);
 908       }
 909
 910       iterator
 911       insert(const_iterator __hint, const value_type& __obj)
 912       {
 913         __glibcxx_check_insert(__hint);
 914         size_type __bucket_count = this->bucket_count();
 915         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
 916         _M_check_rehashed(__bucket_count);
 917         return iterator(__it, this);
 918       }
 919
 920       template<typename _Pair, typename = typename
 921                std::enable_if<std::is_constructible<value_type,
 922                                                     _Pair&&>::value>::type>
 923         iterator
 924         insert(_Pair&& __obj)
 925         {
 926           size_type __bucket_count = this->bucket_count();
 927           _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
 928           _M_check_rehashed(__bucket_count);
 929           return iterator(__it, this);
 930         }
 931
 932       template<typename _Pair, typename = typename
 933                std::enable_if<std::is_constructible<value_type,
 934                                                     _Pair&&>::value>::type>
 935         iterator
 936         insert(const_iterator __hint, _Pair&& __obj)
 937         {
 938           __glibcxx_check_insert(__hint);
 939           size_type __bucket_count = this->bucket_count();
 940           _Base_iterator __it =
 941             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
 942           _M_check_rehashed(__bucket_count);
 943           return iterator(__it, this);
 944         }
 945
 946       void
 947       insert(std::initializer_list<value_type> __l)
 948       { _Base::insert(__l); }
 949
 950       template<typename _InputIterator>
 951         void
 952         insert(_InputIterator __first, _InputIterator __last)
 953         {
 954           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 955           __glibcxx_check_valid_range2(__first, __last, __dist);
 956           size_type __bucket_count = this->bucket_count();
 957
 958           if (__dist.second >= __gnu_debug::__dp_sign)
 959             _Base::insert(__gnu_debug::__unsafe(__first),
 960                           __gnu_debug::__unsafe(__last));
 961           else
 962             _Base::insert(__first, __last);
 963
 964           _M_check_rehashed(__bucket_count);
 965         }
 966
 967 #if __cplusplus > 201402L
 968       using node_type = typename _Base::node_type;
 969
 970       node_type
 971       extract(const_iterator __position)
 972       {
 973         __glibcxx_check_erase(__position);
 974         _Base_const_iterator __victim = __position.base();
 975         this->_M_invalidate_if(
 976             [__victim](_Base_const_iterator __it) { return __it == __victim; }
 977             );
 978         this->_M_invalidate_local_if(
 979             [__victim](_Base_const_local_iterator __it) {
 980                 return __it._M_curr() == __victim._M_cur;
 981             });
 982         return _Base::extract(__position.base());
 983       }
 984
 985       node_type
 986       extract(const key_type& __key)
 987       {
 988         const auto __position = find(__key);
 989         if (__position != end())
 990           return extract(__position);
 991         return {};
 992       }
 993
 994       iterator
 995       insert(node_type&& __nh)
 996       { return iterator(_Base::insert(std::move(__nh)), this); }
 997
 998       iterator
 999       insert(const_iterator __hint, node_type&& __nh)
1000       {
1001         __glibcxx_check_insert(__hint);
1002         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
1003       }
1004
1005       using _Base::merge;
1006 #endif // C++17
1007
1008       iterator
1009       find(const key_type& __key)
1010       { return iterator(_Base::find(__key), this); }
1011
1012       const_iterator
1013       find(const key_type& __key) const
1014       { return const_iterator(_Base::find(__key), this); }
1015
1016       std::pair<iterator, iterator>
1017       equal_range(const key_type& __key)
1018       {
1019         std::pair<_Base_iterator, _Base_iterator> __res =
1020           _Base::equal_range(__key);
1021         return std::make_pair(iterator(__res.first, this),
1022                               iterator(__res.second, this));
1023       }
1024
1025       std::pair<const_iterator, const_iterator>
1026       equal_range(const key_type& __key) const
1027       {
1028         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
1029           _Base::equal_range(__key);
1030         return std::make_pair(const_iterator(__res.first, this),
1031                               const_iterator(__res.second, this));
1032       }
1033
1034       size_type
1035       erase(const key_type& __key)
1036       {
1037         size_type __ret(0);
1038         size_type __bucket_count = this->bucket_count();
1039         std::pair<_Base_iterator, _Base_iterator> __pair =
1040           _Base::equal_range(__key);
1041         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
1042           {
1043             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
1044                             { return __it == __victim; });
1045             this->_M_invalidate_local_if(
1046                             [__victim](_Base_const_local_iterator __it)
1047                             { return __it._M_curr() == __victim._M_cur; });
1048             _Base::erase(__victim++);
1049             ++__ret;
1050           }
1051         _M_check_rehashed(__bucket_count);
1052         return __ret;
1053       }
1054
1055       iterator
1056       erase(const_iterator __it)
1057       {
1058         __glibcxx_check_erase(__it);
1059         _Base_const_iterator __victim = __it.base();
1060         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
1061                         { return __it == __victim; });
1062         this->_M_invalidate_local_if(
1063                         [__victim](_Base_const_local_iterator __it)
1064                         { return __it._M_curr() == __victim._M_cur; });
1065         size_type __bucket_count = this->bucket_count();
1066         _Base_iterator __next = _Base::erase(__it.base());
1067         _M_check_rehashed(__bucket_count);
1068         return iterator(__next, this);
1069       }
1070
1071       iterator
1072       erase(iterator __it)
1073       { return erase(const_iterator(__it)); }
1074
1075       iterator
1076       erase(const_iterator __first, const_iterator __last)
1077       {
1078         __glibcxx_check_erase_range(__first, __last);
1079         for (_Base_const_iterator __tmp = __first.base();
1080              __tmp != __last.base(); ++__tmp)
1081           {
1082             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
1083                                   _M_message(__gnu_debug::__msg_valid_range)
1084                                   ._M_iterator(__first, "first")
1085                                   ._M_iterator(__last, "last"));
1086             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
1087                             { return __it == __tmp; });
1088             this->_M_invalidate_local_if(
1089                             [__tmp](_Base_const_local_iterator __it)
1090                             { return __it._M_curr() == __tmp._M_cur; });
1091           }
1092         size_type __bucket_count = this->bucket_count();
1093         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
1094         _M_check_rehashed(__bucket_count);
1095         return iterator(__next, this);
1096       }
1097
1098       _Base&
1099       _M_base() noexcept { return *this; }
1100
1101       const _Base&
1102       _M_base() const noexcept { return *this; }
1103
1104     private:
1105       void
1106       _M_check_rehashed(size_type __prev_count)
1107       {
1108         if (__prev_count != this->bucket_count())
1109           this->_M_invalidate_locals();
1110       }
1111     };
1112
1113   template<typename _Key, typename _Tp, typename _Hash,
1114            typename _Pred, typename _Alloc>
1115     inline void
1116     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1117          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1118     noexcept(noexcept(__x.swap(__y)))
1119     { __x.swap(__y); }
1120
1121   template<typename _Key, typename _Tp, typename _Hash,
1122            typename _Pred, typename _Alloc>
1123     inline bool
1124     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1125                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1126     { return __x._M_base() == __y._M_base(); }
1127
1128   template<typename _Key, typename _Tp, typename _Hash,
1129            typename _Pred, typename _Alloc>
1130     inline bool
1131     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1132                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1133     { return !(__x == __y); }
1134
1135 } // namespace __debug
1136 } // namespace std
1137
1138 #endif // C++11
1139
1140 #endif