Chapter 31

Home

Maps and Dictionaries

An array maps an index to a value — but only if the index is a non-negative integer. A map (or dictionary) lets you use any type as a key: strings, tuples, even custom objects. If you can hash it, you can map it.

Why Not Just an Array?

Suppose you need to count how many times each word appears in a text. You can't use count["apple"] with an array — arrays need integer indices. A map handles this naturally.

Key → Value "apple" → 5 "banana" → 3 O(1) average lookup hash("apple") → index Lookup regardless of size

C++ — std::unordered_map

#include <bits/stdc++.h>
using namespace std;

int main() {
    // (hash map — O(1) average)
    unordered_map<string, int> freq;

    freq["apple"] = 5;
    freq["banana"] = 3;
    freq["apple"]++;  // now 6

    cout << freq["apple"] << "\n";   // 6
    cout << freq.size() << "\n";     // 2

    // Check if key exists
    if (freq.count("cherry")) {
        cout << "found\n";
    }

    return 0;
}

Accessing a missing key inserts it with a default value (0 for int).

Rust — HashMap

use std::collections::HashMap;

fn main() {
    let mut freq: HashMap<String, i32> = HashMap::new();

    freq.insert("apple".to_string(), 5);
    freq.insert("banana".to_string(), 3);
    *freq.entry("apple".to_string()).or_insert(0) += 1;

    println!("{}", freq["apple"]);        // 6
    println!("{}", freq.len());           // 2

    // Check if key exists
    if freq.contains_key("cherry") {
        println!("found");
    }
}

.entry().or_insert() is the Rustic way to get-or-create. It returns a mutable reference.

🚨 C++: missing keys are auto-inserted

freq["cherry"] in C++ inserts a default entry (0) if the key doesn't exist. If you just want to check existence, use freq.count("cherry") (returns 0 or 1) or freq.find("cherry") (returns iterator or end()).

Ordered vs Unordered

Two flavours of map in both languages:

Unordered (hash map)

unordered_map (C++) / HashMap (Rust) — O(1) average insert/lookup, but keys are unordered. Use this for most competitive programming.

Ordered (tree map)

map (C++) / BTreeMap (Rust) — O(log N) operations, but keys stay sorted. Use this when you need to iterate keys in order, or find the smallest key ≥ some value.

When order matters — std::map

// C++ — ordered map (keys sorted alphabetically)
map<string, int> scores;
scores["zebra"] = 10;
scores["apple"] = 5;
scores["mango"] = 7;

for (auto& p : scores) {
    cout << p.first << ": " << p.second << "\n";
}
// Output:
// apple: 5
// mango: 7
// zebra: 10

Common Patterns

Frequency counting

// C++
for (char c : s) freq[c]++;
// Rust
for c in s.chars() { *freq.entry(c).or_insert(0) += 1; }

Two-sum problem (store value → index)

// C++ — find two numbers that add to target
unordered_map<int,int> seen;
for (int i = 0; i < nums.size(); i++) {
    int need = target - nums[i];
    if (seen.count(need)) {
        cout << seen[need] << " " << i << "\n";
    }
    seen[nums[i]] = i;
}

Key Takeaways

Practice