std::map

std::map is a sorted associative container that stores key-value pairs with unique keys.

Ordering is defined by the comparison object Compare, not by insertion order. Search, insertion, and removal have logarithmic complexity. Most implementations use red-black trees.

# Declarations

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

namespace pmr {
template<
class Key,
class T,
class Compare = std::less<Key>
> using map = std::map<Key, T, Compare,
std::pmr::polymorphic_allocator<std::pair<const Key, T>>>;
}

(since C++17)

std::pmr::map is an alias that uses std::pmr::polymorphic_allocator for memory-resource-based allocation.

# Template parameters

• Key: key type used for ordering and lookup.
• T: mapped value type associated with each key.
• Compare: strict weak ordering used to sort keys and determine key equivalence.
• Allocator: allocator used to manage node storage for std::pair<const Key, T> values.

Two keys are considered equivalent when neither compares less than the other under Compare. That equivalence relation, rather than operator==, controls uniqueness inside the container.

# 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;
    for (const auto& [key, value] : m)
        std::cout << '[' << key << "] = " << value << "; ";
    std::cout << '\n';
}
 
int main()
{
    std::map<std::string, int> m{{"CPU", 10}, {"GPU", 15}, {"RAM", 20}};
 
    print_map("1) Initial map: ", m);
 
    m["CPU"] = 25;
    m["SSD"] = 30;
    print_map("2) Updated map: ", m);
 
    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';
}

This is the common map pattern: ordered unique keys, logarithmic lookup and insertion, and iteration in key order rather than insertion order.

# Member types

# Member classes

Iteration order follows the key ordering defined by Compare.

# Reference map

# Deduction guides

The class has deduction guides so constructors can infer key, mapped, comparator, and allocator-related types from arguments where appropriate.

# Notes

Unlike sequence containers, node-based storage means elements are not contiguous in memory. Ordered lookup and range queries remain cheap because the container maintains key order.

Because map is node-based, inserting elements does not invalidate iterators or references to existing elements.

operator[] inserts a new element with a default-constructed mapped value if the key does not already exist.

std::map is the right fit when keys must stay sorted and unique while preserving logarithmic lookup and insertion complexity.

# Feature-test macros

# Defect reports

# See also

• multimap
• unordered_map
• flat_map