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;
77 _Base_iterator, unordered_map>
iterator;
85 unordered_map() =
default;
88 unordered_map(size_type __n,
89 const hasher& __hf = hasher(),
90 const key_equal& __eql = key_equal(),
91 const allocator_type& __a = allocator_type())
92 : _Base(__n, __hf, __eql, __a) { }
94 template<
typename _InputIterator>
95 unordered_map(_InputIterator __first, _InputIterator __last,
97 const hasher& __hf = hasher(),
98 const key_equal& __eql = key_equal(),
99 const allocator_type& __a = allocator_type())
103 __hf, __eql, __a) { }
105 unordered_map(
const unordered_map&) =
default;
107 unordered_map(
const _Base& __x)
110 unordered_map(unordered_map&&) =
default;
113 unordered_map(
const allocator_type& __a)
116 unordered_map(
const unordered_map& __umap,
117 const allocator_type& __a)
118 : _Base(__umap, __a) { }
120 unordered_map(unordered_map&& __umap,
121 const allocator_type& __a)
122 : _Safe(std::move(__umap._M_safe()), __a),
123 _Base(std::move(__umap._M_base()), __a) { }
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) { }
132 unordered_map(size_type __n,
const allocator_type& __a)
133 : unordered_map(__n, hasher(), key_equal(), __a)
136 unordered_map(size_type __n,
138 const allocator_type& __a)
139 : unordered_map(__n, __hf, key_equal(), __a)
142 template<
typename _InputIterator>
143 unordered_map(_InputIterator __first, _InputIterator __last,
145 const allocator_type& __a)
146 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
149 template<
typename _InputIterator>
150 unordered_map(_InputIterator __first, _InputIterator __last,
153 const allocator_type& __a)
154 : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
159 const allocator_type& __a)
160 : unordered_map(__l, __n, hasher(), key_equal(), __a)
166 const allocator_type& __a)
167 : unordered_map(__l, __n, __hf, key_equal(), __a)
170 ~unordered_map() =
default;
173 operator=(
const unordered_map&) =
default;
176 operator=(unordered_map&&) =
default;
182 this->_M_invalidate_all();
187 swap(unordered_map& __x)
188 noexcept( noexcept(declval<_Base>().swap(__x)) )
198 this->_M_invalidate_all();
203 {
return iterator(_Base::begin(),
this); }
206 begin()
const noexcept
207 {
return const_iterator(_Base::begin(),
this); }
211 {
return iterator(_Base::end(),
this); }
215 {
return const_iterator(_Base::end(),
this); }
218 cbegin()
const noexcept
219 {
return const_iterator(_Base::begin(),
this); }
222 cend()
const noexcept
223 {
return const_iterator(_Base::end(),
this); }
229 __glibcxx_check_bucket_index(__b);
230 return local_iterator(_Base::begin(__b),
this);
236 __glibcxx_check_bucket_index(__b);
237 return local_iterator(_Base::end(__b),
this);
241 begin(size_type __b)
const
243 __glibcxx_check_bucket_index(__b);
244 return const_local_iterator(_Base::begin(__b),
this);
248 end(size_type __b)
const
250 __glibcxx_check_bucket_index(__b);
251 return const_local_iterator(_Base::end(__b),
this);
255 cbegin(size_type __b)
const
257 __glibcxx_check_bucket_index(__b);
258 return const_local_iterator(_Base::cbegin(__b),
this);
262 cend(size_type __b)
const
264 __glibcxx_check_bucket_index(__b);
265 return const_local_iterator(_Base::cend(__b),
this);
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>
299 emplace_hint(const_iterator __hint, _Args&&... __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);
306 return iterator(__it,
this);
310 insert(
const value_type& __obj)
312 size_type __bucket_count = this->bucket_count();
314 _M_check_rehashed(__bucket_count);
319 insert(const_iterator __hint,
const value_type& __obj)
322 size_type __bucket_count = this->bucket_count();
323 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
324 _M_check_rehashed(__bucket_count);
325 return iterator(__it,
this);
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>
345 insert(const_iterator __hint, _Pair&& __obj)
348 size_type __bucket_count = this->bucket_count();
349 _Base_iterator __it =
350 _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
351 _M_check_rehashed(__bucket_count);
352 return iterator(__it,
this);
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
380 {
return const_iterator(_Base::find(__key),
this); }
383 equal_range(
const key_type& __key)
386 _Base::equal_range(__key);
388 iterator(__res.
second,
this));
392 equal_range(
const key_type& __key)
const
395 _Base::equal_range(__key);
397 const_iterator(__res.
second,
this));
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);
421 erase(const_iterator __it)
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);
433 return iterator(__next,
this);
438 {
return erase(const_iterator(__it)); }
441 erase(const_iterator __first, const_iterator __last)
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);
460 return iterator(__next,
this);
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;
530 _Base_iterator, unordered_multimap>
iterator;
538 unordered_multimap() =
default;
541 unordered_multimap(size_type __n,
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>
548 unordered_multimap(_InputIterator __first, _InputIterator __last,
550 const hasher& __hf = hasher(),
551 const key_equal& __eql = key_equal(),
552 const allocator_type& __a = allocator_type())
556 __hf, __eql, __a) { }
558 unordered_multimap(
const unordered_multimap&) =
default;
560 unordered_multimap(
const _Base& __x)
563 unordered_multimap(unordered_multimap&&) =
default;
566 unordered_multimap(
const allocator_type& __a)
569 unordered_multimap(
const unordered_multimap& __umap,
570 const allocator_type& __a)
571 : _Base(__umap, __a) { }
573 unordered_multimap(unordered_multimap&& __umap,
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) { }
585 unordered_multimap(size_type __n,
const allocator_type& __a)
586 : unordered_multimap(__n, hasher(), key_equal(), __a)
589 unordered_multimap(size_type __n,
const hasher& __hf,
590 const allocator_type& __a)
591 : unordered_multimap(__n, __hf, key_equal(), __a)
594 template<
typename _InputIterator>
595 unordered_multimap(_InputIterator __first, _InputIterator __last,
597 const allocator_type& __a)
598 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
601 template<
typename _InputIterator>
602 unordered_multimap(_InputIterator __first, _InputIterator __last,
603 size_type __n,
const hasher& __hf,
604 const allocator_type& __a)
605 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
610 const allocator_type& __a)
611 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
615 size_type __n,
const hasher& __hf,
616 const allocator_type& __a)
617 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
620 ~unordered_multimap() =
default;
623 operator=(
const unordered_multimap&) =
default;
626 operator=(unordered_multimap&&) =
default;
631 this->_M_base() = __l;
632 this->_M_invalidate_all();
637 swap(unordered_multimap& __x)
638 noexcept( noexcept(declval<_Base>().swap(__x)) )
648 this->_M_invalidate_all();
653 {
return iterator(_Base::begin(),
this); }
656 begin()
const noexcept
657 {
return const_iterator(_Base::begin(),
this); }
661 {
return iterator(_Base::end(),
this); }
665 {
return const_iterator(_Base::end(),
this); }
668 cbegin()
const noexcept
669 {
return const_iterator(_Base::begin(),
this); }
672 cend()
const noexcept
673 {
return const_iterator(_Base::end(),
this); }
679 __glibcxx_check_bucket_index(__b);
680 return local_iterator(_Base::begin(__b),
this);
686 __glibcxx_check_bucket_index(__b);
687 return local_iterator(_Base::end(__b),
this);
691 begin(size_type __b)
const
693 __glibcxx_check_bucket_index(__b);
694 return const_local_iterator(_Base::begin(__b),
this);
698 end(size_type __b)
const
700 __glibcxx_check_bucket_index(__b);
701 return const_local_iterator(_Base::end(__b),
this);
705 cbegin(size_type __b)
const
707 __glibcxx_check_bucket_index(__b);
708 return const_local_iterator(_Base::cbegin(__b),
this);
712 cend(size_type __b)
const
714 __glibcxx_check_bucket_index(__b);
715 return const_local_iterator(_Base::cend(__b),
this);
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);
744 return iterator(__it,
this);
747 template<
typename... _Args>
749 emplace_hint(const_iterator __hint, _Args&&... __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);
756 return iterator(__it,
this);
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);
765 return iterator(__it,
this);
769 insert(const_iterator __hint,
const value_type& __obj)
772 size_type __bucket_count = this->bucket_count();
773 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
774 _M_check_rehashed(__bucket_count);
775 return iterator(__it,
this);
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);
787 return iterator(__it,
this);
790 template<
typename _Pair,
typename =
typename
791 std::enable_if<std::is_constructible<value_type,
792 _Pair&&>::value>::type>
794 insert(const_iterator __hint, _Pair&& __obj)
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);
801 return iterator(__it,
this);
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
825 {
return const_iterator(_Base::find(__key),
this); }
828 equal_range(
const key_type& __key)
831 _Base::equal_range(__key);
833 iterator(__res.
second,
this));
837 equal_range(
const key_type& __key)
const
840 _Base::equal_range(__key);
842 const_iterator(__res.
second,
this));
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);
867 erase(const_iterator __it)
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);
879 return iterator(__next,
this);
884 {
return erase(const_iterator(__it)); }
887 erase(const_iterator __first, const_iterator __last)
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);
906 return iterator(__next,
this);
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 _M_invalidate_local_if(_Predicate __pred)
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
_T1 first
second_type is the second bound type
Primary class template hash.
_Iterator & base() noexcept
Return the underlying iterator.
#define __glibcxx_check_erase(_Position)
#define __glibcxx_check_erase_range(_First, _Last)
void _M_invalidate_if(_Predicate __pred)
A standard container composed of unique keys (containing at most one of each key value) that associat...
Class std::unordered_multimap with safety/checking/debug instrumentation.
Base class for constructing a safe unordered container type that tracks iterators that reference it...
ISO C++ entities toplevel namespace is std.
#define __glibcxx_check_insert(_Position)
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
One of the comparison functors.
Safe class dealing with some allocator dependent operations.
Struct holding two objects of arbitrary type.
Class std::unordered_map with safety/checking/debug instrumentation.
Base class that supports tracking of iterators that reference a sequence.
The standard allocator, as per [20.4].
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.
_T2 second
first is a copy of the first object