前言

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

一、unordered系列容器

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

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

unordered_map是一種鍵值對(duì)存儲(chǔ)的容器，每個(gè)鍵唯一對(duì)應(yīng)一個(gè)值；而unordered_set是一種存儲(chǔ)唯一元素的容器。它們的使用方式與紅黑樹結(jié)構(gòu)的關(guān)聯(lián)式容器類似，提供了insert、erase、find等方法來(lái)操作元素。

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

二、unordered_map

| ===============================
| 🔴 unordered_map在線文檔說(shuō)明
| ===============================

1. unordered_map簡(jiǎn)介

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

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

?函數(shù)特點(diǎn)

1. 常數(shù)時(shí)間復(fù)雜度：平均情況下，unordered_map的插入、查找和刪除操作都具有常數(shù)時(shí)間復(fù)雜度。這是因?yàn)楣１沓浞掷昧斯：瘮?shù)的散列性質(zhì)，快速定位元素。

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

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

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

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

🚨🚨注意：使用unordered_map時(shí)，需要包含頭文件<unordered_map>，并使用std命名空間，或者使用using語(yǔ)句簡(jiǎn)化操作。

2. unordered_map接口

- 構(gòu)造函數(shù)

1. 默認(rèn)構(gòu)造函數(shù)：

   unordered_map<Key, T> myMap;
   

   使用默認(rèn)構(gòu)造函數(shù)創(chuàng)建一個(gè)空的unordered_map對(duì)象。

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

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

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

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

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

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

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

   unordered_map(const unordered_map& other);
   

   使用另一個(gè)unordered_map對(duì)象進(jìn)行拷貝構(gòu)造，創(chuàng)建一個(gè)與原unordered_map相同的副本。

5. 移動(dòng)構(gòu)造函數(shù)：

   unordered_map(unordered_map&& other) noexcept;
   

   使用另一個(gè)unordered_map對(duì)象進(jìn)行移動(dòng)構(gòu)造，創(chuàng)建一個(gè)新的unordered_map對(duì)象，并從原對(duì)象中竊取資源。

構(gòu)造函數(shù)	功能介紹
unordered_map()	默認(rèn)構(gòu)造函數(shù)，創(chuàng)建一個(gè)空的unordered_map對(duì)象。
unordered_map(initializer_list<pair<const Key, T>>)	列表初始化構(gòu)造函數(shù)，使用初始化列表創(chuàng)建unordered_map對(duì)象并初始化其中的鍵值對(duì)。
unordered_map(const unordered_map&)	拷貝構(gòu)造函數(shù)，創(chuàng)建一個(gè)與原unordered_map相同的副本。
unordered_map(unordered_map&&) noexcept	移動(dòng)構(gòu)造函數(shù)，創(chuàng)建一個(gè)新的unordered_map對(duì)象，并從原對(duì)象中竊取資源。
unordered_map(size_type)	構(gòu)造函數(shù)，創(chuàng)建具有指定桶數(shù)的unordered_map對(duì)象。
unordered_map(size_type, const hasher&, const key_equal&)	構(gòu)造函數(shù)，創(chuàng)建具有指定桶數(shù)、哈希函數(shù)和相等比較操作符的unordered_map對(duì)象。
template unordered_map(InputIt, InputIt)	區(qū)間構(gòu)造函數(shù)，從指定范圍內(nèi)的元素創(chuàng)建unordered_map對(duì)象。

- unordered_map的容量

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

函數(shù)聲明	功能介紹
unordered_map::size	返回unordered_map中鍵值對(duì)的個(gè)數(shù)。
unordered_map::empty	判斷unordered_map是否為空，返回true或false。
unordered_map::max_size	返回unordered_map所能容納的最大元素?cái)?shù)量。

- unordered_map的迭代器

unordered_map提供了以下迭代器：

迭代器類型	功能介紹
unordered_map::iterator	用于遍歷和修改unordered_map中的鍵值對(duì)，可以通過(guò)解引用操作符*和箭頭操作符->訪問元素。
unordered_map::const_iterator	用于遍歷unordered_map中的鍵值對(duì)，但不允許修改元素值。

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

函數(shù)聲明	功能介紹
unordered_map::begin	返回指向unordered_map起始位置的迭代器。
unordered_map::end	返回指向unordered_map末尾位置的迭代器。
unordered_map::find	返回指向鍵對(duì)應(yīng)的元素的迭代器，如果鍵不存在，則返回尾部迭代器。

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

#include <iostream>
#include <unordered_map>int main() {std::unordered_map<int, std::string> map = {{1, "one"}, {2, "two"}, {3, "three"}};// 使用迭代器遍歷unordered_map并打印鍵值對(duì)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;
}

輸出結(jié)果：

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

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

- unordered_map的元素訪問

1. 下標(biāo)運(yùn)算符 []：使用鍵作為索引來(lái)訪問和修改unordered_map中的元素。如果鍵存在，則返回對(duì)應(yīng)的值；如果鍵不存在，則將該鍵插入到unordered_map中，并返回一個(gè)默認(rèn)構(gòu)造的值。

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

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

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

- unordered_map的修改操作

函數(shù)聲明	功能介紹
insert	向容器中插入鍵值對(duì)
erase	刪除容器中的鍵值對(duì)
void clear()	清空容器中有效元素個(gè)數(shù)
void swap(unordered_map&)	交換兩個(gè)容器中的元素

- unordered_map的桶操作

函數(shù)聲明	功能介紹
size_t bucket_count()const	返回哈希桶中桶的總個(gè)數(shù)
size_t bucket_size(size_t n)const	返回n號(hào)桶中有效元素的總個(gè)數(shù)
size_t bucket(const K& key)	返回元素key所在的桶號(hào)

三、unordered_set

|===============================
| 🔴 unordered_set在線文檔說(shuō)明
|===============================

1. unordered_srt簡(jiǎn)介

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

?函數(shù)特點(diǎn)

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

2. unordered_set接口

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

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

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

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

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

3. find(): 查找元素，返回一個(gè)迭代器指向該元素的位置，如果元素不存在，則返回 end()。查找操作的平均時(shí)間復(fù)雜度是 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(): 獲取某個(gè)元素在 unordered_set 中出現(xiàn)的次數(shù)，返回值為0或1。可以用于判斷元素是否存在。

   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 中當(dāng)前存儲(chǔ)的元素?cái)?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 并不提供按索引方式訪問元素的功能，因?yàn)?unordered_set 是無(wú)序的。 若要遍歷 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 常用的幾個(gè)成員函數(shù)。通過(guò)這些函數(shù)，可以方便地進(jìn)行元素的插入、刪除、查找和遍歷操作。更多的操作可見官方文檔的描述。

溫馨提示

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

再次感謝您的支持和關(guān)注。期待與您建立更緊密的互動(dòng)，共同探索C++、算法和編程的奧秘。祝您生活愉快，排便順暢！