Hashing and exact-key queries
Understand unordered maps, deterministic output, and average versus worst-case cost.
Same records, different guarantees
std::unordered_map, from <unordered_map>, also associates one value with each unique key. Hashing selects buckets and equality checks distinguish keys within them. Different keys can collide without overwriting each other.
Traversal is neither promised to be sorted nor to follow insertion order. begin() does not mean minimum. There are no ordered lower_bound, upper_bound, or rank-selection member operations. Exact-key lookup, insertion, and key erasure are average O(1) for fixed-size keys but can be O(d) in the worst case.
Keep missing queries read-only
The subscript insertion rule still applies. Query with find and return zero on absence if the problem asks for a missing key’s frequency; this preserves the number of distinct input keys.
For sorted output, either use std::map or copy hash entries into a vector and sort it. That extra sort costs O(d log(d + 1)); a hash build followed by sorted output is not simply O(n). Include copied records, buckets, and key text in storage estimates.
// Complete C++23 program. Input: n q, n keys, q query keys.
#include <iostream>
#include <unordered_map>
int main() {
int n, q;
std::cin >> n >> q;
std::unordered_map<int, int> frequency;
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
++frequency[x];
}
while (q--) {
int x;
std::cin >> x;
auto it = frequency.find(x);
std::cout << (it == frequency.end() ? 0 : it->second)
<< '\n';
}
std::cout << frequency.size() << '\n';
}Optional tuning: reserve and rehash
reserve(n) plans bucket room for roughly n entries under the current maximum load factor; it inserts no records. rehash(b) requests a bucket-count lower bound subject to load requirements, not an exact bucket count. Set a chosen max_load_factor before reserve, and avoid repeatedly reserving in a tight loop.
Rehashing invalidates iterators and can change traversal order, but references and pointers to surviving elements remain valid. Insertion can trigger rehashing, so reacquire iterators after operations that may rehash. Erasing an element still invalidates references to that element. Reserving does not remove collisions or promise worst-case constant lookup.
Word frequency map
Split on whitespace. Keys are case-sensitive; punctuation stays attached. Displayed in sorted key order like std::map<string, int>.
code3learn2solve16 words · 3 distinct keys
Guided simulation · Change the inputs to test your understanding.
An empty unordered_map reserves room for 1000 entries. Which statement is guaranteed?
Turn the idea into code
A frequency hash map contains 8 → 2, 2 → 2, 3 → 1. Query absent key 99 without changing the final distinct count. How would you print all records in sorted order?
Give me a hint
Separate exact-key lookup from output ordering.
Show the explained solution
Use find(99); its end() result means output zero, and size() stays 3. For deterministic numeric order, copy entries into a vector of pairs and sort it, or build an ordered map originally. A direct hash traversal does not guarantee 2, 3, 8.
Your notes
Mark complete when you can explain it yourself.