Step 3 of 5

A string-keyed map with erase

A map is a set that carries a value with each key. The buckets store key/value pairs instead of bare keys, and every operation hashes the key, goes to one bucket, and works on that one short list.

#include <functional>
#include <iostream>
#include <list>
#include <string>
#include <utility>
#include <vector>

int main() {
    using Bucket = std::list<std::pair<std::string, double>>;
    std::vector<Bucket> table(8);
    auto bucket_for = [&](const std::string& k) -> Bucket& {
        return table[std::hash<std::string>{}(k) % table.size()];
    };

    // put: overwrite if the key exists, else append
    auto put = [&](const std::string& k, double v) {
        for (auto& [key, val] : bucket_for(k)) {
            if (key == k) { val = v; return; }
        }
        bucket_for(k).emplace_back(k, v);
    };
    // erase: find the pair's position in its list and remove it
    auto erase = [&](const std::string& k) {
        Bucket& b = bucket_for(k);
        for (auto it = b.begin(); it != b.end(); ++it) {
            if (it->first == k) { b.erase(it); return true; }
        }
        return false;
    };

    put("gold", 1900.5);
    put("silver", 23.1);
    put("gold", 1950.0);                       // overwrite
    std::cout << erase("silver") << erase("copper") << "\n";
    for (const auto& b : table)
        for (const auto& [k, v] : b) std::cout << k << " = " << v << "\n";
}

10
gold = 1950

How it works

• put searches the key's bucket. If the key is already there, it overwrites the value through a reference (auto& [key, val]); otherwise it appends a new pair.
• erase walks the bucket with an iterator, because list::erase needs one. It returns right after erasing, so the now-invalid iterator is never used again.
• Iterating over the whole table visits every pair, in no meaningful order. That's why unordered_map has "unordered" in its name.

Returning "maybe a value" as a pointer

Your get returns const int*: a pointer to the value inside the table if the key exists, or nullptr if it doesn't. It avoids copying and signals "missing" without a separate flag, which is how many C-style APIs work. &pair.second gives the pointer. Remember to adjust size_ in put (only for new keys) and in erase.

std::hash<std::string> hashes strings for you. (Under the hood it runs something like the FNV or MurmurHash functions over the bytes.)

Your task

Write StrMap (a fixed 64 buckets is fine here) with:

• void put(const std::string& key, int value): insert or overwrite
• const int* get(const std::string& key) const: pointer to the value, or nullptr
• bool erase(const std::string& key)
• std::size_t size() const

Challenge 2

Add two functions to StrMap. int& at_or_insert(const std::string& key) returns a reference to the key's value, first inserting it with value 0 if it's missing (like std::unordered_map::operator[]). std::vector<std::string> keys() const returns all keys, sorted.

Challenge 3

Now use the standard std::unordered_map. Write std::vector<std::pair<std::string, int>> top_words(const std::string& text, int k): split the text into words (runs of lowercase letters a to z; everything else separates words), count them, and return the k most frequent, highest count first and alphabetical on ties.

Previous: Load factor and rehashing Next: Hashing your own keys