set和map基礎：【C++進階學習】第五彈——二叉搜索樹——二叉樹進階及set和map的鋪墊-CSDN博客
前言：
在上篇的學習中，我們已經學習了如何使用C語言來實現二叉搜索樹，在C++中，我們是有現成的封裝好的類模板來實現二叉搜索樹的——set和map,這也是我們今天要講的重點
目錄
一、容器
二、set和multiset
一、set與multiset概述
二、set與multiset的基本操作
三、高級特性
四、set與multiset的選擇
三、map和multimap
1.?map與multimap的區別
2.?map與multimap的使用場景
3. 基本操作
4. 注意事項
5. 示例代碼
四、總結
一、容器
在前面，我們經常提到容器這個東西，比如stack、queue等許多類模板都稱之為容器，其實今天要講的set和map也是容器的一種，容器這個東西我會在下一章進行單獨講解，有興趣的可以關注一下
二、set和multiset
在C++標準模板庫（STL）中，set和multiset是兩種關聯容器，它們在處理有序集合數據時非常有用。
一、set與multiset概述
set?是一種關聯容器，它存儲唯一（不重復）的元素，并且這些元素會根據特定的排序規則自動排序。set內部通常采用紅黑樹實現，保證了元素的對數時間復雜度的插入、刪除和查找操作。
multiset?與set類似，但它允許存儲重復的元素。multiset同樣基于紅黑樹實現，其操作的時間復雜度特性與set相同。
二、set與multiset的基本操作
在使用set或multiset之前，需要包含相應的頭文件：
#include <set>
#include <multiset>以下是一些基本操作：
- 構造函數：
set<T> s; // 默認構造函數
multiset<T> ms; // 默認構造函數
// 可以通過比較函數和分配器進行自定義構造- 插入元素：
s.insert(key); // set插入元素
ms.insert(key); // multiset插入元素
insert?方法用于向set或multiset中添加元素，如果插入成功，set?的insert方法返回pair<iterator, bool>（這個東西后面會講），其中bool指示是否插入成功。multiset?的insert方法返回指向插入元素的迭代器。
- 刪除元素：
s.erase(key); // 刪除特定元素（set）
ms.erase(key); // 刪除特定元素（multiset）
// 刪除操作在multiset中會刪除所有匹配的元素- 查找元素：
auto it = s.find(key); // 查找元素（set）
auto it = ms.find(key); // 查找元素（multiset）
// find返回指向元素的迭代器，如果未找到則返回end()- 統計元素個數：
s.count(key); // set中元素個數（總是1或0）
ms.count(key); // multiset中元素個數（可能是大于0的整數）- 大小和容量：
s.size(); // 返回元素數量
ms.size(); // 返回元素數量
s.empty(); // 判斷是否為空
ms.empty(); // 判斷是否為空三、高級特性
- 迭代器：
set和multiset都提供迭代器，支持前向和后向遍歷。
for (auto it = s.begin(); it != s.end(); ++it) {// 遍歷set中的元素
}- 排序規則：
默認情況下，set和multiset使用小于操作符
<進行排序，但可以通過自定義比較函數來改變排序規則。
struct CustomCompare {bool operator()(const T& a, const T& b) const {// 自定義比較邏輯}
};
set<T, CustomCompare> s; // 使用自定義比較函數
multiset<T, CustomCompare> ms; // 使用自定義比較函數- 性能考慮：
由于set和multiset基于二叉搜索樹實現，它們的插入、刪除和查找操作通常具有O(log n)的時間復雜度。
四、set與multiset的選擇
選擇使用set還是multiset取決于是否需要存儲重復元素。如果需要存儲唯一的元素集合，則應該使用set。如果允許集合中存在重復元素，那么應該選擇multiset。
三、map和multimap
在C++的STL（標準模板庫）中，map和multimap是兩種關聯容器，它們用于存儲鍵值對。這些容器使用紅黑樹作為底層數據結構，以確保高效的插入、查找和刪除操作。
1.?map與multimap的區別
- 唯一性：
map存儲的是唯一鍵值對，即每個鍵只能對應一個值。而multimap允許相同的鍵對應多個值，提供了一種更靈活的數據存儲方式。- 排序：兩者都按照鍵的自然順序進行排序，通常為升序。可以通過自定義比較函數來改變排序規則。
2.?map與multimap的使用場景
map通常用于需要確保鍵的唯一性且需要對鍵進行排序的場景。例如，統計不同類別的數據數量、實現字典等。multimap則適用于需要處理多個值與相同鍵關聯的場景，如記錄用戶在不同時間段的登錄記錄。
3. 基本操作
下面這些操作與上面set和multiset的操作基本一致，就不再寫了
- 構造與初始化：可以通過構造函數直接初始化
map或multimap，也可以使用std::make_map或std::make_multimap輔助函數。自定義排序可以通過傳遞比較函數來實現。- 插入與刪除：使用
insert方法插入鍵值對，erase方法刪除鍵值對。erase方法還可以用于刪除指定范圍內的元素。- 查找：
find方法用于查找鍵值對，返回指向匹配元素的迭代器；lower_bound和upper_bound方法用于查找鍵的范圍，適用于處理多個相同鍵的值。
4. 注意事項
- 迭代器的失效：刪除元素后，所有指向被刪除元素的迭代器都會失效。在迭代時，需要確保迭代器的有效性。
- 鍵的類型：鍵的類型必須支持比較操作，通常需要有定義的比較運算符或提供一個比較函數。
- 性能：插入、查找和刪除操作的時間復雜度為O(log n)，基于紅黑樹的高效性。
- 值類型：值的類型可以是任何類型，但通常選擇有意義的數據類型，如整型、浮點型或字符串等。
5. 示例代碼
#include <iostream>
#include <map>
#include <string>
using namespace std;int main() {// 使用map存儲唯一鍵值對map<string, int> fruitCounts = {{"apple", 10},{"banana", 15},{"cherry", 5}};// 使用multimap存儲多個值與相同鍵關聯multimap<string, int> logins = {{"Alice", 1001},{"Bob", 2001},{"Alice", 1003}};// 查找和打印map中的元素auto it = fruitCounts.find("banana");if (it != fruitCounts.end()) {cout << "Found banana: " << it->second << endl;}// 查找和打印multimap中的元素auto range = logins.equal_range("Alice");for (auto it = range.first; it != range.second; ++it) {cout << "Login for Alice: " << it->second << endl;}return 0;
}運行結果：
四、總結
以上就是C++中set和map的全部內容，其實底層邏輯就是二叉搜索樹或者準確來說叫紅黑樹，其中有一些小的知識點會在下一節再提一下
感謝各位大佬觀看，創作不易，還請各位大佬點贊支持一下！！！
