61 #if __cplusplus >= 201103L
66 namespace std _GLIBCXX_VISIBILITY(default)
68 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
70 template <
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
97 template <
typename _Key,
typename _Tp,
typename _Compare = std::less<_Key>,
98 typename _Alloc = std::allocator<std::pair<const _Key, _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)
124 friend class map<_Key, _Tp, _Compare, _Alloc>;
128 value_compare(_Compare __c)
139 rebind<value_type>::other _Pair_alloc_type;
141 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
142 key_compare, _Pair_alloc_type> _Rep_type;
152 typedef typename _Alloc_traits::pointer pointer;
153 typedef typename _Alloc_traits::const_pointer const_pointer;
154 typedef typename _Alloc_traits::reference reference;
155 typedef typename _Alloc_traits::const_reference const_reference;
156 typedef typename _Rep_type::iterator iterator;
157 typedef typename _Rep_type::const_iterator const_iterator;
158 typedef typename _Rep_type::size_type size_type;
159 typedef typename _Rep_type::difference_type difference_type;
163 #if __cplusplus > 201402L
164 using node_type =
typename _Rep_type::node_type;
165 using insert_return_type =
typename _Rep_type::insert_return_type;
174 #if __cplusplus < 201103L
186 map(
const _Compare& __comp,
187 const allocator_type& __a = allocator_type())
188 : _M_t(__comp, _Pair_alloc_type(__a)) { }
195 #if __cplusplus < 201103L
221 const _Compare& __comp = _Compare(),
222 const allocator_type& __a = allocator_type())
223 : _M_t(__comp, _Pair_alloc_type(__a))
224 { _M_t._M_insert_unique(__l.begin(), __l.end()); }
228 map(
const allocator_type& __a)
229 : _M_t(_Compare(), _Pair_alloc_type(__a)) { }
232 map(
const map& __m,
const allocator_type& __a)
233 : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
236 map(
map&& __m,
const allocator_type& __a)
237 noexcept(is_nothrow_copy_constructible<_Compare>::value
238 && _Alloc_traits::_S_always_equal())
239 : _M_t(
std::move(__m._M_t), _Pair_alloc_type(__a)) { }
243 : _M_t(_Compare(), _Pair_alloc_type(__a))
244 { _M_t._M_insert_unique(__l.begin(), __l.end()); }
247 template<
typename _InputIterator>
248 map(_InputIterator __first, _InputIterator __last,
249 const allocator_type& __a)
250 : _M_t(_Compare(), _Pair_alloc_type(__a))
251 { _M_t._M_insert_unique(__first, __last); }
264 template<
typename _InputIterator>
265 map(_InputIterator __first, _InputIterator __last)
267 { _M_t._M_insert_unique(__first, __last); }
281 template<
typename _InputIterator>
282 map(_InputIterator __first, _InputIterator __last,
283 const _Compare& __comp,
284 const allocator_type& __a = allocator_type())
285 : _M_t(__comp, _Pair_alloc_type(__a))
286 { _M_t._M_insert_unique(__first, __last); }
288 #if __cplusplus >= 201103L
302 #if __cplusplus < 201103L
331 _M_t._M_assign_unique(__l.begin(), __l.end());
339 {
return allocator_type(_M_t.get_allocator()); }
349 {
return _M_t.begin(); }
358 {
return _M_t.begin(); }
367 {
return _M_t.end(); }
375 end() const _GLIBCXX_NOEXCEPT
376 {
return _M_t.end(); }
385 {
return _M_t.rbegin(); }
392 const_reverse_iterator
394 {
return _M_t.rbegin(); }
403 {
return _M_t.rend(); }
410 const_reverse_iterator
412 {
return _M_t.rend(); }
414 #if __cplusplus >= 201103L
422 {
return _M_t.begin(); }
431 {
return _M_t.end(); }
438 const_reverse_iterator
440 {
return _M_t.rbegin(); }
447 const_reverse_iterator
449 {
return _M_t.rend(); }
458 {
return _M_t.empty(); }
463 {
return _M_t.size(); }
468 {
return _M_t.max_size(); }
487 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
492 #if __cplusplus >= 201103L
499 return (*__i).second;
502 #if __cplusplus >= 201103L
507 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
513 std::forward_as_tuple(std::move(__k)),
515 return (*__i).second;
529 at(
const key_type& __k)
533 __throw_out_of_range(__N(
"map::at"));
534 return (*__i).second;
538 at(
const key_type& __k)
const
542 __throw_out_of_range(__N(
"map::at"));
543 return (*__i).second;
547 #if __cplusplus >= 201103L
566 template<
typename... _Args>
569 {
return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
596 template<
typename... _Args>
600 return _M_t._M_emplace_hint_unique(__pos,
601 std::forward<_Args>(__args)...);
605 #if __cplusplus > 201402L
608 extract(const_iterator __pos)
610 __glibcxx_assert(__pos !=
end());
611 return _M_t.extract(__pos);
616 extract(
const key_type& __x)
617 {
return _M_t.extract(__x); }
622 {
return _M_t._M_reinsert_node_unique(std::move(__nh)); }
626 insert(const_iterator __hint, node_type&& __nh)
627 {
return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); }
629 template<
typename,
typename>
630 friend class _Rb_tree_merge_helper;
632 template<
typename _C2>
634 merge(map<_Key, _Tp, _C2, _Alloc>& __source)
636 using _Merge_helper = _Rb_tree_merge_helper<map, _C2>;
637 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
640 template<
typename _C2>
642 merge(map<_Key, _Tp, _C2, _Alloc>&& __source)
645 template<
typename _C2>
647 merge(multimap<_Key, _Tp, _C2, _Alloc>& __source)
649 using _Merge_helper = _Rb_tree_merge_helper<map, _C2>;
650 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
653 template<
typename _C2>
655 merge(multimap<_Key, _Tp, _C2, _Alloc>&& __source)
659 #if __cplusplus > 201402L
660 #define __cpp_lib_map_try_emplace 201411
681 template <
typename... _Args>
683 try_emplace(
const key_type& __k, _Args&&... __args)
689 std::forward_as_tuple(__k),
690 std::forward_as_tuple(
691 std::forward<_Args>(__args)...));
698 template <
typename... _Args>
700 try_emplace(key_type&& __k, _Args&&... __args)
706 std::forward_as_tuple(std::move(__k)),
707 std::forward_as_tuple(
708 std::forward<_Args>(__args)...));
741 template <
typename... _Args>
743 try_emplace(const_iterator __hint,
const key_type& __k,
747 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
748 if (__true_hint.second)
751 std::forward_as_tuple(__k),
752 std::forward_as_tuple(
753 std::forward<_Args>(__args)...));
755 __i = iterator(__true_hint.first);
760 template <
typename... _Args>
762 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
765 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
766 if (__true_hint.second)
769 std::forward_as_tuple(std::move(__k)),
770 std::forward_as_tuple(
771 std::forward<_Args>(__args)...));
773 __i = iterator(__true_hint.first);
796 {
return _M_t._M_insert_unique(__x); }
798 #if __cplusplus >= 201103L
803 {
return _M_t._M_insert_unique(std::move(__x)); }
805 template<
typename _Pair>
806 __enable_if_t<is_constructible<value_type, _Pair>::value,
809 {
return _M_t._M_emplace_unique(std::forward<_Pair>(__x)); }
813 #if __cplusplus >= 201103L
823 {
insert(__list.begin(), __list.end()); }
851 #if __cplusplus >= 201103L
856 {
return _M_t._M_insert_unique_(__position, __x); }
858 #if __cplusplus >= 201103L
863 {
return _M_t._M_insert_unique_(__position, std::move(__x)); }
865 template<
typename _Pair>
866 __enable_if_t<is_constructible<value_type, _Pair>::value,
iterator>
867 insert(const_iterator __position, _Pair&& __x)
869 return _M_t._M_emplace_hint_unique(__position,
870 std::forward<_Pair>(__x));
883 template<
typename _InputIterator>
885 insert(_InputIterator __first, _InputIterator __last)
886 { _M_t._M_insert_unique(__first, __last); }
888 #if __cplusplus > 201402L
889 #define __cpp_lib_map_insertion 201411
909 template <
typename _Obj>
911 insert_or_assign(
const key_type& __k, _Obj&& __obj)
917 std::forward_as_tuple(__k),
918 std::forward_as_tuple(
919 std::forward<_Obj>(__obj)));
922 (*__i).second = std::forward<_Obj>(__obj);
927 template <
typename _Obj>
929 insert_or_assign(key_type&& __k, _Obj&& __obj)
935 std::forward_as_tuple(std::move(__k)),
936 std::forward_as_tuple(
937 std::forward<_Obj>(__obj)));
940 (*__i).second = std::forward<_Obj>(__obj);
964 template <
typename _Obj>
966 insert_or_assign(const_iterator __hint,
967 const key_type& __k, _Obj&& __obj)
970 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
971 if (__true_hint.second)
975 std::forward_as_tuple(__k),
976 std::forward_as_tuple(
977 std::forward<_Obj>(__obj)));
979 __i = iterator(__true_hint.first);
980 (*__i).second = std::forward<_Obj>(__obj);
985 template <
typename _Obj>
987 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
990 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
991 if (__true_hint.second)
995 std::forward_as_tuple(std::move(__k)),
996 std::forward_as_tuple(
997 std::forward<_Obj>(__obj)));
999 __i = iterator(__true_hint.first);
1000 (*__i).second = std::forward<_Obj>(__obj);
1005 #if __cplusplus >= 201103L
1025 {
return _M_t.erase(__position); }
1028 _GLIBCXX_ABI_TAG_CXX11
1031 {
return _M_t.erase(__position); }
1046 { _M_t.erase(__position); }
1062 {
return _M_t.erase(__x); }
1064 #if __cplusplus >= 201103L
1081 erase(const_iterator __first, const_iterator __last)
1082 {
return _M_t.erase(__first, __last); }
1098 { _M_t.erase(__first, __last); }
1116 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
1117 { _M_t.swap(__x._M_t); }
1136 {
return _M_t.key_comp(); }
1144 {
return value_compare(_M_t.key_comp()); }
1163 {
return _M_t.find(__x); }
1165 #if __cplusplus > 201103L
1166 template<
typename _Kt>
1168 find(
const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
1169 {
return _M_t._M_find_tr(__x); }
1188 {
return _M_t.find(__x); }
1190 #if __cplusplus > 201103L
1191 template<
typename _Kt>
1193 find(
const _Kt& __x)
const -> decltype(_M_t._M_find_tr(__x))
1194 {
return _M_t._M_find_tr(__x); }
1209 {
return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
1211 #if __cplusplus > 201103L
1212 template<
typename _Kt>
1214 count(
const _Kt& __x)
const -> decltype(_M_t._M_count_tr(__x))
1215 {
return _M_t._M_count_tr(__x); }
1233 {
return _M_t.lower_bound(__x); }
1235 #if __cplusplus > 201103L
1236 template<
typename _Kt>
1239 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
1240 {
return iterator(_M_t._M_lower_bound_tr(__x)); }
1258 {
return _M_t.lower_bound(__x); }
1260 #if __cplusplus > 201103L
1261 template<
typename _Kt>
1264 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
1265 {
return const_iterator(_M_t._M_lower_bound_tr(__x)); }
1278 {
return _M_t.upper_bound(__x); }
1280 #if __cplusplus > 201103L
1281 template<
typename _Kt>
1284 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
1285 {
return iterator(_M_t._M_upper_bound_tr(__x)); }
1298 {
return _M_t.upper_bound(__x); }
1300 #if __cplusplus > 201103L
1301 template<
typename _Kt>
1304 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
1305 {
return const_iterator(_M_t._M_upper_bound_tr(__x)); }
1327 {
return _M_t.equal_range(__x); }
1329 #if __cplusplus > 201103L
1330 template<
typename _Kt>
1356 {
return _M_t.equal_range(__x); }
1358 #if __cplusplus > 201103L
1359 template<
typename _Kt>
1363 _M_t._M_equal_range_tr(__x)))
1366 _M_t._M_equal_range_tr(__x));
1371 template<
typename _K1,
typename _T1,
typename _C1,
typename _A1>
1376 template<
typename _K1,
typename _T1,
typename _C1,
typename _A1>
1392 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1396 {
return __x._M_t == __y._M_t; }
1409 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1413 {
return __x._M_t < __y._M_t; }
1416 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1420 {
return !(__x == __y); }
1423 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1427 {
return __y < __x; }
1430 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1434 {
return !(__y < __x); }
1437 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1441 {
return !(__x < __y); }
1444 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1448 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1451 _GLIBCXX_END_NAMESPACE_CONTAINER
1453 #if __cplusplus > 201402L
1454 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1456 template<
typename _Key,
typename _Val,
typename _Cmp1,
typename _Alloc,
1459 _Rb_tree_merge_helper<_GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>,
1463 friend class _GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>;
1466 _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)
1467 {
return __map._M_t; }
1470 _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)
1471 {
return __map._M_t; }
1473 _GLIBCXX_END_NAMESPACE_VERSION