C++ Maps

A C++ map (std::map) is an associative container that stores elements as key-value pairs, where every key is unique and the elements are always kept sorted by key. Instead of looking up values by a numeric index like you would with an array or vector, you look them up by a meaningful key — a name, an ID, a word, anything that can be compared. Internally, std::map is implemented as a self-balancing binary search tree, which gives it predictable logarithmic performance for insertion, deletion, and lookup, plus automatically sorted iteration. Maps are one of the most useful containers in C++ because they let you model real relationships — names to phone numbers, words to word counts, IDs to records — directly and efficiently.

Overview / How It Works

To use std::map you must include the <map> header. Its full template signature is:

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

In practice you almost always just write map<KeyType, ValueType> and let the last two template parameters default. Each element stored in the map is a std::pair<const Key, T> — the key is const because changing a key in place would break the tree’s sorted structure, so if you need to change a key you must erase the old entry and insert a new one.

Under the hood, std::map is almost always implemented as a red-black tree, a type of self-balancing binary search tree. Every node holds one key-value pair plus pointers to its parent and two children, along with a color bit (red or black) used to keep the tree balanced. Because the container is a tree of individually allocated nodes rather than one contiguous block of memory (like vector), a few important consequences follow:

Insertion, deletion, and lookup are all O(log n) — fast and predictable even for huge maps.
Iterating over a map always visits elements in ascending key order (or according to a custom comparator), because an in-order traversal of a binary search tree yields sorted output.
Inserting or erasing an element does not invalidate iterators or references to other elements (only the iterator to the erased element itself becomes invalid). This is a major advantage over vector, where inserting can reallocate the entire buffer.
There is no random-access index — you cannot write myMap[2] to mean "the second element"; the [] operator on a map always means "the value for this key."

Keys must be unique. If you need to store multiple values under the same key, use std::multimap instead. If you don’t need sorted order and want average O(1) lookups, consider std::unordered_map, which uses a hash table instead of a tree — it trades ordering for speed.

Syntax

#include <map>

std::map<KeyType, ValueType> myMap;      // empty map
std::map<KeyType, ValueType> myMap = {   // initializer list
    {key1, value1},
    {key2, value2}
};

Member	Purpose
`m[key] = value`	Inserts `key` with `value` if absent, or overwrites the existing value. Inserts a default-constructed value if used to merely read a missing key.
`m.insert({key, value})`	Inserts only if the key is not already present; never overwrites.
`m.emplace(key, value)`	Constructs the pair in place, avoiding a temporary copy; behaves like `insert`.
`m.at(key)`	Returns a reference to the value for `key`; throws `std::out_of_range` if the key is missing. Never inserts.
`m.find(key)`	Returns an iterator to the element, or `m.end()` if not found. Never inserts.
`m.count(key)`	Returns 1 if the key exists, 0 otherwise (map keys are unique).
`m.erase(key)` / `m.erase(it)`	Removes an element by key or by iterator.
`m.size()` / `m.empty()`	Number of elements / whether the map has zero elements.
`m.begin()` / `m.end()`	Iterators over elements in ascending key order.
`m.clear()`	Removes all elements.

Examples

Example 1: Basic map operations

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, double> prices;

    prices["apple"] = 1.50;
    prices["banana"] = 0.75;
    prices.insert({"cherry", 3.25});
    prices.insert(make_pair("date", 4.00));

    for (const auto& entry : prices) {
        cout << entry.first << ": $" << entry.second << endl;
    }

    cout << "Total items: " << prices.size() << endl;
    return 0;
}

Output:

apple: $1.5
banana: $0.75
cherry: $3.25
date: $4
Total items: 4

Notice the output is printed in alphabetical order — apple, banana, cherry, date — even though "date" and "cherry" were inserted last. That’s the tree’s sorted structure at work, not the order you inserted things in.

Example 2: Safely checking for a key

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> ages;
    ages["Alice"] = 30;
    ages["Bob"] = 25;

    auto it = ages.find("Charlie");
    if (it == ages.end()) {
        cout << "Charlie not found" << endl;
    } else {
        cout << "Charlie is " << it->second << endl;
    }

    if (ages.count("Alice")) {
        cout << "Alice is " << ages["Alice"] << endl;
    }

    try {
        cout << ages.at("Dave") << endl;
    } catch (const out_of_range& e) {
        cout << "Caught exception: " << e.what() << endl;
    }

    cout << "Map size: " << ages.size() << endl;
    return 0;
}

Output:

Charlie not found
Alice is 30
Caught exception: map::at
Map size: 2

This example contrasts three lookup tools. find() and count() never modify the map, so they’re safe for existence checks. at() is bounds-checked and throws if the key is missing, which is useful when a missing key represents a genuine error in your program’s logic.

Example 3: A realistic word-frequency counter

#include <iostream>
#include <map>
#include <string>
#include <sstream>
using namespace std;

int main() {
    string text = "the quick brown fox jumps over the lazy dog the fox runs";
    map<string, int> wordCount;

    stringstream ss(text);
    string word;
    while (ss >> word) {
        wordCount[word]++;
    }

    for (const auto& [w, count] : wordCount) {
        cout << w << " -> " << count << endl;
    }

    return 0;
}

Output:

brown -> 1
dog -> 1
fox -> 2
jumps -> 1
lazy -> 1
over -> 1
quick -> 1
runs -> 1
the -> 3

This is exactly the pattern a map excels at: wordCount[word]++ works because operator[] inserts a default value (0 for int) the first time a word is seen, then increments it. The structured binding auto& [w, count] (C++17) unpacks each pair<const string, int> cleanly during iteration.

Under the Hood: Step by Step

When you call m.insert({key, value}) on a red-black tree map, roughly this happens:

Starting at the root, the tree compares key against the current node’s key using the comparator (operator< by default).
If key is smaller, the search moves to the left child; if larger, to the right child; this repeats until an empty spot (a leaf position) is found.
A new node is allocated there and colored red.
The tree then checks red-black invariants (no two red nodes in a row, equal black-height on every path) and performs rotations and recoloring as needed to restore balance. This rebalancing is what keeps the tree height at O(log n) instead of degenerating into a linked list.

find(key) performs the same comparison-guided descent without inserting: at most O(log n) comparisons before returning an iterator or end(). Iterating with begin()/++it performs an in-order tree walk, always producing keys in ascending order — this is why maps never need to be manually sorted.

Common Mistakes

Mistake 1: Using `operator[]` to check whether a key exists

The wrong way:

map<string, int> ages;
ages["Alice"] = 30;

if (ages["Bob"] > 0) {
    cout << "Bob exists" << endl;
} else {
    cout << "Bob does not exist, but was inserted!" << endl;
}

cout << "Map size: " << ages.size() << endl;

This compiles and runs, but it silently inserts "Bob" with a default value of 0 just by reading ages["Bob"], growing the map size from 1 to 2 even though you only meant to check whether Bob was present. The fix is to use find() or count(), which never insert:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> ages;
    ages["Alice"] = 30;

    if (ages.find("Bob") != ages.end()) {
        cout << "Bob exists" << endl;
    } else {
        cout << "Bob does not exist" << endl;
    }

    cout << "Map size: " << ages.size() << endl;
    return 0;
}

Output:

Bob does not exist
Map size: 1

Mistake 2: Erasing an element while iterating incorrectly

The wrong way (undefined behavior — do not run this):

map<int, string> m = {{1, "a"}, {2, "b"}, {3, "c"}};
for (auto it = m.begin(); it != m.end(); ++it) {
    if (it->first == 2) {
        m.erase(it); // it is now a dangling iterator
    }
}
// the loop's "++it" then operates on the invalidated iterator: undefined behavior

erase(it) invalidates it immediately, so the loop’s own ++it step runs on a dangling iterator — this can crash or corrupt the tree unpredictably. The fix is to capture erase‘s return value, which is a valid iterator to the next element:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<int, string> m = {{1, "a"}, {2, "b"}, {3, "c"}};

    for (auto it = m.begin(); it != m.end(); ) {
        if (it->first == 2) {
            it = m.erase(it);
        } else {
            ++it;
        }
    }

    for (const auto& [key, val] : m) {
        cout << key << ": " << val << endl;
    }

    return 0;
}

Output:

1: a
3: c

Best Practices

Use find() or count() when you only want to check whether a key exists; reserve operator[] for when you intend to insert-or-update.
Use at() when a missing key indicates a bug you want to surface immediately via an exception, rather than silently inserting a default value.
Prefer emplace() over insert() when constructing the value in place avoids an unnecessary temporary copy, especially for expensive-to-construct value types.
When erasing while iterating, always reassign the iterator from erase()‘s return value instead of incrementing an iterator you just erased.
If you don’t need sorted order, consider std::unordered_map for average O(1) operations instead of a map’s O(log n).
Use structured bindings (for (auto& [k, v] : m)) in C++17 and later for cleaner iteration code.
Remember map keys are immutable once inserted; to "rename" a key you must erase the old entry and insert a new one.

Practice Exercises

Exercise 1: Write a program that counts how many times each character appears in the string "programming" using a map<char, int>, then prints each character and its count in alphabetical order.

Exercise 2: Build a map<string, int> of student names to exam scores. Insert at least four students, then iterate over the map to find and print the name and score of the student with the highest score (do not assume any particular insertion order).

Exercise 3: Start with a map<string, int> inventory containing {"apple", 10} and {"pear", 5}. Write code that increases "apple"‘s count by 5, inserts "banana" with count 10 only if it is not already present, and finally prints every item in alphabetical order along with the total number of distinct items.

Summary

std::map stores unique key-value pairs, automatically sorted by key, and requires <map>.
It is typically implemented as a red-black tree, giving O(log n) insertion, deletion, and lookup, and stable iterators across insert/erase of other elements.
operator[] inserts a default value if the key is missing — use find(), count(), or at() instead when you don’t want that side effect.
Iterating a map always visits elements in ascending key order via an in-order tree traversal.
When erasing during iteration, reassign the iterator from erase()‘s return value to avoid undefined behavior.
Choose std::unordered_map instead when you need faster average-case lookups and don’t care about ordering.

C++ Maps

Overview / How It Works

Syntax

Examples

Example 1: Basic map operations

Example 2: Safely checking for a key

Example 3: A realistic word-frequency counter

Under the Hood: Step by Step

Common Mistakes

Mistake 1: Using operator[] to check whether a key exists

Mistake 2: Erasing an element while iterating incorrectly

Best Practices

Practice Exercises

Summary

Table of Contents

Mistake 1: Using `operator[]` to check whether a key exists