61#if __cplusplus >= 201103L
66namespace std _GLIBCXX_VISIBILITY(default)
68_GLIBCXX_BEGIN_NAMESPACE_VERSION
69_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
71 template <
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
98 template <
typename _Key,
typename _Tp,
typename _Compare = std::less<_Key>,
99 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
103 typedef _Key key_type;
104 typedef _Tp mapped_type;
106 typedef _Compare key_compare;
107 typedef _Alloc allocator_type;
110#ifdef _GLIBCXX_CONCEPT_CHECKS
112 typedef typename _Alloc::value_type _Alloc_value_type;
113# if __cplusplus < 201103L
114 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
116 __glibcxx_class_requires4(_Compare,
bool, _Key, _Key,
117 _BinaryFunctionConcept)
118 __glibcxx_class_requires2(
value_type, _Alloc_value_type, _SameTypeConcept)
121#if __cplusplus >= 201103L && defined(__STRICT_ANSI__)
123 "std::map must have the same value_type as its allocator");
130 friend class map<_Key, _Tp, _Compare, _Alloc>;
134 value_compare(_Compare __c)
145 rebind<value_type>::other _Pair_alloc_type;
147 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
148 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;
169#if __cplusplus > 201402L
170 using node_type =
typename _Rep_type::node_type;
171 using insert_return_type =
typename _Rep_type::insert_return_type;
180#if __cplusplus < 201103L
192 map(
const _Compare& __comp,
193 const allocator_type& __a = allocator_type())
194 : _M_t(__comp, _Pair_alloc_type(__a)) { }
201#if __cplusplus < 201103L
227 const _Compare& __comp = _Compare(),
228 const allocator_type& __a = allocator_type())
229 : _M_t(__comp, _Pair_alloc_type(__a))
230 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); }
234 map(
const allocator_type& __a)
235 : _M_t(_Pair_alloc_type(__a)) { }
238 map(
const map& __m,
const allocator_type& __a)
239 : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
242 map(
map&& __m,
const allocator_type& __a)
244 && _Alloc_traits::_S_always_equal())
245 : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
249 : _M_t(_Pair_alloc_type(__a))
250 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); }
253 template<
typename _InputIterator>
254 map(_InputIterator __first, _InputIterator __last,
255 const allocator_type& __a)
256 : _M_t(_Pair_alloc_type(__a))
257 { _M_t._M_insert_range_unique(__first, __last); }
270 template<
typename _InputIterator>
271 map(_InputIterator __first, _InputIterator __last)
273 { _M_t._M_insert_range_unique(__first, __last); }
287 template<
typename _InputIterator>
288 map(_InputIterator __first, _InputIterator __last,
289 const _Compare& __comp,
290 const allocator_type& __a = allocator_type())
291 : _M_t(__comp, _Pair_alloc_type(__a))
292 { _M_t._M_insert_range_unique(__first, __last); }
294#if __cplusplus >= 201103L
308#if __cplusplus < 201103L
337 _M_t._M_assign_unique(__l.begin(), __l.end());
345 {
return allocator_type(_M_t.get_allocator()); }
355 {
return _M_t.begin(); }
364 {
return _M_t.begin(); }
373 {
return _M_t.end(); }
381 end() const _GLIBCXX_NOEXCEPT
382 {
return _M_t.end(); }
391 {
return _M_t.rbegin(); }
398 const_reverse_iterator
400 {
return _M_t.rbegin(); }
409 {
return _M_t.rend(); }
416 const_reverse_iterator
418 {
return _M_t.rend(); }
420#if __cplusplus >= 201103L
428 {
return _M_t.begin(); }
437 {
return _M_t.end(); }
444 const_reverse_iterator
446 {
return _M_t.rbegin(); }
453 const_reverse_iterator
455 {
return _M_t.rend(); }
462 _GLIBCXX_NODISCARD
bool
464 {
return _M_t.empty(); }
469 {
return _M_t.size(); }
474 {
return _M_t.max_size(); }
493 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
498#if __cplusplus >= 201103L
505 return (*__i).second;
508#if __cplusplus >= 201103L
513 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
521 return (*__i).second;
535 at(
const key_type& __k)
539 __throw_out_of_range(__N(
"map::at"));
540 return (*__i).second;
544 at(
const key_type& __k)
const
548 __throw_out_of_range(__N(
"map::at"));
549 return (*__i).second;
553#if __cplusplus >= 201103L
572 template<
typename... _Args>
575 {
return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
602 template<
typename... _Args>
606 return _M_t._M_emplace_hint_unique(__pos,
607 std::forward<_Args>(__args)...);
611#if __cplusplus > 201402L
614 extract(const_iterator __pos)
616 __glibcxx_assert(__pos !=
end());
617 return _M_t.extract(__pos);
622 extract(
const key_type& __x)
623 {
return _M_t.extract(__x); }
628 {
return _M_t._M_reinsert_node_unique(std::move(__nh)); }
632 insert(const_iterator __hint, node_type&& __nh)
633 {
return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); }
635 template<
typename,
typename>
636 friend class std::_Rb_tree_merge_helper;
638 template<
typename _C2>
640 merge(map<_Key, _Tp, _C2, _Alloc>& __source)
642 using _Merge_helper = _Rb_tree_merge_helper<map, _C2>;
643 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
646 template<
typename _C2>
648 merge(map<_Key, _Tp, _C2, _Alloc>&& __source)
651 template<
typename _C2>
653 merge(multimap<_Key, _Tp, _C2, _Alloc>& __source)
655 using _Merge_helper = _Rb_tree_merge_helper<map, _C2>;
656 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
659 template<
typename _C2>
661 merge(multimap<_Key, _Tp, _C2, _Alloc>&& __source)
665#if __cplusplus > 201402L
666#define __cpp_lib_map_try_emplace 201411
687 template <
typename... _Args>
689 try_emplace(
const key_type& __k, _Args&&... __args)
697 std::forward<_Args>(__args)...));
704 template <
typename... _Args>
706 try_emplace(key_type&& __k, _Args&&... __args)
714 std::forward<_Args>(__args)...));
747 template <
typename... _Args>
749 try_emplace(const_iterator __hint,
const key_type& __k,
753 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
754 if (__true_hint.second)
759 std::forward<_Args>(__args)...));
761 __i = iterator(__true_hint.first);
766 template <
typename... _Args>
768 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
771 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
772 if (__true_hint.second)
777 std::forward<_Args>(__args)...));
779 __i = iterator(__true_hint.first);
802 {
return _M_t._M_insert_unique(__x); }
804#if __cplusplus >= 201103L
809 {
return _M_t._M_insert_unique(std::move(__x)); }
811 template<
typename _Pair>
812 __enable_if_t<is_constructible<value_type, _Pair>::value,
815 {
return _M_t._M_emplace_unique(std::forward<_Pair>(__x)); }
819#if __cplusplus >= 201103L
829 {
insert(__list.begin(), __list.end()); }
857#if __cplusplus >= 201103L
862 {
return _M_t._M_insert_unique_(__position, __x); }
864#if __cplusplus >= 201103L
869 {
return _M_t._M_insert_unique_(__position, std::move(__x)); }
871 template<
typename _Pair>
872 __enable_if_t<is_constructible<value_type, _Pair>::value,
iterator>
873 insert(const_iterator __position, _Pair&& __x)
875 return _M_t._M_emplace_hint_unique(__position,
876 std::forward<_Pair>(__x));
889 template<
typename _InputIterator>
891 insert(_InputIterator __first, _InputIterator __last)
892 { _M_t._M_insert_range_unique(__first, __last); }
894#if __cplusplus > 201402L
895#define __cpp_lib_map_insertion 201411
915 template <
typename _Obj>
917 insert_or_assign(
const key_type& __k, _Obj&& __obj)
925 std::forward<_Obj>(__obj)));
928 (*__i).second = std::forward<_Obj>(__obj);
933 template <
typename _Obj>
935 insert_or_assign(key_type&& __k, _Obj&& __obj)
943 std::forward<_Obj>(__obj)));
946 (*__i).second = std::forward<_Obj>(__obj);
970 template <
typename _Obj>
972 insert_or_assign(const_iterator __hint,
973 const key_type& __k, _Obj&& __obj)
976 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
977 if (__true_hint.second)
983 std::forward<_Obj>(__obj)));
985 __i = iterator(__true_hint.first);
986 (*__i).second = std::forward<_Obj>(__obj);
991 template <
typename _Obj>
993 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
996 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
997 if (__true_hint.second)
1003 std::forward<_Obj>(__obj)));
1005 __i = iterator(__true_hint.first);
1006 (*__i).second = std::forward<_Obj>(__obj);
1011#if __cplusplus >= 201103L
1031 {
return _M_t.erase(__position); }
1034 _GLIBCXX_ABI_TAG_CXX11
1037 {
return _M_t.erase(__position); }
1052 { _M_t.erase(__position); }
1068 {
return _M_t.erase(__x); }
1070#if __cplusplus >= 201103L
1087 erase(const_iterator __first, const_iterator __last)
1088 {
return _M_t.erase(__first, __last); }
1104 { _M_t.erase(__first, __last); }
1122 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
1123 { _M_t.swap(__x._M_t); }
1142 {
return _M_t.key_comp(); }
1150 {
return value_compare(_M_t.key_comp()); }
1169 {
return _M_t.find(__x); }
1171#if __cplusplus > 201103L
1172 template<
typename _Kt>
1174 find(
const _Kt& __x) ->
decltype(_M_t._M_find_tr(__x))
1175 {
return _M_t._M_find_tr(__x); }
1194 {
return _M_t.find(__x); }
1196#if __cplusplus > 201103L
1197 template<
typename _Kt>
1199 find(
const _Kt& __x)
const ->
decltype(_M_t._M_find_tr(__x))
1200 {
return _M_t._M_find_tr(__x); }
1215 {
return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
1217#if __cplusplus > 201103L
1218 template<
typename _Kt>
1220 count(
const _Kt& __x)
const ->
decltype(_M_t._M_count_tr(__x))
1221 {
return _M_t._M_count_tr(__x); }
1225#if __cplusplus > 201703L
1233 contains(
const key_type& __x)
const
1234 {
return _M_t.find(__x) != _M_t.end(); }
1236 template<
typename _Kt>
1238 contains(
const _Kt& __x)
const
1239 ->
decltype(_M_t._M_find_tr(__x), void(),
true)
1240 {
return _M_t._M_find_tr(__x) != _M_t.end(); }
1258 {
return _M_t.lower_bound(__x); }
1260#if __cplusplus > 201103L
1261 template<
typename _Kt>
1264 ->
decltype(iterator(_M_t._M_lower_bound_tr(__x)))
1265 {
return iterator(_M_t._M_lower_bound_tr(__x)); }
1283 {
return _M_t.lower_bound(__x); }
1285#if __cplusplus > 201103L
1286 template<
typename _Kt>
1289 ->
decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
1290 {
return const_iterator(_M_t._M_lower_bound_tr(__x)); }
1303 {
return _M_t.upper_bound(__x); }
1305#if __cplusplus > 201103L
1306 template<
typename _Kt>
1309 ->
decltype(iterator(_M_t._M_upper_bound_tr(__x)))
1310 {
return iterator(_M_t._M_upper_bound_tr(__x)); }
1323 {
return _M_t.upper_bound(__x); }
1325#if __cplusplus > 201103L
1326 template<
typename _Kt>
1329 ->
decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
1330 {
return const_iterator(_M_t._M_upper_bound_tr(__x)); }
1352 {
return _M_t.equal_range(__x); }
1354#if __cplusplus > 201103L
1355 template<
typename _Kt>
1381 {
return _M_t.equal_range(__x); }
1383#if __cplusplus > 201103L
1384 template<
typename _Kt>
1388 _M_t._M_equal_range_tr(__x)))
1391 _M_t._M_equal_range_tr(__x));
1396 template<
typename _K1,
typename _T1,
typename _C1,
typename _A1>
1401 template<
typename _K1,
typename _T1,
typename _C1,
typename _A1>
1408#if __cpp_deduction_guides >= 201606
1410 template<
typename _InputIterator,
1411 typename _Compare = less<__iter_key_t<_InputIterator>>,
1412 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1413 typename = _RequireInputIter<_InputIterator>,
1414 typename = _RequireNotAllocator<_Compare>,
1415 typename = _RequireAllocator<_Allocator>>
1416 map(_InputIterator, _InputIterator,
1417 _Compare = _Compare(), _Allocator = _Allocator())
1418 -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
1419 _Compare, _Allocator>;
1421 template<
typename _Key,
typename _Tp,
typename _Compare = less<_Key>,
1422 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1423 typename = _RequireNotAllocator<_Compare>,
1424 typename = _RequireAllocator<_Allocator>>
1425 map(initializer_list<pair<_Key, _Tp>>,
1426 _Compare = _Compare(), _Allocator = _Allocator())
1427 -> map<_Key, _Tp, _Compare, _Allocator>;
1429 template <
typename _InputIterator,
typename _Allocator,
1430 typename = _RequireInputIter<_InputIterator>,
1431 typename = _RequireAllocator<_Allocator>>
1432 map(_InputIterator, _InputIterator, _Allocator)
1433 -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
1434 less<__iter_key_t<_InputIterator>>, _Allocator>;
1436 template<
typename _Key,
typename _Tp,
typename _Allocator,
1437 typename = _RequireAllocator<_Allocator>>
1438 map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1439 -> map<_Key, _Tp, less<_Key>, _Allocator>;
1453 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1457 {
return __x._M_t == __y._M_t; }
1470 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1474 {
return __x._M_t < __y._M_t; }
1477 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1481 {
return !(__x == __y); }
1484 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1488 {
return __y < __x; }
1491 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1495 {
return !(__y < __x); }
1498 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1502 {
return !(__x < __y); }
1505 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1509 _GLIBCXX_NOEXCEPT_IF(
noexcept(__x.swap(__y)))
1512_GLIBCXX_END_NAMESPACE_CONTAINER
1514#if __cplusplus > 201402L
1516 template<
typename _Key,
typename _Val,
typename _Cmp1,
typename _Alloc,
1519 _Rb_tree_merge_helper<_GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>,
1523 friend class _GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>;
1526 _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)
1527 {
return __map._M_t; }
1530 _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)
1531 {
return __map._M_t; }
1535_GLIBCXX_END_NAMESPACE_VERSION
constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
std::forward_as_tuple
_GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct
piecewise_construct
ISO C++ entities toplevel namespace is std.
Primary class template, tuple.
is_nothrow_copy_constructible
A standard container made up of (key,value) pairs, which can be retrieved based on a key,...
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to build and insert a std::pair into the map.
const_iterator find(const key_type &__x) const
Tries to locate an element in a map.
map(_InputIterator __first, _InputIterator __last, const allocator_type &__a)
Allocator-extended range constructor.
__enable_if_t< is_constructible< value_type, _Pair >::value, iterator > insert(const_iterator __position, _Pair &&__x)
Attempts to insert a std::pair into the map.
auto count(const _Kt &__x) const -> decltype(_M_t._M_count_tr(__x))
Finds the number of elements with given key.
auto equal_range(const _Kt &__x) const -> decltype(pair< const_iterator, const_iterator >(_M_t._M_equal_range_tr(__x)))
Finds a subsequence matching given key.
const_reverse_iterator rend() const noexcept
value_compare value_comp() const
auto lower_bound(const _Kt &__x) const -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
Finds the beginning of a subsequence matching given key.
void insert(_InputIterator __first, _InputIterator __last)
Template function that attempts to insert a range of elements.
iterator upper_bound(const key_type &__x)
Finds the end of a subsequence matching given key.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
map(initializer_list< value_type > __l, const _Compare &__comp=_Compare(), const allocator_type &__a=allocator_type())
Builds a map from an initializer_list.
auto find(const _Kt &__x) -> decltype(_M_t._M_find_tr(__x))
Tries to locate an element in a map.
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the map.
map(map &&)=default
Map move constructor.
size_type count(const key_type &__x) const
Finds the number of elements with given key.
const_reverse_iterator rbegin() const noexcept
reverse_iterator rbegin() noexcept
const_iterator end() const noexcept
const_iterator cend() const noexcept
mapped_type & at(const key_type &__k)
Access to map data.
auto upper_bound(const _Kt &__x) -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
Finds the end of a subsequence matching given key.
key_compare key_comp() const
auto lower_bound(const _Kt &__x) -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
Finds the beginning of a subsequence matching given key.
map(_InputIterator __first, _InputIterator __last)
Builds a map from a range.
_GLIBCXX_NODISCARD bool empty() const noexcept
const_reverse_iterator crbegin() const noexcept
void swap(map &__x) noexcept(/*conditional */)
Swaps data with another map.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
map(initializer_list< value_type > __l, const allocator_type &__a)
Allocator-extended initialier-list constructor.
map(const map &)=default
Map copy constructor.
map(map &&__m, const allocator_type &__a) noexcept(is_nothrow_copy_constructible< _Compare >::value &&_Alloc_traits::_S_always_equal())
Allocator-extended move constructor.
map(const allocator_type &__a)
Allocator-extended default constructor.
iterator insert(const_iterator __position, value_type &&__x)
Attempts to insert a std::pair into the map.
iterator insert(const_iterator __position, const value_type &__x)
Attempts to insert a std::pair into the map.
map(const _Compare &__comp, const allocator_type &__a=allocator_type())
Creates a map with no elements.
reverse_iterator rend() noexcept
iterator erase(const_iterator __first, const_iterator __last)
Erases a [first,last) range of elements from a map.
void insert(std::initializer_list< value_type > __list)
Attempts to insert a list of std::pairs into the map.
map & operator=(const map &)=default
Map assignment operator.
const_iterator lower_bound(const key_type &__x) const
Finds the beginning of a subsequence matching given key.
size_type size() const noexcept
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
auto upper_bound(const _Kt &__x) const -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
Finds the end of a subsequence matching given key.
iterator find(const key_type &__x)
Tries to locate an element in a map.
map(_InputIterator __first, _InputIterator __last, const _Compare &__comp, const allocator_type &__a=allocator_type())
Builds a map from a range.
__enable_if_t< is_constructible< value_type, _Pair >::value, pair< iterator, bool > > insert(_Pair &&__x)
Attempts to insert a std::pair into the map.
iterator erase(const_iterator __position)
Erases an element from a map.
auto find(const _Kt &__x) const -> decltype(_M_t._M_find_tr(__x))
Tries to locate an element in a map.
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to map data.
iterator lower_bound(const key_type &__x)
Finds the beginning of a subsequence matching given key.
const_reverse_iterator crend() const noexcept
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
map & operator=(initializer_list< value_type > __l)
Map list assignment operator.
_GLIBCXX_ABI_TAG_CXX11 iterator erase(iterator __position)
Erases an element from a map.
map(const map &__m, const allocator_type &__a)
Allocator-extended copy constructor.
auto equal_range(const _Kt &__x) -> decltype(pair< iterator, iterator >(_M_t._M_equal_range_tr(__x)))
Finds a subsequence matching given key.
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the map.
const_iterator cbegin() const noexcept
size_type max_size() const noexcept
const_iterator begin() const noexcept
iterator begin() noexcept
map & operator=(map &&)=default
Move assignment operator.
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert a std::pair into the map.
map()=default
Default constructor creates no elements.
const_iterator upper_bound(const key_type &__x) const
Finds the end of a subsequence matching given key.
Struct holding two objects of arbitrary type.
_T1 first
second_type is the second bound type
Uniform interface to C++98 and C++11 allocators.