STL · Lesson 42

Maps

A map is a container that stores pairs — every key has a value, and the keys always stay in sorted order. Think of a phone book: you look up a name (the key) and you get the number (the value). In C++, that is std::map.

1. What Is a Map?

A map is an STL container that stores key–value pairs. Each key is unique, and the map keeps all its keys sorted from smallest to largest. You never have to sort it yourself — the map does that for you every time you add something.

Maps are perfect whenever you need to look something up by name: a student's marks by their name, a product's price by its code, or a word's meaning by the word itself. Behind the scenes a map is usually built as a balanced tree, so finding, adding and removing a key are all fast — about as fast as searching a phone book by flipping it open in the middle, again and again.

To use a map, include the <map> header and write std::map<KeyType, ValueType>. For example, std::map<std::string, int> is a map from words (strings) to whole numbers. Each entry inside is one std::pair — the key in .first and the value in .second.

2. Your First Map

Let us build a small map of names and exam scores. We add three pairs with square brackets, then print the scores one by one. Watch the output order — the map prints the names in alphabetical order, even though we added them in a different order.

Code story: We create a map called scores that links a student's name to their marks. We store three students, then ask the map for Alice's, Bob's and Charlie's marks and print them. Notice that the printed names come out sorted, not in the order we typed them.

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

int main() {
    map<string, int> scores;
    scores["Charlie"] = 76;
    scores["Alice"] = 95;
    scores["Bob"] = 88;

    cout << "Alice: " << scores["Alice"] << endl;
    cout << "Bob: " << scores["Bob"] << endl;
    cout << "Charlie: " << scores["Charlie"] << endl;
    return 0;
}

Alice: 95
Bob: 88
Charlie: 76

3. Inserting and Accessing Values

There are two everyday ways to put values into a map. The square-bracket way — m[key] = value — is short and simple, and it also overwrites a value if the key already exists. The insert() way adds a pair only if the key is new, and it will not overwrite an old value.

To read safely, use at(): it returns the value for a key, and if the key is missing it throws an error instead of silently creating a new entry. That difference matters — operator[] on a missing key quietly inserts it with a default value (0 for numbers, empty for strings), which can surprise you.

Code story: We keep a map of subject names and marks. First we add Math with 90 and Science with 85, then we try to change Math to 95 using insert — it stays 90 because insert never overwrites. Finally we use at() to read Science safely and print the map's size.

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

int main() {
    map<string, int> marks;
    marks["Math"] = 90;
    marks["Science"] = 85;
    marks.insert({"Math", 95});   // ignored: Math is already there

    cout << "Math: " << marks.at("Math") << endl;
    cout << "Science: " << marks.at("Science") << endl;
    cout << "Size: " << marks.size() << endl;
    return 0;
}

Math: 90
Science: 85
Size: 2

Here is the whole everyday toolbox at a glance:

4. Finding and Counting Keys

Before you read a value, it is often smart to check whether the key is even there. The find() function returns an iterator to the pair if the key exists, or end() if it does not. The count() function is simpler: it returns 1 if the key exists and 0 if it does not, because a map never holds the same key twice.

Checking first is the safe habit. It keeps you from accidentally creating new entries with operator[] and from reading a value that was never stored.

Code story: A small shop keeps fruit prices in a map. We check whether "banana" and "mango" are in the shop's list. For banana we find the pair and print its price; for mango we confirm it is missing. Then we print the map's size.

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

int main() {
    map<string, int> prices;
    prices["apple"] = 50;
    prices["banana"] = 60;

    cout << "Has banana: " << prices.count("banana") << endl;
    cout << "Has mango: " << prices.count("mango") << endl;

    auto it = prices.find("banana");
    if (it != prices.end()) {
        cout << "Price of banana: " << it->second << endl;
    }
    cout << "Size: " << prices.size() << endl;
    return 0;
}

Has banana: 1
Has mango: 0
Price of banana: 60
Size: 2

5. Searching by Position: lower_bound and upper_bound

Sometimes you do not want one exact key — you want the first key that is at least a certain value, or the first key after it. That is what lower_bound() and upper_bound() are for. lower_bound(k) returns an iterator to the first key that is not less than k — so it lands on k itself if k is present. upper_bound(k) returns an iterator to the first key greater than k.

These two functions are how you answer questions like "what is the first score of 30 or more?" or "how many keys are below 40?" — range questions that a plain find() cannot answer.

Code story: The map holds number words for the keys 10, 20, 30, 40 and 50. lower_bound(30) jumps to the first key that is 30 or more — that is 30 itself. upper_bound(30) jumps past 30 to the next key, 40. Then we count all the keys smaller than 40 by hand: 10, 20 and 30.

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

int main() {
    map<int, string> codes;
    codes[10] = "ten";
    codes[20] = "twenty";
    codes[30] = "thirty";
    codes[40] = "forty";
    codes[50] = "fifty";

    auto low = codes.lower_bound(30);
    auto high = codes.upper_bound(30);

    cout << "From 30: " << low->second << endl;
    cout << "After 30: " << high->second << endl;

    int below = 0;
    for (auto it = codes.begin(); it != codes.end(); ++it) {
        if (it->first < 40) below++;
    }
    cout << "Count below 40: " << below << endl;
    return 0;
}

From 30: thirty
After 30: forty
Count below 40: 3

6. Iterating Over a Map

To visit every pair, use a range-based for loop with auto&. Each step hands you one pair: .first is the key and .second is the value. Because a map is always sorted, the loop visits the pairs in key order — names in alphabetical order, numbers from smallest to largest.

Use auto& (with the &) so you work with the real pair inside the map and not a copy of it. If you only need to read, const auto& is the cleanest choice.

Code story: We store the ages of three friends in a map. Then we walk through the whole map with a range-based for loop. Each step hands us one pair: .first is the friend's name and .second is their age. Watch the printed order — it is alphabetical, because the map always keeps its keys sorted.

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

int main() {
    map<string, int> ages;
    ages["Ravi"] = 25;
    ages["Maya"] = 22;
    ages["Arjun"] = 28;

    for (auto& pair : ages) {
        cout << pair.first << " is " << pair.second << endl;
    }
    return 0;
}

Arjun is 28
Maya is 22
Ravi is 25

7. Removing Entries

Entries leave a map in two ways. erase(key) removes one pair — the one with that key — and returns how many pairs it removed (0 or 1). clear() empties the whole map at once. Both are handy when data goes out of date: a product is discontinued, a student leaves, a price list is rebuilt from scratch.

Code story: A shop's stock map holds four items. We erase the pencils and watch the size drop from 4 to 3, then clear everything and the size becomes 0. erase() removes one key; clear() empties the whole map.

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

int main() {
    map<string, int> stock;
    stock["pen"] = 10;
    stock["pencil"] = 20;
    stock["eraser"] = 15;
    stock["ruler"] = 5;

    cout << "Before: " << stock.size() << endl;
    stock.erase("pencil");
    cout << "After erase: " << stock.size() << endl;
    stock.clear();
    cout << "After clear: " << stock.size() << endl;
    return 0;
}

Before: 4
After erase: 3
After clear: 0

8. A Real Example: Word Frequency Counter

Let us put everything together in a program you will see again and again in real code: counting how often each word appears. A map is the perfect tool — the word is the key, and the count is the value. Every time a word shows up, we add 1 to its count.

Code story: This program counts the words in a sentence. It reads the sentence one character at a time, building words letter by letter. Each finished word becomes a key in the map, and its count goes up by one. At the end we print the number of different words and list each word with its count — already in alphabetical order, thanks to the map.

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

int main() {
    string sentence = "the cat sat on the mat the sun";
    map<string, int> words;
    string word = "";
    for (char ch : sentence) {
        if (ch == ' ') {
            words[word]++;
            word = "";
        } else {
            word += ch;
        }
    }
    if (word != "") words[word]++;

    cout << "Unique words: " << words.size() << endl;
    for (auto& pair : words) {
        cout << "- " << pair.first << ": " << pair.second << endl;
    }
    return 0;
}

Unique words: 6
- cat: 1
- mat: 1
- on: 1
- sat: 1
- sun: 1
- the: 2

Which container should you reach for? It depends on whether you need order, pairs, or speed:

9. Common Mistakes

Watch out for these five traps — every beginner meets at least one of them: