C++ map and set: unordered_map and STL Guide

Q: How do I sort a map by value in C++?

A map is always sorted by key, so copy its pairs into a vector first: vector<pair<string, int>> v(m.begin(), m.end());. Then sort the vector with a lambda that compares .second, for example return a.second > b.second; for highest first. The map itself is unchanged.

Q: Can a C++ map have duplicate keys?

No. A map keeps one value per key, and assigning to an existing key replaces its value. If you need several values for one key, use std::multimap, whose insert always adds a new pair, or keep a map<string, vector<int>> and push values onto each key's vector, which is often easier to work with.

Q: How do I get the smallest or largest key in a map?

Because a map is sorted, the first element has the smallest key and the last has the largest. m.begin()->first gives the smallest, and m.rbegin()->first gives the largest. Check that the map isn't empty first, since both are invalid on an empty map.

Q: How do I use my own struct as a map key?

A map needs to know how to order keys, so give the struct an operator<, such as one comparing x and then y, or use C++20's auto operator<=>(const Pt&) const = default;. A set needs the same. An unordered_map instead needs a hash function and operator==, which takes more work, so map is the easier choice for struct keys.

Q: What is the difference between map insert and operator[]?

m[key] = value always stores the value, replacing any existing one. m.insert({key, value}) does nothing if the key is already there, and returns a pair whose .second is false to tell you so. C++17's insert_or_assign(key, value) behaves like [] but tells you whether it inserted, and it doesn't need the value type to have a default constructor.

The Standard Template Library (STL) is a collection of ready-made containers and algorithms that ships with every C++ compiler. You've already used one of its containers, std::vector. This lesson introduces three more that you'll reach for constantly: std::map, std::unordered_map and std::set.

A map stores key-value pairs: look up a product's price by its name, a student's score by their ID, or a word's count by the word itself. A set stores unique values, perfect for answering "have I seen this before?". Together with vectors, these containers solve most everyday data problems without writing your own data structures.

You'll also meet a few STL algorithms from <algorithm>, such as sort, find and count_if, which work on any container and save you from writing the same loops again and again.

std::map

C++

#include <map>

map<string, double> prices;
prices["Pen"] = 1.20;
prices["Notebook"] = 3.50;
prices.insert({"Lamp", 24.50});
cout << prices["Pen"];        // 1.2
cout << prices.size();        // 3

map<KeyType, ValueType> stores pairs, sorted by key.
m[key] = value adds a pair or replaces the value for an existing key.
m.at(key) reads a value and throws std::out_of_range if the key is missing.
Keys are unique: assigning to an existing key replaces its value.

Looking things up safely

Be careful with m[key] when reading: if the key isn't there, [] quietly inserts it with a default value (0 for numbers, an empty string for strings). To check without inserting:

Code	Meaning
`m.count(k)`	1 if the key exists, otherwise 0
`m.contains(k)`	`true` or `false` (C++20)
`auto it = m.find(k); it != m.end()`	Found; `it->second` is the value
`m.erase(k)`	Remove the key and its value

find returns an iterator, a pointer-like object that refers to an element. Comparing it with m.end() means "was anything found?".

Looping and unordered_map

Loop through a map with a range-based for loop. Since C++17, structured bindings unpack each pair into two names:

C++

for (const auto& [name, price] : prices) {
    cout << name << ": " << price << endl;
}

A std::map visits keys in sorted order. std::unordered_map (from <unordered_map>) has the same operations but stores keys by their hash, which makes lookups faster on average for large maps, at the cost of having no particular order. Use map when you need sorted output and unordered_map when you only need fast lookups.

std::set and algorithms

A set from <set> keeps unique values in sorted order:

C++

set<string> tags = {"cpp", "games", "cpp"};
tags.insert("stl");
tags.count("games");   // 1

insert returns a pair whose .second is false if the value was already there. unordered_set is the unordered, hash-based version.

The <algorithm> header works with any container through iterators: sort(v.begin(), v.end()), find(v.begin(), v.end(), x), count_if(v.begin(), v.end(), predicate), max_element(...) and many more. The predicate can be a lambda, a small unnamed function such as [](int x) { return x > 10; }.

Removing entries while looping

Sometimes you need to delete every entry that matches a rule, such as products that are out of stock. Erasing inside a range-based for loop doesn't work, because the loop would carry on from an element that no longer exists. Use an iterator loop and take the iterator that erase returns:

C++

for (auto it = stock.begin(); it != stock.end(); ) {
    if (it->second == 0) {
        it = stock.erase(it);   // erase returns the next element
    } else {
        ++it;
    }
}

Notice that ++it is in the body, not in the loop header. When an element is erased, it already points at the next one, so moving on again would skip an element.

C++20 adds a much shorter way for maps, sets and the other standard containers:

C++

erase_if(stock, [](const auto& item) { return item.second == 0; });

erase_if takes a lambda that returns true for the entries to remove and returns how many it removed. For a map, each entry the lambda receives is a key-value pair, so item.first is the key and item.second is the value. The same patterns work for set, unordered_map and unordered_set.

C++ Maps and Sets Syntax

Map, set and algorithm syntax

#include <map>
#include <set>
#include <algorithm>

map<string, int> m;
m["key"] = 1;
if (m.count("key")) { ... }
for (const auto& [k, v] : m) { ... }

set<int> s = {3, 1, 2};
s.insert(4);

sort(v.begin(), v.end());
count_if(v.begin(), v.end(), [](int x) { return x > 0; });

C++ Maps and Sets Summary

map<K, V> stores unique keys with values, sorted by key; unordered_map is unsorted but often faster.
m[k] = v writes; reading with [] inserts missing keys, so use count, find or at to check.
Loop with for (const auto& [k, v] : m).
set<T> stores unique, sorted values; insert reports whether the value was new.
<algorithm> provides sort, find, count_if and more, often with lambdas.

C++ Maps and Sets Examples

Each example shows the code, the output it produces and what each part does.

Example 1

A price list with map

C++

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

int main() {
    map<string, double> prices = {
        {"Pen", 1.20}, {"Notebook", 3.50}, {"Backpack", 34.99}
    };
    prices["Pen"] = 1.10;
    prices["Lamp"] = 24.50;

    for (const auto& [name, price] : prices) {
        cout << name << ": " << price << endl;
    }

    string wanted = "Sofa";
    if (prices.count(wanted) == 0) {
        cout << wanted << " isn't sold here" << endl;
    }
    cout << "Items: " << prices.size() << endl;
    return 0;
}

Output

Backpack: 34.99
Lamp: 24.5
Notebook: 3.5
Pen: 1.1
Sofa isn't sold here
Items: 4

Line-by-line explanation

Lines 7 to 9A map can be filled with pairs in braces.
Line 10Assigning to an existing key replaces the value.
Lines 13 to 15Keys come out in alphabetical order, because std::map is sorted.
Line 18count checks for the key without inserting it.

Example 2

Counting words

C++

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

int main() {
    string text = "the cat and the hat and the bat";
    map<string, int> counts;

    istringstream words(text);
    string word;
    while (words >> word) {
        counts[word]++;
    }

    for (const auto& [w, n] : counts) {
        if (n > 1) cout << w << ": " << n << endl;
    }
    return 0;
}

Output

and: 2
the: 3

Line-by-line explanation

Lines 11 to 14istringstream reads the text word by word, just like cin.
Line 14counts[word]++ inserts a new word with 0, then adds 1. Here that's exactly what we want.
Lines 17 to 19The map is sorted, so "and" comes before "the".

Example 3

Sets and algorithms together

C++

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    vector<int> scores = {72, 95, 61, 88, 61, 79, 95};

    set<int> unique(scores.begin(), scores.end());
    cout << "Different scores: " << unique.size() << endl;

    sort(scores.begin(), scores.end(), [](int a, int b) { return a > b; });
    cout << "Top score: " << scores[0] << endl;

    int passes = count_if(scores.begin(), scores.end(), [](int s) { return s >= 70; });
    cout << "Passes: " << passes << " of " << scores.size() << endl;

    auto it = find(scores.begin(), scores.end(), 88);
    cout << "88 found? " << (it != scores.end()) << endl;
    return 0;
}

Output

Different scores: 5
Top score: 95
Passes: 5 of 7
88 found? 1

Line-by-line explanation

Line 10Building a set from the vector removes the duplicates 61 and 95.
Line 13sort with a lambda that puts larger numbers first.
Line 16count_if counts the scores where the lambda returns true.
Lines 19 to 20find returns end() when the value isn't there.

Common C++ Maps and Sets Mistakes

Reading a missing key with []

Don't

map<string, int> stock;
if (stock["Lamp"] > 0) { ... }   // silently adds "Lamp" with 0

map<string, int> stock;
if (stock.count("Lamp") && stock.at("Lamp") > 0) { ... }

Expecting unordered_map to be sorted

Don't

unordered_map<string, int> ages;   // printed order looks random

map<string, int> ages;             // printed in key order

Forgetting begin() and end()

Don't

sort(scores);

sort(scores.begin(), scores.end());

Classic STL algorithms work on a range given by two iterators. (C++20 adds ranges::sort(scores).)

C++ Maps and Sets in Real Projects

STL containers in real code

Compilers keep symbol tables in hash maps, games map entity IDs to objects, and network servers keep unordered_maps of connected users. Competitive programmers rely heavily on map, set and <algorithm> to solve problems quickly, and they're among the first tools professional C++ developers reach for.

C++ Maps and Sets FAQ

How do I sort a map by value in C++?

A map is always sorted by key, so copy its pairs into a vector first: vector<pair<string, int>> v(m.begin(), m.end());. Then sort the vector with a lambda that compares .second, for example return a.second > b.second; for highest first. The map itself is unchanged.

Can a C++ map have duplicate keys?

No. A map keeps one value per key, and assigning to an existing key replaces its value. If you need several values for one key, use std::multimap, whose insert always adds a new pair, or keep a map<string, vector<int>> and push values onto each key's vector, which is often easier to work with.

How do I get the smallest or largest key in a map?

Because a map is sorted, the first element has the smallest key and the last has the largest. m.begin()->first gives the smallest, and m.rbegin()->first gives the largest. Check that the map isn't empty first, since both are invalid on an empty map.

How do I use my own struct as a map key?

A map needs to know how to order keys, so give the struct an operator<, such as one comparing x and then y, or use C++20's auto operator<=>(const Pt&) const = default;. A set needs the same. An unordered_map instead needs a hash function and operator==, which takes more work, so map is the easier choice for struct keys.

What is the difference between map insert and operator[]?

m[key] = value always stores the value, replacing any existing one. m.insert({key, value}) does nothing if the key is already there, and returns a pair whose .second is false to tell you so. C++17's insert_or_assign(key, value) behaves like [] but tells you whether it inserted, and it doesn't need the value type to have a default constructor.

C++ Maps and Sets Exercises

Answer each one and check it instantly. If you get stuck, open the hint before the answer.

Fill in the blankseasy

Complete the code so it stores a score for "Ana".

map<string, int> scores;
scores.({"Ana", 82});

Predict the outputeasy

What does this print?

set<int> s = {5, 1, 5, 3};
cout << s.size();

Predict the outputmedium

What does this print?

map<string, int> m;
cout << m["x"] << " " << m.size();

Multiple choicemedium

Which container gives fast lookups by key with no particular order?

Multiple choicehard

What does m.find(k) != m.end() check?

C++ Maps and Sets Quiz

5 questions to check what you learned.

In what order does std::map store its keys?
- Insertion order
- Random order
- Sorted order
- Reverse insertion order
What does a std::set guarantee?
- Values in insertion order
- Each value appears only once
- Constant size
- Values can be changed in place
What are structured bindings in for (const auto& [k, v] : m)?
- A way to sort maps
- A kind of pointer
- A map method
- A way to unpack each pair into two named variables
What is [](int x) { return x > 10; }?
- A lambda: a small unnamed function
- An array
- A map literal
- A template
Why can m[key] be risky when only reading?
- It throws an exception
- It inserts the key with a default value if it isn't already there
- It deletes the key
- It returns a copy of the map

std::map

Looking things up safely

Looping and unordered_map

std::set and algorithms

Removing entries while looping

C++ Maps and Sets Syntax

C++ Maps and Sets Summary

C++ Maps and Sets Examples

Common C++ Maps and Sets Mistakes

!Reading a missing key with []

!Expecting unordered_map to be sorted

!Forgetting begin() and end()

C++ Maps and Sets in Real Projects

STL containers in real code

C++ Maps and Sets FAQ

C++ Maps and Sets Exercises

C++ Maps and Sets Quiz

Related C++ topics

Reading a missing key with []

Expecting unordered_map to be sorted

Forgetting begin() and end()