A standard container made up of (key,value) pairs, which can be retrieved based on a key, in logarithmic time.
- Template Parameters
-
| _Key | Type of key objects. |
| _Tp | Type of mapped objects. |
| _Compare | Comparison function object type, defaults to less<_Key>. |
| _Alloc | Allocator type, defaults to allocator<pair<const _Key, _Tp>. |
Meets the requirements of a container, a reversible container, and an associative container (using unique keys). For a map<Key,T> the key_type is Key, the mapped_type is T, and the value_type is std::pair<const Key,T>.
Maps support bidirectional iterators.
The private tree data is declared exactly the same way for map and multimap; the distinction is made entirely in how the tree functions are called (*_unique versus *_equal, same as the standard).
This turns a red-black tree into a [multi]map.
The actual tree structure.
Default constructor creates no elements.
Creates a map with no elements.
- Parameters
-
| __comp | A comparison object. |
| __a | An allocator object. |
Map copy constructor.
- Parameters
-
| __x | A map of identical element and allocator types. |
The newly-created map uses a copy of the allocation object used by __x.
Builds a map from a range.
- Parameters
-
| __first | An input iterator. |
| __last | An input iterator. |
Create a map consisting of copies of the elements from [__first,__last). This is linear in N if the range is already sorted, and NlogN otherwise (where N is distance(__first,__last)).
Builds a map from a range.
- Parameters
-
| __first | An input iterator. |
| __last | An input iterator. |
| __comp | A comparison functor. |
| __a | An allocator object. |
Create a map consisting of copies of the elements from [__first,__last). This is linear in N if the range is already sorted, and NlogN otherwise (where N is distance(__first,__last)).
The dtor only erases the elements, and note that if the elements themselves are pointers, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.
Map assignment operator.
- Parameters
-
| __x | A map of identical element and allocator types. |
All the elements of __x are copied, but unlike the copy constructor, the allocator object is not copied.
Get a copy of the memory allocation object.
Returns a read/write iterator that points to the first pair in the map. Iteration is done in ascending order according to the keys.
Returns a read-only (constant) iterator that points to the first pair in the map. Iteration is done in ascending order according to the keys.
Returns a read/write iterator that points one past the last pair in the map. Iteration is done in ascending order according to the keys.
Returns a read-only (constant) iterator that points one past the last pair in the map. Iteration is done in ascending order according to the keys.
Returns a read/write reverse iterator that points to the last pair in the map. Iteration is done in descending order according to the keys.
Returns a read-only (constant) reverse iterator that points to the last pair in the map. Iteration is done in descending order according to the keys.
Returns a read/write reverse iterator that points to one before the first pair in the map. Iteration is done in descending order according to the keys.
Returns a read-only (constant) reverse iterator that points to one before the first pair in the map. Iteration is done in descending order according to the keys.
Returns true if the map is empty. (Thus begin() would equal end().)
Returns the size of the map.
Returns the maximum size of the map.
Subscript (
- Parameters
-
| __k | The key for which data should be retrieved. |
- Returns
- A reference to the data of the (key,data) pair.
Allows for easy lookup with the subscript (
Lookup requires logarithmic time.
Access to map data.
- Parameters
-
| __k | The key for which data should be retrieved. |
- Returns
- A reference to the data whose key is equivalent to __k, if such a data is present in the map.
- Exceptions
-
| std::out_of_range | If no such data is present. |
Attempts to insert a std::pair into the map.
- Parameters
-
| __x | Pair to be inserted (see std::make_pair for easy creation of pairs). |
- Returns
- A pair, of which the first element is an iterator that points to the possibly inserted pair, and the second is a bool that is true if the pair was actually inserted.
This function attempts to insert a (key, value) pair into the map. A map relies on unique keys and thus a pair is only inserted if its first element (the key) is not already present in the map.
Insertion requires logarithmic time.
Attempts to insert a std::pair into the map.
- Parameters
-
| __position | An iterator that serves as a hint as to where the pair should be inserted. |
| __x | Pair to be inserted (see std::make_pair for easy creation of pairs). |
- Returns
- An iterator that points to the element with key of __x (may or may not be the pair passed in).
This function is not concerned about whether the insertion took place, and thus does not return a boolean like the single-argument insert() does. Note that the first parameter is only a hint and can potentially improve the performance of the insertion process. A bad hint would cause no gains in efficiency.
See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html for more on hinting.
Insertion requires logarithmic time (if the hint is not taken).
Template function that attempts to insert a range of elements.
- Parameters
-
| __first | Iterator pointing to the start of the range to be inserted. |
| __last | Iterator pointing to the end of the range. |
Complexity similar to that of the range constructor.
Erases an element from a map.
- Parameters
-
| __position | An iterator pointing to the element to be erased. |
This function erases an element, pointed to by the given iterator, from a map. Note that this function only erases the element, and that if the element is itself a pointer, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.
Erases elements according to the provided key.
- Parameters
-
| __x | Key of element to be erased. |
- Returns
- The number of elements erased.
This function erases all the elements located by the given key from a map. Note that this function only erases the element, and that if the element is itself a pointer, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.
Erases a [__first,__last) range of elements from a map.
- Parameters
-
| __first | Iterator pointing to the start of the range to be erased. |
| __last | Iterator pointing to the end of the range to be erased. |
This function erases a sequence of elements from a map. Note that this function only erases the element, and that if the element is itself a pointer, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.
Swaps data with another map.
- Parameters
-
| __x | A map of the same element and allocator types. |
This exchanges the elements between two maps in constant time. (It is only swapping a pointer, an integer, and an instance of the Compare type (which itself is often stateless and empty), so it should be quite fast.) Note that the global std::swap() function is specialized such that std::swap(m1,m2) will feed to this function.
Erases all elements in a map. Note that this function only erases the elements, and that if the elements themselves are pointers, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.
Returns the key comparison object out of which the map was constructed.
Returns a value comparison object, built from the key comparison object out of which the map was constructed.
Tries to locate an element in a map.
- Parameters
-
| __x | Key of (key, value) pair to be located. |
- Returns
- Iterator pointing to sought-after element, or end() if not found.
This function takes a key and tries to locate the element with which the key matches. If successful the function returns an iterator pointing to the sought after pair. If unsuccessful it returns the past-the-end ( end() ) iterator.
Tries to locate an element in a map.
- Parameters
-
| __x | Key of (key, value) pair to be located. |
- Returns
- Read-only (constant) iterator pointing to sought-after element, or end() if not found.
This function takes a key and tries to locate the element with which the key matches. If successful the function returns a constant iterator pointing to the sought after pair. If unsuccessful it returns the past-the-end ( end() ) iterator.
Finds the number of elements with given key.
- Parameters
-
| __x | Key of (key, value) pairs to be located. |
- Returns
- Number of elements with specified key.
This function only makes sense for multimaps; for map the result will either be 0 (not present) or 1 (present).
Finds the beginning of a subsequence matching given key.
- Parameters
-
| __x | Key of (key, value) pair to be located. |
- Returns
- Iterator pointing to first element equal to or greater than key, or end().
This function returns the first element of a subsequence of elements that matches the given key. If unsuccessful it returns an iterator pointing to the first element that has a greater value than given key or end() if no such element exists.
Finds the beginning of a subsequence matching given key.
- Parameters
-
| __x | Key of (key, value) pair to be located. |
- Returns
- Read-only (constant) iterator pointing to first element equal to or greater than key, or end().
This function returns the first element of a subsequence of elements that matches the given key. If unsuccessful it returns an iterator pointing to the first element that has a greater value than given key or end() if no such element exists.
Finds the end of a subsequence matching given key.
- Parameters
-
| __x | Key of (key, value) pair to be located. |
- Returns
- Iterator pointing to the first element greater than key, or end().
Finds the end of a subsequence matching given key.
- Parameters
-
| __x | Key of (key, value) pair to be located. |
- Returns
- Read-only (constant) iterator pointing to first iterator greater than key, or end().
Finds a subsequence matching given key.
- Parameters
-
| __x | Key of (key, value) pairs to be located. |
- Returns
- Pair of iterators that possibly points to the subsequence matching given key.
This function is equivalent to
std::make_pair(c.lower_bound(val),
c.upper_bound(val))
(but is faster than making the calls separately).
This function probably only makes sense for multimaps.
Finds a subsequence matching given key.
- Parameters
-
| __x | Key of (key, value) pairs to be located. |
- Returns
- Pair of read-only (constant) iterators that possibly points to the subsequence matching given key.
This function is equivalent to
std::make_pair(c.lower_bound(val),
c.upper_bound(val))
(but is faster than making the calls separately).
This function probably only makes sense for multimaps.
Map equality comparison.
- Parameters
-
| __x | A map. |
| __y | A map of the same type as x. |
- Returns
- True iff the size and elements of the maps are equal.
This is an equivalence relation. It is linear in the size of the maps. Maps are considered equivalent if their sizes are equal, and if corresponding elements compare equal.
Map ordering relation.
- Parameters
-
| __x | A map. |
| __y | A map of the same type as x. |
- Returns
- True iff x is lexicographically less than y.
This is a total ordering relation. It is linear in the size of the maps. The elements must be comparable with <.
See std::lexicographical_compare() for how the determination is made.
Based on operator==
Based on operator<
Based on operator<
Based on operator<
See std::map::swap().
68 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
94 template <
typename _Key,
typename _Tp,
typename _Compare = std::less<_Key>,
95 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
99 typedef _Key key_type;
100 typedef _Tp mapped_type;
101 typedef std::pair<const _Key, _Tp> value_type;
102 typedef _Compare key_compare;
103 typedef _Alloc allocator_type;
107 typedef typename _Alloc::value_type _Alloc_value_type;
110 _BinaryFunctionConcept)
115 : public std::binary_function<value_type, value_type,
bool>
117 friend class map<_Key, _Tp, _Compare, _Alloc>;
121 value_compare(_Compare __c)
125 bool operator()(
const value_type& __x,
const value_type& __y)
const
126 {
return comp(__x.first, __y.first); }
131 typedef typename _Alloc::template rebind<value_type>::other
134 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
135 key_compare, _Pair_alloc_type> _Rep_type;
143 typedef typename _Pair_alloc_type::pointer pointer;
144 typedef typename _Pair_alloc_type::const_pointer const_pointer;
145 typedef typename _Pair_alloc_type::reference reference;
146 typedef typename _Pair_alloc_type::const_reference const_reference;
147 typedef typename _Rep_type::iterator iterator;
148 typedef typename _Rep_type::const_iterator const_iterator;
149 typedef typename _Rep_type::size_type size_type;
150 typedef typename _Rep_type::difference_type difference_type;
151 typedef typename _Rep_type::reverse_iterator reverse_iterator;
152 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
169 map(
const _Compare& __comp,
170 const allocator_type& __a = allocator_type())
171 : _M_t(__comp, _Pair_alloc_type(__a)) { }
183 #if __cplusplus >= 201103L
192 noexcept(is_nothrow_copy_constructible<_Compare>::value)
193 : _M_t(std::move(__x._M_t)) { }
206 map(initializer_list<value_type> __l,
207 const _Compare& __comp = _Compare(),
208 const allocator_type& __a = allocator_type())
209 : _M_t(__comp, _Pair_alloc_type(__a))
210 { _M_t._M_insert_unique(__l.begin(), __l.end()); }
223 template<
typename _InputIterator>
224 map(_InputIterator __first, _InputIterator __last)
226 { _M_t._M_insert_unique(__first, __last); }
240 template<
typename _InputIterator>
241 map(_InputIterator __first, _InputIterator __last,
242 const _Compare& __comp,
243 const allocator_type& __a = allocator_type())
244 : _M_t(__comp, _Pair_alloc_type(__a))
245 { _M_t._M_insert_unique(__first, __last); }
264 operator=(
const map& __x)
270 #if __cplusplus >= 201103L
300 operator=(initializer_list<value_type> __l)
303 this->insert(__l.begin(), __l.end());
310 get_allocator() const _GLIBCXX_NOEXCEPT
311 {
return allocator_type(_M_t.get_allocator()); }
320 begin() _GLIBCXX_NOEXCEPT
321 {
return _M_t.begin(); }
329 begin() const _GLIBCXX_NOEXCEPT
330 {
return _M_t.begin(); }
338 end() _GLIBCXX_NOEXCEPT
339 {
return _M_t.end(); }
347 end() const _GLIBCXX_NOEXCEPT
348 {
return _M_t.end(); }
356 rbegin() _GLIBCXX_NOEXCEPT
357 {
return _M_t.rbegin(); }
364 const_reverse_iterator
365 rbegin() const _GLIBCXX_NOEXCEPT
366 {
return _M_t.rbegin(); }
374 rend() _GLIBCXX_NOEXCEPT
375 {
return _M_t.rend(); }
382 const_reverse_iterator
383 rend() const _GLIBCXX_NOEXCEPT
384 {
return _M_t.rend(); }
386 #if __cplusplus >= 201103L
393 cbegin() const noexcept
394 {
return _M_t.begin(); }
402 cend() const noexcept
403 {
return _M_t.end(); }
410 const_reverse_iterator
411 crbegin() const noexcept
412 {
return _M_t.rbegin(); }
419 const_reverse_iterator
420 crend() const noexcept
421 {
return _M_t.rend(); }
429 empty() const _GLIBCXX_NOEXCEPT
430 {
return _M_t.empty(); }
434 size() const _GLIBCXX_NOEXCEPT
435 {
return _M_t.size(); }
439 max_size() const _GLIBCXX_NOEXCEPT
440 {
return _M_t.max_size(); }
456 operator[](
const key_type& __k)
461 iterator __i = lower_bound(__k);
463 if (__i == end() || key_comp()(__k, (*__i).first))
464 #if __cplusplus >= 201103L
465 __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
466 std::tuple<const key_type&>(__k),
469 __i = insert(__i, value_type(__k, mapped_type()));
471 return (*__i).second;
474 #if __cplusplus >= 201103L
476 operator[](key_type&& __k)
481 iterator __i = lower_bound(__k);
483 if (__i == end() || key_comp()(__k, (*__i).first))
484 __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
485 std::forward_as_tuple(std::move(__k)),
501 at(
const key_type& __k)
503 iterator __i = lower_bound(__k);
504 if (__i == end() || key_comp()(__k, (*__i).first))
505 __throw_out_of_range(__N(
"map::at"));
506 return (*__i).second;
510 at(
const key_type& __k)
const
512 const_iterator __i = lower_bound(__k);
513 if (__i == end() || key_comp()(__k, (*__i).first))
514 __throw_out_of_range(__N(
"map::at"));
515 return (*__i).second;
519 #if __cplusplus >= 201103L
538 template<
typename... _Args>
539 std::pair<iterator, bool>
540 emplace(_Args&&... __args)
541 {
return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
568 template<
typename... _Args>
570 emplace_hint(const_iterator __pos, _Args&&... __args)
572 return _M_t._M_emplace_hint_unique(__pos,
573 std::forward<_Args>(__args)...);
593 std::pair<iterator, bool>
594 insert(
const value_type& __x)
595 {
return _M_t._M_insert_unique(__x); }
597 #if __cplusplus >= 201103L
598 template<
typename _Pair,
typename =
typename
599 std::enable_if<std::is_constructible<value_type,
600 _Pair&&>::value>::type>
601 std::pair<iterator, bool>
603 {
return _M_t._M_insert_unique(std::forward<_Pair>(__x)); }
606 #if __cplusplus >= 201103L
615 insert(std::initializer_list<value_type> __list)
616 { insert(__list.begin(), __list.end()); }
643 #if __cplusplus >= 201103L
644 insert(const_iterator __position,
const value_type& __x)
646 insert(iterator __position,
const value_type& __x)
648 {
return _M_t._M_insert_unique_(__position, __x); }
650 #if __cplusplus >= 201103L
651 template<
typename _Pair,
typename =
typename
652 std::enable_if<std::is_constructible<value_type,
653 _Pair&&>::value>::type>
655 insert(const_iterator __position, _Pair&& __x)
656 {
return _M_t._M_insert_unique_(__position,
657 std::forward<_Pair>(__x)); }
668 template<
typename _InputIterator>
670 insert(_InputIterator __first, _InputIterator __last)
671 { _M_t._M_insert_unique(__first, __last); }
673 #if __cplusplus >= 201103L
690 erase(const_iterator __position)
691 {
return _M_t.erase(__position); }
694 _GLIBCXX_ABI_TAG_CXX11
696 erase(iterator __position)
697 {
return _M_t.erase(__position); }
710 erase(iterator __position)
711 { _M_t.erase(__position); }
726 erase(
const key_type& __x)
727 {
return _M_t.erase(__x); }
729 #if __cplusplus >= 201103L
746 erase(const_iterator __first, const_iterator __last)
747 {
return _M_t.erase(__first, __last); }
762 erase(iterator __first, iterator __last)
763 { _M_t.erase(__first, __last); }
779 { _M_t.swap(__x._M_t); }
788 clear() _GLIBCXX_NOEXCEPT
798 {
return _M_t.key_comp(); }
806 {
return value_compare(_M_t.key_comp()); }
821 find(
const key_type& __x)
822 {
return _M_t.find(__x); }
836 find(
const key_type& __x)
const
837 {
return _M_t.find(__x); }
848 count(
const key_type& __x)
const
849 {
return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
863 lower_bound(
const key_type& __x)
864 {
return _M_t.lower_bound(__x); }
878 lower_bound(
const key_type& __x)
const
879 {
return _M_t.lower_bound(__x); }
888 upper_bound(
const key_type& __x)
889 {
return _M_t.upper_bound(__x); }
898 upper_bound(
const key_type& __x)
const
899 {
return _M_t.upper_bound(__x); }
916 std::pair<iterator, iterator>
917 equal_range(
const key_type& __x)
918 {
return _M_t.equal_range(__x); }
935 std::pair<const_iterator, const_iterator>
936 equal_range(
const key_type& __x)
const
937 {
return _M_t.equal_range(__x); }
939 template<
typename _K1,
typename _T1,
typename _C1,
typename _A1>
942 const map<_K1, _T1, _C1, _A1>&);
944 template<
typename _K1,
typename _T1,
typename _C1,
typename _A1>
946 operator<(const map<_K1, _T1, _C1, _A1>&,
947 const map<_K1, _T1, _C1, _A1>&);
960 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
962 operator==(
const map<_Key, _Tp, _Compare, _Alloc>& __x,
963 const map<_Key, _Tp, _Compare, _Alloc>& __y)
964 {
return __x._M_t == __y._M_t; }
977 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
979 operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
980 const map<_Key, _Tp, _Compare, _Alloc>& __y)
981 {
return __x._M_t < __y._M_t; }
984 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
986 operator!=(
const map<_Key, _Tp, _Compare, _Alloc>& __x,
987 const map<_Key, _Tp, _Compare, _Alloc>& __y)
988 {
return !(__x == __y); }
991 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
993 operator>(
const map<_Key, _Tp, _Compare, _Alloc>& __x,
994 const map<_Key, _Tp, _Compare, _Alloc>& __y)
995 {
return __y < __x; }
998 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1000 operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1001 const map<_Key, _Tp, _Compare, _Alloc>& __y)
1002 {
return !(__y < __x); }
1005 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1007 operator>=(
const map<_Key, _Tp, _Compare, _Alloc>& __x,
1008 const map<_Key, _Tp, _Compare, _Alloc>& __y)
1009 {
return !(__x < __y); }
1012 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
1014 swap(map<_Key, _Tp, _Compare, _Alloc>& __x,
1015 map<_Key, _Tp, _Compare, _Alloc>& __y)
1018 _GLIBCXX_END_NAMESPACE_CONTAINER
#define __glibcxx_function_requires(...)
Definition: concept_check.h:47
bool operator>=(const _Safe_iterator< _IteratorL, _Sequence > &__lhs, const _Safe_iterator< _IteratorR, _Sequence > &__rhs)
Definition: safe_iterator.h:644
bool operator==(const exception_ptr &, const exception_ptr &) _GLIBCXX_USE_NOEXCEPT __attribute__((__pure__))
#define __glibcxx_class_requires(_a, _b)
Definition: concept_check.h:48
return(unsigned int) __res
bool operator>(const _Safe_iterator< _IteratorL, _Sequence > &__lhs, const _Safe_iterator< _IteratorR, _Sequence > &__rhs)
Definition: safe_iterator.h:612
#define __glibcxx_class_requires2(_a, _b, _c)
Definition: concept_check.h:49
bool operator!=(const exception_ptr &, const exception_ptr &) _GLIBCXX_USE_NOEXCEPT __attribute__((__pure__))
void swap(exception_ptr &__lhs, exception_ptr &__rhs)
Definition: exception_ptr.h:160
#define __glibcxx_class_requires4(_a, _b, _c, _d, _e)
Definition: concept_check.h:51
1.8.6