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

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