特點比較

1. std::map

• 底層實現：基于紅黑樹（一種自平衡的二叉搜索樹）。
• 元素順序：元素按照鍵（key）的升序排列。
• 鍵的唯一性：每個鍵只能出現一次，插入重復鍵的元素會被忽略。
• 查找效率：查找操作的時間復雜度為 $O(logn)$，其中 $n$ 是容器中元素的數量。
• 插入和刪除效率：插入和刪除操作的時間復雜度也為 $O(logn)$。

2. std::unordered_map

• 底層實現：基于哈希表。
• 元素順序：元素沒有特定的順序，存儲位置由鍵的哈希值決定。
• 鍵的唯一性：每個鍵只能出現一次，插入重復鍵的元素會覆蓋原有的元素。
• 查找效率：平均情況下，查找操作的時間復雜度為 $O(1)$，但在最壞情況下可能達到 $O(n)$。
• 插入和刪除效率：平均情況下，插入和刪除操作的時間復雜度為 $O(1)$。

3. std::multimap

• 底層實現：同樣基于紅黑樹。
• 元素順序：元素按照鍵的升序排列。
• 鍵的唯一性：允許鍵重復，即可以有多個元素具有相同的鍵。
• 查找效率：查找操作的時間復雜度為 $O(logn)$。
• 插入和刪除效率：插入和刪除操作的時間復雜度為 $O(logn)$。

4. std::unordered_multimap

• 底層實現：基于哈希表。
• 元素順序：元素沒有特定的順序，由鍵的哈希值決定存儲位置。
• 鍵的唯一性：允許鍵重復。
• 查找效率：平均情況下，查找操作的時間復雜度為 $O(1)$，最壞情況下為 $O(n)$。
• 插入和刪除效率：平均情況下，插入和刪除操作的時間復雜度為 $O(1)$。

5. hash_map（SGI STL 擴展）

• 底層實現：基于哈希表。
• 元素順序：元素沒有特定的順序，由鍵的哈希值決定存儲位置。
• 鍵的唯一性：每個鍵只能出現一次，插入重復鍵的元素會覆蓋原有的元素。
• 查找效率：平均情況下，查找操作的時間復雜度為 $O(1)$，最壞情況下為 $O(n)$。
• 插入和刪除效率：平均情況下，插入和刪除操作的時間復雜度為 $O(1)$。
  在早期的 C++ 標準（如 C++98、C++03）中有 hash_map，不過它并非標準庫的一部分，而是來自于 SGI STL 擴展。在 C++11 及以后的標準中，hash_map 被 std::unordered_map 替代，std::unordered_map 成為標準的哈希表實現。不過有些編譯器仍然支持 hash_map，下面為你加入 hash_map 并進行比較，同時給出相應的 C++ 示例代碼。

C++ 示例代碼

#include <iostream>
#include <map>
#include <unordered_map>
#include <ext/hash_map>  // 對于支持 hash_map 的編譯器// 演示 std::map 的使用
void testStdMap() {std::map<int, std::string> myMap;myMap[1] = "apple";myMap[2] = "banana";myMap[1] = "cherry";  // 鍵 1 重復，會覆蓋原有的值std::cout << "std::map:" << std::endl;for (const auto& pair : myMap) {std::cout << pair.first << ": " << pair.second << std::endl;}
}// 演示 std::unordered_map 的使用
void testUnorderedMap() {std::unordered_map<int, std::string> myUnorderedMap;myUnorderedMap[1] = "apple";myUnorderedMap[2] = "banana";myUnorderedMap[1] = "cherry";  // 鍵 1 重復，會覆蓋原有的值std::cout << "\nstd::unordered_map:" << std::endl;for (const auto& pair : myUnorderedMap) {std::cout << pair.first << ": " << pair.second << std::endl;}
}// 演示 std::multimap 的使用
void testMultiMap() {std::multimap<int, std::string> myMultiMap;myMultiMap.insert({1, "apple"});myMultiMap.insert({2, "banana"});myMultiMap.insert({1, "cherry"});  // 鍵 1 重復，允許插入std::cout << "\nstd::multimap:" << std::endl;for (const auto& pair : myMultiMap) {std::cout << pair.first << ": " << pair.second << std::endl;}
}// 演示 std::unordered_multimap 的使用
void testUnorderedMultiMap() {std::unordered_multimap<int, std::string> myUnorderedMultiMap;myUnorderedMultiMap.insert({1, "apple"});myUnorderedMultiMap.insert({2, "banana"});myUnorderedMultiMap.insert({1, "cherry"});  // 鍵 1 重復，允許插入std::cout << "\nstd::unordered_multimap:" << std::endl;for (const auto& pair : myUnorderedMultiMap) {std::cout << pair.first << ": " << pair.second << std::endl;}
}// 演示 hash_map 的使用
void testHashMap() {__gnu_cxx::hash_map<int, std::string> myHashMap;myHashMap[1] = "apple";myHashMap[2] = "banana";myHashMap[1] = "cherry";  // 鍵 1 重復，會覆蓋原有的值std::cout << "\nhash_map:" << std::endl;for (const auto& pair : myHashMap) {std::cout << pair.first << ": " << pair.second << std::endl;}
}int main() {testStdMap();testUnorderedMap();testMultiMap();testUnorderedMultiMap();testHashMap();return 0;
}

代碼解釋

• testStdMap 函數演示了 std::map 的使用，插入重復鍵的元素會覆蓋原有的值，元素按照鍵的升序排列。
• testUnorderedMap 函數演示了 std::unordered_map 的使用，插入重復鍵的元素也會覆蓋原有的值，元素沒有特定的順序。
• testMultiMap 函數演示了 std::multimap 的使用，允許插入重復鍵的元素，元素按照鍵的升序排列。
• testUnorderedMultiMap 函數演示了 std::unordered_multimap 的使用，允許插入重復鍵的元素，元素沒有特定的順序。
• testHashMap 函數演示了 hash_map 的使用，插入重復鍵的元素會覆蓋原有的值，元素沒有特定的順序。

需要注意的是，hash_map 不是標準 C++ 的一部分，如果你使用的編譯器不支持 ext/hash_map 頭文件，代碼可能無法編譯。建議優先使用標準的 std::unordered_map。