在 C++ STL 中，map/set 与 unordered_map/unordered_set 是高频使用的关联式容器，其底层分别基于平衡二叉搜索树（红黑树）和哈希表实现。本文将结合核心代码，拆解底层数据结构原理，梳理常用方法，帮助读者快速上手使用。

一、底层数据结构核心原理

1. 红黑树（map/set 底层）

红黑树是一种近似平衡的二叉搜索树，通过颜色约束（红 / 黑）确保最长路径不超过最短路径的 2 倍，时间复杂度稳定在 O (log N)。

• 核心规则：根为黑色、无连续红色节点、每条路径黑色节点数相同
• 关键特性：支持有序遍历（中序遍历），天然去重（map/set），支持 key 冗余（multimap/multiset）

2. 哈希表（unordered_map/unordered_set 底层）

哈希表通过哈希函数将 key 映射到存储位置，用链地址法解决冲突，平均时间复杂度 O (1)。

• 核心机制：哈希函数（将 key 转为整形）、负载因子（控制扩容时机，默认≤1）
• 关键特性：无序遍历，天然去重，支持 key 冗余（unordered_multimap/unordered_multiset）

二、四大容器常用方法速查（含代码示例）

1. set（有序去重）

底层红黑树，仅存储 key，支持有序遍历，不允许修改元素。

常用方法

#include <set>
using namespace std;

// 1. 构造与初始化
set<int> s1; // 空构造
set<int> s2 = {2, 1, 3, 2}; // 初始化列表（自动去重+升序）
set<int, greater<int>> s3 = {2, 1, 3}; // 降序排列

// 2. 增删查
s1.insert(5); // 插入单个元素，返回pair<iterator, bool>
s1.insert({2, 3, 5}); // 批量插入
s1.erase(3); // 按值删除，返回删除个数
s1.erase(s1.begin()); // 按迭代器删除
auto it = s1.find(2); // 查找元素，返回迭代器（未找到返回end()）
int cnt = s1.count(5); // 统计元素个数（0或1）

// 3. 遍历
for (auto e : s1) cout << e << " "; // 范围for（升序）
for (auto it = s1.begin(); it != s1.end(); ++it) {
    // *it = 10; 错误：不允许修改元素
    cout << *it << " ";
}

// 4. 其他常用
s1.empty(); // 判断是否为空
s1.size(); // 获取元素个数
s1.clear(); // 清空容器

2. map（有序 key-value 映射）

底层红黑树，存储 pair<const Key, T>，key 唯一且有序，支持修改 value。

常用方法

#include <map>
using namespace std;

// 1. 构造与初始化
map<string, string> dict;
map<string, int> countMap = {{"apple", 2}, {"banana", 1}};

// 2. 增删查改
// 插入方式
dict.insert(pair<string, string>("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert({"insert", "插入"});
dict["sort"] = "排序"; // 运算符[]：插入+修改（推荐）

// 删除
dict.erase("left"); // 按key删除
dict.erase(dict.find("right")); // 按迭代器删除

// 查找与修改
auto it = dict.find("insert");
if (it != dict.end()) {
    it->second = "插入（修改后）"; // 允许修改value
    cout << it->first << ":" << it->second << endl;
}

// 3. 遍历
for (const auto& e : dict) {
    cout << e.first << ":" << e.second << endl;
}

// 4. 运算符[]核心用法（统计次数）
string arr[] = {"apple", "banana", "apple", "orange"};
for (auto& str : arr) {
    countMap[str]++; // 不存在则插入{str, 0}后+1，存在则直接+1
}

// 5. 其他常用
dict.empty();
dict.size();
dict.clear();

3. unordered_set（无序去重）

底层哈希表，仅存储 key，无序遍历，查询效率更高（平均 O (1)）。

常用方法

#include <unordered_set>
using namespace std;

// 1. 构造与初始化
unordered_set<int> us1;
unordered_set<int> us2 = {3, 1, 2, 3}; // 自动去重，无序

// 2. 增删查
us1.insert(4);
us1.insert({5, 6, 4});
us1.erase(5);
auto it = us1.find(6); // 查找效率高于set
int cnt = us1.count(4);

// 3. 遍历（无序）
for (auto e : us1) cout << e << " ";

// 4. 其他常用
us1.empty();
us1.size();
us1.clear();

4. unordered_map（无序 key-value 映射）

底层哈希表，存储 pair<const Key, T>，key 唯一且无序，适合高频查询场景。

常用方法

#include <unordered_map>
using namespace std;

// 1. 构造与初始化
unordered_map<string, string> dict;
unordered_map<string, int> fruitCount;

// 2. 增删查改
dict.insert({"left", "左边"});
dict["right"] = "右边"; // 运算符[]：插入+修改
dict["left"] = "左边（修改）"; // 直接修改value

dict.erase("right");
auto it = dict.find("left");
if (it != dict.end()) {
    cout << it->first << ":" << it->second << endl;
}

// 3. 遍历（无序）
for (const auto& e : dict) {
    cout << e.first << ":" << e.second << endl;
}

// 4. 统计应用
string fruits[] = {"apple", "banana", "apple", "apple"};
for (auto& f : fruits) {
    fruitCount[f]++;
}

// 5. 其他常用
dict.empty();
dict.size();
dict.clear();

三、容器选型指南

场景需求	推荐容器	原因
有序遍历 / 范围查询	set/map	红黑树中序遍历天然有序
高频查询（无顺序要求）	unordered_set/unordered_map	哈希表平均 O (1) 查询效率
key 允许重复	multiset/multimap	支持 key 冗余存储
统计元素出现次数	map/unordered_map	运算符 [] 简化统计逻辑

四、注意事项

1. set/map 的迭代器是双向迭代器，不支持随机访问；unordered 系列是单向迭代器
2. set 和 unordered_set 的元素不可修改，map 和 unordered_map 的 key 不可修改
3. 自定义类型作为 key 时：
   • set/map 需重载<运算符
   • unordered 系列需提供哈希函数和==运算符
4. 哈希表的性能依赖哈希函数设计，避免频繁扩容（负载因子控制在 1 以内）