An unordered map can retrieve a value by key without maintaining sorted key order. Its usefulness depends on a coherent equality and hash policy. If two equivalent keys produce different hashes, the container's assumptions are broken. Rehashing also changes traversal validity even when references to existing elements remain usable.
This guide uses C++17. You will build a composite warehouse-location key, reserve capacity without relying on bucket counts, and produce sorted reporting from unordered storage. The examples never claim a particular iteration order or print a supposedly permanent hash identifier. Hash-based lookup is an implementation strategy, not a durable identity contract.
Equality defines key equivalence
An unordered set stores keys, while an unordered map associates keys with values. Their equality predicate determines whether two keys represent the same key for that container. It must be an equivalence relation, including symmetry and transitivity. A product-code policy that ignores case must apply that same rule consistently.
The hash function must return equal hashes for equivalent keys. Unequal keys can collide, because a hash has finite size. The container uses equality to distinguish candidate entries within its lookup structure. A hash value therefore cannot replace the original key or prove identity. Do not persist it as a permanent database ID or assume it remains identical across implementations and library versions.
Composite keys need matching fields
A location might be identified by warehouse and shelf together. Equality should compare both fields, and hashing should combine both under a compatible policy. If equality ignores one field but hashing includes it, equivalent keys can be assigned different hashes. If hashing ignores a field that equality uses, correctness may remain possible but distribution can become poor.
Keep key identity stable while stored. Map keys are exposed as const within entries, which helps prevent casual mutation, but pointer-based keys can refer to externally mutable data. A hash or equality function that reads changing pointed-to state can still break the contract. Prefer owned immutable key values whose meaning does not depend on unrelated global configuration.
Average efficiency is not a worst-case guarantee
Unordered lookup commonly has favorable average complexity under a useful distribution. Collisions can worsen behavior, and the standard's worst-case contract is not constant time. Bound untrusted input counts and key lengths even when the chosen container usually performs well.
Reserve can reduce rehashing when an approximate entry count is known. It does not impose a maximum size or promise an exact bucket count. The implementation chooses details under its contract. Max_load_factor and rehash are tuning controls, not substitutes for measuring the actual workload. Avoid oversizing from an unvalidated user value because the capacity request itself can create excessive memory pressure.
Rehash affects iterators differently from references
Rehashing invalidates iterators and can change traversal order and bucket placement. Pointers and references to existing elements remain valid under the specified rehash contract. Erasing an element still invalidates access to that element, and destroying the container ends all its element lifetimes.
Do not keep an iterator and use it after reserve or insertion that may rehash. Reacquire it through lookup when needed. Reference stability does not make mutation concurrent-safe, and a mapped object's own internals can have additional invalidation rules. If the mapped value is a vector, a reference to that vector can remain while a pointer to one of its elements is invalidated by the vector's growth.
Lookup can accidentally mutate the map
The map's operator[] inserts a default mapped value when a key is absent. That is convenient for counting, but unsuitable when a read-only lookup must not create entries. Use find or at according to the missing-key contract. Find permits an explicit branch; at throws for a missing key.
Try_emplace can insert only when absent without replacing an existing mapped value. Insert_or_assign expresses replacement intentionally. Choose the operation from the required transition rather than using the indexer everywhere. An unexpected default entry can make later logic believe a record exists, so test both present and absent cases.
Test behavior instead of implementation details
Test independent equivalent keys, unequal keys, missing lookups, duplicate insertion and lookup after enough growth to exercise rehash possibilities. Avoid asserting an exact bucket count or hash number unless you are testing a specifically documented custom algorithm as its own feature.
A custom equality policy should have tests for symmetry and representative transitivity cases. Verify that equivalent keys have equal hashes. A constant hash is technically compatible with equality but can have poor performance, so correctness tests alone do not establish useful distribution. Separate the key's meaning, container correctness and measured performance when reviewing a hashing design.
Official references
C++ Unordered Containers and Hashing Examples
Each example shows the code, the output it produces and what each part does.
A composite location key
This complete program defines equality and a small hash combiner for a pair of integers. The demonstration prints lookup results rather than bucket order.
The simple combiner illustrates the equality contract; it is not a cryptographic hash or a recommendation for every adversarial workload. Rehashing does not invalidate this reference to an existing element under unordered-container rules.
#include <cstddef>
#include <functional>
#include <iostream>
#include <unordered_map>
struct Location {
int warehouse;
int shelf;
bool operator==(const Location& other) const noexcept {
return warehouse == other.warehouse && shelf == other.shelf;
}
};
struct LocationHash {
std::size_t operator()(const Location& key) const noexcept {
std::size_t first = std::hash<int>{}(key.warehouse);
std::size_t second = std::hash<int>{}(key.shelf);
return first ^ (second << 1);
}
};
int main() {
std::unordered_map<Location, int, LocationHash> stock;
stock.try_emplace(Location{1, 2}, 5);
stock.try_emplace(Location{1, 3}, 9);
int& selected = stock.at(Location{1, 2});
std::cout << "Before: " << selected << '\n';
stock.reserve(50);
selected += 3;
std::cout << "After: " << stock.at(Location{1, 2}) << '\n';
}Before: 5
After: 8C++ Unordered Containers and Hashing in Real Projects
Worked exercise: count words and report in sorted order
The task is to count a bounded set of words through unordered lookup, then print stable alphabetic output. Incrementing the indexer is intentional here because a missing word should start at zero. Reporting creates a separate sorted snapshot rather than depending on hash traversal order.
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
int main() {
std::unordered_map<std::string, int> counts;
for (const std::string word : {"bolt", "nut", "bolt", "washer"})
++counts[word];
std::vector<std::pair<std::string, int>> report(
counts.begin(), counts.end());
std::sort(report.begin(), report.end(),
[](const auto& left, const auto& right) {
return left.first < right.first;
});
for (const auto& [word, count] : report)
std::cout << word << ": " << count << '\n';
}bolt: 2
nut: 1
washer: 1The lookup representation and presentation order serve different needs. A map would be another reasonable choice when sorted traversal is required throughout the workflow rather than only for an occasional report.
C++ Unordered Containers and Hashing FAQ
Can different keys have the same hash?
Yes. Hash collisions are expected in a finite representation. The container checks equality to distinguish keys that share a lookup area. Equal keys must hash equally, but equal hashes do not prove equal keys. Keep the original key available and never use a hash alone as a permanent identity or as evidence that a record matches.
Why not rely on unordered iteration order?
The container does not promise a sorted order, and rehashing or an implementation change can alter traversal. A report requiring stability should sort an explicit snapshot or use an ordered representation. Tests should assert the required presentation order rather than the incidental order seen on one compiler. The main example avoids that dependency entirely.
Does reserve invalidate every reference?
For unordered containers, rehash invalidates iterators but does not invalidate pointers or references to existing elements under the specified rule. Erasure and destruction have different consequences. Do not generalize this rule to vector or to objects nested inside a mapped value. Review each owner's own operation contract and keep retained handles limited to the necessary lifetime.
When is operator[] appropriate?
Use it when insertion of a default mapped value is intended, such as beginning a word count at zero. For an observation that must not create records, use find or at. The choice changes application state, so it should be explicit. Test missing-key behavior and avoid silently creating zero-valued inventory entries when the correct response is an unknown product.
C++ Unordered Containers and Hashing Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
A report must print unordered-map entries in alphabetic key order. Which design fits?
C++ Unordered Containers and Hashing Quiz
2 questions to check what you learned.
Which equality/hash rule is required?
- Equivalent keys must produce equal hashes.
- Every unequal key must have a unique hash.
- Hashes must be sorted in iteration order.
- Hash values must remain permanent external identifiers.
What can operator[] do when the key is absent?
- Always return a read-only missing marker.
- Insert a default mapped value.
- Return a missing marker without changing the map.
- Prevent future rehashing.