C++ 中 map 和 set 的使用详解
在 C++ STL 中，std::map 和 std::set 是两种非常常用的有序关联容器，它们底层都基于红黑树实现，具有以下共同特点：
- 元素自动按照键排序
- 键（key）唯一（不允许重复）
- 查找、插入、删除的时间复杂度均为 O(log n)
- 元素在插入时自动排序
下面分别详细说明两者的使用方式、区别和典型场景。
1. std::set 基本使用
set 是一个只存储键的有序集合，不允许重复元素。
#include <iostream>
#include <set>
#include <string>
int main() {
// 1. 定义与初始化
std::set<int> s1; // 空集合
std::set<int> s2 = {5, 2, 8, 1, 9, 3}; // 初始化列表（自动排序+去重）
std::set<std::string> names{"Alice", "Bob", "Charlie", "Bob"}; // Bob 只出现一次
// 2. 插入元素
s1.insert(10);
s1.insert(7);
s1.insert(10); // 重复元素不会插入成功
// 3. 查找
if (s1.count(7)) {
std::cout << "7 在集合中\n";
}
auto it = s1.find(10);
if (it != s1.end()) {
std::cout << "找到: " << *it << "\n";
}
// 4. 遍历（天然有序）
std::cout << "set 内容: ";
for (int x : s1) {
std::cout << x << " ";
}
std::cout << "\n";
// 5. 删除
s1.erase(7); // 删除值为7的元素
s1.erase(s1.find(10)); // 通过迭代器删除
return 0;
}set 常用操作总结
| 操作 | 写法 | 时间复杂度 | 说明 |
|---|---|---|---|
| 插入 | insert(x) | O(log n) | 插入失败返回 pair<迭代器, bool> |
| 查找是否存在 | count(x) 或 find(x) | O(log n) | count 返回 0 或 1 |
| 删除 | erase(x) 或 erase(it) | O(log n) | |
| 获取大小 | size() | O(1) | |
| 清空 | clear() | O(n) | |
| 判空 | empty() | O(1) |
2. std::map 基本使用
map 是键-值对的有序关联容器，键唯一，值可以重复。
#include <iostream>
#include <map>
#include <string>
int main() {
// 1. 定义与初始化
std::map<std::string, int> age_map;
std::map<int, std::string> id_to_name = {
{1001, "Alice"},
{1002, "Bob"},
{1003, "Charlie"}
};
// 2. 插入（三种常用方式）
age_map["Alice"] = 20; // 最常用（[] 操作符）
age_map.insert({"Bob", 22}); // 使用 pair
age_map.emplace("Charlie", 19); // C++11 推荐（原地构造）
// 3. 访问
std::cout << "Alice 年龄: " << age_map["Alice"] << "\n"; // 注意：[] 会插入默认值！
// 更安全的访问方式（C++17）
if (auto it = age_map.find("David"); it != age_map.end()) {
std::cout << "David 年龄: " << it->second << "\n";
} else {
std::cout << "未找到 David\n";
}
// 4. 遍历
std::cout << "\nmap 内容（按 key 升序）：\n";
for (const auto& [key, value] : age_map) { // C++17 结构化绑定
std::cout << key << " -> " << value << "\n";
}
// 5. 删除
age_map.erase("Bob"); // 按 key 删除
age_map.erase(age_map.find("Alice")); // 按迭代器删除
return 0;
}map 常用操作总结
| 操作 | 写法 | 时间复杂度 | 说明 |
|---|---|---|---|
| 插入/修改 | m[key] = value | O(log n) | 不存在则插入，存在则修改 |
| 插入（不覆盖） | insert() / emplace() | O(log n) | 返回 pair<迭代器, bool> |
| 查找 | find(key) / count(key) | O(log n) | |
| 访问值（安全） | at(key) / find()->second | O(log n) | at() 不存在会抛异常 |
| 删除 | erase(key) / erase(it) | O(log n) | |
| 下界/上界 | lower_bound(key) / upper_bound(key) | O(log n) | 非常常用（区间查询） |
3. map 和 set 的核心对比
| 特性 | set | map |
|---|---|---|
| 存储内容 | 只有 key | key-value 对 |
| 元素是否唯一 | key 唯一 | key 唯一 |
| 是否允许修改元素 | 不允许修改 key | 可以修改 value（但不能改 key） |
| 典型用途 | 去重 + 排序、存在性判断、去重排序 | 键值映射、词频统计、字典、优先级管理 |
| 下标访问 | 无 | 有 [] 和 at() |
| 修改元素 | 只能删除再插入 | 直接修改 m[key] = new_value |
4. 常用高级用法（面试/比赛高频）
4.1 使用自定义比较器
// 按成绩降序排序（set 示例）
struct Student {
std::string name;
int score;
};
auto cmp = [](const Student& a, const Student& b) {
return a.score > b.score; // 降序
};
std::set<Student, decltype(cmp)> top_students(cmp);4.2 map 实现词频统计
std::map<std::string, int> freq;
for (const auto& word : words) {
freq[word]++; // 非常优雅
}4.3 使用 lower_bound 做区间查询
// 查找 [l, r] 区间内所有元素
auto it1 = s.lower_bound(l);
auto it2 = s.upper_bound(r); // upper_bound 是 > r 的第一个位置
for (auto it = it1; it != it2; ++it) {
// 处理 *it
}4.4 multimap 和 multiset（允许重复键）
std::multiset：允许重复元素std::multimap：允许相同 key 对应多个 value
std::multimap<int, std::string> score_to_name;
score_to_name.insert({90, "Alice"});
score_to_name.insert({90, "Bob"}); // 允许5. 总结口诀
- 只关心元素是否存在 + 排序 → 用
set/multiset - 需要 key → value 映射 → 用
map/multimap - 需要快速随机访问 → 考虑
unordered_map/unordered_set（哈希表） - 需要严格有序 + 不重复 → 首选
set和map - 比赛中：大部分去重排序题用
set，统计映射用map
希望这个总结对你清晰掌握 map 和 set 有帮助！
如果想继续深入某个方向（比如 map 在红黑树中的实现细节、自定义比较器写法、与 unordered_map 的性能对比、典型算法题中的用法等），随时告诉我。
