std::unordered_map 和 std::map 是 C++ 標準庫中兩種不同的關聯容器，它們都用于存儲鍵值對，但在實現方式、性能特點和使用場景上存在顯著區別。以下是它們的主要區別：
1. 數據結構
std::map：- 基于 紅黑樹（一種自平衡二叉搜索樹）實現。
- 鍵值對按照鍵的順序存儲，支持有序遍歷。
std::unordered_map：- 基于 哈希表 實現。
- 鍵值對存儲在哈希表中，不保證順序。
2. 性能特點
- 查找操作：
std::map：平均時間復雜度為 O(log n)，因為需要在紅黑樹中進行二分查找。std::unordered_map：平均時間復雜度為 O(1)，但在最壞情況下（大量沖突）可能退化到 O(n)。
- 插入操作：
std::map：平均時間復雜度為 O(log n)，因為需要在紅黑樹中插入節點并保持平衡。std::unordered_map：平均時間復雜度為 O(1)，但在最壞情況下可能退化到 O(n)。
- 刪除操作：
std::map：平均時間復雜度為 O(log n)，因為需要在紅黑樹中刪除節點并保持平衡。std::unordered_map：平均時間復雜度為 O(1)，但在最壞情況下可能退化到 O(n)。
3. 內存使用
std::map：- 內存使用較為緊湊，因為紅黑樹的節點結構相對簡單。
std::unordered_map：- 通常需要預留一定的空間來減少沖突，因此可能占用更多的內存。
4. 順序
std::map：- 鍵值對按照鍵的順序存儲，支持有序遍歷。
- 可以通過迭代器按順序訪問所有元素。
std::unordered_map：- 不保證鍵值對的順序，遍歷時的順序是不確定的。
5. 適用場景
std::map：- 適用于需要按鍵的順序訪問元素的場景。
- 適用于需要頻繁進行范圍查詢的場景。
std::unordered_map：- 適用于需要快速查找、插入和刪除操作的場景。
- 適用于鍵的順序不重要的場景。
示例代碼
std::map
#include <iostream>
#include <map>int main() {std::map<int, std::string> m;m[1] = "one";m[3] = "three";m[2] = "two";// 遍歷 map，按鍵的順序輸出for (const auto& pair : m) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}
std::unordered_map
#include <iostream>
#include <unordered_map>int main() {std::unordered_map<int, std::string> um;um[1] = "one";um[3] = "three";um[2] = "two";// 遍歷 unordered_map，順序不確定for (const auto& pair : um) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}
總結
std::map：- 基于紅黑樹實現，支持有序遍歷。
- 查找、插入和刪除操作的平均時間復雜度為 O(log n)。
- 適用于需要按鍵的順序訪問元素或進行范圍查詢的場景。
std::unordered_map：- 基于哈希表實現，不保證順序。
- 查找、插入和刪除操作的平均時間復雜度為 O(1)。
- 適用于需要快速查找、插入和刪除操作的場景。
選擇哪種容器取決于你的具體需求，例如是否需要有序遍歷、是否需要高效查找等。
