map / multimap / unordered_map

map — unique sorted keys

• Keys are **unique** and **sorted**; each key maps to one value.
• operator[] **inserts** a default value if the key is missing.
• Prefer find / at when you must not insert accidentally (at throws if missing).
• **Real-life:** phone book (name → number); employee ID → salary in ID order; country code → capital.

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

int main() {
    map<string, int> ages;
    ages["Ann"] = 20;
    ages.insert({"Bob", 22});
    cout << ages["Ann"] << "\n";
    if (ages.find("Zoe") == ages.end()) cout << "missing\n";
    return 0;
}

multimap — duplicate keys allowed

• Same key can appear **many times** with different values.
• **No** operator[] — use insert and equal_range to read all values for a key.
• Useful for indexes: one category → many items.
• **Real-life:** student name → multiple course scores; department → many employees; tag → many blog posts.

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

int main() {
    multimap<string, int> scores;
    scores.insert({"Ali", 90});
    scores.insert({"Ali", 85});
    auto [lo, hi] = scores.equal_range("Ali");
    for (auto it = lo; it != hi; ++it)
        cout << it->second << " ";
    cout << "\n";
    return 0;
}

unordered_map — unique hashed keys

• Unique keys; **not sorted** — ideal for dictionaries and counters.
• Average **O(1)** lookup; [] inserts a default if missing.
• reserve(n) can reduce rehashing when size is known.
• **Real-life:** word frequency in a document; product SKU → price lookup; session token → user data cache.

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

int main() {
    unordered_map<string, int> cnt;
    cnt["apple"]++;
    cnt["apple"]++;
    cnt["banana"]++;
    cout << cnt["apple"] << "\n"; // 2
    return 0;
}

Common patterns

• Iterate: for (auto& [k, v] : m) (C++17 structured bindings).
• Check before insert: if (m.find(k) == m.end()) ….
• Counters: unordered_map + m[key]++ is a classic interview pattern.

Real-life examples by container

• Map everyday problems to the right map type.

Map family applications

• Maps appear whenever you look up or update data by a key.

When to use which

• Need ordered keys or range queries by key order → **map**.
• Need many values per key in order → **multimap**.
• Need speed and uniqueness, order irrelevant → **unordered_map**.
• **Real-life rule of thumb:** alphabetical directory → map; one person many records → multimap; cart/cache/counter → unordered_map.