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__
122 static_assert(is_same<typename _Alloc::value_type, value_type>::value,
123 "std::multimap must have the same value_type as its allocator");
131 friend class multimap<_Key, _Tp, _Compare, _Alloc>;
135 value_compare(_Compare __c)
139 bool operator()(
const value_type& __x,
const value_type& __y)
const
140 {
return comp(__x.first, __y.first); }
146 rebind<value_type>::other _Pair_alloc_type;
148 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
149 key_compare, _Pair_alloc_type> _Rep_type;
158 typedef typename _Alloc_traits::pointer pointer;
159 typedef typename _Alloc_traits::const_pointer const_pointer;
160 typedef typename _Alloc_traits::reference reference;
161 typedef typename _Alloc_traits::const_reference const_reference;
162 typedef typename _Rep_type::iterator iterator;
163 typedef typename _Rep_type::const_iterator const_iterator;
164 typedef typename _Rep_type::size_type size_type;
165 typedef typename _Rep_type::difference_type difference_type;
166 typedef typename _Rep_type::reverse_iterator reverse_iterator;
167 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
169 #if __cplusplus > 201402L
170 using node_type =
typename _Rep_type::node_type;
179 #if __cplusplus < 201103L
192 const allocator_type& __a = allocator_type())
193 : _M_t(__comp, _Pair_alloc_type(__a)) { }
200 #if __cplusplus < 201103L
226 const _Compare& __comp = _Compare(),
227 const allocator_type& __a = allocator_type())
228 : _M_t(__comp, _Pair_alloc_type(__a))
229 { _M_t._M_insert_range_equal(__l.begin(), __l.end()); }
234 : _M_t(_Pair_alloc_type(__a)) { }
238 : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
243 && _Alloc_traits::_S_always_equal())
244 : _M_t(
std::
move(__m._M_t), _Pair_alloc_type(__a)) { }
248 : _M_t(_Pair_alloc_type(__a))
249 { _M_t._M_insert_range_equal(__l.begin(), __l.end()); }
252 template<
typename _InputIterator>
253 multimap(_InputIterator __first, _InputIterator __last,
254 const allocator_type& __a)
255 : _M_t(_Pair_alloc_type(__a))
256 { _M_t._M_insert_range_equal(__first, __last); }
268 template<
typename _InputIterator>
269 multimap(_InputIterator __first, _InputIterator __last)
271 { _M_t._M_insert_range_equal(__first, __last); }
284 template<
typename _InputIterator>
285 multimap(_InputIterator __first, _InputIterator __last,
286 const _Compare& __comp,
287 const allocator_type& __a = allocator_type())
288 : _M_t(__comp, _Pair_alloc_type(__a))
289 { _M_t._M_insert_range_equal(__first, __last); }
291 #if __cplusplus >= 201103L
305 #if __cplusplus < 201103L
334 _M_t._M_assign_equal(__l.begin(), __l.end());
342 {
return allocator_type(_M_t.get_allocator()); }
352 {
return _M_t.begin(); }
361 {
return _M_t.begin(); }
370 {
return _M_t.end(); }
378 end() const _GLIBCXX_NOEXCEPT
379 {
return _M_t.end(); }
388 {
return _M_t.rbegin(); }
395 const_reverse_iterator
397 {
return _M_t.rbegin(); }
406 {
return _M_t.rend(); }
413 const_reverse_iterator
415 {
return _M_t.rend(); }
417 #if __cplusplus >= 201103L
425 {
return _M_t.begin(); }
434 {
return _M_t.end(); }
441 const_reverse_iterator
443 {
return _M_t.rbegin(); }
450 const_reverse_iterator
452 {
return _M_t.rend(); }
457 _GLIBCXX_NODISCARD
bool
459 {
return _M_t.empty(); }
464 {
return _M_t.size(); }
469 {
return _M_t.max_size(); }
472 #if __cplusplus >= 201103L
489 template<
typename... _Args>
492 {
return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
516 template<
typename... _Args>
520 return _M_t._M_emplace_hint_equal(__pos,
521 std::forward<_Args>(__args)...);
540 {
return _M_t._M_insert_equal(__x); }
542 #if __cplusplus >= 201103L
547 {
return _M_t._M_insert_equal(
std::move(__x)); }
549 template<
typename _Pair>
550 __enable_if_t<is_constructible<value_type, _Pair>::value,
iterator>
552 {
return _M_t._M_emplace_equal(std::forward<_Pair>(__x)); }
578 #if __cplusplus >= 201103L
583 {
return _M_t._M_insert_equal_(__position, __x); }
585 #if __cplusplus >= 201103L
590 {
return _M_t._M_insert_equal_(__position,
std::move(__x)); }
592 template<
typename _Pair>
593 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
iterator>
594 insert(const_iterator __position, _Pair&& __x)
596 return _M_t._M_emplace_hint_equal(__position,
597 std::forward<_Pair>(__x));
611 template<
typename _InputIterator>
613 insert(_InputIterator __first, _InputIterator __last)
614 { _M_t._M_insert_range_equal(__first, __last); }
616 #if __cplusplus >= 201103L
626 { this->
insert(__l.begin(), __l.end()); }
629 #if __cplusplus > 201402L
632 extract(const_iterator __pos)
634 __glibcxx_assert(__pos !=
end());
635 return _M_t.extract(__pos);
640 extract(
const key_type& __x)
641 {
return _M_t.extract(__x); }
646 {
return _M_t._M_reinsert_node_equal(
std::move(__nh)); }
650 insert(const_iterator __hint, node_type&& __nh)
651 {
return _M_t._M_reinsert_node_hint_equal(__hint,
std::move(__nh)); }
653 template<
typename,
typename>
654 friend class std::_Rb_tree_merge_helper;
656 template<
typename _Cmp2>
658 merge(multimap<_Key, _Tp, _Cmp2, _Alloc>& __source)
660 using _Merge_helper = _Rb_tree_merge_helper<multimap, _Cmp2>;
661 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
664 template<
typename _Cmp2>
666 merge(multimap<_Key, _Tp, _Cmp2, _Alloc>&& __source)
669 template<
typename _Cmp2>
671 merge(map<_Key, _Tp, _Cmp2, _Alloc>& __source)
673 using _Merge_helper = _Rb_tree_merge_helper<multimap, _Cmp2>;
674 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
677 template<
typename _Cmp2>
679 merge(map<_Key, _Tp, _Cmp2, _Alloc>&& __source)
683 #if __cplusplus >= 201103L
703 {
return _M_t.erase(__position); }
706 _GLIBCXX_ABI_TAG_CXX11
709 {
return _M_t.erase(__position); }
724 { _M_t.erase(__position); }
740 {
return _M_t.erase(__x); }
742 #if __cplusplus >= 201103L
760 erase(const_iterator __first, const_iterator __last)
761 {
return _M_t.erase(__first, __last); }
780 { _M_t.erase(__first, __last); }
798 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
799 { _M_t.swap(__x._M_t); }
818 {
return _M_t.key_comp(); }
826 {
return value_compare(_M_t.key_comp()); }
844 {
return _M_t.find(__x); }
846 #if __cplusplus > 201103L
847 template<
typename _Kt>
849 find(
const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
850 {
return _M_t._M_find_tr(__x); }
867 find(
const key_type& __x)
const
868 {
return _M_t.find(__x); }
870 #if __cplusplus > 201103L
871 template<
typename _Kt>
873 find(
const _Kt& __x)
const -> decltype(_M_t._M_find_tr(__x))
874 {
return _M_t._M_find_tr(__x); }
886 {
return _M_t.count(__x); }
888 #if __cplusplus > 201103L
889 template<
typename _Kt>
891 count(
const _Kt& __x)
const -> decltype(_M_t._M_count_tr(__x))
892 {
return _M_t._M_count_tr(__x); }
896 #if __cplusplus > 201703L
904 contains(
const key_type& __x)
const
905 {
return _M_t.find(__x) != _M_t.end(); }
907 template<
typename _Kt>
909 contains(
const _Kt& __x)
const
910 -> decltype(_M_t._M_find_tr(__x),
void(),
true)
911 {
return _M_t._M_find_tr(__x) != _M_t.end(); }
929 {
return _M_t.lower_bound(__x); }
931 #if __cplusplus > 201103L
932 template<
typename _Kt>
935 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
936 {
return iterator(_M_t._M_lower_bound_tr(__x)); }
954 {
return _M_t.lower_bound(__x); }
956 #if __cplusplus > 201103L
957 template<
typename _Kt>
960 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
961 {
return const_iterator(_M_t._M_lower_bound_tr(__x)); }
974 {
return _M_t.upper_bound(__x); }
976 #if __cplusplus > 201103L
977 template<
typename _Kt>
980 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
981 {
return iterator(_M_t._M_upper_bound_tr(__x)); }
994 {
return _M_t.upper_bound(__x); }
996 #if __cplusplus > 201103L
997 template<
typename _Kt>
1000 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
1001 {
return const_iterator(_M_t._M_upper_bound_tr(__x)); }
1021 {
return _M_t.equal_range(__x); }
1023 #if __cplusplus > 201103L
1024 template<
typename _Kt>
1048 {
return _M_t.equal_range(__x); }
1050 #if __cplusplus > 201103L
1051 template<
typename _Kt>
1055 _M_t._M_equal_range_tr(__x)))
1058 _M_t._M_equal_range_tr(__x));
1063 template<
typename _K1,
typename _T1,
typename _C1,
typename _A1>
1068 template<
typename _K1,
typename _T1,
typename _C1,
typename _A1>
1074 #if __cpp_deduction_guides >= 201606
1076 template<
typename _InputIterator,
1077 typename _Compare = less<__iter_key_t<_InputIterator>>,
1078 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1079 typename = _RequireInputIter<_InputIterator>,
1080 typename = _RequireNotAllocator<_Compare>,
1081 typename = _RequireAllocator<_Allocator>>
1082 multimap(_InputIterator, _InputIterator,
1083 _Compare = _Compare(), _Allocator = _Allocator())
1084 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
1085 _Compare, _Allocator>;
1087 template<
typename _Key,
typename _Tp,
typename _Compare = less<_Key>,
1088 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1089 typename = _RequireNotAllocator<_Compare>,
1090 typename = _RequireAllocator<_Allocator>>
1091 multimap(initializer_list<pair<_Key, _Tp>>,
1092 _Compare = _Compare(), _Allocator = _Allocator())
1093 -> multimap<_Key, _Tp, _Compare, _Allocator>;
1095 template<
typename _InputIterator,
typename _Allocator,
1096 typename = _RequireInputIter<_InputIterator>,
1097 typename = _RequireAllocator<_Allocator>>
1098 multimap(_InputIterator, _InputIterator, _Allocator)
1099 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
1100 less<__iter_key_t<_InputIterator>>, _Allocator>;
1102 template<
typename _Key,
typename _Tp,
typename _Allocator,
1103 typename = _RequireAllocator<_Allocator>>
1104 multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1105 -> multimap<_Key, _Tp, less<_Key>, _Allocator>;
1119 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1123 {
return __x._M_t == __y._M_t; }
1136 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1140 {
return __x._M_t < __y._M_t; }
1143 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1147 {
return !(__x == __y); }
1150 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1154 {
return __y < __x; }
1157 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1161 {
return !(__y < __x); }
1164 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1168 {
return !(__x < __y); }
1171 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1175 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1178 _GLIBCXX_END_NAMESPACE_CONTAINER
1180 #if __cplusplus > 201402L
1182 template<
typename _Key,
typename _Val,
typename _Cmp1,
typename _Alloc,
1185 _Rb_tree_merge_helper<_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>,
1189 friend class _GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>;
1192 _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)
1193 {
return __map._M_t; }
1196 _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)
1197 {
return __map._M_t; }
1201 _GLIBCXX_END_NAMESPACE_VERSION