Maps & Sets (map, unordered_map, set)

Reviewed & published by Brayan K

Vectors are great for ordered lists, but real programs constantly need to answer "have I seen this before?" and "what value is stored under this key?". That's exactly what sets and maps are for. By the end of this lesson you'll store key/value data, count and deduplicate in a few lines, and know when to pick the sorted tree version over the faster hash version.

Part of the free C++ course at LearnCodingFast — hands-on lessons with worked examples and the output they print, plus practice exercises and a quick quiz.

What You'll Learn

• Store key/value pairs with std::map and access them by key
• Choose between std::map (sorted) and std::unordered_map (hash, fast)
• Count occurrences and deduplicate in just a few lines
• Use std::set / std::unordered_set for unique collections
• Look up safely with find, count, contains, and at
• Iterate with structured bindings and erase entries correctly

💡 Real-World Analogy

A map is a dictionary: you look up a word (the key) to get its definition (the value). You don't scan every page — you jump straight to the entry. A set is a guest list at a door: each name appears once, and the bouncer only cares "is this name on the list?" — not how many times. A std::map<K,V> keeps its words alphabetized; a std::unordered_map<K,V> throws them in a giant hashed filing cabinet where you can still find any one instantly, but they're no longer in alphabetical order.

📊 Map & Set at a Glance

Rule of thumb: reach for unordered_map / unordered_set for speed; switch to map / set when you need sorted order or ordered range queries.

1. std::map — Key → Value

A std::map<K, V> stores pairs where each key is unique and maps to one value. You include the <map> header, then read and write with map[key]. When you iterate, a map walks its keys in sorted order — handy when you want predictable output. Each element is a std::pair, so entry.first is the key and entry.second is the value.

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

int main() {
    // A map stores KEY -> VALUE pairs. Here: name -> age.
    map<string, int> ages;

    // Insert with operator[] (creates the key if missing):
    ages["Alice"] = 30;
    ages["Bob"]   = 25;
    ages["Cara"]  = 42;

    // Look a value up by its key:
    cout << "Bob is " << ages["Bob"] << endl;   // Bob is 25

    // A std::map iterates in SORTED key order (Alice, Bob, Cara):
    for (const auto& entry : ages) {
        // entry.first  = key,  entry.second = value
        cout << entry.first << " -> " << entry.second << endl;
    }
    cout << "Total people: " << ages.size() << endl; // 3
    return 0;
}

// ✅ Expected output:
//    Bob is 25
//    Alice -> 30
//    Bob -> 25
//    Cara -> 42
//    Total people: 3

2. Looking Up Keys Safely

There's a famous gotcha: map[key] on a key that doesn't exist inserts it with a default value (0 for numbers) and the map silently grows. To check whether a key exists without changing the map, use .count(key), .contains(key) (C++20), or .find(key). Use .at(key) when you want an exception if the key is missing.

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

int main() {
    map<string, int> stock = {{"apples", 12}, {"pears", 5}};

    // ❌ operator[] on a MISSING key inserts it (value 0):
    cout << stock["bananas"] << endl;  // 0  -- and "bananas" now exists!
    cout << "size now: " << stock.size() << endl; // 3, oops

    // ✅ .count() / .contains() check WITHOUT inserting:
    if (stock.count("apples")) {
        cout << "apples in stock: " << stock["apples"] << endl; // 12
    }

    // ✅ .find() returns an iterator; end() means "not found":
    auto it = stock.find("pears");
    if (it != stock.end()) {
        cout << it->first << " = " << it->second << endl; // pears = 5
    }

    // ✅ .at() throws std::out_of_range if the key is missing:
    cout << stock.at("apples") << endl; // 12
    return 0;
}

// ✅ Expected output:
//    0
//    size now: 3
//    apples in stock: 12
//    pears = 5
//    12

The "insert on access" behaviour is actually a feature for counting. Fill in the blank to tally how often each word appears:

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

int main() {
    // 🎯 YOUR TURN — count how many times each word appears.
    string words[] = {"red", "blue", "red", "green", "red", "blue"};

    map<string, int> counts;
    for (const string& w : words) {
        // operator[] value-initializes a missing key to 0,
        // so ++ on it just works as a tally.
        ___;          // 👉 counts[w]++;
    }

    for (const auto& [word, n] : counts) {   // structured bindings (C++17)
        cout << word << ": " << n << endl;
    }
    // ✅ Expected output (sorted by key):
    //    blue: 2
    //    green: 1
    //    red: 3
    return 0;
}

3. unordered_map — The Fast Default

std::unordered_map uses a hash table: it computes a hash of the key to jump straight to a bucket, giving average O(1) lookup and insertion. The trade-off is that iteration order is unspecified. For most "look up by key" work where you don't care about ordering, this is the container to reach for. The interface is almost identical to map.

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

int main() {
    // unordered_map: a HASH TABLE. Average O(1) lookup/insert,
    // but NO sorted order when you iterate.
    unordered_map<string, double> prices;
    prices["coffee"] = 3.50;
    prices["tea"]    = 2.25;
    prices["cake"]   = 4.75;

    // Direct lookup is the common case and is very fast:
    cout << "Cake costs $" << prices["cake"] << endl; // Cake costs $4.75

    // Iteration order is UNSPECIFIED here (could be any order):
    for (const auto& [item, price] : prices) {
        cout << item << " -> $" << price << endl;
    }

    // Update in place:
    prices["coffee"] += 0.50;
    cout << "Coffee now $" << prices["coffee"] << endl; // Coffee now $4
    return 0;
}

// ⚠️ No expected-output panel for this one, on purpose.
// An unordered container iterates in whatever order its hash function and
// bucket count produce. That order is not part of the standard, so it can
// differ between compilers and between library versions. The sorted map
// above it is the one with a guaranteed order — that is the trade you are
// making.
//
// One real run on the machine that builds this site printed:
//    Cake costs $4.75
//    cake -> $4.75
//    tea -> $2.25
//    coffee -> $3.5
//    Coffee now $4

🧩 Reorder Challenge

These lines build a map of fruit prices, raise one price, and print the total — but they're scrambled. Put them in the correct order:

A.     cout << "Total: $" << menu["apple"] + menu["pear"] << endl;
B.     menu["apple"] += 0.20;
C. int main() {
D.     map<string,double> menu = {{"apple",1.00},{"pear",1.50}};
E.     return 0;
F. }

Correct order: C → D → B → A → E → F

Open main (C), declare and initialize the map (D), bump the apple price (B), print the combined total — now 1.20 + 1.50 = $2.7 (A), then return 0; (E) and close the brace (F).

4. std::set — Unique Values

A std::set stores unique values in sorted order. Inserting a duplicate is simply ignored, which makes deduplication a one-liner. .insert() returns a pair whose .second tells you whether the value was actually new. As with maps, there's an unordered_set hash-based variant for speed.

#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

int main() {
    // A set stores UNIQUE values in sorted order.
    set<int> seen;
    int data[] = {4, 1, 4, 2, 1, 3, 4};
    for (int x : data) seen.insert(x);  // duplicates are ignored

    cout << "Unique sorted: ";
    for (int x : seen) cout << x << " "; // 1 2 3 4
    cout << endl;
    cout << "Count of distinct values: " << seen.size() << endl; // 4

    // .insert() reports whether the value was actually new:
    auto result = seen.insert(2);   // already present
    cout << "Inserted 2? " << result.second << endl; // 0 (false)

    // Membership test:
    cout << "Has 3? " << (seen.count(3) ? "yes" : "no") << endl; // yes

    // unordered_set: same uniqueness, hash-based, no ordering.
    unordered_set<string> tags = {"news", "tech", "news"};
    cout << "Distinct tags: " << tags.size() << endl; // 2
    return 0;
}

// ✅ Expected output:
//    Unique sorted: 1 2 3 4
//    Count of distinct values: 4
//    Inserted 2? 0
//    Has 3? yes
//    Distinct tags: 2

5. Erasing Entries

Remove a single key with .erase(key). Removing entries while iterating needs care: map::erase returns an iterator to the next element, so the safe pattern is to assign that result back rather than incrementing a now-invalid iterator. In C++20 you can use the free function std::erase_if for a one-liner.

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

int main() {
    map<string, int> inventory = {
        {"sword", 1}, {"potion", 5}, {"shield", 2}, {"key", 3}
    };

    // Remove by key:
    inventory.erase("shield");

    // Remove entries whose value is below a threshold (C++20 erase_if):
    // erase_if(inventory, [](const auto& kv){ return kv.second < 3; });

    // Manual safe erase while iterating (works in all standards):
    for (auto it = inventory.begin(); it != inventory.end(); ) {
        if (it->second < 3) it = inventory.erase(it); // erase returns next
        else ++it;
    }

    for (const auto& [name, qty] : inventory) {
        cout << name << " x" << qty << endl;
    }
    // ✅ Expected (sorted): key x3, potion x5
    return 0;
}

// ✅ Expected output:
//    key x3
//    potion x5

🔎 Deep Dive: structured bindings & insert vs emplace

Since C++17 you can unpack a key/value pair directly in the loop header with structured bindings: for (const auto& [key, value] : myMap). It reads far better than entry.first / entry.second.

To add elements you can use .insert({key, value}) or .emplace(key, value). emplace constructs the element in place and can avoid a temporary. Both refuse to overwrite an existing key — use operator[] or .insert_or_assign() (C++17) when you intend to replace.

map<string,int> m;
m.emplace("a", 1);            // inserts a->1
m.insert({"b", 2});           // inserts b->2
m.insert({"a", 99});          // IGNORED: "a" already exists -> still 1
m["a"] = 99;                  // overwrites: now a->99
m.insert_or_assign("c", 3);   // inserts or replaces (C++17)
for (const auto& [k, v] : m)  // structured bindings
    cout << k << "=" << v << " ";

Pro Tips

• 💡 Default to unordered_map: unless you need sorted iteration or ordered range queries, the hash version is usually faster.
• 💡 Guard operator[]: it inserts missing keys. For read-only checks use .count(), .contains(), or .find().
• 💡 Counting idiom: ++counts[key]; is the canonical frequency-count one-liner — the missing key starts at 0.
• 💡 Deduplicate fast: dump a vector into a set (or unordered_set) to get unique values instantly.

🧠 Quick Recall

Predict the output before revealing the answer.

map<string,int> m;
m["x"]++;
m["x"]++;
cout << m["x"];

2 — the first m["x"] creates the key at 0, then two ++ raise it to 2.

2. What is the size after this runs?

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

3 — duplicates are dropped, leaving the unique values 1, 2, 3.

3. What does this print, and what is the size of m afterward?

map<string,int> m = {{"a", 5}};
cout << m["b"] << " " << m.size();

0 2 — reading m["b"] inserts "b" with value 0, so the map now holds two keys.

Common Errors (and the fix)

• Accidental insertion with []: checking if (m["key"]) inserts the key. Use if (m.count("key")) or if (m.contains("key")) instead.
• Iterator invalidation on erase: for (auto it = m.begin(); it != m.end(); ++it) m.erase(it); is undefined behaviour. Use it = m.erase(it); and only ++it when you don't erase.
• .at() on a missing key throws: m.at("nope") raises std::out_of_range. Check existence first, or catch the exception.
• Forgetting the header: you need #include <map>, #include <unordered_map>, #include <set>, or #include <unordered_set> as appropriate.
• Expecting order from unordered: never rely on the iteration order of unordered_map / unordered_set — switch to map / set if order matters.

📋 Quick Reference

Mini-Challenge: Vote Tallier

Combine everything: build a frequency map, iterate it, and find the maximum. The outline in the comments keeps you on track.

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

int main() {
    // 🎯 MINI-CHALLENGE: Vote tallier
    // 1. Given the votes below, build a map<string,int> of name -> count.
    // 2. Print every candidate and their vote count (map prints sorted).
    // 3. BONUS: find and print the winner (the key with the highest count).
    //
    string votes[] = {"Maya", "Leo", "Maya", "Maya", "Leo", "Zoe"};
    //
    // ✅ Example output:
    //    Leo: 2
    //    Maya: 3
    //    Zoe: 1
    //    Winner: Maya

    // your code here
    return 0;
}

🎉 Lesson Complete

• ✅ std::map stores sorted key→value pairs; access with m[key]
• ✅ std::unordered_map is hash-based with average O(1) lookup, no order
• ✅ operator[] inserts missing keys — use count/contains/find to check safely
• ✅ std::set and std::unordered_set store unique values; duplicates are ignored
• ✅ ++m[key] is the frequency-count idiom; structured bindings unpack pairs cleanly

Practice quiz

Continue this course

• Previous: Vectors (std::vector)
• Next: auto & decltype — Let the compiler deduce types
• Quick reference: C++ cheat sheet › STL Containers
• From the blog: C++ STL Containers: A Complete Guide

Frequently asked questions

When should I use std::map vs std::unordered_map?

Use std::unordered_map by default — it offers average O(1) lookup using a hash table and is usually faster. Reach for std::map when you need the keys kept in sorted order (so iteration is ordered) or need ordered operations like lower_bound. std::map is a balanced tree giving O(log n) operations.

What happens if I use map[key] for a key that doesn't exist?

operator[] inserts the key with a value-initialized value (0 for int, empty string for std::string) and returns a reference to it. That is convenient for counting, but it silently grows the map. If you only want to look without inserting, use .find() or .at() instead.

Why does std::set not allow duplicate values?

A set models a mathematical set: each element is unique. Inserting a value that already exists is simply ignored — .insert() returns a pair whose .second is false. If you need to allow duplicates, use std::multiset.

How do I check whether a key exists without inserting it?

Use .count(key) which returns 0 or 1 for a map/set, or .contains(key) in C++20 which returns a bool. Both leave the container unchanged, unlike operator[].

Are map and set ordered or unordered?

std::map and std::set are ordered (sorted by key, using < by default). std::unordered_map and std::unordered_set are unordered — iteration order is unspecified and can change as the table rehashes.