Back to all concepts
Intermediate 12 min

Map and Multimap

Master std::map and std::multimap for efficient key-value storage with automatic sorting and fast lookups

Master key-value storage with std::map and std::multimap for efficient lookups and automatic sorting by key.

A Simple Example 

#include <iostream>
#include <map>
#include <string>

int main() {
    // std::map - unique keys, sorted by key
    std::map<std::string, int> ages;

    // Insertion methods
    ages["Alice"] = 25;              // Using []
    ages.insert({"Bob", 30});        // Using insert
    ages.emplace("Charlie", 28);     // Construct in-place

    // Access
    std::cout << "Alice's age: " << ages["Alice"] << "\n";  // 25

    // DANGER: [] creates element if it doesn't exist!
    std::cout << "David's age: " << ages["David"] << "\n";  // Creates David with age 0

    // Safe access with find
    auto it = ages.find("Eve");
    if (it != ages.end()) {
        std::cout << "Eve's age: " << it->second << "\n";
    } else {
        std::cout << "Eve not found" << "\n";
    }

    // Iterate (sorted by key)
    std::cout << "\nAll ages:" << "\n";
    for (const auto& [name, age] : ages) {  // Structured binding (C++17)
        std::cout << name << ": " << age << "\n";
    }

    return 0;
}

Breaking It Down

std::map - Key-Value Pairs

  • What it is: Sorted associative container storing key-value pairs
  • Keys are unique and automatically sorted
  • O(log n) for insertion, deletion, and lookup
  • Use for: Dictionaries, caches, configurations, frequency counting

The [] Operator - Convenient but Dangerous

  • map[key] creates the key with default value if it doesn't exist
  • This makes map[key]++ work for counting (creates 0, then increments)
  • But if (map[key]) creates the key even when checking existence!
  • Remember: Use find() to check existence without creating entries

Accessing Elements Safely

  • find() returns iterator to element or end() if not found
  • at() throws exception if key doesn't exist (safer than [])
  • count() returns 0 or 1 for existence checking
  • Remember: it->first is the key, it->second is the value

std::multimap - Multiple Values per Key

  • What it is: Like map but allows duplicate keys
  • Cannot use [] operator (which key would it return?)
  • Use insert() and find() instead
  • Use for: One-to-many relationships (author to books, tag to posts)

Why This Matters

  • Maps are one of the most useful data structures in programming.
  • They're perfect for lookups (word to definition), caching (URL to cached data), counting (item to frequency), and configuration (setting name to value).
  • Understanding maps makes complex data relationships simple and efficient.

Critical Insight

The [] operator is both incredibly convenient and dangerously misleading. map[key] doesn't just look up a value - it creates an entry with a default value if the key doesn't exist!

This is why map[key]++ works for counting (creates 0, then increments to 1), but also why if (map[key]) can give wrong results (it creates the key with default value 0/false/empty).

Use find() when you need to check existence without creating entries!

Best Practices

Use find() for safe existence checks: Avoid using [] when you only want to check if a key exists, as it creates the key.

Prefer emplace() over insert(): emplace() constructs the element in-place, potentially avoiding copies.

Use structured bindings for clarity: for (const auto& [key, value] : map) is more readable than it->first and it->second.

Consider at() for safer access: at() throws an exception if the key doesn't exist, making bugs more obvious than silent default creation.

Common Mistakes

Using [] for existence checking: if (map[key]) creates the key if it doesn't exist! Use find() or count() instead.

Modifying keys: Map keys are immutable. To change a key, you must erase the old entry and insert a new one.

Iterator invalidation: Inserting or erasing invalidates only iterators to erased elements, not others.

Debug Challenge

This code should check if a key exists without creating it. Click the highlighted line to fix it:

1 #include <iostream>
2 #include <map>
3
4 int main() {
5 std::map<std::string, int> scores;
6 scores["Alice"] = 95;
7 if (scores["Bob"]) {
8 std::cout << "Bob found";
9 }
10 return 0;
11 }

Quick Quiz

  1. What does map["newkey"] do if "newkey" doesn't exist?
Creates "newkey" with default value and returns reference to it
Returns nullptr
Throws an exception
  1. What's the time complexity of map::find()?
O(log n)
O(1)
O(n)

Practice Playground

Time to try out what you just learned! Play with the example code below, experiment by making changes and running the code to deepen your understanding.

Lesson Progress

  • Fix This Code
  • Quick Quiz
  • Practice Playground - run once