std::unordered_map

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.

Exercise Work with unordered_map

Create std::unordered_map<std::string, int> m;. Add m["apple"] = 3; and m["pear"] = 5;. Print m.size().

Show example 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;
}

Test yourself

What is the advantage of unordered_map?
```
std::unordered_map<std::string, int> m;
```
- Sorted keys
- Average O(1) access
- Less memory
- Fixed size
Show answer

Average O(1) access — unordered_map provides average O(1) access.

unordered_map declaration

std::unordered_map<std::string, ____> m;

Show answer

std::unordered_map<std::string, int> m;

Match the concept

hash table

unordered_map base
O(1) lookup

Fast access
unordered

Not sorted
bucket

Hash slot

Next lesson: std::set

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies