我们将详细解析 C++ 标准库中的 set/multiset 和 map/multimap 容器。它们都是关联容器，基于红黑树实现，能自动对元素进行排序并支持高效的查找、插入和删除操作。

---

1. set 与 multiset

底层实现

• 基于红黑树（自平衡二叉搜索树）。
• 元素自动按键值排序（默认升序，可通过比较函数自定义）。

set（集合）

• 特性：存储唯一键值，不允许重复。
• 头文件：#include <set>
• 定义：

  std::set<KeyType, Compare = std::less<KeyType>> mySet;
  

• 操作示例：

  std::set<int> s;
  s.insert(3);  // 插入元素
  s.insert(1);
  s.insert(2);
  s.insert(2);  // 重复插入无效
  
  // 遍历（自动排序）
  for (int x : s) std::cout << x << " ";  // 输出：1 2 3
  
  // 查找
  auto it = s.find(2);  // 返回迭代器，找不到返回 s.end()
  s.erase(1);           // 删除元素
  

---

multiset（多重集合）

• 特性：允许重复键值。
• 头文件：#include <set>
• 操作示例：

  std::multiset<int> ms;
  ms.insert(2);
  ms.insert(1);
  ms.insert(2);  // 允许重复
  
  // 遍历输出：1 2 2
  ms.count(2);   // 返回 2（计数）
  ms.erase(2);   // 删除所有值为 2 的元素
  

---

2. map 与 multimap

底层实现

• 基于红黑树，存储键值对 (key, value)。

map（映射）

• 特性：键值唯一，每个键对应一个值。
• 头文件：#include <map>
• 定义：

  std::map<KeyType, ValueType, Compare = std::less<KeyType>> myMap;
  

• 操作示例：

  std::map<std::string, int> m;
  m["Alice"] = 90;    // 插入或更新
  m.insert({"Bob", 85});
  
  // 遍历（按键排序）
  for (auto& p : m) 
      std::cout << p.first << ": " << p.second << std::endl;
  
  // 查找
  auto it = m.find("Bob");
  if (it != m.end()) 
      it->second = 95;  // 修改值
  

---

multimap（多重映射）

• 特性：允许重复键值，一键可对应多值。
• 头文件：#include <map>
• 操作示例：

  std::multimap<std::string, int> mm;
  mm.insert({"Alice", 90});
  mm.insert({"Alice", 88});  // 允许重复键
  
  // 遍历所有 "Alice"
  auto range = mm.equal_range("Alice");
  for (auto it = range.first; it != range.second; ++it)
      std::cout << it->second << " ";  // 输出：90 88
  

---

3. 核心特性对比

特性	set	multiset	map	multimap
键唯一性	唯一	可重复	唯一	可重复
存储内容	键	键	键值对	键值对
插入时间复杂度	$$O(\log n)$$	$$O(\log n)$$	$$O(\log n)$$	$$O(\log n)$$
查找时间复杂度	$$O(\log n)$$	$$O(\log n)$$	$$O(\log n)$$	$$O(\log n)$$

---

4. 应用场景

• set/multiset：
  需要有序唯一/重复元素集合（如去重、排序统计）。
• map：
  键值对映射（如字典、缓存）。
• multimap：
  一键多值（如学生姓名对应多个成绩）。

---

5. 注意事项

1. 自定义排序：
   可通过仿函数自定义比较规则（如降序）：

   std::set<int, std::greater<int>> s;
   

2. map 的 [] 操作符：
   若键不存在，会插入新键值对（值默认初始化），可能引发非预期行为。
3. 迭代器失效：
   插入/删除操作可能使迭代器失效（除当前操作节点外）。

---

总结

• set/map：适用唯一键场景，操作高效（$$O(\log n)$$）。
• multiset/multimap：处理重复键需求，结构灵活。
• 红黑树保证：自动排序、操作稳定，是关联容器的核心优势。