pair, map, and unordered_map

How a vector grows

Lesson 8-1 described a vector as an RAII-managed heap array. When it grows past its current capacity, it allocates a bigger block, roughly double the size, moves the elements over, and frees the old block.

That reallocation is why push_back is fast on average rather than always, and why you never touch new[] or delete[] yourself. This lesson adds the other workhorse container, the map, which looks values up by key instead of by index.

Looking things up by key

If you take one interview tool from this course, make it the hash map. Counting occurrences and answering whether something has been seen before are the beating heart of hundreds of problems.

Swapping a nested-loop O(n²) brute force for one map pass at O(n), in lesson 8-4's terms, is the single most common optimization interviewers want to see.

pair: two values traveling together

#include <utility>
std::pair<std::string, int> p = {"alice", 30};
p.first    // "alice"
p.second   // 30

STL maps store their entries as pairs, so .first and .second come up constantly.

map and unordered_map: Python's dict, twice

#include <map>
std::map<std::string, int> age;
age["alice"] = 30;          // insert or overwrite
age["bob"]++;               // a missing key is inserted as 0, then incremented
age.count("alice")          // 1 if present, 0 if not
age.erase("bob");

for (const auto& kv : age)  // iterates in SORTED key order
    std::cout << kv.first << " " << kv.second << "\n";

std::map keeps its keys sorted using a balanced tree underneath, so lookup and insert both cost O(log n), which is the repeated-halving cost from lesson 8-4, and iteration comes out ordered. std::unordered_map is a hash table, like Python's dict, averaging O(1) lookup but iterating in no useful order.

Reach for unordered_map for pure speed, and map when you need sorted keys or predictable iteration.

One trap deserves emphasis: age["carol"] on a missing key inserts carol with value 0, even inside a read-only-looking expression. Check existence with .count(k) or .find(k) when that is not what you want.

Counting word frequencies

The most reused interview pattern in the language. A map keeps the output alphabetical without any sorting step.

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

int main() {
    std::map<std::string, int> freq;

    std::string w;
    while (std::cin >> w) {     // read words until input ends
        freq[w]++;              // missing key starts at 0
    }

    for (const auto& kv : freq) {
        std::cout << kv.first << ": " << kv.second << "\n";
    }
    return 0;
}

Input

the cat and the dog and the bird

Output

and: 2
bird: 1
cat: 1
dog: 1
the: 3

The whole count is one line, freq[w]++, and it works because a missing key is inserted with a value of 0 before the increment. This is the one case where the auto-insertion trap is a feature, since the alternative would be an explicit check for whether the word had been seen.

while (std::cin >> w) is a new shape worth noting. The stream extraction returns the stream, which converts to false when a read fails, so the loop ends at end of input. That is the standard way to consume an unknown number of values.

The alphabetical output is free, coming from the map's sorted tree rather than from any code here. An unordered_map would count identically and print in an arbitrary order, so this is a case where map earns its extra log factor.

The loop variable is const auto& kv, which avoids copying each pair and forbids modifying the map while walking it, exactly as lesson 8-3 recommends.

Choosing between the two maps

When you need the fastest possible average-case lookups and do not care about ordering, the answer is std::unordered_map.

It is a hash table, giving average O(1) insert and lookup against map's O(log n) tree. The price is losing sorted iteration, and also losing the worst-case guarantee, since a hash table degrades to O(n) if many keys collide in the same bucket. That degradation is rare with the standard hash functions and common in adversarially constructed test data.

In interviews, reach for unordered_map by default and switch to map only when order matters. Order matters more often than people expect, including whenever the expected output is sorted, whenever you need the smallest or largest key, or whenever the answer depends on a range of keys.

One practical constraint: unordered_map needs a hash function for its key type, and the standard library supplies those for the built-in types and std::string but not for a std::pair or your own structs. map only needs operator<, which is why a map<pair<int,int>, int> compiles while the unordered version does not.

Character counts in alphabetical order

A map<char, int> counting the characters of a word, which sorts the output for free.

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

int main() {
    std::string w;
    std::cin >> w;

    std::map<char, int> freq;
    for (char c : w) {
        freq[c]++;
    }

    for (const auto& kv : freq) {
        std::cout << kv.first << " " << kv.second << "\n";
    }
    return 0;
}

Input

hello

Output

e 1
h 1
l 2
o 1

Four lines come out of a five-character word, because the two l characters collapse into one entry with a count of 2. The number of lines is the number of distinct characters, which is a useful thing to notice when a problem asks about uniqueness.

The keys sort as characters, and since lesson 8-2 established that chars are small integers, that means they sort by character code. For lowercase input that is alphabetical, but mixed-case input would put every uppercase letter before every lowercase one, since 'Z' has a smaller code than 'a'.

The counting loop is a range-based for over the string, taking each char by value, which is right because copying a char is free and the loop only reads.

Character counts with a hash map

The same counting pass using unordered_map, then reading three specific keys back out.

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::string s = "abracadabra";
    std::unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
    std::cout << freq['a'] << " " << freq['b'] << " " << freq['r'] << "\n";
    return 0;
}

Output

5 2 2

One line does all the work, since freq[c]++ inserts a missing key as 0 and then increments it. The loop over the string is the range-based for from lesson 8-3.

Reading with freq['a'] is safe here because all three characters are known to be present, and this is exactly where the insertion trap would bite otherwise. A lookup of freq['z'] would print 0 and also add a 'z' entry to the map, silently growing it during what looked like a read. Using freq.count('z') first, or freq.at('z') which throws instead of inserting, avoids that.

The unordered_map is the right choice here because nothing iterates over the container. The three lookups are explicit, so the missing ordering costs nothing, and the counts are the same either way.