Skip to content

← Containers, Strings, Algorithms step 3 of 5

Medium Primitives

The lookup that writes 

int score = scores[name];

In most languages that line reads. In C++ it reads and, if the key is not there, inserts it with a value-initialised value — a zero, an empty string, an empty vector — and hands you a reference to that.

This is not a wart; operator[] has to return a reference you can assign through, and it cannot do that for a key that does not exist. But it means the read-only-looking line above can grow your map, and the growth is invisible until something iterates it.

The tell is that operator[] does not exist on a const map. If you have ever had to remove a const to make a lookup compile, that was the language telling you the lookup was a write.

The catalogue

Missing key Inserts On a const map
m[k] inserts {} yes does not compile
m.at(k) throws std::out_of_range no fine
m.find(k) returns end() no fine
m.contains(k) returns false no fine (C++20)
m.count(k) returns 0 no fine

One lookup, not two

This is the shape almost everyone writes first:

if (m.count(k) > 0) {      // lookup 1
    use(m[k]);             // lookup 2
    m[k] += 1;             // lookup 3
}

Three searches of the same tree for one key. The alternative asks once and keeps the answer:

auto it = m.find(k);       // the only lookup
if (it != m.end()) {
    use(it->second);
    it->second += 1;
}

An iterator into a map is a handle on the element. it->first is the key, it->second is the value, and writing through it->second writes into the map. Nothing needs to be looked up again.

For the insert side, C++17 added the ones that also ask only once:

m.try_emplace(k, args...);      // constructs only if absent
m.insert_or_assign(k, value);   // sets it either way, tells you which

map or unordered_map?

std::map std::unordered_map
Lookup O(log n) O(1) average
Order sorted by key none, and it changes
Needs operator< a hash and operator==

Reach for unordered_map unless you need the ordering — but note that iteration order is genuinely unspecified, so anything that prints or hashes the contents of one is not reproducible.

Your task

std::vector<int> lookup(std::map<std::string, int>& scores,
                        const std::vector<std::string>& queries, int bonus);

For each query, in order:

  • if the key is present, record its current score and then add bonus to it;
  • if it is absent, record -1 and leave the map alone.

A score of 0 is a real score. The harness reports the results, the map’s final size, and its values in key order — so an accidental insertion and a zero mistaken for a miss are both caught.