Note, this article is not finished! You can help by editing this doc page.
Overview
- Simplified (since C++98)
- Detailed
template< class Key, class Value, /* ... */ >
class map;
- Regular (since C++98)
- Polymorphic (since C++17)
template<
class Key,
class Value,
class Compare = std::less<Key>,
class Allocator = std::allocator< std::pair<const Key, Value> >
>
class map;
namespace pmr {
template< class Key, class Value, class Compare = std::less<Key> >
using map = std::map<Key, Value, Compare,
std::pmr::polymorphic_allocator<std::pair<const Key, Value>>>
}
The std::map
is a container that stores key-value pairs with unique keys in a specified order.
Technical details
Technical definition of a map
std::map
is a sorted associative container that contains key-value pairs with unique keys.
Keys are sorted by using the comparison function Compare
. Search, removal,
and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.
Everywhere the standard library uses the Compare
requirements, uniqueness is determined by
using the equivalence relation. In imprecise terms, two objects a
and b
are considered equivalent
(not unique) if neither compares less than the other: !comp(a, b) && !comp(b, a)
.
std::map
Defined in | map |
Template parameters
pub | Key | The type of stored keys. |
pub | Value | The type of stored values. |
pub | Compare | A comparator type satisfying Compare. |
pub | Allocator | An allocator type responsible for allocating and deallocating memory. Must satisfy Allocator. |
Type names
pub | key_type | Key |
pub | mapped_type | Value |
pub | value_type | std::pair<const Key, Value> |
pub | size_type | Unsigned integer type (usually ). |
pub | difference_type | Signed integer type (usually ). |
pub | key_compare | Compare |
pub | allocator_type | Allocator |
pub | reference | value_type& |
pub | const_reference | const value_type& |
pub | pointer | Allocator::pointer (until C++11)std::allocator_traits<Allocator>::pointer (since C++11) |
pub | const_pointer | Allocator::const_pointer (until C++11)std::allocator_traits<Allocator>::const_pointer (since C++11) |
pub | iterator | LegacyBidirectionalIterator to value_type |
pub | const_iterator | LegacyBidirectionalIterator to const value_type |
pub | reverse_iterator | std::reverse_iterator<iterator> |
pub | const_reverse_iterator | std::reverse_iterator<const_iterator> |
pub | node_type (since c++17) | A specialization of node handle representing a container node. |
pub | insert_return_type (since C++17) | Type describing the result of inserting a
instantiated with template arguments |
Member classes
pub | value_compare | Compares two objects of type |
Member functions
pub | (constructors) | Constructs a new map. |
pub | (destructor) | Destructs a map. |
pub | operator= | Assigns one map to another. |
pub | get_allocator | Returns an associated allocator. |
Element access
pub | at | Accesses a specified element with bounds checking. |
pub | operator[] | Accesses or inserts a specified element. |
Iterators
pub | begin cbegin(since C++11) | Returns an iterator to the beginning. |
pub | end cend(since C++11) | Returns an iterator to the end. |
pub | rbegin crbegin(since C++11) | Returns a reverse iterator to the beginning. |
pub | rend crend(since C++11) | Returns a reverse iterator to the end. |
Capacity
pub | empty | Returns |
pub | size | Returns the number of elements in a map. |
pub | max_size | Returns the maximum possible number of elements. |
Modifiers
pub | clear | Clears the contents of a map. |
pub | insert | Inserts elements or nodes (extracted with |
pub | insert_or_assign (since C++17) | Inserts a new element or assigns to an already existing one if it already exists. |
pub | emplace (since C++11) | Constructs a new element in place. |
pub | emplace_hint (since C++11) | Constructs elements in-place using a hint (iterator). |
pub | try_emplace | Inserts a new element in-place if the key does not exist, does nothing if the key exists. |
pub | erase | Erases elements. |
pub | swap | Swaps two maps. |
pub | extract (since C++17) | Extracts nodes from a map (can be later inserted somewhere else). |
pub | merge (since C++17) | Merges two maps together. |
Lookup
pub | count | Returns the number of elements matching a specific key (for a map always |
pub | find | Searches for an element and returns an iterator to it, or end iterator if not found. |
pub | contains (since C++20) | Returns |
pub | equal_range | Returns a range of elements matching a specific key. (for a map the range will always contain one element). |
pub | lower_bound | Returns an iterator to the first element not less than the given key. |
pub | upper_bound | Returns an iterator to the first element greater than the given key. |
Observers
pub | key_comp | Returns an internal function object that compares keys. |
pub | value_comp | Returns an internal function object that compares keys in objects of type |
Non-member functions
pub | operator== operator!= (removed in C++20) operator< (removed in C++20) operator> (removed in C++20) operator<= (removed in C++20) operator>= (removed in C++20) operator<=> (since C++20) | Lexicographically compares the values in a map. |
pub | std::swap (std::map) | An overload for a std::swap algorithm. |
pub | erase_if (std::map) (since C++20) | Overload for a std::erase_if algorithm. |
Deduction guides (since C++17)
Click to expand
Deduction guides
// (1)
template< class InputIt, class Alloc >
map( InputIt, InputIt, Alloc )
-> map<iter_key_t<InputIt>, iter_val_t<InputIt>,
std::less<iter_key_t<InputIt>>, Alloc>;
// (2)
template< class InputIt,
class Comp = std::less<iter_key_t<InputIt>>,
class Alloc = std::allocator<iter_to_alloc_t<InputIt>> >
map( InputIt, InputIt, Comp = Comp(), Alloc = Alloc() )
-> map<iter_key_t<InputIt>, iter_val_t<InputIt>, Comp, Alloc>;
(1)
and(2)
allow for deduction from an iterator range
// (3)
template< class Key, class T, class Allocator >
map( std::initializer_list<std::pair<Key, T>>, Allocator )
-> map<Key, T, std::less<Key>, Allocator>;
// (4)
template< class Key,
class T,
class Comp = std::less<Key>,
class Alloc = std::allocator<std::pair<const Key, T>> >
map( std::initializer_list<std::pair<Key, T>>, Comp = Comp(), Alloc = Alloc() )
-> map<Key, T, Comp, Alloc>;
(3)
and(4)
allow for deduction from astd::initializer_list
Aliases iter_key_t
, iter_val_t
and iter_to_alloc_t
are defined as if follows:
template< class InputIt >
using iter_key_t = std::remove_const_t<
typename std::iterator_traits<InputIt>::value_type::first_type>;
template< class InputIt >
using iter_val_t = typename std::iterator_traits<InputIt>::value_type::second_type;
template< class InputIt >
using iter_to_alloc_t = std::pair<
std::add_const_t<typename std::iterator_traits<InputIt>::value_type::first_type>,
typename std::iterator_traits<InputIt>::value_type::second_type
>
Note that these aliases aren't guaranteed to be found anywhere in the standard library. They are defined solely for presentation purposes of these deduction guides and weren't present in the standard library at the point of writing of this document.
Overload resolution
In order for any of the deduction guides to participate in overload resolution, the folllowing requirements must be met:
InputIt
satisfiesLegacyInputIterator
Alloc
satisfiesAllocator
Comp
doesn't satisfyAllocator
The extent to which the library determines that a type does not satisfy LegacyInputIterator
is unspecified,
except that as a minimum:
- Integral types do not qualify as input iterators.
Likewise, the extent to which it determines that a type does not satisfy Allocator
is unspecified,
except that as a minimum:
- The member type
Alloc::value_type
must exist. - The expression
std::declval<Alloc&>().allocate(std::size_t{})
must be well-formed when treated as an unevaluated operand.
More examples
Basic manipulation
#include <iostream>
#include <string>
#include <map>
int main(){
std::map<std::string, int> player_stats { {"C1", -10}, {"B2", 25} };
player_stats.insert(std::make_pair("A3", 200));
player_stats.emplace("D4", 500);
player_stats["A3"] = 90;
for (auto& [key, value] : player_stats)
std::cout << key << " " << value << std::endl;
return 0;
}
A3 90
B2 25
C1 -10
D4 500
Hover to see the original license.