在C++的标准模板库（STL）中，multiset和set是一对名称相似、底层实现也相近的容器。它们都基于高效的红黑树结构，因此在插入、删除和查找等核心操作上，都能提供O(log n)的优秀时间复杂度。不过，名字里多出来的这个“multi”，恰恰点明了二者最根本的区别，也决定了它们各自适用的场景。

核心特性与声明方式

简单来说，multiset是一个允许元素重复的有序集合。这意味着，同一个值可以在容器中间出现多次。它的接口设计与set高度统一，你熟悉的那些操作——获取大小(size)、判空(empty)、清空(clear)、插入(insert)、删除(erase)、查找(find)以及获取首尾迭代器——在multiset中几乎完全一致。

要使用它，首先需要在源文件中包含对应的头文件：

#include 

声明和初始化一个multiset的语法也很直观：

std::multiset myMultiset; // 声明一个存储int类型的空multiset
std::multiset words = {"apple", "banana", "apple"}; // 初始化，允许重复

为何需要multiset？

既然有了set，为什么标准库还要提供multiset呢？关键在于“重复”二字。在很多实际场景中，数据的重复出现本身就是有意义的、需要被记录的信息，而不是应该被自动过滤的“噪音”。

例如，统计一段文本中每个单词出现的频率，或者记录一系列可能重复的考试成绩。在这些情况下，multiset允许重复元素的特性，使得它成为比set更自然、更直接的选择。下图清晰地展示了二者在功能约束上的核心差异：

关键行为差异：count()与find()

允许重复的特性，直接影响了multiset中某些成员方法的行为和效率考量。

最典型的就是count(x)方法。在set中，由于元素唯一，count(x)的结果只能是0或1，本质上等同于存在性检查。但在multiset中，count(x)会返回值x在容器中真实出现的次数，这是一个非常有用的功能。需要注意的是，其时间复杂度是O(k + log n)，其中k是值x的重复次数。

反过来，当仅仅需要判断一个元素是否存在时，在set中可以直接用find(x) != end()，效率是O(log n)。在multiset中虽然也可以这样做，但如果你知道元素很可能存在且重复，使用find(x)找到的是第一个等于x的迭代器，语义上略有不同。下图通过一个例子说明了这种差异：

对元素类型的要求

和set一样，multiset要求其存储的元素类型必须是可比较的，默认使用operator<来维护内部的有序结构。

• 对于int、double、std::string等内置或标准库类型，系统已经定义了小于运算符，可以直接使用。
• 如果存储的是自定义的结构体或类对象，则必须显式地为这个类型重载operator<，否则编译器会报错。这确保了红黑树在插入和查找时，能够正确地对元素进行排序和定位。

总而言之，你可以将multiset理解为一个“允许重复的set”。在选择容器时，明确你的数据是否需要保持唯一性，是做出正确决定的关键。根据实际需求在set和multiset之间进行选择，不仅能更准确地表达程序意图，也能提升代码的清晰度和开发效率。

《夸克》非常好用的免费AI浏览器

下载APP查看