std::unordered_map
- C++ course
- Intermediate
- Lesson 56/116
- 5 min
Learn hash-based maps with std::unordered_map.
std::unordered_map
std::unordered_map is a hash-table-based key-value container. Average insert and access are O(1). Elements are not ordered; when order doesn't matter, it is faster than map.
Example: std::unordered_map<std::string, int> m; m["apple"] = 3;. m["apple"] returns 3 in average O(1). In map the same operation is O(log n). When sorted traversal isn't needed, unordered_map is preferred. The key type must have a std::hash specialization; std::string and primitive types already do.
Hash function
unordered_map distributes keys into buckets via a hash function. Good distribution gives O(1); bad distribution degrades to O(n). Collisions are resolved by separate chaining.
Custom types need a hash specialization. std::string, int, double have std::hash ready. Example: std::hash<std::string> turns a string into an integer. This integer gives the bucket index. On m["apple"] = 3;, the hash is computed first, then the bucket is found.
Practice Work with unordered_map
Create std::unordered_map<std::string, int> m;. Add m["apple"] = 3; and m["pear"] = 5;. Print m.size().
Starter code
#include <iostream>
#include <unordered_map>
#include <string>
// create an unordered_map and add two items
int main() {
// print the size
return 0;
}Sample solution
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<std::string, int> m;
m["apple"] = 3;
m["pear"] = 5;
std::cout << m.size() << std::endl;
return 0;
}Expected output
2
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is the advantage of unordered_map?
std::unordered_map<std::string, int> m;- Sorted keys
- Average O(1) access Correct answer
- Less memory
- Fixed size
Explanation: unordered_map provides average O(1) access.
2 unordered_map declaration
std::unordered_map<std::string, ____> m;std::unordered_map<std::string, int> m;Explanation: The value type is int; std::unordered_map<std::string, int> m;
3 Match the concept
| Term | Meaning |
|---|---|
hash table |
unordered_map base |
O(1) lookup |
Fast access |
unordered |
Not sorted |
bucket |
Hash slot |