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