Przejdź do głównej zawartości
uwaga

Note, this article is not finished! You can help by editing this doc page.

Overview

template< class Key, class Value, /* ... */ >
class map;

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 inmap

Template parameters

pubKeyThe type of stored keys.
pubValueThe type of stored values.
pubCompareA comparator type satisfying Compare.
pubAllocatorAn allocator type responsible for allocating and deallocating memory. Must satisfy Allocator.

Type names

pubkey_typeKey
pubmapped_typeValue
pubvalue_typestd::pair<const Key, Value>
pubsize_typeUnsigned integer type (usually
std::size_t
).
pubdifference_typeSigned integer type (usually
std::ptrdiff_t
).
pubkey_compareCompare
puballocator_typeAllocator
pubreferencevalue_type&
pubconst_referenceconst value_type&
pubpointerAllocator::pointer(until C++11)
std::allocator_traits<Allocator>::pointer(since C++11)
pubconst_pointerAllocator::const_pointer(until C++11)
std::allocator_traits<Allocator>::const_pointer(since C++11)
pubiteratorLegacyBidirectionalIterator to value_type
pubconst_iteratorLegacyBidirectionalIterator to const value_type
pubreverse_iteratorstd::reverse_iterator<iterator>
pubconst_reverse_iteratorstd::reverse_iterator<const_iterator>
pubnode_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 node_type, a specialization of

template < class Iter, class NodeType >
struct /* unspecified */ {
Iter position;
bool inserted;
NodeType node;
};

instantiated with template arguments iterator and node_type.

Member classes

pubvalue_compare

Compares two objects of type value_type.

Member functions

pub(constructors)

Constructs a new map.

pub(destructor)

Destructs a map.

puboperator=

Assigns one map to another.

pubget_allocator

Returns an associated allocator.

Element access

pubat

Accesses a specified element with bounds checking.

puboperator[]

Accesses or inserts a specified element.

Iterators

pubbegin
cbegin(since C++11)

Returns an iterator to the beginning.

pubend
cend(since C++11)

Returns an iterator to the end.

pubrbegin
crbegin(since C++11)

Returns a reverse iterator to the beginning.

pubrend
crend(since C++11)

Returns a reverse iterator to the end.

Capacity

pubempty

Returns true if a map is empty, otherwise false.

pubsize

Returns the number of elements in a map.

pubmax_size

Returns the maximum possible number of elements.

Modifiers

pubclear

Clears the contents of a map.

pubinsert

Inserts elements or nodes (extracted with .extract()) (since C++17).

pubinsert_or_assign (since C++17)

Inserts a new element or assigns to an already existing one if it already exists.

pubemplace (since C++11)

Constructs a new element in place.

pubemplace_hint (since C++11)

Constructs elements in-place using a hint (iterator).

pubtry_emplace

Inserts a new element in-place if the key does not exist, does nothing if the key exists.

puberase

Erases elements.

pubswap

Swaps two maps.

pubextract (since C++17)

Extracts nodes from a map (can be later inserted somewhere else).

pubmerge (since C++17)

Merges two maps together.

Lookup

pubcount

Returns the number of elements matching a specific key (for a map always 0/1).

pubfind

Searches for an element and returns an iterator to it, or end iterator if not found.

pubcontains (since C++20)

Returns true if an element is inside a map, otherwise false.

pubequal_range

Returns a range of elements matching a specific key. (for a map the range will always contain one element).

publower_bound

Returns an iterator to the first element not less than the given key.

pubupper_bound

Returns an iterator to the first element greater than the given key.

Observers

pubkey_comp

Returns an internal function object that compares keys.

pubvalue_comp

Returns an internal function object that compares keys in objects of type value_type (std::pair<Key, Value>).

Non-member functions

puboperator==
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.
pubstd::swap (std::map)An overload for a std::swap algorithm.
puberase_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 a std::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
>
zanotuj

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:

zanotuj

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:

More examples

Basic manipulation

Creating map, inserting pair, changing values and printing it out
#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;
}
Result
A3 90
B2 25
C1 -10
D4 500
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.
uwaga

Note, this article is not finished! You can help by editing this doc page.

Overview

template< class Key, class Value, /* ... */ >
class map;

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 inmap

Template parameters

pubKeyThe type of stored keys.
pubValueThe type of stored values.
pubCompareA comparator type satisfying Compare.
pubAllocatorAn allocator type responsible for allocating and deallocating memory. Must satisfy Allocator.

Type names

pubkey_typeKey
pubmapped_typeValue
pubvalue_typestd::pair<const Key, Value>
pubsize_typeUnsigned integer type (usually
std::size_t
).
pubdifference_typeSigned integer type (usually
std::ptrdiff_t
).
pubkey_compareCompare
puballocator_typeAllocator
pubreferencevalue_type&
pubconst_referenceconst value_type&
pubpointerAllocator::pointer(until C++11)
std::allocator_traits<Allocator>::pointer(since C++11)
pubconst_pointerAllocator::const_pointer(until C++11)
std::allocator_traits<Allocator>::const_pointer(since C++11)
pubiteratorLegacyBidirectionalIterator to value_type
pubconst_iteratorLegacyBidirectionalIterator to const value_type
pubreverse_iteratorstd::reverse_iterator<iterator>
pubconst_reverse_iteratorstd::reverse_iterator<const_iterator>
pubnode_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 node_type, a specialization of

template < class Iter, class NodeType >
struct /* unspecified */ {
Iter position;
bool inserted;
NodeType node;
};

instantiated with template arguments iterator and node_type.

Member classes

pubvalue_compare

Compares two objects of type value_type.

Member functions

pub(constructors)

Constructs a new map.

pub(destructor)

Destructs a map.

puboperator=

Assigns one map to another.

pubget_allocator

Returns an associated allocator.

Element access

pubat

Accesses a specified element with bounds checking.

puboperator[]

Accesses or inserts a specified element.

Iterators

pubbegin
cbegin(since C++11)

Returns an iterator to the beginning.

pubend
cend(since C++11)

Returns an iterator to the end.

pubrbegin
crbegin(since C++11)

Returns a reverse iterator to the beginning.

pubrend
crend(since C++11)

Returns a reverse iterator to the end.

Capacity

pubempty

Returns true if a map is empty, otherwise false.

pubsize

Returns the number of elements in a map.

pubmax_size

Returns the maximum possible number of elements.

Modifiers

pubclear

Clears the contents of a map.

pubinsert

Inserts elements or nodes (extracted with .extract()) (since C++17).

pubinsert_or_assign (since C++17)

Inserts a new element or assigns to an already existing one if it already exists.

pubemplace (since C++11)

Constructs a new element in place.

pubemplace_hint (since C++11)

Constructs elements in-place using a hint (iterator).

pubtry_emplace

Inserts a new element in-place if the key does not exist, does nothing if the key exists.

puberase

Erases elements.

pubswap

Swaps two maps.

pubextract (since C++17)

Extracts nodes from a map (can be later inserted somewhere else).

pubmerge (since C++17)

Merges two maps together.

Lookup

pubcount

Returns the number of elements matching a specific key (for a map always 0/1).

pubfind

Searches for an element and returns an iterator to it, or end iterator if not found.

pubcontains (since C++20)

Returns true if an element is inside a map, otherwise false.

pubequal_range

Returns a range of elements matching a specific key. (for a map the range will always contain one element).

publower_bound

Returns an iterator to the first element not less than the given key.

pubupper_bound

Returns an iterator to the first element greater than the given key.

Observers

pubkey_comp

Returns an internal function object that compares keys.

pubvalue_comp

Returns an internal function object that compares keys in objects of type value_type (std::pair<Key, Value>).

Non-member functions

puboperator==
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.
pubstd::swap (std::map)An overload for a std::swap algorithm.
puberase_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 a std::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
>
zanotuj

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:

zanotuj

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:

More examples

Basic manipulation

Creating map, inserting pair, changing values and printing it out
#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;
}
Result
A3 90
B2 25
C1 -10
D4 500
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.