C++算法

C++ 关联式容器：map 与 set 详解

C++ STL 中的关联式容器，包括 set、multiset、map 和 multimap。这些容器基于红黑树实现，提供有序存储和高效查找功能。文章详细讲解了键值对结构、各容器的特性差异（如是否允许重复键）、常用操作接口（插入、删除、查找）以及 map 下标运算符的使用场景。重点阐述了如何利用 set 进行排序去重，以及利用 map 统计元素出现次数。

协议工匠发布于 2026/3/23更新于 2026/4/183.7K 浏览

C++ 关联式容器概述

序列式与关联式容器

序列式容器：vector、list、deque、forward_list(C++11) 等，底层为线性序列数据结构，存储元素本身。
关联式容器：存储<key, value>结构的键值对，数据检索效率通常比序列式容器更高。

键值对<key, value>

通过 key 找 value，表示具有一一对应关系的结构。一般包含 key 和 value 两个成员变量。例如英汉字典，英文单词（key）对应中文含义（value）。

树形结构的关联式容器

STL 实现了两种管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。共同点是使用平衡搜索树（红黑树）作为底层结构，元素是有序序列（中序遍历）。

set 容器（key 模型）

功能介绍

set 是按照一定次序存储元素的容器。
在 set 中，元素的 value 也标识它（value 就是 key），每个 value 必须唯一。
元素不能在容器中修改，但可以插入或删除。
内部按照特定严格弱排序准则进行排序。
底层用二叉搜索树（红黑树）实现。

注意事项

map/multimap 存储真正的键值对<key, value>，set 只放 value，但底层实际存放<value, value>。
插入元素时只需插入 value，无需构造键值对。
元素不可重复（可用于去重）。
迭代器遍历可得有序序列。
默认按小于号比较。
查找时间复杂度为 O(log n)。
头文件：。

基本使用

插入与遍历

需先查看文档学习接口。迭代器使用方法与其他容器相同。

排序和去重

set 根据搜索二叉树的中序遍历插入，可对一组数排序并自动去重。

erase（删除）的区别

删除迭代器位置：若存在则删除，不存在报错。需配合 find 函数判断是否存在。
删除 val 值：返回删除的个数。
删除区间：左闭右开。利用 lower_bound（大于等于 k）和 upper_bound（大于 k）得到区间。

multiset 容器（允许插入重复值）

介绍

按特定顺序存储元素，元素可重复。
value 识别自身（<value, value>），类型 T。
元素不可修改，可插入或删除。
底层结构为二叉搜索树（红黑树）。

基本使用

与 set 类似，最大区别是支持存储重复数据。

接口区别

删除返回值：返回删除元素的个数。
count 函数：返回 val 在容器中的个数。
find 函数：查找中序遍历中出现的第一个 val 值并返回位置。

map 容器（<key, value>模型）

介绍

按特定次序（key 比较）存储键值组合元素。
key 用于排序和唯一标识，value 存储关联内容。
内部 key 与 value 通过 pair 绑定，typedef pair<const key, T> value_type。
允许根据顺序直接迭代。
支持下标访问符 []。
通常实现为平衡二叉搜索树（红黑树）。
头文件：。

pair 模板类

定义在头文件中，将两个不同类型的值组合成一个对象。可用 make_pair 函数构建。

模版参数说明

key: 键值对中 key 的类型。
T: 键值对中 value 的类型。
Compare: 比较器类型，缺省按小于比较，自定义类型需显式传递。
Alloc: 空间配置器，通常不需要用户传递。

insert 函数

常用参数为 value_type 引用（即 pair 对象）。打印时不能直接解引用访问，需用点（.）或箭头（->）访问 pair 成员。建议范围 for 循环加引用以避免拷贝代价。

去重特性

map 根据键值去重，字符串排序依次根据首字母 ASCII 码值进行。

multimap 容器

与 multiset 对应，map 也有对应的 multimap 容器。区别在于可以插入重复键值 k。

map 容器的 [ ] 操作符

场景：计算水果出现次数

使用迭代器和 find 函数：标准查找方式。
使用 insert 返回值：insert 返回 pair<iterator, bool>。bool 表示插入成功与否，iterator 指向新插入或已存在的结点。
使用 map 的 [ ]：
- 当访问不存在的 key 时，会调用 insert 插入默认构造的 value。
- 例如 int 默认为 0，指针默认为 nullptr。
- 逻辑上等同于：if (it == end()) insert(...); return it->second;
- 外面对 mapCount[e] 进行 ++，即对键值 e 对应结点的 second 进行累加，达到计数功能。

C++ 关联式容器：map 与 set 详解

C++ 关联式容器概述

序列式与关联式容器

键值对<key, value>

树形结构的关联式容器

set 容器（key 模型）

功能介绍

注意事项

基本使用

插入与遍历

排序和去重

erase（删除）的区别

multiset 容器（允许插入重复值）

介绍

基本使用

接口区别

map 容器（<key, value>模型）

介绍

pair 模板类

模版参数说明

insert 函数

去重特性

multimap 容器

map 容器的 [ ] 操作符

场景：计算水果出现次数

更多推荐文章

相关免费在线工具

C++ 关联式容器：map 与 set 详解

C++ 关联式容器概述

序列式与关联式容器

键值对<key, value>

树形结构的关联式容器

set 容器（key 模型）

功能介绍

注意事项

基本使用

插入与遍历

排序和去重

erase（删除）的区别

multiset 容器（允许插入重复值）

介绍

基本使用

接口区别

map 容器（<key, value>模型）

介绍

pair 模板类

模版参数说明

insert 函数

去重特性

multimap 容器

map 容器的 [ ] 操作符

场景：计算水果出现次数

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具