29 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
30 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
32 #if __cplusplus < 201103L
42 namespace std _GLIBCXX_VISIBILITY(default)
47 template<
typename _Key,
typename _Tp,
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>
57 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
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;
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;
73 typedef typename _Base::key_type key_type;
74 typedef typename _Base::value_type value_type;
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) { }
94 template<
typename _InputIterator>
97 const hasher& __hf = hasher(),
98 const key_equal& __eql = key_equal(),
99 const allocator_type& __a = allocator_type())
103 __hf, __eql, __a) { }
117 const allocator_type& __a)
118 :
_Base(__umap, __a) { }
121 const allocator_type& __a)
122 :
_Safe(std::move(__umap._M_safe()), __a),
123 _Base(std::move(__umap._M_base()), __a) { }
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) { }
138 const allocator_type& __a)
142 template<
typename _InputIterator>
145 const allocator_type& __a)
146 :
unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
149 template<
typename _InputIterator>
153 const allocator_type& __a)
154 :
unordered_map(__first, __last, __n, __hf, key_equal(), __a)
159 const allocator_type& __a)
166 const allocator_type& __a)
182 this->_M_invalidate_all();
188 noexcept( noexcept(declval<_Base>().
swap(__x)) )
198 this->_M_invalidate_all();
203 {
return iterator(_Base::begin(),
this); }
206 begin()
const noexcept
211 {
return iterator(_Base::end(),
this); }
218 cbegin()
const noexcept
222 cend()
const noexcept
229 __glibcxx_check_bucket_index(__b);
236 __glibcxx_check_bucket_index(__b);
241 begin(size_type __b)
const
243 __glibcxx_check_bucket_index(__b);
248 end(size_type __b)
const
250 __glibcxx_check_bucket_index(__b);
255 cbegin(size_type __b)
const
257 __glibcxx_check_bucket_index(__b);
262 cend(size_type __b)
const
264 __glibcxx_check_bucket_index(__b);
269 bucket_size(size_type __b)
const
271 __glibcxx_check_bucket_index(__b);
272 return _Base::bucket_size(__b);
276 max_load_factor()
const noexcept
277 {
return _Base::max_load_factor(); }
280 max_load_factor(
float __f)
282 __glibcxx_check_max_load_factor(__f);
283 _Base::max_load_factor(__f);
286 template<
typename... _Args>
288 emplace(_Args&&... __args)
290 size_type __bucket_count = this->bucket_count();
292 = _Base::emplace(std::forward<_Args>(__args)...);
293 _M_check_rehashed(__bucket_count);
297 template<
typename... _Args>
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);
310 insert(
const value_type& __obj)
312 size_type __bucket_count = this->bucket_count();
314 _M_check_rehashed(__bucket_count);
322 size_type __bucket_count = this->bucket_count();
323 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
324 _M_check_rehashed(__bucket_count);
328 template<
typename _Pair,
typename =
typename
329 std::enable_if<std::is_constructible<value_type,
330 _Pair&&>::value>::type>
332 insert(_Pair&& __obj)
334 size_type __bucket_count = this->bucket_count();
336 _Base::insert(std::forward<_Pair>(__obj));
337 _M_check_rehashed(__bucket_count);
341 template<
typename _Pair,
typename =
typename
342 std::enable_if<std::is_constructible<value_type,
343 _Pair&&>::value>::type>
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);
358 size_type __bucket_count = this->bucket_count();
360 _M_check_rehashed(__bucket_count);
363 template<
typename _InputIterator>
365 insert(_InputIterator __first, _InputIterator __last)
367 __glibcxx_check_valid_range(__first, __last);
368 size_type __bucket_count = this->bucket_count();
371 _M_check_rehashed(__bucket_count);
375 find(
const key_type& __key)
376 {
return iterator(_Base::find(__key),
this); }
379 find(
const key_type& __key)
const
383 equal_range(
const key_type& __key)
386 _Base::equal_range(__key);
392 equal_range(
const key_type& __key)
const
395 _Base::equal_range(__key);
401 erase(
const key_type& __key)
404 _Base_iterator __victim(_Base::find(__key));
405 if (__victim != _Base::end())
408 {
return __it == __victim; });
410 [__victim](_Base_const_local_iterator __it)
411 {
return __it._M_curr() == __victim._M_cur; });
412 size_type __bucket_count = this->bucket_count();
413 _Base::erase(__victim);
414 _M_check_rehashed(__bucket_count);
424 _Base_const_iterator __victim = __it.
base();
426 {
return __it == __victim; });
428 [__victim](_Base_const_local_iterator __it)
429 {
return __it._M_curr() == __victim._M_cur; });
430 size_type __bucket_count = this->bucket_count();
431 _Base_iterator __next = _Base::erase(__it.base());
432 _M_check_rehashed(__bucket_count);
444 for (_Base_const_iterator __tmp = __first.
base();
445 __tmp != __last.
base(); ++__tmp)
447 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
448 _M_message(__gnu_debug::__msg_valid_range)
449 ._M_iterator(__first,
"first")
450 ._M_iterator(__last,
"last"));
452 {
return __it == __tmp; });
454 [__tmp](_Base_const_local_iterator __it)
455 {
return __it._M_curr() == __tmp._M_cur; });
457 size_type __bucket_count = this->bucket_count();
458 _Base_iterator __next = _Base::erase(__first.
base(), __last.
base());
459 _M_check_rehashed(__bucket_count);
464 _M_base() noexcept {
return *
this; }
467 _M_base()
const noexcept {
return *
this; }
471 _M_check_rehashed(size_type __prev_count)
473 if (__prev_count != this->bucket_count())
474 this->_M_invalidate_locals();
478 template<
typename _Key,
typename _Tp,
typename _Hash,
479 typename _Pred,
typename _Alloc>
485 template<
typename _Key,
typename _Tp,
typename _Hash,
486 typename _Pred,
typename _Alloc>
490 {
return __x._M_base() == __y._M_base(); }
492 template<
typename _Key,
typename _Tp,
typename _Hash,
493 typename _Pred,
typename _Alloc>
495 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
496 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
497 {
return !(__x == __y); }
501 template<
typename _Key,
typename _Tp,
507 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
508 __gnu_debug::_Safe_unordered_container>,
509 public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
511 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
512 _Pred, _Alloc>
_Base;
515 typedef typename _Base::const_iterator _Base_const_iterator;
516 typedef typename _Base::iterator _Base_iterator;
517 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
518 typedef typename _Base::local_iterator _Base_local_iterator;
521 typedef typename _Base::size_type size_type;
522 typedef typename _Base::hasher hasher;
523 typedef typename _Base::key_equal key_equal;
524 typedef typename _Base::allocator_type allocator_type;
526 typedef typename _Base::key_type key_type;
527 typedef typename _Base::value_type value_type;
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) { }
547 template<
typename _InputIterator>
550 const hasher& __hf = hasher(),
551 const key_equal& __eql = key_equal(),
552 const allocator_type& __a = allocator_type())
556 __hf, __eql, __a) { }
570 const allocator_type& __a)
571 :
_Base(__umap, __a) { }
574 const allocator_type& __a)
575 :
_Safe(std::move(__umap._M_safe()), __a),
576 _Base(std::move(__umap._M_base()), __a) { }
580 const hasher& __hf = hasher(),
581 const key_equal& __eql = key_equal(),
582 const allocator_type& __a = allocator_type())
583 :
_Base(__l, __n, __hf, __eql, __a) { }
590 const allocator_type& __a)
594 template<
typename _InputIterator>
597 const allocator_type& __a)
601 template<
typename _InputIterator>
603 size_type __n,
const hasher& __hf,
604 const allocator_type& __a)
610 const allocator_type& __a)
615 size_type __n,
const hasher& __hf,
616 const allocator_type& __a)
631 this->_M_base() = __l;
632 this->_M_invalidate_all();
638 noexcept( noexcept(declval<_Base>().
swap(__x)) )
648 this->_M_invalidate_all();
653 {
return iterator(_Base::begin(),
this); }
656 begin()
const noexcept
661 {
return iterator(_Base::end(),
this); }
668 cbegin()
const noexcept
672 cend()
const noexcept
679 __glibcxx_check_bucket_index(__b);
686 __glibcxx_check_bucket_index(__b);
691 begin(size_type __b)
const
693 __glibcxx_check_bucket_index(__b);
698 end(size_type __b)
const
700 __glibcxx_check_bucket_index(__b);
705 cbegin(size_type __b)
const
707 __glibcxx_check_bucket_index(__b);
712 cend(size_type __b)
const
714 __glibcxx_check_bucket_index(__b);
719 bucket_size(size_type __b)
const
721 __glibcxx_check_bucket_index(__b);
722 return _Base::bucket_size(__b);
726 max_load_factor()
const noexcept
727 {
return _Base::max_load_factor(); }
730 max_load_factor(
float __f)
732 __glibcxx_check_max_load_factor(__f);
733 _Base::max_load_factor(__f);
736 template<
typename... _Args>
738 emplace(_Args&&... __args)
740 size_type __bucket_count = this->bucket_count();
742 = _Base::emplace(std::forward<_Args>(__args)...);
743 _M_check_rehashed(__bucket_count);
747 template<
typename... _Args>
752 size_type __bucket_count = this->bucket_count();
753 _Base_iterator __it = _Base::emplace_hint(__hint.
base(),
754 std::forward<_Args>(__args)...);
755 _M_check_rehashed(__bucket_count);
760 insert(
const value_type& __obj)
762 size_type __bucket_count = this->bucket_count();
763 _Base_iterator __it = _Base::insert(__obj);
764 _M_check_rehashed(__bucket_count);
772 size_type __bucket_count = this->bucket_count();
773 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
774 _M_check_rehashed(__bucket_count);
778 template<
typename _Pair,
typename =
typename
779 std::enable_if<std::is_constructible<value_type,
780 _Pair&&>::value>::type>
782 insert(_Pair&& __obj)
784 size_type __bucket_count = this->bucket_count();
785 _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
786 _M_check_rehashed(__bucket_count);
790 template<
typename _Pair,
typename =
typename
791 std::enable_if<std::is_constructible<value_type,
792 _Pair&&>::value>::type>
797 size_type __bucket_count = this->bucket_count();
798 _Base_iterator __it =
799 _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
800 _M_check_rehashed(__bucket_count);
806 { _Base::insert(__l); }
808 template<
typename _InputIterator>
810 insert(_InputIterator __first, _InputIterator __last)
812 __glibcxx_check_valid_range(__first, __last);
813 size_type __bucket_count = this->bucket_count();
816 _M_check_rehashed(__bucket_count);
820 find(
const key_type& __key)
821 {
return iterator(_Base::find(__key),
this); }
824 find(
const key_type& __key)
const
828 equal_range(
const key_type& __key)
831 _Base::equal_range(__key);
837 equal_range(
const key_type& __key)
const
840 _Base::equal_range(__key);
846 erase(
const key_type& __key)
849 size_type __bucket_count = this->bucket_count();
851 _Base::equal_range(__key);
852 for (_Base_iterator __victim = __pair.
first; __victim != __pair.
second;)
855 {
return __it == __victim; });
857 [__victim](_Base_const_local_iterator __it)
858 {
return __it._M_curr() == __victim._M_cur; });
859 _Base::erase(__victim++);
862 _M_check_rehashed(__bucket_count);
870 _Base_const_iterator __victim = __it.
base();
872 {
return __it == __victim; });
874 [__victim](_Base_const_local_iterator __it)
875 {
return __it._M_curr() == __victim._M_cur; });
876 size_type __bucket_count = this->bucket_count();
877 _Base_iterator __next = _Base::erase(__it.base());
878 _M_check_rehashed(__bucket_count);
890 for (_Base_const_iterator __tmp = __first.
base();
891 __tmp != __last.
base(); ++__tmp)
893 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
894 _M_message(__gnu_debug::__msg_valid_range)
895 ._M_iterator(__first,
"first")
896 ._M_iterator(__last,
"last"));
898 {
return __it == __tmp; });
900 [__tmp](_Base_const_local_iterator __it)
901 {
return __it._M_curr() == __tmp._M_cur; });
903 size_type __bucket_count = this->bucket_count();
904 _Base_iterator __next = _Base::erase(__first.
base(), __last.
base());
905 _M_check_rehashed(__bucket_count);
910 _M_base() noexcept {
return *
this; }
913 _M_base()
const noexcept {
return *
this; }
917 _M_check_rehashed(size_type __prev_count)
919 if (__prev_count != this->bucket_count())
920 this->_M_invalidate_locals();
924 template<
typename _Key,
typename _Tp,
typename _Hash,
925 typename _Pred,
typename _Alloc>
931 template<
typename _Key,
typename _Tp,
typename _Hash,
932 typename _Pred,
typename _Alloc>
936 {
return __x._M_base() == __y._M_base(); }
938 template<
typename _Key,
typename _Tp,
typename _Hash,
939 typename _Pred,
typename _Alloc>
941 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
942 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
943 {
return !(__x == __y); }
void swap(basic_filebuf< _CharT, _Traits > &__x, basic_filebuf< _CharT, _Traits > &__y)
Swap specialization for filebufs.
#define __glibcxx_check_insert(_Position)
Base class that supports tracking of iterators that reference a sequence.
Primary class template hash.
#define __glibcxx_check_erase(_Position)
Class std::unordered_map with safety/checking/debug instrumentation.
void _M_invalidate_if(_Predicate __pred)
The standard allocator, as per [20.4].
void _M_invalidate_local_if(_Predicate __pred)
_Iterator & base() noexcept
Return the underlying iterator.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
_T2 second
first is a copy of the first object
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
_T1 first
second_type is the second bound type
Class std::unordered_multimap with safety/checking/debug instrumentation.
Base class for constructing a safe unordered container type that tracks iterators that reference it...
A standard container composed of unique keys (containing at most one of each key value) that associat...
#define __glibcxx_check_erase_range(_First, _Last)
One of the comparison functors.
Safe class dealing with some allocator dependent operations.
Struct holding two objects of arbitrary type.