前言

我们之前聊过二叉搜索树（BST）和平衡二叉搜索树，而 C++ STL 里的map 和 set，底层就是封装好的红黑树（一种高效的平衡二叉搜索树）。它们天生自带有序性，插入、删除、查询的时间复杂度稳定在O(logn)，是 C++ 开发和考试里最高频的容器之二，今天我们就把它俩讲透，全是可直接跑的示例。

一、先搞懂核心区别：set vs map

表格

容器 核心结构 核心特点 核心适用场景
set 集合 只存key 键值，key 不可重复，天然去重、有序 元素去重、排序、快速判断元素是否存在
map 键值对 存 **<key, value> 键值对 **，key 不可重复，按 key 有序 字典映射、key-value 关联存储、通过 key 快速查 value

补充：它们都有对应的「允许重复 key」的版本：multiset、multimap，核心用法基本一致，只是放开了 key 的唯一性限制。

二、set 用法全解（附完整示例）

2.1 核心特性

  1. 底层红黑树实现，元素默认升序排列
  2. 元素本身就是 key，不允许重复，自带去重能力
  3. 不允许通过迭代器修改元素值（key 是 const 常量，修改会破坏红黑树的排序结构）
  4. 插入、删除、查询的时间复杂度稳定在 O (logn)

2.2 必备头文件

cpp

运行

#include <set> // set/multiset 都在这个头文件里
#include <iostream>
using namespace std; // 新手入门先这么用，不用反复写std::前缀

2.3 定义方式

cpp

运行

// 1. 基础定义：默认升序排列的int型set
set<int> s1;

// 2. 自定义排序：降序排列
set<int, greater<int>> s2;

// 3. 列表初始化（自动去重+排序）
set<int> s3 = {3,1,4,1,5,9}; // 最终存储：1,3,4,5,9

2.4 核心常用接口（考试 / 开发最高频）

表格

接口 核心作用 用法示例
insert(elem) 插入元素，自动去重 + 排序 s.insert(10);
erase(elem) 删除值为 elem 的元素 s.erase(3);
erase(iterator) 删除迭代器指向的元素 s.erase(s.begin());
find(elem) 查找元素，找到返回对应迭代器，找不到返回 s.end () auto it = s.find(5);
count(elem) 统计元素出现次数（set 只能返回 0 或 1，multiset 可大于 1） if (s.count (5)) 元素存在
empty() 判断容器是否为空 if (s.empty ()) 容器为空
size() 返回容器内元素个数 int n = s.size();
clear() 清空容器内所有元素 s.clear();
begin()/end() 返回首尾迭代器（begin 指向第一个元素，end 指向最后一个元素的下一位） 遍历容器用

2.5 set 完整可运行示例

cpp

运行

#include <set>
#include <iostream>
using namespace std;

int main() {
    // 1. 初始化set，自动去重+升序排列
    set<int> s = {5, 2, 8, 2, 5, 9, 1};
    cout << "1. 初始化后set（自动去重+升序）：" << endl;
    // 遍历方式1：范围for（C++11及以上，最简单易用）
    for (int num : s) {
        cout << num << " ";
    }
    cout << endl << "set的元素个数：" << s.size() << endl << endl;

    // 2. 插入元素
    s.insert(6);
    cout << "2. 插入6后的set：" << endl;
    for (int num : s) cout << num << " ";
    cout << endl << endl;

    // 3. 删除元素
    s.erase(2); // 删除值为2的元素
    cout << "3. 删除2后的set：" << endl;
    for (int num : s) cout << num << " ";
    cout << endl << endl;

    // 4. 查找元素
    auto it = s.find(8);
    if (it != s.end()) {
        cout << "4. 找到元素：" << *it << endl;
    } else {
        cout << "4. 元素不存在" << endl;
    }

    // 5. 快速判断元素是否存在（count写法更简洁）
    if (s.count(9)) {
        cout << "5. 9存在于set中" << endl << endl;
    }

    // 6. 清空容器
    s.clear();
    cout << "6. 清空后set是否为空：" << (s.empty() ? "是" : "否") << endl;

    return 0;
}
运行结果

plaintext

1. 初始化后set（自动去重+升序）：
1 2 5 8 9 
set的元素个数：5

2. 插入6后的set：
1 2 5 6 8 9 

3. 删除2后的set：
1 5 6 8 9 

4. 找到元素：8
5. 9存在于set中

6. 清空后set是否为空：是

2.6 multiset 补充（允许重复 key）

用法和 set 完全一致，唯一区别是允许重复元素，count()可以返回大于 1 的数值：

cpp

运行

#include <set>
#include <iostream>
using namespace std;

int main() {
    multiset<int> ms = {2, 2, 1, 3, 2};
    cout << "multiset元素：";
    for (int num : ms) cout << num << " ";
    cout << endl;
    cout << "2出现的次数：" << ms.count(2) << endl; // 输出3
    return 0;
}

三、map 用法全解（附完整示例）

3.1 核心特性

  1. 底层红黑树实现，按key排序，默认升序
  2. 每个元素是pair<key, value>键值对，key 唯一不可重复，value 可重复
  3. key 是 const 常量，不可修改，value 可以随意修改
  4. 插入、删除、查询的时间复杂度稳定在 O (logn)，支持通过 key 快速查找 value

3.2 必备头文件

cpp

运行

#include <map> // map/multimap 都在这个头文件里
#include <iostream>
#include <string> // 示例用string作为key/value
using namespace std;

3.3 定义方式

cpp

运行

// 1. 基础定义：key为int，value为string，默认升序
map<int, string> m1;

// 2. 自定义排序：按key降序
map<int, string, greater<int>> m2;

// 3. 列表初始化
map<int, string> m3 = {{1, "张三"}, {2, "李四"}, {3, "王五"}};

3.4 核心常用接口（考试 / 开发最高频）

表格

接口 核心作用 用法示例
insert(pair<key, value>) 插入键值对，key 已存在则插入失败 m.insert (pair<int, string>(1, "张三"));
m[key] = value 最常用的插入 / 修改方式，key 不存在则插入，存在则覆盖 value m [2] = "李四";
erase(key) 删除 key 对应的键值对 m.erase(3);
erase(iterator) 删除迭代器指向的键值对 m.erase(m.begin());
find(key) 查找 key，找到返回对应迭代器，找不到返回 m.end () auto it = m.find(2);
count(key) 统计 key 出现次数（map 只能返回 0 或 1，multimap 可大于 1） if (m.count (2)) key 存在
empty() 判断容器是否为空 if (m.empty ()) 容器为空
size() 返回容器内键值对个数 int n = m.size();
clear() 清空容器内所有元素 m.clear();
begin()/end() 返回首尾迭代器 遍历容器用

3.5 map 完整可运行示例

cpp

运行

#include <map>
#include <iostream>
#include <string>
using namespace std;

int main() {
    // 1. 初始化map，按key升序排列，key自动去重
    map<int, string> m = {{3, "Java"}, {1, "C++"}, {2, "Python"}, {1, "C"}};
    cout << "1. 初始化后map（按key升序，key唯一）：" << endl;
    // 遍历方式1：范围for
    for (auto &p : m) {
        cout << "key:" << p.first << "  value:" << p.second << endl;
    }
    cout << "map的键值对个数：" << m.size() << endl << endl;

    // 2. 插入元素
    // 方式1：[] 最常用，key不存在则插入，存在则修改value
    m[4] = "Go";
    // 方式2：insert插入，key已存在的话，不会覆盖原有value
    m.insert(pair<int, string>(2, "PHP")); // key=2已存在，插入失败
    cout << "2. 插入后的map：" << endl;
    for (auto &p : m) {
        cout << "key:" << p.first << "  value:" << p.second << endl;
    }
    cout << endl;

    // 3. 修改value
    m[2] = "Python3"; // key=2存在，直接修改value
    cout << "3. 修改key=2的value后：" << endl;
    cout << "key:2  value:" << m[2] << endl << endl;

    // 4. 删除元素
    m.erase(3); // 删除key=3的键值对
    cout << "4. 删除key=3后的map：" << endl;
    for (auto &p : m) {
        cout << "key:" << p.first << "  value:" << p.second << endl;
    }
    cout << endl;

    // 5. 查找元素
    auto it = m.find(1);
    if (it != m.end()) {
        cout << "5. 找到key=1，对应的value：" << it->second << endl;
    } else {
        cout << "5. key不存在" << endl;
    }

    // 6. 快速判断key是否存在
    if (m.count(4)) {
        cout << "6. key=4存在于map中" << endl << endl;
    }

    // 7. 清空容器
    m.clear();
    cout << "7. 清空后map是否为空：" << (m.empty() ? "是" : "否") << endl;

    return 0;
}
运行结果

plaintext

1. 初始化后map（按key升序，key唯一）：
key:1  value:C++
key:2  value:Python
key:3  value:Java
map的键值对个数：3

2. 插入后的map：
key:1  value:C++
key:2  value:Python
key:3  value:Java
key:4  value:Go

3. 修改key=2的value后：
key:2  value:Python3

4. 删除key=3后的map：
key:1  value:C++
key:2  value:Python3
key:4  value:Go

5. 找到key=1，对应的value：C++
6. key=4存在于map中

7. 清空后map是否为空：是

3.6 multimap 补充（允许重复 key）

用法和 map 基本一致，唯一区别是允许重复 key，不支持 [] 运算符（key 重复时无法确定返回哪个 value）：

cpp

运行

#include <map>
#include <iostream>
#include <string>
using namespace std;

int main() {
    multimap<int, string> mm;
    mm.insert({1, "苹果"});
    mm.insert({1, "香蕉"});
    mm.insert({2, "橙子"});

    cout << "multimap元素：" << endl;
    for (auto &p : mm) {
        cout << "key:" << p.first << "  value:" << p.second << endl;
    }
    cout << "key=1的元素个数：" << mm.count(1) << endl; // 输出2
    return 0;
}

四、高频考点 & 避坑指南

1. 迭代器失效问题

  • set/map 插入元素时，不会导致任何迭代器失效
  • erase 元素时，只有被删除的那个迭代器失效，其他迭代器可正常使用
  • 正确的循环删除写法（考试高频考点）：

cpp

运行

// set循环删除示例，map同理
set<int> s = {1,2,3,4,5};
auto it = s.begin();
while (it != s.end()) {
    if (*it % 2 == 0) {
        it = s.erase(it); // erase返回下一个有效迭代器
    } else {
        ++it;
    }
}

2. 能不能修改 key？

绝对不能！set 的元素、map 的 key，都是 const 常量，它们是红黑树的排序依据，擅自修改会破坏红黑树的结构，直接导致程序崩溃。如果需要修改 key，只能先删除旧的键值，再插入新的键值。

3. insert 和 [] 的区别（map 专属）

  • insert：key 不存在则插入，key 已存在则插入失败，不会覆盖原有 value
  • []：key 不存在则插入，key 已存在则直接覆盖原有 value
  • 注意：如果只是想判断 key 是否存在，用find或count，别用[]—— 因为[]会在 key 不存在时自动插入一个默认值的元素，改变 map 的大小。

4. 自定义类型怎么放进 set/map？

因为 set/map 需要排序，所以自定义类型必须重载<运算符，告诉编译器如何比较大小：

cpp

运行

#include <set>
#include <iostream>
#include <string>
using namespace std;

// 自定义类型
class Student {
public:
    int id;
    string name;
    // 重载<运算符，按id升序排序
    bool operator<(const Student &other) const {
        return this->id < other.id;
    }
};

int main() {
    set<Student> s;
    s.insert({1, "张三"});
    s.insert({2, "李四"});
    for (auto &stu : s) {
        cout << "id:" << stu.id << "  name:" << stu.name << endl;
    }
    return 0;
}

五、总结

  1. set：有序、去重的集合，适合存储单一值，做去重、排序、存在性判断
  2. map：有序、key 唯一的键值对字典，适合做 key-value 映射、通过 key 快速查找 value
  3. 两者底层都是红黑树，核心操作时间复杂度稳定在 O (logn)，效率极高
  4. 高频接口：insert、erase、find、count，日常遍历用范围 for 最省事
  5. 核心坑点：不能修改 key，循环删除要接收 erase 的返回值，map 判断 key 存在别用[]
# c++
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

人工智能训练师-职业发展规划与持续学习

avatar 亚马逊云科技技术品牌专区

AIGC（生成式AI）试用 53 -- 个人知识库 DocsGpt(Agent)

AIGC（生成式AI）试用 53 -- 个人知识库 DocsGpt(Agent)

avatar 亚马逊云科技技术品牌专区
cover

【硬件+APP+云平台】30.1.智能仓储-V2.0-基于STM32嵌入式物联网单片机软硬件毕业生系统设计

avatar 亚马逊云科技技术品牌专区