caution

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

Overview

Simplified (since C++98)

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

Detailed

Regular (since C++98)

template<
    class Key,
    class Value,
    class Compare = std::less<Key>,
    class Allocator = std::allocator< std::pair<const Key, Value> >
>
class map;

Polymorphic (since C++17)

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 std::size_t ).
pub	difference_type	Signed integer type (usually std::ptrdiff_t ).
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 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

pub

value_compare

Compares two objects of type value_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 true if a map is empty, otherwise false.
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 .extract()) (since C++17).
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 0/1).
pub	find	Searches for an element and returns an iterator to it, or end iterator if not found.
pub	contains (since C++20)	Returns true if an element is inside a map, otherwise false.
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 value_type (std::pair<Key, Value>).

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 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
>

note

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 satisfies LegacyInputIterator
• Alloc satisfies Allocator
• Comp doesn't satisfy Allocator

note

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

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