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?
Returns nullptr
Throws an exception
Returns an empty optional
Creates "newkey" with default value and returns reference to it
  1. What's the time complexity of map::find()?
O(1)
O(n)
O(log n)
O(n log n)

Step Through the Code

Walk through the code step by step. Watch how variables change and see the program output at each line.

Lesson Progress

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