這里再提二叉樹（二叉搜索樹），是為了后面講解map和set做準備。
一、二叉搜索樹
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹。
若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
它的左右子樹也分別為二叉搜索樹。
二、關聯式容器
在STL部分，我們已經接觸過STL中的部分容器，比如：vector、list、deque、
forward_list(C++11)等，這些容器統稱為序列式容器，因為其底層為線性序列的數據結構，里面
存儲的是元素本身。那什么是關聯式容器？它與序列式容器有什么區別？
關聯式容器也是用來存儲數據的，與序列式容器不同的是，其里面存儲的是<key, value>結構的
鍵值對，在數據檢索時比序列式容器效率更高。
補充：什么是鍵值對
用來表示具有一一對應關系的一種結構，該結構中一般只包含兩個成員變量key和value，key代
表鍵值，value表示與key對應的信息。比如：現在要建立一個英漢互譯的字典，那該字典中必然
有英文單詞與其對應的中文含義，而且，英文單詞與其中文含義是一一對應的關系，即通過該應
該單詞，在詞典中就可以找到與其對應的中文含義。
template <class T1, class T2> // 定義一個模板結構體，接受兩個類型參數 T1 和 T2
struct pair
{typedef T1 first_type; // 定義 first_type 為第一個模板參數 T1 的別名typedef T2 second_type; // 定義 second_type 為第二個模板參數 T2 的別名T1 first; // 結構體的第一個成員，類型為 T1T2 second; // 結構體的第二個成員，類型為 T2// 默認構造函數：使用默認構造函數初始化 first 和 secondpair(): first(T1()), second(T2()){}// 帶參數的構造函數：使用給定的參數 a 和 b 分別初始化 first 和 secondpair(const T1& a, const T2& b): first(a), second(b){}
};三、樹形結構的關聯式容器
根據應用場景的不桶，STL總共實現了兩種不同結構的管理式容器：樹型結構與哈希結構。樹型結
構的關聯式容器主要有四種：map、set、multimap、multiset。這四種容器的共同點是：使
用平衡搜索樹(即紅黑樹)作為其底層結果，容器中的元素是一個有序的序列。下面一依次介紹每一個容器。
set容器
set基本介紹：
官方文檔：
http://www.cplusplus.com/reference/set/set/?kw=set
1. set是按照一定次序存儲元素的容器
2. 在set中，元素的value也標識它(value就是key，類型為T)，并且每個value必須是唯一的。
set中的元素不能在容器中修改(元素總是const)，但是可以從容器中插入或刪除它們。
3. 在內部，set中的元素總是按照其內部比較對象(類型比較)所指示的特定嚴格弱排序準則進行
排序。
4. set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據順序對
子集進行直接迭代。
5. set在底層是用二叉搜索樹(紅黑樹)實現的。
注意：
1. 與map/multimap不同，map/multimap中存儲的是真正的鍵值對<key, value>，set中只放
value，但在底層實際存放的是由<value, value>構成的鍵值對。
2. set中插入元素時，只需要插入value即可，不需要構造鍵值對。
3. set中的元素不可以重復(因此可以使用set進行去重)。
4. 使用set的迭代器遍歷set中的元素，可以得到有序序列
5. set中的元素默認按照小于來比較
6. set中查找某個元素，時間復雜度為：O(log n)
7. set中的元素不允許修改(為什么?)
- 維護有序性 ：set?有序排列特性依賴底層紅黑樹結構，直接修改元素值易破壞有序性，如將有序元素 5 改為 2 會擾亂順序。
- 維護紅黑樹的平衡性 ：紅黑樹有嚴格平衡性質以保證操作時間復雜度，修改元素鍵值易破壞平衡，恢復平衡需復雜操作，增加程序復雜度和運行時間。
- 元素的唯一性 ：set?要求元素唯一，插入時會檢查重復。直接修改元素值可能導致重復元素出現，違反唯一性要求。
- 迭代器失效問題 ：set?迭代器指向樹節點，修改元素值可能改變其在樹中的位置，導致迭代器指向錯誤位置，引發未定義行為。
- 解決方法 ：不能直接修改元素值，可通過先刪除再插入新值，或利用其有序性特點插入新元素后按需刪除舊元素來實現類似修改效果。
8. set中的底層使用二叉搜索樹(紅黑樹)來實現。
set的使用:
?聲明和初始化
#include <iostream>
#include <set>
using namespace std;int main()
{// 聲明一個 set 容器set<int> s;// 初始化一個 set 容器set<int> s1 = { 1, 3, 5, 7, 9 };return 0;
}插入元素
#include <iostream>
#include <set>
using namespace std;int main()
{set<int> s;// 插入單個元素s.insert(10);s.insert(20);s.insert(30);// 輸出插入后的 setfor (int num : s){cout << num << " ";}return 0;
}運行結果：
插入元素
#include <iostream>
#include <set>
#include <vector>
using namespace std;int main()
{set<int> s;vector<int> vec = { 5, 6, 7, 8, 9 };// 區間插入s.insert(vec.begin(), vec.end());// 輸出插入后的 setfor (int num : s) {cout << num << " ";}return 0;
}綜合運用，用pair實現鍵值對
#include <iostream>
#include <set>
#include <string>
#include <iomanip>
#include <climits> // 添加INT_MAX所需的頭文件// 自定義比較器：按值排序（值大的在前）
struct ValueComparator
{bool operator()(const std::pair<std::string, int>& a,const std::pair<std::string, int>& b) const{// 添加名稱比較，確保價格相同時也能正確排序if (a.second != b.second) {return a.second > b.second; // 降序排列}return a.first < b.first;}
};int main()
{// 1. 基本set使用// 自動排序且去重，元素類型為intstd::set<int> numbers = { 5, 2, 8, 2, 1, 4, 3 };std::cout << "1. 基本set使用 (自動排序且唯一):\n";for (int num : numbers){std::cout << num << " ";}std::cout << "\n\n";// 2. 使用set存儲pair實現鍵值對// 默認按pair.first(名稱)的字典序排序std::set<std::pair<std::string, int>> products;// 插入產品信息 (名稱, 價格)products.insert({ "Laptop", 1200 });products.insert({ "Phone", 800 });products.insert({ "Tablet", 600 });products.insert({ "Headphones", 150 });products.insert({ "Camera", 950 });// 默認按pair.first (名稱) 排序std::cout << "2. 按產品名稱排序:\n";std::cout << std::left << std::setw(15) << "產品" << "價格\n";std::cout << "-------------------\n";for (const auto& product : products){std::cout << std::setw(15) << product.first << "$" << product.second << "\n";}std::cout << "\n";// 3. 使用自定義比較器按值排序// 使用ValueComparator實現按價格降序排列std::set<std::pair<std::string, int>, ValueComparator> productsByValue;// 插入相同數據for (const auto& product : products){productsByValue.insert(product);}std::cout << "3. 按產品價格排序 (降序):\n";std::cout << std::left << std::setw(15) << "產品" << "價格\n";std::cout << "-------------------\n";for (const auto& product : productsByValue) {std::cout << std::setw(15) << product.first << "$" << product.second << "\n";}std::cout << "\n";// 4. 查找操作 - 修正：只需提供鍵（名稱）// 利用pair的字典序比較，second值用0占位auto it = products.find({ "Tablet", 0 }); // 價格值不重要，只需名稱匹配if (it != products.end()){std::cout << "4. 查找結果: 找到產品 - "<< it->first << " ($" << it->second << ")\n\n";}// 5. 更新操作（刪除+重新插入）// set無法直接修改鍵，需刪除后重新插入auto old = products.find({ "Phone", 0 }); // 只需名稱匹配if (old != products.end()){// 保存實際價格值std::string name = old->first;int price = old->second;products.erase(old);products.insert({ "Phone Pro", 999 });std::cout << "5. 更新操作: " << name << " ($" << price<< ") 已更新為 Phone Pro ($999)\n\n";}// 6. 范圍查詢修正 - 使用線性掃描代替邊界查詢// 由于set按名稱排序，無法直接使用lower_bound/upper_boundstd::cout << "6. 價格在 $500 到 $1000 之間的產品:\n";std::cout << std::left << std::setw(15) << "產品" << "價格\n";std::cout << "-------------------\n";for (const auto& product : products){if (product.second >= 500 && product.second <= 1000){std::cout << std::setw(15) << product.first << "$" << product.second << "\n";}}std::cout << "\n";// 7. 統計操作修正 - 使用count檢查高價產品std::cout << "7. 統計:\n";std::cout << " 產品總數: " << products.size() << "\n";bool hasExpensive = false;for (const auto& product : products){if (product.second > 1000){hasExpensive = true;break;}}std::cout << " 是否有價格超過$1000的產品? "<< (hasExpensive ? "是" : "否") << "\n\n";// 8. 刪除操作修正 - 只需提供鍵（名稱）products.erase({ "Headphones", 0 }); // 價格值不重要std::cout << "8. 刪除 Headphones 后剩余產品數: " << products.size() << "\n\n";// 9. 綜合應用：價格分析int total = 0;int maxPrice = 0;int minPrice = INT_MAX;for (const auto& product : products){int price = product.second;total += price;if (price > maxPrice) maxPrice = price;if (price < minPrice) minPrice = price;}std::cout << "9. 價格分析:\n";std::cout << " 最貴產品: $" << maxPrice << "\n";std::cout << " 最便宜產品: $" << minPrice << "\n";std::cout << " 平均價格: $" << static_cast<double>(total) / products.size() << "\n";return 0;
}map容器
官方文檔
cplusplus.com/reference/map/map/?kw=map
map的基本介紹
std::map ?是 C++ STL 中的關聯容器，存儲鍵值對，按鍵有序（默認升序），基于紅黑樹實現，查找、插入、刪除復雜度均為 O(log n)。
核心特性
1.?有序性：元素按鍵自動排序（可自定義比較規則）。
2.?唯一性：鍵唯一（重復插入會被忽略）。
3.?鍵值對結構：類型為 ?std::pair<const Key, Value
?
基礎用法
1. 頭文件
#include <map>2. 創建與初始化
// 空map
std::map<std::string, int> map1; // 帶初始值
std::map map2 = {{"apple", 3}, {"banana", 5}}; // 自定義降序排序
struct CompareDesc { bool operator()(const std::string& a, const std::string& b) const
{ return a > b; } };
std::map<std::string, int, CompareDesc> map3; 3. 插入元素
map["key"] = 10; // 下標操作（鍵不存在時創建）
map.insert({{"key2", 20}}); // insert 函數
map.emplace("key3", 30); // C++11 emplace（避免臨時對象） 4.訪問元素
//4. 訪問元素int val = map["key"]; // 鍵不存在時創建默認值（可能意外）
int val_safe = map.at("key"); // 鍵不存在時拋異常
auto it = map.find("key"); // 安全查找，返回迭代器 //5. 刪除元素map.erase("key"); // 按鍵刪除
map.erase(it); // 按迭代器刪除
map.erase(first, last); // 刪除區間 [first, last) //6. 遍歷與查詢// 遍歷（C++11 范圍for）
for (const auto& [k, v] : map) { std::cout << k << ":" << v; } // 范圍查詢
auto low = map.lower_bound(20); // 首個 >= 鍵的元素
auto high = map.upper_bound(40); // 首個 > 鍵的元素 綜合應用：
#include <map>
#include <string>
#include <iostream>
#include <cctype>
#include <algorithm> // 包含std::tolowerint main()
{// 使用map統計單詞出現次數，鍵為單詞，值為次數std::map<std::string, int> wordCount;std::string text = "This is a test. Test again.";std::string word;// 遍歷文本中的每個字符for (char c : text){// 如果是字母，轉換為小寫并添加到當前單詞if (std::isalpha(static_cast<unsigned char>(c)))word += std::tolower(static_cast<unsigned char>(c));// 如果不是字母且當前單詞非空，表示一個單詞結束else if (!word.empty()){// 將單詞加入統計并重置當前單詞wordCount[word]++;word.clear();}}// 處理文本末尾的最后一個單詞if (!word.empty())wordCount[word]++;// 方法1：使用pair的first和second成員（兼容所有C++版本）std::cout << "Method 1 (using first/second):\n";for (const auto& entry : wordCount){// entry.first為單詞，entry.second為次數std::cout << entry.first << ": " << entry.second << "\n";}// 方法2：結構化綁定（需要C++17支持）// 如果編譯器支持C++17，可以取消注釋以下代碼/*std::cout << "\nMethod 2 (using structured binding):\n";for (const auto& [w, c] : wordCount){std::cout << w << ": " << c << "\n";}*/return 0;
}
