std::map in C++ Standard Library

What std::map is

std::map is an ordered associative container from the C++ Standard Library. It stores key-value pairs and keeps keys sorted in ascending order. Under the hood it is typically a red-black tree, which gives O(log n) lookup, insertion, and deletion.

Include the <map> header to use it.

Declaring and inserting

The type parameters are the key type and the value type. Use operator[] or insert to add entries.

#include <map>
#include <string>

std::map<std::string, int> scores;

scores["Alice"] = 95;
scores["Bob"]   = 82;
scores["Carol"] = 78;

operator[] inserts a default value if the key does not already exist. That is often convenient but can also hide bugs.

Lookup and safe access

To read a value when you are not sure the key exists, prefer find() over operator[].

auto it = scores.find("Alice");
if (it != scores.end()) {
    std::cout << it->second << std::endl;  // prints 95
}

at() is another safe option. It throws std::out_of_range if the key is missing, which is useful when a missing key indicates a programming error.

Iterating over a map

Iteration always follows sorted key order. A range-for loop gives you a reference to each std::pair<const Key, Value>.

for (const auto& [name, score] : scores) {
    std::cout << name << ": " << score << std::endl;
}
// Output (sorted): Alice: 95, Bob: 82, Carol: 78

Removing elements

Use erase with a key or with an iterator.

scores.erase("Bob");  // remove by key

auto it = scores.find("Carol");
if (it != scores.end()) {
    scores.erase(it);  // remove by iterator
}

When to use std::map vs unordered_map

Use std::map when you need sorted iteration or when keys must stay ordered. Its O(log n) time is predictable and has no worst-case spikes.

Use std::unordered_map when order does not matter and you need O(1) average-case lookup. It uses a hash table, which is faster on average but can degrade if many keys hash to the same bucket.