这里再提二叉树（二叉搜索树），是为了后面讲解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;
}
