目錄

關(guān)聯(lián)式容器

關(guān)聯(lián)式容器的特點(diǎn)和使用場(chǎng)景

樹形結(jié)構(gòu)與哈希結(jié)構(gòu)?

樹形結(jié)構(gòu)

哈希結(jié)構(gòu)

鍵值對(duì)?

set

?set的介紹

set的定義方式

?set的使用

multiset

map?

map的介紹

map的定義方式

map的使用

multimap?

---

關(guān)聯(lián)式容器

C++標(biāo)準(zhǔn)模板庫（STL）中的關(guān)聯(lián)式容器（Associative Containers）是一類根據(jù)鍵值對(duì)元素進(jìn)行存儲(chǔ)和操作的數(shù)據(jù)結(jié)構(gòu)。它們?cè)试S快速查找、插入和刪除操作，并且通常是基于樹或哈希表實(shí)現(xiàn)的。C++ STL中的關(guān)聯(lián)式容器包括四種主要類型：

1. std::set 和 std::multiset：

   • std::set 是一種集合，其中每個(gè)元素是唯一的，按特定順序排序。
   • std::multiset 與 std::set 類似，但允許重復(fù)元素。
   • 這兩種容器通常使用紅黑樹等平衡二叉搜索樹實(shí)現(xiàn)，因此其查找、插入和刪除操作的時(shí)間復(fù)雜度為 O(log n)。

2. std::map 和 std::multimap：

   • std::map 是一種關(guān)聯(lián)數(shù)組，其中每個(gè)元素都是一個(gè)鍵-值對(duì)，鍵是唯一的，按特定順序排序。
   • std::multimap 與 std::map 類似，但允許鍵重復(fù)。
   • 這兩種容器也通常使用平衡二叉搜索樹實(shí)現(xiàn)，其查找、插入和刪除操作的時(shí)間復(fù)雜度同樣為 O(log n)。

3. std::unordered_set 和 std::unordered_multiset：

   • std::unordered_set 是一種無序集合，其中每個(gè)元素是唯一的，元素?zé)o特定順序。
   • std::unordered_multiset 與 std::unordered_set 類似，但允許重復(fù)元素。
   • 這兩種容器使用哈希表實(shí)現(xiàn)，因此其平均情況下的查找、插入和刪除操作時(shí)間復(fù)雜度為 O(1)。

4. std::unordered_map 和 std::unordered_multimap：

   • std::unordered_map 是一種無序關(guān)聯(lián)數(shù)組，其中每個(gè)元素是一個(gè)鍵-值對(duì)，鍵是唯一的，元素?zé)o特定順序。
   • std::unordered_multimap 與 std::unordered_map 類似，但允許鍵重復(fù)。
   • 這兩種容器也使用哈希表實(shí)現(xiàn)，其平均情況下的查找、插入和刪除操作時(shí)間復(fù)雜度為 O(1)。

關(guān)聯(lián)式容器的特點(diǎn)和使用場(chǎng)景

1. 有序關(guān)聯(lián)容器（set、multiset、map、multimap）：

   • 排序：元素按照鍵的順序排列，可以方便地進(jìn)行范圍查詢。
   • 使用場(chǎng)景：需要按順序訪問元素或進(jìn)行范圍查詢時(shí)，例如實(shí)現(xiàn)有序字典或集合。

2. 無序關(guān)聯(lián)容器（unordered_set、unordered_multiset、unordered_map、unordered_multimap）：

   • 無序：元素?zé)o特定順序，通過哈希值快速訪問。
   • 使用場(chǎng)景：關(guān)注查找、插入和刪除的平均時(shí)間效率，而不在乎元素順序時(shí)，例如實(shí)現(xiàn)哈希表或快速查找的數(shù)據(jù)結(jié)構(gòu)。

樹形結(jié)構(gòu)與哈希結(jié)構(gòu)?

樹形結(jié)構(gòu)

樹形結(jié)構(gòu)常用于實(shí)現(xiàn)有序關(guān)聯(lián)容器，如 std::set、std::multiset、std::map 和 std::multimap。具體來說，這些容器通常采用平衡二叉搜索樹（如紅黑樹）來實(shí)現(xiàn)。以下是樹形結(jié)構(gòu)的一些關(guān)鍵點(diǎn)：

1. 自動(dòng)排序：元素按鍵值自動(dòng)排序，支持有序遍歷。
2. 平衡性：紅黑樹等平衡二叉樹保證了樹的高度在O(log n)范圍內(nèi)，從而確保查找、插入和刪除操作的時(shí)間復(fù)雜度為O(log n)。
3. 復(fù)雜性：相對(duì)于哈希表實(shí)現(xiàn)，樹形結(jié)構(gòu)的插入和刪除操作更為復(fù)雜，需要維護(hù)樹的平衡。

適用場(chǎng)景

• 需要按順序訪問或處理數(shù)據(jù)，例如范圍查詢。
• 需要查找鍵的前驅(qū)或后繼等順序關(guān)系操作。

哈希結(jié)構(gòu)

哈希結(jié)構(gòu)用于實(shí)現(xiàn)無序關(guān)聯(lián)容器，如 std::unordered_set、std::unordered_multiset、std::unordered_map 和 std::unordered_multimap。這些容器基于哈希表來實(shí)現(xiàn)。以下是哈希結(jié)構(gòu)的一些關(guān)鍵點(diǎn)：

1. 無序存儲(chǔ)：元素?zé)o特定順序，基于哈希值進(jìn)行存儲(chǔ)。
2. 快速訪問：平均情況下，查找、插入和刪除操作的時(shí)間復(fù)雜度為O(1)。
3. 哈希沖突：需要處理哈希沖突，一般采用鏈地址法或開放地址法等策略。

適用場(chǎng)景

• 更關(guān)注操作的平均時(shí)間效率，而不在乎元素的順序。
• 大量頻繁的查找、插入和刪除操作，例如實(shí)現(xiàn)哈希表或集合。

?

鍵值對(duì)?

? 鍵值對(duì)是用來表示具有一一對(duì)應(yīng)關(guān)系的一種結(jié)構(gòu)，該結(jié)構(gòu)中一般只包含兩個(gè)成員變量key和value，key代表鍵值，value表示與key對(duì)應(yīng)的信息。

? 比如我們?nèi)羰且⒁粋€(gè)英譯漢的字典，那么該字典中的英文單詞與其對(duì)應(yīng)的中文含義就是一一對(duì)應(yīng)的關(guān)系，即通過單詞可以找到與其對(duì)應(yīng)的中文含義。

在SGI-STL中關(guān)于鍵值對(duì)的定義如下：

template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()){}pair(const T1& a, const T2& b) : first(a), second(b){}
};

set

?set的介紹

1.set是按照一定次序存儲(chǔ)元素的容器，使用set的迭代器遍歷set中的元素，可以得到有序序列。

2.set當(dāng)中存儲(chǔ)元素的value都是唯一的，不可以重復(fù)，因此可以使用set進(jìn)行去重。

3.與map/multimap不同，map/multimap中存儲(chǔ)的是真正的鍵值對(duì)<key, value>，set中只放value，但在底層實(shí)際存放的是由<value, value>構(gòu)成的鍵值對(duì)，因此在set容器中插入元素時(shí)，只需要插入value即可，不需要構(gòu)造鍵值對(duì)。

4.set中的元素不能被修改，因?yàn)閟et在底層是用二叉搜索樹來實(shí)現(xiàn)的，若是對(duì)二叉搜索樹當(dāng)中某個(gè)結(jié)點(diǎn)的值進(jìn)行了修改，那么這棵樹將不再是二叉搜索樹。

5.在內(nèi)部，set中的元素總是按照其內(nèi)部比較對(duì)象所指示的特定嚴(yán)格弱排序準(zhǔn)則進(jìn)行排序。當(dāng)不傳入內(nèi)部比較對(duì)象時(shí)，set中的元素默認(rèn)按照小于來比較。

6.set容器通過key訪問單個(gè)元素的速度通常比unordered_set容器慢，但set容器允許根據(jù)順序?qū)υ剡M(jìn)行直接迭代。

7.set在底層是用平衡搜索樹（紅黑樹）實(shí)現(xiàn)的，所以在set當(dāng)中查找某個(gè)元素的時(shí)間復(fù)雜度為logN。

set的定義方式

方式一：?構(gòu)造一個(gè)某類型的空容器。

set<int> s1; //構(gòu)造int類型的空容器

方式二：?拷貝構(gòu)造某類型set容器的復(fù)制品。?

set<int> s2(s1); //拷貝構(gòu)造int類型s1容器的復(fù)制品

?方式三：?使用迭代器拷貝構(gòu)造某一段內(nèi)容。

string str("abcdef");
set<char> s3(str.begin(), str.end()); //構(gòu)造string對(duì)象某段區(qū)間的復(fù)制品

方式四：?構(gòu)造一個(gè)某類型的空容器，比較方式指定為大于。

set < int, greater<int>> s4; //構(gòu)造int類型的空容器，比較方式指定為大于

?set的使用

set當(dāng)中常用的成員函數(shù)如下：

set當(dāng)中迭代器相關(guān)函數(shù)如下：

?

使用示例：?

#include <iostream>
#include <set>int main() {// 創(chuàng)建一個(gè)整數(shù)類型的set容器std::set<int> mySet;// 插入一些元素到set中mySet.insert(5);mySet.insert(3);mySet.insert(8);mySet.insert(2);// 使用迭代器遍歷容器并輸出元素（正向遍歷）std::cout << "使用迭代器正向遍歷容器：" << std::endl;for (auto it = mySet.begin(); it != mySet.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 刪除一個(gè)元素mySet.erase(3);// 使用范圍 for 循環(huán)遍歷容器并輸出元素std::cout << "使用范圍 for 循環(huán)正向遍歷容器：" << std::endl;for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;// 檢查集合中是否包含特定元素int target = 8;if (mySet.count(target)) {std::cout << "集合包含 " << target << std::endl;} else {std::cout << "集合不包含 " << target << std::endl;}// 獲取集合的大小std::cout << "集合的大小：" << mySet.size() << std::endl;// 清空集合mySet.clear();// 檢查集合是否為空if (mySet.empty()) {std::cout << "集合為空" << std::endl;} else {std::cout << "集合不為空" << std::endl;}// 向空集合中插入一些元素mySet.insert(10);mySet.insert(20);mySet.insert(30);// 使用反向迭代器遍歷容器并輸出元素（反向遍歷）std::cout << "使用反向迭代器反向遍歷容器：" << std::endl;for (auto rit = mySet.rbegin(); rit != mySet.rend(); ++rit) {std::cout << *rit << " ";}std::cout << std::endl;return 0;
}

multiset

? ? multiset容器與set容器的底層實(shí)現(xiàn)一樣，都是平衡搜索樹（紅黑樹），其次，multiset容器和set容器所提供的成員函數(shù)的接口都是基本一致的，這里就不再列舉了，multiset容器和set容器的唯一區(qū)別就是，multiset允許鍵值冗余，即multiset容器當(dāng)中存儲(chǔ)的元素是可以重復(fù)的。

#include <iostream>
#include <set>int main() {// 創(chuàng)建一個(gè)允許重復(fù)元素的 multiset 容器std::multiset<int> ms;// 插入一些元素到 multiset 中ms.insert(1);ms.insert(4);ms.insert(3);ms.insert(3);ms.insert(2);ms.insert(2);ms.insert(3);// 使用范圍 for 循環(huán)遍歷容器并輸出元素for (auto e : ms) {std::cout << e << " ";}std::cout << std::endl; // 輸出：1 2 2 3 3 3 4return 0;
}

由于multiset容器允許鍵值冗余，因此兩個(gè)容器中成員函數(shù)find和count的意義也有所不同：

?

map?

map的介紹

1.map是關(guān)聯(lián)式容器，它按照特定的次序（按照key來比較）存儲(chǔ)鍵值key和值value組成的元素，使用map的迭代器遍歷map中的元素，可以得到有序序列。

2.在map中，鍵值key通常用于排序和唯一地標(biāo)識(shí)元素，而值value中存儲(chǔ)與此鍵值key關(guān)聯(lián)的內(nèi)容。鍵值key和值value的類型可能不同，并且在map的內(nèi)部，key與value通過成員類型value_type綁定在一起，并取別名為pair。

3.map容器中元素的鍵值key不能被修改，但是元素的值value可以被修改，因?yàn)閙ap底層的二叉搜索樹是根據(jù)每個(gè)元素的鍵值key進(jìn)行構(gòu)建的，而不是值value。

4.在內(nèi)部，map中的元素總是按照鍵值key進(jìn)行比較排序的。當(dāng)不傳入內(nèi)部比較對(duì)象時(shí)，map中元素的鍵值key默認(rèn)按照小于來比較。

5.map容器通過鍵值key訪問單個(gè)元素的速度通常比unordered_map容器慢，但map容器允許根據(jù)順序?qū)υ剡M(jìn)行直接迭代。

6.map容器支持下標(biāo)訪問符，即在[]中放入key，就可以找到與key對(duì)應(yīng)的value。

7.map在底層是用平衡搜索樹（紅黑樹）實(shí)現(xiàn)的，所以在map當(dāng)中查找某個(gè)元素的時(shí)間復(fù)雜度為logN。

map的定義方式

方式一：?指定key和value的類型構(gòu)造一個(gè)空容器。

map<int, double> m1; //構(gòu)造一個(gè)key為int類型，value為double類型的空容器

方式二：?拷貝構(gòu)造某同類型容器的復(fù)制品。?

map<int, double> m2(m1); //拷貝構(gòu)造key為int類型，value為double類型的m1容器的復(fù)制品

方式三：?使用迭代器拷貝構(gòu)造某一段內(nèi)容。

map<int, double> m3(m2.begin(), m2.end()); //使用迭代器拷貝構(gòu)造m2容器某段區(qū)間的復(fù)制品

方式四：?指定key和value的類型構(gòu)造一個(gè)空容器，key比較方式指定為大于。

map<int, double, greater<int>> m4; //構(gòu)造一個(gè)key為int類型，value為double類型的空容器，key比較方式指定為大于

map的使用

map的插入 map的查找 map的刪除 map的[ ]運(yùn)算符重載 map的迭代器?

#include <iostream>
#include <map>int main() {// 創(chuàng)建一個(gè)鍵為整數(shù)，值為字符串的 map 容器std::map<int, std::string> myMap;// 插入元素到 map 中myMap.insert(std::make_pair(1, "One"));myMap.insert(std::make_pair(2, "Two"));myMap.insert(std::make_pair(3, "Three"));// 查找 map 中的元素int keyToFind = 2;auto it = myMap.find(keyToFind);if (it != myMap.end()) {std::cout << "鍵為 " << keyToFind << " 的值為：" << it->second << std::endl;} else {std::cout << "鍵為 " << keyToFind << " 的元素未找到" << std::endl;}// 刪除 map 中的元素int keyToDelete = 1;myMap.erase(keyToDelete);// 使用 [] 運(yùn)算符向 map 中插入或訪問元素myMap[4] = "Four";// 使用迭代器遍歷 map 并輸出鍵值對(duì)std::cout << "遍歷 map：" << std::endl;for (auto it = myMap.begin(); it != myMap.end(); ++it) {std::cout << "鍵：" << it->first << " 值：" << it->second << std::endl;}return 0;
}

map的其他成員函數(shù)

除了上述成員函數(shù)外，map當(dāng)中還有如下幾個(gè)常用的成員函數(shù)：

#include <iostream>
#include <string>
#include <map>int main() {// 創(chuàng)建一個(gè) map 容器，鍵為整數(shù)，值為字符串std::map<int, std::string> myMap;// 插入一些鍵值對(duì)到 map 中myMap.insert(std::make_pair(2, "two"));myMap.insert(std::make_pair(1, "one"));myMap.insert(std::make_pair(3, "three"));// 獲取容器中元素的個(gè)數(shù)std::cout << "容器中元素的個(gè)數(shù)：" << myMap.size() << std::endl; // 輸出：3// 容器中 key 值為 2 的元素個(gè)數(shù)std::cout << "容器中 key 值為 2 的元素個(gè)數(shù)：" << myMap.count(2) << std::endl; // 輸出：1// 清空容器myMap.clear();// 容器判空std::cout << "容器是否為空：" << myMap.empty() << std::endl; // 輸出：1// 創(chuàng)建一個(gè)臨時(shí)的 map 容器，并交換數(shù)據(jù)std::map<int, std::string> tmpMap;myMap.swap(tmpMap);return 0;
}

multimap?

? ? multimap容器與map容器的底層實(shí)現(xiàn)一樣，也都是平衡搜索樹（紅黑樹），其次，multimap容器和map容器所提供的成員函數(shù)的接口都是基本一致的，這里也就不再列舉了，multimap容器和map容器的區(qū)別與multiset容器和set容器的區(qū)別一樣，multimap允許鍵值冗余，即multimap容器當(dāng)中存儲(chǔ)的元素是可以重復(fù)的。

#include <iostream>
#include <string>
#include <map>int main() {// 創(chuàng)建一個(gè) multimap 容器，鍵為整數(shù)，值為字符串std::multimap<int, std::string> mm;// 插入一些鍵值對(duì)到 multimap 中（允許重復(fù)鍵）mm.insert(std::make_pair(2, "two"));mm.insert(std::make_pair(2, "double"));mm.insert(std::make_pair(1, "one"));mm.insert(std::make_pair(3, "three"));// 使用范圍 for 循環(huán)遍歷 multimap 并輸出鍵值對(duì)for (const auto& e : mm) {std::cout << "<" << e.first << "," << e.second << "> ";}std::cout << std::endl; // 輸出：<1,one> <2,two> <2,double> <3,three>return 0;
}

?由于multimap容器允許鍵值冗余，因此兩個(gè)容器中成員函數(shù)find和count的意義也有所不同：

其次，由于multimap容器允許鍵值冗余，調(diào)用[ ]運(yùn)算符重載函數(shù)時(shí)，應(yīng)該返回鍵值為key的哪一個(gè)元素的value的引用存在歧義，因此在multimap容器當(dāng)中沒有實(shí)現(xiàn)[ ]運(yùn)算符重載函數(shù)。?