56 #ifndef _STL_MULTIMAP_H
57 #define _STL_MULTIMAP_H 1
60 #if __cplusplus >= 201103L
64 namespace std _GLIBCXX_VISIBILITY(default)
66 _GLIBCXX_BEGIN_NAMESPACE_VERSION
67 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
69 template <
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
96 template <
typename _Key,
typename _Tp,
102 typedef _Key key_type;
103 typedef _Tp mapped_type;
105 typedef _Compare key_compare;
106 typedef _Alloc allocator_type;
109 #ifdef _GLIBCXX_CONCEPT_CHECKS
111 typedef typename _Alloc::value_type _Alloc_value_type;
112 # if __cplusplus < 201103L
113 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
115 __glibcxx_class_requires4(_Compare,
bool, _Key, _Key,
116 _BinaryFunctionConcept)
117 __glibcxx_class_requires2(
value_type, _Alloc_value_type, _SameTypeConcept)
120 #if __cplusplus >= 201103L
121 #if __cplusplus > 201703L || defined __STRICT_ANSI__
123 "std::multimap must have the same value_type as its allocator");
128 #pragma GCC diagnostic push
129 #pragma GCC diagnostic ignored "-Wdeprecated-declarations"
133 friend class multimap<_Key, _Tp, _Compare, _Alloc>;
137 value_compare(_Compare __c)
144 #pragma GCC diagnostic pop
149 rebind<value_type>::other _Pair_alloc_type;
151 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
152 key_compare, _Pair_alloc_type> _Rep_type;
161 typedef typename _Alloc_traits::pointer pointer;
162 typedef typename _Alloc_traits::const_pointer const_pointer;
163 typedef typename _Alloc_traits::reference reference;
164 typedef typename _Alloc_traits::const_reference const_reference;
165 typedef typename _Rep_type::iterator iterator;
166 typedef typename _Rep_type::const_iterator const_iterator;
167 typedef typename _Rep_type::size_type size_type;
168 typedef typename _Rep_type::difference_type difference_type;
172 #if __cplusplus > 201402L
182 #if __cplusplus < 201103L
195 const allocator_type& __a = allocator_type())
196 : _M_t(__comp, _Pair_alloc_type(__a)) { }
203 #if __cplusplus < 201103L
229 const _Compare& __comp = _Compare(),
230 const allocator_type& __a = allocator_type())
231 : _M_t(__comp, _Pair_alloc_type(__a))
232 { _M_t._M_insert_range_equal(__l.begin(), __l.end()); }
237 : _M_t(_Pair_alloc_type(__a)) { }
241 const __type_identity_t<allocator_type>& __a)
242 : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
247 && _Alloc_traits::_S_always_equal())
248 : _M_t(
std::
move(__m._M_t), _Pair_alloc_type(__a)) { }
252 : _M_t(_Pair_alloc_type(__a))
253 { _M_t._M_insert_range_equal(__l.begin(), __l.end()); }
256 template<
typename _InputIterator>
257 multimap(_InputIterator __first, _InputIterator __last,
258 const allocator_type& __a)
259 : _M_t(_Pair_alloc_type(__a))
260 { _M_t._M_insert_range_equal(__first, __last); }
272 template<
typename _InputIterator>
273 multimap(_InputIterator __first, _InputIterator __last)
275 { _M_t._M_insert_range_equal(__first, __last); }
288 template<
typename _InputIterator>
289 multimap(_InputIterator __first, _InputIterator __last,
290 const _Compare& __comp,
291 const allocator_type& __a = allocator_type())
292 : _M_t(__comp, _Pair_alloc_type(__a))
293 { _M_t._M_insert_range_equal(__first, __last); }
295 #if __cplusplus >= 201103L
309 #if __cplusplus < 201103L
338 _M_t._M_assign_equal(__l.begin(), __l.end());
346 {
return allocator_type(_M_t.get_allocator()); }
356 {
return _M_t.begin(); }
365 {
return _M_t.begin(); }
374 {
return _M_t.end(); }
382 end() const _GLIBCXX_NOEXCEPT
383 {
return _M_t.end(); }
392 {
return _M_t.rbegin(); }
399 const_reverse_iterator
401 {
return _M_t.rbegin(); }
410 {
return _M_t.rend(); }
417 const_reverse_iterator
419 {
return _M_t.rend(); }
421 #if __cplusplus >= 201103L
429 {
return _M_t.begin(); }
438 {
return _M_t.end(); }
445 const_reverse_iterator
447 {
return _M_t.rbegin(); }
454 const_reverse_iterator
456 {
return _M_t.rend(); }
461 _GLIBCXX_NODISCARD
bool
463 {
return _M_t.empty(); }
468 {
return _M_t.size(); }
473 {
return _M_t.max_size(); }
476 #if __cplusplus >= 201103L
493 template<
typename... _Args>
496 {
return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
520 template<
typename... _Args>
524 return _M_t._M_emplace_hint_equal(__pos,
525 std::forward<_Args>(__args)...);
544 {
return _M_t._M_insert_equal(__x); }
546 #if __cplusplus >= 201103L
551 {
return _M_t._M_insert_equal(
std::move(__x)); }
553 template<
typename _Pair>
554 __enable_if_t<is_constructible<value_type, _Pair>::value,
iterator>
556 {
return _M_t._M_emplace_equal(std::forward<_Pair>(__x)); }
582 #if __cplusplus >= 201103L
587 {
return _M_t._M_insert_equal_(__position, __x); }
589 #if __cplusplus >= 201103L
594 {
return _M_t._M_insert_equal_(__position,
std::move(__x)); }
596 template<
typename _Pair>
597 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
iterator>
598 insert(const_iterator __position, _Pair&& __x)
600 return _M_t._M_emplace_hint_equal(__position,
601 std::forward<_Pair>(__x));
615 template<
typename _InputIterator>
617 insert(_InputIterator __first, _InputIterator __last)
618 { _M_t._M_insert_range_equal(__first, __last); }
620 #if __cplusplus >= 201103L
630 { this->
insert(__l.begin(), __l.end()); }
633 #if __cplusplus > 201402L
638 __glibcxx_assert(__pos !=
end());
639 return _M_t.extract(__pos);
645 {
return _M_t.extract(__x); }
650 {
return _M_t._M_reinsert_node_equal(
std::move(__nh)); }
654 insert(const_iterator __hint, node_type&& __nh)
655 {
return _M_t._M_reinsert_node_hint_equal(__hint,
std::move(__nh)); }
657 template<
typename,
typename>
658 friend struct std::_Rb_tree_merge_helper;
660 template<
typename _Cmp2>
664 using _Merge_helper = _Rb_tree_merge_helper<multimap, _Cmp2>;
665 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
668 template<
typename _Cmp2>
670 merge(multimap<_Key, _Tp, _Cmp2, _Alloc>&& __source)
673 template<
typename _Cmp2>
675 merge(map<_Key, _Tp, _Cmp2, _Alloc>& __source)
677 using _Merge_helper = _Rb_tree_merge_helper<multimap, _Cmp2>;
678 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
681 template<
typename _Cmp2>
683 merge(map<_Key, _Tp, _Cmp2, _Alloc>&& __source)
687 #if __cplusplus >= 201103L
707 {
return _M_t.erase(__position); }
710 _GLIBCXX_ABI_TAG_CXX11
713 {
return _M_t.erase(__position); }
728 { _M_t.erase(__position); }
744 {
return _M_t.erase(__x); }
746 #if __cplusplus >= 201103L
764 erase(const_iterator __first, const_iterator __last)
765 {
return _M_t.erase(__first, __last); }
784 { _M_t.erase(__first, __last); }
802 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
803 { _M_t.swap(__x._M_t); }
822 {
return _M_t.key_comp(); }
830 {
return value_compare(_M_t.key_comp()); }
848 {
return _M_t.find(__x); }
850 #if __cplusplus > 201103L
851 template<
typename _Kt>
853 find(
const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
854 {
return _M_t._M_find_tr(__x); }
871 find(
const key_type& __x)
const
872 {
return _M_t.find(__x); }
874 #if __cplusplus > 201103L
875 template<
typename _Kt>
877 find(
const _Kt& __x)
const -> decltype(_M_t._M_find_tr(__x))
878 {
return _M_t._M_find_tr(__x); }
890 {
return _M_t.count(__x); }
892 #if __cplusplus > 201103L
893 template<
typename _Kt>
895 count(
const _Kt& __x)
const -> decltype(_M_t._M_count_tr(__x))
896 {
return _M_t._M_count_tr(__x); }
900 #if __cplusplus > 201703L
909 {
return _M_t.find(__x) != _M_t.end(); }
911 template<
typename _Kt>
914 -> decltype(_M_t._M_find_tr(__x),
void(),
true)
915 {
return _M_t._M_find_tr(__x) != _M_t.end(); }
933 {
return _M_t.lower_bound(__x); }
935 #if __cplusplus > 201103L
936 template<
typename _Kt>
939 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
940 {
return iterator(_M_t._M_lower_bound_tr(__x)); }
958 {
return _M_t.lower_bound(__x); }
960 #if __cplusplus > 201103L
961 template<
typename _Kt>
964 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
965 {
return const_iterator(_M_t._M_lower_bound_tr(__x)); }
978 {
return _M_t.upper_bound(__x); }
980 #if __cplusplus > 201103L
981 template<
typename _Kt>
984 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
985 {
return iterator(_M_t._M_upper_bound_tr(__x)); }
998 {
return _M_t.upper_bound(__x); }
1000 #if __cplusplus > 201103L
1001 template<
typename _Kt>
1004 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
1005 {
return const_iterator(_M_t._M_upper_bound_tr(__x)); }
1025 {
return _M_t.equal_range(__x); }
1027 #if __cplusplus > 201103L
1028 template<
typename _Kt>
1052 {
return _M_t.equal_range(__x); }
1054 #if __cplusplus > 201103L
1055 template<
typename _Kt>
1059 _M_t._M_equal_range_tr(__x)))
1062 _M_t._M_equal_range_tr(__x));
1067 template<
typename _K1,
typename _T1,
typename _C1,
typename _A1>
1072 #if __cpp_lib_three_way_comparison
1073 template<
typename _K1,
typename _T1,
typename _C1,
typename _A1>
1074 friend __detail::__synth3way_t<pair<const _K1, _T1>>
1078 template<
typename _K1,
typename _T1,
typename _C1,
typename _A1>
1085 #if __cpp_deduction_guides >= 201606
1087 template<
typename _InputIterator,
1088 typename _Compare = less<__iter_key_t<_InputIterator>>,
1089 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1090 typename = _RequireInputIter<_InputIterator>,
1091 typename = _RequireNotAllocator<_Compare>,
1092 typename = _RequireAllocator<_Allocator>>
1093 multimap(_InputIterator, _InputIterator,
1094 _Compare = _Compare(), _Allocator = _Allocator())
1095 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
1096 _Compare, _Allocator>;
1098 template<
typename _Key,
typename _Tp,
typename _Compare = less<_Key>,
1099 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1100 typename = _RequireNotAllocator<_Compare>,
1101 typename = _RequireAllocator<_Allocator>>
1102 multimap(initializer_list<pair<_Key, _Tp>>,
1103 _Compare = _Compare(), _Allocator = _Allocator())
1104 -> multimap<_Key, _Tp, _Compare, _Allocator>;
1106 template<
typename _InputIterator,
typename _Allocator,
1107 typename = _RequireInputIter<_InputIterator>,
1108 typename = _RequireAllocator<_Allocator>>
1109 multimap(_InputIterator, _InputIterator, _Allocator)
1110 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
1111 less<__iter_key_t<_InputIterator>>, _Allocator>;
1113 template<
typename _Key,
typename _Tp,
typename _Allocator,
1114 typename = _RequireAllocator<_Allocator>>
1115 multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1116 -> multimap<_Key, _Tp, less<_Key>, _Allocator>;
1118 #endif // deduction guides
1130 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1134 {
return __x._M_t == __y._M_t; }
1136 #if __cpp_lib_three_way_comparison
1151 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1152 inline __detail::__synth3way_t<pair<const _Key, _Tp>>
1153 operator<=>(
const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1154 const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1155 {
return __x._M_t <=> __y._M_t; }
1168 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1172 {
return __x._M_t < __y._M_t; }
1175 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1179 {
return !(__x == __y); }
1182 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1186 {
return __y < __x; }
1189 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1193 {
return !(__y < __x); }
1196 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1200 {
return !(__x < __y); }
1201 #endif // three-way comparison
1204 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1208 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.
swap(__y)))
1211 _GLIBCXX_END_NAMESPACE_CONTAINER
1213 #if __cplusplus > 201402L
1215 template<
typename _Key,
typename _Val,
typename _Cmp1,
typename _Alloc,
1218 _Rb_tree_merge_helper<_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>,
1222 friend class _GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>;
1225 _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)
1226 {
return __map._M_t; }
1229 _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)
1230 {
return __map._M_t; }
1234 _GLIBCXX_END_NAMESPACE_VERSION