<map>

std::map is a asorted associative container that contains key-value with unique keys. Keys are sorted by using the omparison function Compare. Search, removal and insertion operations have logarithmic complexity. Maps are usually implemented as Red-black trees

Iterators of std::map iterate inascending order of keys, where ascending is defined by the comparison that was used for construction. That is, given

- `m`, a std::map

- `it_l` and `it_r`, dereferenceable iterators to `m`, with `it_l < it_r`.

m.value_comp()(*it_l, *it_r) == true (least to greatest if using the default comparison).

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

Since c++26: All member functions of std::map are constexpr: it is possible to create and use std::map objects in the evaluation of a constant expression. However, std::map objects generally cannot be constexpr, because any dynamically allocated strage must be released in the same evaluation of constant expression.

Member types

Type	Definition
key_type	Key
mapped_type	T
value_type	std::pair<const Key, T>
size_type	Unsigned integer type (usually std::ptrdiff_t)
key_compare	Compare
allocator_type	Allocator
reference	value_type&
const_reference	const value_type&
pointer	Allocator::pointer (until c++11); std::allocator_traits::pointer (since c++11)
const_pointer	Allocator::const_pointer (until c++11); std::allocator_traits::const_pointer (since c++11)
iterator	LegacyBidirectionalIterator and ConstexprIterator (since c++26) to value_type
const_iterator	LegacyBidirectionalIterator and ConstexprIterator (since c++26) to const value_type
reverse_iterator	std::reverse_iterator
const_reverse_iterator	std::reverse_iterator<const_iterator>
node_type (since c++17)	a specialization of node handle representing a container node
insert_return_type (since c++17)	type descriiing the result of inserting a node_type, a specialization of instantiated with template arguments iterator and node_type

Member classes

Class	Definition
value_compare	compares objects of type value_type

Member functions

Name	Definition
constructor	constructs the map
destructor	destructs the map
operator=	assigns values to the container
get_allocator	returns the associated allocator
at	access specified element with bounds checking
operator[]	returns the associated allocator
begin/cbegin(c++11)	returns an iterator to the beginning
end/cend(c++11)	returns an iterator to the end
rbegin/crbegin(c++11)	returns a reverse iterator to the beginning
rend/crend(c++11)	returns a reverse iterator to the end
empty	checks whether the container is empty
size	returns the number of elements
max_size	returns the maximum possible number of elements
clear	clears the contents
insert	inserts elements or nodes
insert_range(c++23)	inserts a range of elements
insert_or_assign(c++17)	inserts and element or assigns to the current element if the key already exists
emplace(c++11)	constructs element in-place
emplace_hint(c++11)	constructs elements in-place using a hint
try_emplace(c++17)	inserts in-place if the key does not exist, does nothing if the key exits
erase	erases elements
swap	swaps the contents
extract(c++17)	extracts nodes from the container
merge(c++17)	splices nodes from another container
count	returns the number of elements matching specific key
find	finds element with specific key
contains(c++20)	checks if the container contains element with specific key
equal_range	returns range of elements matching a specific key
lower_bound	returns an iterator to the first element not less than the given key
upper_bound	returns an iterator to the first element grater than the given key
key_comp	returns the function that compares keys
value_comp	returns the function that compares keys in objects of type value_type

Non-member functions

Name	Definition
operator==
operator!= (removed om c++20)
operator< (removed om c++20)
operator<= (removed om c++20)
operator> (removed om c++20)
operator>= (removed om c++20)
operator<=> (c++20)
std::swap(std::map)	specializes the std::swap algorithm
erase_id(std::map) (c++20)	erases all elements satisfying specific criteria

Example

#include <iostream>
#include <map>
#include <string>
#include <string_view>

void print_map(std::string_view comment, const std::map<std::string, int>& m) {
  std::cout << comment
  // Iterate using C++ facilities
  for (const auto& [key, value] : m)
    std::cout << '[' << key << "] =" << value << "; ";

  // c++11 alternative:
  // for(const auto& n : m)
  //  std::cout << n.first << " = " << n.second << "; ";

  // C++98 alternative:
  // for (std::map<std::string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
  //   std::cout << it->first << " = " << it->second << "; ";

  std::cout << "\n";
}

int main() {
  // Create a map of three (string, int) pairs
  std::map<std::string, int> m{ {"CPU", 10}, {"GPU", 15}, {"RAM", 20} };

  print_map("1) Initial map: ", m);
  m["CPU"] = 25; // update an existing value
  m["SSD"] = 30; // insert a new value
  print_map("2) Updated map: ", m);

  // Using operator[] with non-existent key always performs an insert
  std::cout << "3) m[UPS] = " << m["UPS"] << "\n";
  print_map("4) Updated map: ", m);

  m.erase("GPU");
  print_map("5) After erase: ", m);

  std::erase_if(m, [](const auto& pair) { return pair.second > 25 });
  print_map("6) After erase: ", m);
  std::cout << "7) m.size() = " << m.size() << "\n";

  m.clear();
  std::cout << std::boolalpha << "8) Map is empty" << m.empty() << "\n";
}

// Output
/**
 * 1) Initial map: [CPU] =10; [GPU] =15; [RAM] =20;
  2) Updated map: [CPU] =25; [GPU] =15; [RAM] =20; [SSD] =30;
  3) m[UPS] = 0
  4) Updated map: [CPU] =25; [GPU] =15; [RAM] =20; [SSD] =30; [UPS] =0;
  5) After erase: [CPU] =25; [RAM] =20; [SSD] =30; [UPS] =0;
  6) After erase: [CPU] =25; [RAM] =20; [UPS] =0;
  7) m.size() = 3
  8) Map is empty true
 */

Reference

1. Red-black trees
2. std::map