前言

歡迎各位大佬們的關顧，本文將介紹unordered系列容器以及其中的兩個重要成員：unordered_map和unordered_set。unordered_map是一種無序的關聯(lián)容器，它使用哈希表來存儲鍵值對，并提供高效的插入、查找和刪除操作。在本文中，我們將首先介紹unordered_map的基本概念和特點，然后詳細講解其接口和用法。接下來，我們將介紹unordered_set，它是一種無序的集合容器，同樣基于哈希表實現(xiàn)。我們將對unordered_set進行簡要介紹，并深入探討其接口和用法。通過學習本文，您將對unordered系列容器有更加清晰的理解，并能夠靈活運用它們解決實際問題。下面話不多說，坐穩(wěn)扶好咱們要開車了??

一、unordered系列容器

在C++98中，STL提供了一系列底層為紅黑樹結構的關聯(lián)式容器，包括set、multiset、map和multimap。這些容器在查詢操作時的時間復雜度為$O(logN)$，其中N是容器中元素的數(shù)量。

為了提高查詢效率，C++11引入了unordered_map和unordered_set這兩個底層基于哈希表的關聯(lián)式容器。與紅黑樹結構的關聯(lián)式容器相比，unordered系列容器在平均情況下具有更高的查詢效率，時間復雜度為常數(shù)級別$O(1)$。當哈希函數(shù)設計得好且沒有太多的沖突時，它們可以在插入、查找和刪除等操作上表現(xiàn)出很好的性能。

unordered_map是一種鍵值對存儲的容器，每個鍵唯一對應一個值；而unordered_set是一種存儲唯一元素的容器。它們的使用方式與紅黑樹結構的關聯(lián)式容器類似，提供了insert、erase、find等方法來操作元素。

????注意：unordered_map和unordered_set的元素順序是根據(jù)哈希函數(shù)計算的哈希值來確定的，因此它們無法保證元素的順序穩(wěn)定。如果需要有序的容器，仍然可以使用紅黑樹結構的關聯(lián)式容器。

二、unordered_map

| ===============================
| ?? unordered_map在線文檔說明
| ===============================

1. unordered_map簡介

unordered_map是C++標準庫中的一個關聯(lián)式容器，它是基于哈希表實現(xiàn)的。unordered_map提供了一種存儲鍵值對的方式，每個鍵唯一對應一個值。它被設計為在平均情況下具有常數(shù)時間復雜度的插入、查找和刪除操作。

unordered_map與map的用法類似，但其內(nèi)部結構不同。unordered_map使用哈希函數(shù)將鍵映射到桶（bucket）中，并在桶內(nèi)使用鏈表或其他數(shù)據(jù)結構解決沖突。通過哈希函數(shù)和桶的結構，可以快速定位鍵對應的值。

?函數(shù)特點

1. 常數(shù)時間復雜度：平均情況下，unordered_map的插入、查找和刪除操作都具有常數(shù)時間復雜度。這是因為哈希表充分利用了哈希函數(shù)的散列性質(zhì)，快速定位元素。

2. 無序存儲：與map不同，unordered_map不會按照鍵的順序進行存儲，而是根據(jù)哈希函數(shù)計算得到的哈希值進行存儲。因此，遍歷unordered_map的結果是無序的。

3. 自定義哈希函數(shù)：unordered_map支持自定義哈希函數(shù)，可以根據(jù)鍵的類型，實現(xiàn)一個符合需求的哈希函數(shù)來提高查詢效率。如果不提供自定義哈希函數(shù)，會使用默認的哈希函數(shù)。

4. 沖突處理：由于哈希函數(shù)的限制，可能會出現(xiàn)多個元素映射到同一個桶的情況，這就是沖突。unordered_map使用鏈表或其他數(shù)據(jù)結構來解決沖突，保證鍵值對的正確存儲和查找。

5. 支持各種數(shù)據(jù)類型：unordered_map可以存儲各種數(shù)據(jù)類型的鍵值對，包括內(nèi)置類型和自定義類型。

????注意：使用unordered_map時，需要包含頭文件<unordered_map>，并使用std命名空間，或者使用using語句簡化操作。

2. unordered_map接口

- 構造函數(shù)

1. 默認構造函數(shù)：

   unordered_map<Key, T> myMap;
   

   使用默認構造函數(shù)創(chuàng)建一個空的unordered_map對象。

2. 列表初始化構造函數(shù)：

   unordered_map<Key, T> myMap = {{key1, value1}, {key2, value2}, ...};
   

   使用初始化列表創(chuàng)建unordered_map對象并初始化其中的鍵值對。

3. 區(qū)間構造函數(shù)：

   template<class InputIt>
   unordered_map(InputIt first, InputIt last);
   

   從指定范圍內(nèi)的元素創(chuàng)建unordered_map對象。范圍由迭代器first和last指定，可以是數(shù)組、容器或其他實現(xiàn)了前向迭代器的數(shù)據(jù)結構。

4. 拷貝構造函數(shù)：

   unordered_map(const unordered_map& other);
   

   使用另一個unordered_map對象進行拷貝構造，創(chuàng)建一個與原unordered_map相同的副本。

5. 移動構造函數(shù)：

   unordered_map(unordered_map&& other) noexcept;
   

   使用另一個unordered_map對象進行移動構造，創(chuàng)建一個新的unordered_map對象，并從原對象中竊取資源。

- unordered_map的容量

unordered_map的容量相關的成員函數(shù)主要包括：

- unordered_map的迭代器

unordered_map提供了以下迭代器：

你可以使用以下成員函數(shù)來獲取迭代器：

使用迭代器可以遍歷unordered_map中的所有元素，示例代碼如下所示：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> map = {{1, "one"}, {2, "two"}, {3, "three"}};
    
    // 使用迭代器遍歷unordered_map并打印鍵值對
    for (auto it = map.begin(); it != map.end(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }
    
    // 使用find函數(shù)查找指定鍵的元素
    auto findIt = map.find(2);
    if (findIt != map.end()) {
        std::cout << "Key: " << findIt->first << ", Value: " << findIt->second << std::endl;
    }
    
    return 0;
}

輸出結果：

Key: 1, Value: one
Key: 2, Value: two
Key: 3, Value: three
Key: 2, Value: two

通過迭代器，我們可以依次訪問unordered_map中的鍵值對，并通過迭代器的解引用操作符 -> 來訪問元素的鍵和值。使用find函數(shù)可以查找指定鍵的元素，并返回一個指向該元素的迭代器。

- unordered_map的元素訪問

1. 下標運算符 []：使用鍵作為索引來訪問和修改unordered_map中的元素。如果鍵存在，則返回對應的值；如果鍵不存在，則將該鍵插入到unordered_map中，并返回一個默認構造的值。

   std::unordered_map<std::string, int> map = {{"apple", 1}, {"banana", 2}, {"orange", 3}};
   
   int value = map["apple"];  // 訪問鍵"apple"對應的值
   map["banana"] = 5;         // 修改鍵"banana"對應的值
   map["grape"] = 4;          // 插入新鍵"grape"并對應一個值
   
   

2. 使用成員函數(shù) at()：使用鍵作為參數(shù)來訪問和修改unordered_map中的元素。如果鍵存在，則返回對應的值；如果鍵不存在，則拋出std::out_of_range異常。

   std::unordered_map<std::string, int> map = {{"apple", 1}, {"banana", 2}, {"orange", 3}};
   
   int value = map.at("apple");  // 訪問鍵"apple"對應的值
   map.at("banana") = 5;         // 修改鍵"banana"對應的值
   map.at("grape") = 4;          // 拋出異常，因為鍵"grape"不存在
   

- unordered_map的修改操作

- unordered_map的桶操作

三、unordered_set

|===============================
| ?? unordered_set在線文檔說明
|===============================

1. unordered_srt簡介

std::unordered_set 是 C++ STL 提供的一個哈希表實現(xiàn)的無序集合容器。與 std::set 不同，std::unordered_set 中元素的順序是不確定的，它使用哈希函數(shù)來快速訪問、插入和刪除元素。哈希函數(shù)將元素的鍵轉換為一個哈希值，然后用該哈希值來映射到對應的桶中，每個桶中存儲一組鍵值相同的元素。當需要訪問、插入或刪除某個元素時，首先根據(jù)哈希函數(shù)計算出該元素對應的桶的位置，然后在該桶中查找該元素。

?函數(shù)特點

• 元素的順序是不確定的，不能保證元素的插入順序就是元素的訪問順序。
• 訪問、插入和刪除元素的平均時間復雜度是 $O(1)$。
• 查找元素的時間復雜度取決于哈希函數(shù)的質(zhì)量，最壞情況下會退化為線性時間復雜度 $O(n)$。
• 支持使用自定義類型作為元素，需要提供哈希函數(shù)和相等比較函數(shù)。
• 內(nèi)部結構是一個哈希表，具有一定的空間浪費和碰撞問題。

2. unordered_set接口

std::unordered_set 是 C++ STL 提供的一個哈希表實現(xiàn)的無序集合容器。它提供了一系列成員函數(shù)用于插入、刪除、查找和遍歷元素。下面是 std::unordered_set 常用的成員函數(shù)：

1. insert(): 向 unordered_set 中插入元素。有多種重載形式，可以接受單個元素、區(qū)間或者初始化列表作為參數(shù)。插入操作的平均時間復雜度是 O(1)。

   std::unordered_set<int> set;
   
   set.insert(10);                  // 插入單個元素
   set.insert({20, 30, 40});        // 插入初始化列表
   set.insert(begin(vec), end(vec)); // 插入?yún)^(qū)間
   

2. erase(): 從 unordered_set 中刪除元素。有多種重載形式，可以接受單個元素、區(qū)間或者迭代器作為參數(shù)。刪除操作的平均時間復雜度是 O(1)。

   std::unordered_set<int> set = {10, 20, 30, 40};
   
   set.erase(20);                // 刪除單個元素
   set.erase(begin(set), end(set)); // 刪除整個區(qū)間
   set.erase(set.find(30));      // 刪除指定迭代器位置的元素
   

3. find(): 查找元素，返回一個迭代器指向該元素的位置，如果元素不存在，則返回 end()。查找操作的平均時間復雜度是 O(1)。

   std::unordered_set<int> set = {10, 20, 30, 40};
   
   auto it = set.find(20);     // 查找元素
   if (it != set.end()) {
       std::cout << "Found: " << *it << std::endl;
   } else {
       std::cout << "Not found" << std::endl;
   }
   

4. count(): 獲取某個元素在 unordered_set 中出現(xiàn)的次數(shù)，返回值為0或1?？梢杂糜谂袛嘣厥欠翊嬖凇?/p>

   std::unordered_set<int> set = {10, 20, 30, 40};
   
   if (set.count(20) > 0) {
       std::cout << "Element 20 exists in the set" << std::endl;
   } else {
       std::cout << "Element 20 does not exist in the set" << std::endl;
   }
   

5. size(): 獲取 unordered_set 中當前存儲的元素數(shù)量。

   std::unordered_set<int> set = {10, 20, 30, 40};
   
   std::cout << "Size of set: " << set.size() << std::endl;
   

6. empty(): 檢查 unordered_set 是否為空，如果為空返回 true，否則返回 false。

   std::unordered_set<int> set;
   
   if (set.empty()) {
       std::cout << "Set is empty" << std::endl;
   } else {
       std::cout << "Set is not empty" << std::endl;
   }
   

7. clear(): 清空 unordered_set 中的所有元素。

   std::unordered_set<int> set = {10, 20, 30, 40};
   
   set.clear();
   

????注意：std::unordered_set 并不提供按索引方式訪問元素的功能，因為 unordered_set 是無序的。 若要遍歷 unordered_set 中的元素，可以使用迭代器：

std::unordered_set<int> set = {10, 20, 30, 40};

for (auto it = set.begin(); it != set.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

以上是 std::unordered_set 常用的幾個成員函數(shù)。通過這些函數(shù)，可以方便地進行元素的插入、刪除、查找和遍歷操作。更多的操作可見官方文檔的描述。

溫馨提示

感謝您對博主文章的關注與支持！另外，我計劃在未來的更新中持續(xù)探討與本文相關的內(nèi)容，會為您帶來更多關于C++以及編程技術問題的深入解析、應用案例和趣味玩法等。請繼續(xù)關注博主的更新，不要錯過任何精彩內(nèi)容！

再次感謝您的支持和關注。期待與您建立更緊密的互動，共同探索C++、算法和編程的奧秘。祝您生活愉快，排便順暢！
文章來源地址http://www.zghlxwxcb.cn/news/detail-714971.html

到了這里，關于【C++入門到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入門 ]的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！