C++ STL 容器详解：map 与 set 原理及实战
在 C++ 的 STL 体系中，除了常见的序列式容器（如 vector、list），关联式容器同样占据核心地位。它们主要用于处理键值映射或唯一性集合的场景。本文将深入探讨基于红黑树实现的 map 和 set，结合代码示例讲解其底层逻辑与实战用法。
一、序列式与关联式容器
序列式容器（如 string、vector、list）按存储位置线性保存数据，元素间无紧密关联。而关联式容器则不同，它们通常采用非线性结构（如树或哈希表），通过关键字来保存和访问元素。
STL 中的关联式容器主要分为两类：
- 树形结构：包括 map、set、multimap、multiset。底层均为平衡二叉搜索树（红黑树），支持有序遍历。
- 哈希结构：包括 unordered_map、unordered_set。底层为哈希表，查找效率高但不保证顺序。
简单记忆：set 是 key 搜索场景，map 是 key/value 搜索场景。
二、键值对基础
关联式容器的核心在于'键值对'（Key-Value Pair）。这种结构包含两个成员变量：key 代表键值，value 表示对应的信息。例如字典中，英文单词是 key，中文含义是 value。
在 C++ 标准库中，pair 模板类用于将两个不同类型的数据组合在一起，它是 map 等容器内部存储的基本单元。
三、Set 容器详解
1. Set 简介
std::set 是按照一定次序存储元素的容器。其特点如下：
- 唯一性：每个 value 必须是唯一的，插入重复元素会失败。因此常用于去重。
- 有序性：默认按小于号（<）排序，内部使用红黑树实现。
- 不可修改 Key：为了保证树的结构不被破坏，set 中的元素一旦插入便不能修改 key 值。
- 查找效率：时间复杂度为 O(log n)。
虽然 set 只存放 value，但在底层实际存放的是由 <value, value> 构成的键值对。
2. 构造与迭代器
set 支持正向和反向迭代遍历，默认按升序顺序（中序遍历）。需要注意的是，set 的 iterator 不支持修改数据，因为修改关键字会破坏底层搜索树结构。
#include <set>
#include <iostream>
using namespace std;
int main() {
// 默认升序
set<int> s1;
// 降序，传入 greater 仿函数
set<int, greater<int>> s2;
s2.insert();
s();
s();
s();
( it = s(); it != s(); ++it) {
cout << *it << ;
}
cout << endl;
( & e : s2) {
cout << e << ;
}
;
}
