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>
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); }
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>
943 {
return !(__x == __y); }
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Base class that supports tracking of iterators that reference a sequence.
_Iterator & base() noexcept
Return the underlying iterator.
Class std::unordered_multimap with safety/checking/debug instrumentation.
_T2 second
first is a copy of the first object
One of the comparison functors.
#define __glibcxx_check_erase(_Position)
#define __glibcxx_check_erase_range(_First, _Last)
ISO C++ entities toplevel namespace is std.
Class std::unordered_map with safety/checking/debug instrumentation.
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Safe class dealing with some allocator dependent operations.
void _M_invalidate_if(_Predicate __pred)
Struct holding two objects of arbitrary type.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
Base class for constructing a safe unordered container type that tracks iterators that reference it...
The standard allocator, as per [20.4].
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
void _M_invalidate_local_if(_Predicate __pred)
#define __glibcxx_check_insert(_Position)
Primary class template hash.
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.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
_T1 first
second_type is the second bound type