std::map and std::unordered_map

Why maps?

Often you need to look things up by a name or ID instead of a position: the price of an item by its code, the number of votes per candidate, the stock left per product. A map (also called a dictionary or associative array) stores pairs of key and value, and finds the value for a key quickly. Each key appears at most once.

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

int main() {
    std::map<std::string, int> stock;
    stock["rice"] = 40;
    stock["dal"] = 25;
    stock["atta"] = 60;
    stock["rice"] -= 5;                    // update existing key

    for (const auto& [item, qty] : stock) {   // sorted by key
        std::cout << item << ": " << qty << '\n';
    }
    // atta: 60
    // dal: 25
    // rice: 35
}

The operator[] trap

std::map<std::string, int> price = {{"tea", 15}};
if (price["coffee"] == 0) {      // BUG: this INSERTS "coffee" with value 0
    std::cout << "not sold\n";
}
std::cout << price.size();       // 2, not 1

// Correct ways to check:
if (price.count("coffee") == 0) { }          // count is 0 or 1 for map
if (price.find("coffee") == price.end()) { } // find returns end() when missing
if (!price.contains("coffee")) { }           // C++20

Counting with a map

std::vector<std::string> votes = {"Asha", "Ravi", "Asha", "Meena", "Asha"};
std::unordered_map<std::string, int> count;
for (const auto& v : votes) ++count[v];     // missing keys start at 0
std::cout << count["Asha"] << '\n';         // 3

map versus unordered_map

Hashing in one paragraph

A hash function turns a key (like "rice") into a number. The unordered_map uses that number to choose a bucket (a slot in an internal array). Different keys can land in the same bucket (a collision); then the map must compare keys inside the bucket. With a good hash, buckets stay small and lookups are O(1) on average. With a bad hash or carefully chosen hostile input, everything lands in one bucket and lookups become O(n).

Useful operations

• m.insert({key, value}) or m.emplace(key, value) adds only if the key is not there yet.
• m.insert_or_assign(key, value) (C++17) adds or overwrites.
• m.erase(key) removes a key.
• m.at(key) returns the value or throws std::out_of_range if the key is missing (works on const maps).
• std::multimap / std::unordered_multimap allow repeated keys.