Skip to content

← Containers, Strings, Algorithms step 3 of 5

Medium Primitives

The lookup that writes

Reading a map with operator[] can change it:

int score = scores[name];

If name exists, this reads its score. If it is absent, operator[] inserts it with a value-initialized mapped value, which is zero for int. That makes subscript useful for updates such as counting, but unsuitable for checking whether a key exists without inserting it.

Choose the lookup operation

These operations apply to a map with unique keys:

Operation Missing key Can insert? Available on a const map?
m[k] Inserts a value-initialized mapped value Yes No
m.at(k) Throws std::out_of_range No Yes
m.find(k) Returns m.end() No Yes
m.contains(k) Returns false No Yes, since C++20
m.count(k) Returns zero No Yes

A present key has count one regardless of its mapped value. In particular, a score of zero does not mean the key is missing.

Reuse the iterator when reading and updating

Calling contains or count, then subscript to read, then subscript to update searches for the same key repeatedly. find returns an iterator that lets you do all three jobs:

auto it = scores.find(name);
if (it != scores.end()) {
    int old_score = it->second;
    it->second += bonus;
    // use old_score
}

it->first is the key and it->second is its mapped value. A mutable map iterator lets you update that value directly. Always check against end() before accessing the element. This avoids a separate search for each access.

If insertion is intended, C++17 also provides try_emplace and insert_or_assign. try_emplace(k, args...) constructs a mapped value only when the key is absent; its argument expressions still run before the call. insert_or_assign(k, value) inserts a missing key or replaces an existing mapped value. Their non-hint overloads return an iterator and an insertion flag.

Choosing a map type

Property std::map std::unordered_map
Lookup complexity O(log n) Average O(1), worst case O(n)
Iteration Key order according to its comparator Unspecified order
Key operations A strict weak ordering comparator A hash and compatible equality predicate

The defaults commonly use < for ordered comparison and == for equality, but both containers accept custom operations. Choose based on ordering, workload and performance requirements. For reproducible output from an unordered map, collect and sort entries before writing them. This exercise uses std::map, so the harness can report final scores in key order.

Your task

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

Process queries in order:

  • For a present key, append its current score to the result, then add bonus to that score in the map.
  • For a missing key, append -1 and leave the map unchanged.

Repeated queries see earlier updates. For scores {"a": 0}, queries ["a", "missing", "a"] and bonus 2, return [0, -1, 2]. The final map contains only "a", with score 4.

Negative scores and bonuses are allowed; test updates fit in int. A real score of -1 is still present and must receive the bonus, even though the output also uses -1 for a miss. Determine presence from the key lookup.

The harness reports the results, final map size and final scores in key order. It checks behaviour, including accidental insertions and zero-valued scores; it does not count how many searches your implementation performs.