C++std::map | std::unordered_map | |
|---|---|---|
| Cấu trúc nội bộ | Red-Black Tree | Hash Table |
| Thứ tự key | Có thứ tự | Không có thứ tự |
| find / insert / erase | O(log n) | O(1) trung bình, O(n) worst |
| Iterator hợp lệ | giữ nguyên sau insert | có thể invalid sau rehash |
| Key yêu cầu | operator< | std::hash<K> + operator== |
Chọn map khi: cần duyệt theo thứ tự key, range query (lower_bound), key là kiểu không hash được.
Chọn unordered_map khi: ưu tiên tốc độ lookup, không cần thứ tự, key là string/int thông thường.
std::map | std::unordered_map | |
|---|---|---|
| Internal structure | Red-Black Tree | Hash Table |
| Key order | Sorted | Unordered |
| find / insert / erase | O(log n) | O(1) average, O(n) worst |
| Iterator validity | preserved after insert | may invalidate after rehash |
| Key requirement | operator< | std::hash<K> + operator== |
Choose map when: you need sorted iteration, range queries (lower_bound), or a non-hashable key type.
Choose unordered_map when: lookup speed is the priority, order doesn't matter, key is a common type (string/int).