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 turn: 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

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