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())
100 :
_Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
102 __gnu_debug::__base(__last), __n,
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)
368 __glibcxx_check_valid_range2(__first, __last, __dist);
369 size_type __bucket_count = this->bucket_count();
371 if (__dist.
second >= __gnu_debug::__dp_sign)
372 _Base::insert(__gnu_debug::__unsafe(__first),
373 __gnu_debug::__unsafe(__last));
375 _Base::insert(__first, __last);
377 _M_check_rehashed(__bucket_count);
380 #if __cplusplus > 201402L
381 template <
typename... _Args>
383 try_emplace(
const key_type& __k, _Args&&... __args)
385 auto __res = _Base::try_emplace(__k,
386 std::forward<_Args>(__args)...);
387 return {
iterator(__res.first,
this), __res.second };
390 template <
typename... _Args>
392 try_emplace(key_type&& __k, _Args&&... __args)
394 auto __res = _Base::try_emplace(std::move(__k),
395 std::forward<_Args>(__args)...);
396 return {
iterator(__res.first,
this), __res.second };
399 template <
typename... _Args>
406 std::forward<_Args>(__args)...),
410 template <
typename... _Args>
412 try_emplace(
const_iterator __hint, key_type&& __k, _Args&&... __args)
415 return iterator(_Base::try_emplace(__hint.
base(), std::move(__k),
416 std::forward<_Args>(__args)...),
420 template <
typename _Obj>
422 insert_or_assign(
const key_type& __k, _Obj&& __obj)
424 auto __res = _Base::insert_or_assign(__k,
425 std::forward<_Obj>(__obj));
426 return {
iterator(__res.first,
this), __res.second };
429 template <
typename _Obj>
431 insert_or_assign(key_type&& __k, _Obj&& __obj)
433 auto __res = _Base::insert_or_assign(std::move(__k),
434 std::forward<_Obj>(__obj));
435 return {
iterator(__res.first,
this), __res.second };
438 template <
typename _Obj>
444 return iterator(_Base::insert_or_assign(__hint.
base(), __k,
445 std::forward<_Obj>(__obj)),
449 template <
typename _Obj>
451 insert_or_assign(
const_iterator __hint, key_type&& __k, _Obj&& __obj)
456 std::forward<_Obj>(__obj)),
463 find(
const key_type& __key)
464 {
return iterator(_Base::find(__key),
this); }
467 find(
const key_type& __key)
const
471 equal_range(
const key_type& __key)
474 _Base::equal_range(__key);
480 equal_range(
const key_type& __key)
const
483 _Base::equal_range(__key);
489 erase(
const key_type& __key)
492 _Base_iterator __victim(_Base::find(__key));
493 if (__victim != _Base::end())
496 {
return __it == __victim; });
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);
512 _Base_const_iterator __victim = __it.
base();
514 {
return __it == __victim; });
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);
532 for (_Base_const_iterator __tmp = __first.
base();
533 __tmp != __last.
base(); ++__tmp)
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"));
540 {
return __it == __tmp; });
542 [__tmp](_Base_const_local_iterator __it)
543 {
return __it._M_curr() == __tmp._M_cur; });
545 size_type __bucket_count = this->bucket_count();
546 _Base_iterator __next = _Base::erase(__first.
base(), __last.
base());
547 _M_check_rehashed(__bucket_count);
552 _M_base() noexcept {
return *
this; }
555 _M_base()
const noexcept {
return *
this; }
559 _M_check_rehashed(size_type __prev_count)
561 if (__prev_count != this->bucket_count())
562 this->_M_invalidate_locals();
566 template<
typename _Key,
typename _Tp,
typename _Hash,
567 typename _Pred,
typename _Alloc>
571 noexcept(noexcept(__x.swap(__y)))
574 template<
typename _Key,
typename _Tp,
typename _Hash,
575 typename _Pred,
typename _Alloc>
579 {
return __x._M_base() == __y._M_base(); }
581 template<
typename _Key,
typename _Tp,
typename _Hash,
582 typename _Pred,
typename _Alloc>
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); }
590 template<
typename _Key,
typename _Tp,
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>
600 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
601 _Pred, _Alloc>
_Base;
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;
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;
615 typedef typename _Base::key_type key_type;
616 typedef typename _Base::value_type value_type;
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) { }
636 template<
typename _InputIterator>
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,
644 __gnu_debug::__base(__last), __n,
645 __hf, __eql, __a) { }
659 const allocator_type& __a)
660 :
_Base(__umap, __a) { }
663 const allocator_type& __a)
664 :
_Safe(std::move(__umap._M_safe()), __a),
665 _Base(std::move(__umap._M_base()), __a) { }
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) { }
679 const allocator_type& __a)
683 template<
typename _InputIterator>
686 const allocator_type& __a)
690 template<
typename _InputIterator>
692 size_type __n,
const hasher& __hf,
693 const allocator_type& __a)
699 const allocator_type& __a)
704 size_type __n,
const hasher& __hf,
705 const allocator_type& __a)
720 this->_M_base() = __l;
721 this->_M_invalidate_all();
727 noexcept( noexcept(declval<_Base&>().
swap(__x)) )
737 this->_M_invalidate_all();
742 {
return iterator(_Base::begin(),
this); }
745 begin()
const noexcept
750 {
return iterator(_Base::end(),
this); }
757 cbegin()
const noexcept
761 cend()
const noexcept
768 __glibcxx_check_bucket_index(__b);
775 __glibcxx_check_bucket_index(__b);
780 begin(size_type __b)
const
782 __glibcxx_check_bucket_index(__b);
787 end(size_type __b)
const
789 __glibcxx_check_bucket_index(__b);
794 cbegin(size_type __b)
const
796 __glibcxx_check_bucket_index(__b);
801 cend(size_type __b)
const
803 __glibcxx_check_bucket_index(__b);
808 bucket_size(size_type __b)
const
810 __glibcxx_check_bucket_index(__b);
811 return _Base::bucket_size(__b);
815 max_load_factor()
const noexcept
816 {
return _Base::max_load_factor(); }
819 max_load_factor(
float __f)
821 __glibcxx_check_max_load_factor(__f);
822 _Base::max_load_factor(__f);
825 template<
typename... _Args>
827 emplace(_Args&&... __args)
829 size_type __bucket_count = this->bucket_count();
831 = _Base::emplace(std::forward<_Args>(__args)...);
832 _M_check_rehashed(__bucket_count);
836 template<
typename... _Args>
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);
849 insert(
const value_type& __obj)
851 size_type __bucket_count = this->bucket_count();
852 _Base_iterator __it = _Base::insert(__obj);
853 _M_check_rehashed(__bucket_count);
861 size_type __bucket_count = this->bucket_count();
862 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
863 _M_check_rehashed(__bucket_count);
867 template<
typename _Pair,
typename =
typename
868 std::enable_if<std::is_constructible<value_type,
869 _Pair&&>::value>::type>
871 insert(_Pair&& __obj)
873 size_type __bucket_count = this->bucket_count();
874 _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
875 _M_check_rehashed(__bucket_count);
879 template<
typename _Pair,
typename =
typename
880 std::enable_if<std::is_constructible<value_type,
881 _Pair&&>::value>::type>
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);
895 { _Base::insert(__l); }
897 template<
typename _InputIterator>
899 insert(_InputIterator __first, _InputIterator __last)
902 __glibcxx_check_valid_range2(__first, __last, __dist);
903 size_type __bucket_count = this->bucket_count();
905 if (__dist.
second >= __gnu_debug::__dp_sign)
906 _Base::insert(__gnu_debug::__unsafe(__first),
907 __gnu_debug::__unsafe(__last));
909 _Base::insert(__first, __last);
911 _M_check_rehashed(__bucket_count);
915 find(
const key_type& __key)
916 {
return iterator(_Base::find(__key),
this); }
919 find(
const key_type& __key)
const
923 equal_range(
const key_type& __key)
926 _Base::equal_range(__key);
932 equal_range(
const key_type& __key)
const
935 _Base::equal_range(__key);
941 erase(
const key_type& __key)
944 size_type __bucket_count = this->bucket_count();
946 _Base::equal_range(__key);
947 for (_Base_iterator __victim = __pair.
first; __victim != __pair.
second;)
950 {
return __it == __victim; });
952 [__victim](_Base_const_local_iterator __it)
953 {
return __it._M_curr() == __victim._M_cur; });
954 _Base::erase(__victim++);
957 _M_check_rehashed(__bucket_count);
965 _Base_const_iterator __victim = __it.
base();
967 {
return __it == __victim; });
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);
985 for (_Base_const_iterator __tmp = __first.
base();
986 __tmp != __last.
base(); ++__tmp)
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"));
993 {
return __it == __tmp; });
995 [__tmp](_Base_const_local_iterator __it)
996 {
return __it._M_curr() == __tmp._M_cur; });
998 size_type __bucket_count = this->bucket_count();
999 _Base_iterator __next = _Base::erase(__first.
base(), __last.
base());
1000 _M_check_rehashed(__bucket_count);
1005 _M_base() noexcept {
return *
this; }
1008 _M_base()
const noexcept {
return *
this; }
1012 _M_check_rehashed(size_type __prev_count)
1014 if (__prev_count != this->bucket_count())
1015 this->_M_invalidate_locals();
1019 template<
typename _Key,
typename _Tp,
typename _Hash,
1020 typename _Pred,
typename _Alloc>
1024 noexcept(noexcept(__x.swap(__y)))
1027 template<
typename _Key,
typename _Tp,
typename _Hash,
1028 typename _Pred,
typename _Alloc>
1032 {
return __x._M_base() == __y._M_base(); }
1034 template<
typename _Key,
typename _Tp,
typename _Hash,
1035 typename _Pred,
typename _Alloc>
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); }
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
_Iterator & base() noexcept
Return the underlying iterator.
Primary class template hash.
Base class for constructing a safe unordered container type that tracks iterators that reference it...
The standard allocator, as per [20.4].
void swap(basic_filebuf< _CharT, _Traits > &__x, basic_filebuf< _CharT, _Traits > &__y)
Swap specialization for filebufs.
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.
Safe class dealing with some allocator dependent operations.
Base class that supports tracking of iterators that reference a sequence.
Class std::unordered_multimap with safety/checking/debug instrumentation.
void _M_invalidate_if(_Predicate __pred)
A standard container composed of unique keys (containing at most one of each key value) that associat...
One of the comparison functors.
#define __glibcxx_check_erase_range(_First, _Last)
_T2 second
first is a copy of the first object
void _M_invalidate_local_if(_Predicate __pred)
Struct holding two objects of arbitrary type.
Class std::unordered_map with safety/checking/debug instrumentation.
_T1 first
second_type is the second bound type
#define __glibcxx_check_erase(_Position)
#define __glibcxx_check_insert(_Position)