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.