快捷導(dǎo)航

C++?各種map特點(diǎn)對比分析

更新時(shí)間：2025年03月22日 13:43:16 作者：越甲八千

文章比較了C++中不同類型的map（如std::map,?std::unordered_map,?std::multimap,?std::unordered_multimap,?hash_map）的底層實(shí)現(xiàn)、元素順序、鍵的唯一性以及查找和插入刪除操作的效率,感興趣的朋友一起看看吧

特點(diǎn)比較

1. std::map

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

2. std::unordered_map

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

3. std::multimap

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

4. std::unordered_multimap

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

5. hash_map（SGI STL 擴(kuò)展）

底層實(shí)現(xiàn)：基于哈希表。
元素順序：元素沒有特定的順序，由鍵的哈希值決定存儲位置。
鍵的唯一性：每個(gè)鍵只能出現(xiàn)一次，插入重復(fù)鍵的元素會覆蓋原有的元素。
查找效率：平均情況下，查找操作的時(shí)間復(fù)雜度為 O ( 1 ) O(1) O(1)，最壞情況下為 O ( n ) O(n) O(n)。
插入和刪除效率：平均情況下，插入和刪除操作的時(shí)間復(fù)雜度為 O ( 1 ) O(1) O(1)。
在早期的 C++ 標(biāo)準(zhǔn)（如 C++98、C++03）中有 hash_map，不過它并非標(biāo)準(zhǔn)庫的一部分，而是來自于 SGI STL 擴(kuò)展。在 C++11 及以后的標(biāo)準(zhǔn)中，hash_map 被 std::unordered_map 替代，std::unordered_map 成為標(biāo)準(zhǔn)的哈希表實(shí)現(xiàn)。不過有些編譯器仍然支持 hash_map，下面為你加入 hash_map 并進(jìn)行比較，同時(shí)給出相應(yīng)的 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 重復(fù)，會覆蓋原有的值
    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 重復(fù)，會覆蓋原有的值
    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 重復(fù)，允許插入
    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 重復(fù)，允許插入
    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 重復(fù)，會覆蓋原有的值
    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 函數(shù)演示了 std::map 的使用，插入重復(fù)鍵的元素會覆蓋原有的值，元素按照鍵的升序排列。
testUnorderedMap 函數(shù)演示了 std::unordered_map 的使用，插入重復(fù)鍵的元素也會覆蓋原有的值，元素沒有特定的順序。
testMultiMap 函數(shù)演示了 std::multimap 的使用，允許插入重復(fù)鍵的元素，元素按照鍵的升序排列。
testUnorderedMultiMap 函數(shù)演示了 std::unordered_multimap 的使用，允許插入重復(fù)鍵的元素，元素沒有特定的順序。
testHashMap 函數(shù)演示了 hash_map 的使用，插入重復(fù)鍵的元素會覆蓋原有的值，元素沒有特定的順序。