在 C++ 中，容器是存放数据的重要数据结构，分为序列式容器和关联式容器。序列式容器（如 vector、list、deque）按线性顺序存储元素，元素的位置与值无关；而关联式容器则通过键（key）建立元素间的关联，实现高效的查找、插入和删除操作。本文将详细介绍关联式容器中最常用的 map 和 set，包括它们的底层实现、核心特性、使用方法及实际应用。

一、关联式容器的核心概念

1. 容器分类与特点

        关联式容器的核心是 “关联关系”，即通过键（key）快速定位元素，而无需像序列式容器那样遍历整个容器。其特点如下：

• 元素按特定规则排序（有序容器）或无序存储（无序容器）；
• 插入位置由元素的键决定，而非用户指定；
• 查找效率极高，平均时间复杂度为 O(logN)（有序容器）或 O(1)（无序容器）。

2. 底层实现

        有序容器（set、map 等）的底层通常采用 平衡二叉搜索树（红黑树） 实现，其特性为：

• 左子树所有节点的值 < 根节点的值；
• 右子树所有节点的值 > 根节点的值；
• 树的高度保持平衡，确保查找、插入、删除操作的时间复杂度为 O(logN)。

        无序容器（unordered_set、unordered_map 等）的底层采用 哈希表 实现，通过哈希函数将键映射到存储位置，平均时间复杂度为 O(1)，但最坏情况下可能退化为 O(N)。

3. 搜索模型

        关联式容器分为两种搜索模型：

• K 模型：仅存储键（key），如 set，核心功能是判断元素是否存在；
• KV 模型：存储键值对（key-value），如 map，核心功能是通过键查找对应的值。

二、set 的原理与使用

1. set 的核心特性

        set 是 有序、不重复 的 K 模型容器，底层为红黑树。其核心特性：

• 自动排序：插入元素后，容器会按键的升序（默认）排列；
• 自动去重：插入重复元素时，操作会失败，容器中仅保留一个实例；
• 不可修改元素：set 中的元素是 const 类型，修改元素会破坏红黑树的结构，需通过 “删除旧元素 + 插入新元素” 实现。

2. set 的常用操作

（1）插入操作

        set 不支持 push_back/push_front，需使用 insert() 插入元素：

1 2 3 4 5 6

#include <set> using namespace std; set<int> s; s.insert(3);   s.insert(1);   s.insert(3);   // 重复插入，操作失败

        插入后，set 中的元素会自动排序为 {1, 3}。

（2）遍历操作

set 支持迭代器遍历和范围 for 遍历：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

void test(){     set<int> s;     s.insert(3);     s.insert(4);     s.insert(1);     s.insert(2);     s.insert(3);     s.insert(7);     //排序＋去重     set<int>::iterator it = s.begin();     while (it != s.end())     {         cout << *it << " ";         it++;     }     cout << endl;     for (auto e : s)     {         cout << e << " ";     }     cout << endl; }

（3）删除操作

        set 支持两种删除方式：

• 通过迭代器删除（需先通过 find() 查找元素）；
• 直接通过值删除。

1 2 3 4 5 6 7 8 9

// 方式 1：通过迭代器删除 set<int>::iterator pos = s.find(7);   //log(N) //set<int>::iterator pos = find(s.begin(), s.end(), 4); //OP(N) if (pos != s.end()) {     s.erase(pos); } // 方式 2：直接通过值删除 s.erase(1);  // 删除元素 1，若不存在则无操作

（4）查找操作

        set 的查找功能是其核心，提供两种方式：

• 成员函数 find()：利用红黑树特性，时间复杂度 O(logN)；
• 算法 std::find()：线性遍历，时间复杂度 O(N)。

示例对比：

1 2 3 4 5

#include <algorithm>  // 包含 std::find // 成员函数 find() set<int>::iterator pos1 = s.find(3);  // 高效查找 // 算法 find() set<int>::iterator pos2 = find(s.begin(), s.end(), 3);  // 低效遍历

使用建议：优先使用 set 的成员函数 find() 以获得最佳性能。

3. set 的实际应用

        set 的核心优势是 快速存在性检查 和 高效去重排序，适用于以下场景：

• 存储学号、身份证号等唯一标识，快速验证是否存在；
• 对输入数据去重并排序，如统计考试成绩的不重复分数；
• 实现集合运算（交集、并集、差集）。

示例：验证学号是否存在

1 2 3 4 5 6 7 8 9

student_ids.insert("001"); student_ids.insert("002"); student_ids.insert("003"); string id = "002"; if (student_ids.find(id) != student_ids.end()) {     cout << "学号 " << id << " 存在" << endl; } else {     cout << "学号 " << id << " 不存在" << endl; }

三、map 的原理与使用

1. map 的核心特性

        map 是 有序、键唯一 的 KV 模型容器，底层为红黑树。其核心特性：

• 存储键值对（key-value），键（key）唯一，值（value）可重复；
• 按键自动排序（默认升序）；
• 通过键快速查找对应的值，时间复杂度 O(logN)；
• 支持通过键修改值，但键不可修改（否则会破坏红黑树结构）。

2. map 的常用操作

（1）pair 类型介绍

        map 中的元素是 pair<const key_type, value_type> 类型，pair 是一个模板结构体，包含两个成员：

• first：键（key），不可修改；
• second：值（value），可修改。

创建 pair 的方式：

1 2 3 4

// 方式 1：显式指定模板参数 pair<int, string> p1(1, "张三"); // 方式 2：使用 make_pair（自动推导类型） pair<int, string> p2 = make_pair(2, "李四");

（2）插入操作

        map 通过 insert() 插入 pair 类型元素：

1 2 3 4 5 6 7 8 9

#include <map> using namespace std; map<int, string> student_info; // 方式 1：插入 pair 对象 student_info.insert(pair<int, string>(1, "张三")); // 方式 2：使用 make_pair（推荐，更简洁） student_info.insert(make_pair(2, "李四")); // 方式 3：C++11 统一初始化 student_info.insert({3, "王五"});

复制讲解

        插入后，map 会按键的升序排列：{1:张三, 2:李四, 3:王五}。

（3）遍历操作

        map 支持迭代器遍历和范围 for 遍历，通过 it->first 访问键，it->second 访问值：

1 2 3 4 5 6 7 8 9 10

// 迭代器遍历 map<int, string>::iterator it = student_info.begin(); while (it != student_info.end()) {     cout << "学号：" << it->first << "，姓名：" << it->second << endl;     ++it; } // 范围 for 遍历 for (auto e : student_info) {     cout << "学号：" << e.first << "，姓名：" << e.second << endl; }

（4）查找与修改操作

        通过键查找值有两种方式：

• 成员函数 find()：返回指向该键值对的迭代器；
• 下标运算符 []：直接通过键访问值（若键不存在，会自动插入一个默认构造的键值对）。