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