C++ multiset 全面解析与实战指南

C++ multiset 全面解析与实战指南

在C++标准模板库（STL）的关联容器中，multiset是一种支持元素重复存储的有序集合。它与基础的set容器核心逻辑一致，均基于红黑树（自平衡二叉搜索树）实现，保证了元素的有序性和高效的增删查操作；但区别于set的“元素唯一性”限制，multiset允许相同值的元素共存，这使其在处理需要存储重复数据且需有序排列的场景时极具优势。本文将从底层原理出发，详细拆解multiset的核心特性、常用接口，结合实战案例演示具体用法，并对比set明确适用边界，帮助大家彻底掌握这一实用容器。

一、multiset 核心原理与特性

要理解multiset的行为逻辑，首先需要明确其底层实现和核心特性，这是正确使用它的基础。

1.1 底层实现：红黑树的支撑

multiset与set、map、multimap同属STL关联容器，底层均依赖红黑树（一种自平衡的二叉搜索树）实现。红黑树通过节点颜色（红/黑）的约束和动态旋转操作，确保树的高度始终维持在O(log n)级别，从而保证了插入、删除、查找等核心操作的时间复杂度稳定为O(log n)。

对于multiset而言，红黑树的“二叉搜索树特性”（左子树节点值 ≤ 父节点值 ≤ 右子树节点值，支持重复元素）是其“有序性”和“重复存储”的核心保障。当插入新元素时，红黑树会根据元素值找到合适的插入位置，维持整体有序；当删除元素时，会通过旋转调整保持树的平衡，确保后续操作效率。

1.2 核心特性总结

• 有序性：元素默认按升序排列（可通过自定义比较函数修改排序规则）；
• 允许重复：支持存储多个值相同的元素，无“唯一性”限制；
• 高效操作：插入、删除、查找的时间复杂度均为O(log n)，效率稳定；
• 不可直接修改元素：元素是排序的依据，直接修改会破坏红黑树的有序性，需先删除旧元素再插入新元素；
• 迭代器特性：支持双向迭代器（可++/–遍历），不支持随机访问；插入/删除元素时，除指向被删除元素的迭代器外，其他迭代器均不失效；
• 无下标访问：因元素有序但无索引概念，不支持operator[]和at()接口。

1.3 与set的核心区别

multiset与set的底层实现完全一致，核心差异仅在于对“元素唯一性”的要求，这也导致了两者接口和用法的细微区别。通过下表可快速区分：

二、C++ multiset 常用接口详解

使用multiset前，需包含头文件 <set>（与set共用头文件），并使用std命名空间（或显式指定std::multiset）。multiset的接口与set大部分一致，以下重点讲解核心接口及多元素场景下的特殊用法。

2.1 构造与析构

2.2 迭代器相关

multiset的迭代器用于遍历有序元素，核心接口与其他关联容器一致：

#include<set>#include<iostream>usingnamespace std;intmain(){// 构造multiset，包含重复元素，默认升序 multiset<int> ms ={2,1,3,2,4,1};// 正向遍历（升序） cout <<"正向遍历（升序）：";for(auto it = ms.begin(); it != ms.end();++it){ cout <<*it <<" ";// 输出：1 1 2 2 3 4} cout << endl;// 反向遍历（降序） cout <<"反向遍历（降序）：";for(auto it = ms.rbegin(); it != ms.rend();++it){ cout <<*it <<" ";// 输出：4 3 2 2 1 1} cout << endl;// 自定义降序的multiset multiset<int, greater<int>> ms_desc ={2,1,3,2,4,1}; cout <<"自定义降序遍历：";for(auto x : ms_desc){ cout << x <<" ";// 输出：4 3 2 2 1 1} cout << endl;return0;}

2.3 容量相关

2.4 插入与删除（核心操作）

multiset的插入操作因支持重复元素，接口返回值与set不同；删除操作可按元素值、迭代器删除，灵活性较高。

#include<set>#include<iostream>usingnamespace std;intmain(){ multiset<int> ms;// 1. 插入单个元素 ms.insert(2); ms.insert(2);// 插入重复元素，成功 ms.emplace(1);// emplace直接构造，效率更高 cout <<"插入后size："<< ms.size()<< endl;// 输出：3 cout <<"插入后元素：";for(auto x : ms) cout << x <<" ";// 输出：1 2 2 cout << endl;// 2. 插入区间元素int arr[]={3,2,4}; ms.insert(arr, arr +3); cout <<"插入区间后元素：";for(auto x : ms) cout << x <<" ";// 输出：1 2 2 2 3 4 cout << endl;// 3. 按元素值删除（删除所有2） size_t delCount = ms.erase(2); cout <<"删除元素2的个数："<< delCount << endl;// 输出：3 cout <<"删除后元素：";for(auto x : ms) cout << x <<" ";// 输出：1 3 4 cout << endl;// 4. 按迭代器删除（删除第一个元素）auto it = ms.begin(); ms.erase(it); cout <<"按迭代器删除后元素：";for(auto x : ms) cout << x <<" ";// 输出：3 4 cout << endl;// 5. 清空容器 ms.clear(); cout <<"clear后empty："<< ms.empty()<< endl;// 输出：1（true）return0;}

2.5 查找与统计（核心操作）

因multiset支持重复元素，查找操作除了常规的find()，还提供了专门用于定位“重复元素区间”的接口（lower_bound()、upper_bound()、equal_range()），这是处理重复元素的核心关键。

#include<set>#include<iostream>usingnamespace std;intmain(){ multiset<int> ms ={1,2,2,3,2,4,1};// 1. 查找第一个值为2的元素auto findIt = ms.find(2);if(findIt != ms.end()){ cout <<"第一个值为2的元素："<<*findIt << endl;// 输出：2}// 2. 统计值为2的元素个数 size_t count = ms.count(2); cout <<"值为2的元素个数："<< count << endl;// 输出：3// 3. 用lower_bound和upper_bound遍历所有值为2的元素auto lowIt = ms.lower_bound(2);auto upIt = ms.upper_bound(2); cout <<"lower_bound & upper_bound遍历值为2的元素：";for(auto it = lowIt; it != upIt;++it){ cout <<*it <<" ";// 输出：2 2 2} cout << endl;// 4. 用equal_range遍历所有值为2的元素（更简洁）auto range = ms.equal_range(2); cout <<"equal_range遍历值为2的元素：";for(auto it = range.first; it != range.second;++it){ cout <<*it <<" ";// 输出：2 2 2} cout << endl;// 5. 查找不存在的元素auto noIt = ms.find(5);if(noIt == ms.end()){ cout <<"值为5的元素不存在"<< endl;}return0;}

三、multiset 实战案例

multiset的核心优势是“有序存储+支持重复”，以下通过两个经典场景演示其实际应用：

3.1 场景1：统计数组元素出现频率并排序

需求：给定一个整数数组，统计每个元素的出现次数，并按元素值升序输出结果。

#include<set>#include<iostream>#include<vector>usingnamespace std;voidcountAndSortElements(const vector<int>& arr){// 1. 插入数组元素到multiset（自动排序+保留重复） multiset<int>ms(arr.begin(), arr.end());// 2. 遍历统计每个元素的出现次数auto it = ms.begin();while(it != ms.end()){int val =*it;// 统计当前元素的个数 size_t count = ms.count(val);// 输出结果 cout <<"元素 "<< val <<" 出现次数："<< count << endl;// 跳过当前元素的所有重复项 it = ms.upper_bound(val);}}intmain(){ vector<int> arr ={3,1,4,1,5,9,2,6,5,3,5}; cout <<"数组元素频率统计（按元素升序）："<< endl;countAndSortElements(arr);return0;}

输出结果：

 数组元素频率统计（按元素升序）： 元素 1 出现次数：2 元素 2 出现次数：1 元素 3 出现次数：2 元素 4 出现次数：1 元素 5 出现次数：3 元素 6 出现次数：1 元素 9 出现次数：1 

3.2 场景2：维护一个有序的数据流，支持快速查询中位数

需求：设计一个数据结构，支持向数据流中插入整数，并能快速查询当前数据流的中位数。中位数是有序列表中间的数（若列表长度为偶数，取中间两个数的平均值）。

思路：利用两个multiset构建“双堆”结构——左半部分（大根堆）存储较小的元素，右半部分（小根堆）存储较大的元素，确保左半部分元素个数≥右半部分（最多相差1）。此时：

• 若元素总数为奇数，左半部分的最大值（大根堆顶）即为中位数；
• 若元素总数为偶数，中位数为左半部分最大值与右半部分最小值的平均值。

#include<set>#include<iostream>#include<algorithm>usingnamespace std;classMedianFinder{private:// 左半部分：大根堆（用greater排序，最大元素在末尾） multiset<int, greater<int>> left;// 右半部分：小根堆（默认升序，最小元素在开头） multiset<int> right;public:// 插入元素voidaddNum(int num){// 先插入左半部分，再调整平衡 left.insert(num);// 确保左半部分的最大元素 ≤ 右半部分的最小元素if(!left.empty()&&!right.empty()&&*left.begin()>*right.begin()){int val =*left.begin(); left.erase(left.begin()); right.insert(val);}// 确保左半部分元素个数最多比右半部分多1if(left.size()> right.size()+1){int val =*left.begin(); left.erase(left.begin()); right.insert(val);}// 确保右半部分元素个数不超过左半部分if(right.size()> left.size()){int val =*right.begin(); right.erase(right.begin()); left.insert(val);}}// 查询中位数doublefindMedian(){if(left.size()> right.size()){// 奇数个元素，左半部分最大值为中位数return*left.begin();}else{// 偶数个元素，取两部分顶元素的平均值return(*left.begin()+*right.begin())/2.0;}}};intmain(){ MedianFinder mf; mf.addNum(1); mf.addNum(2); cout <<"当前中位数："<< mf.findMedian()<< endl;// 输出：1.5 mf.addNum(3); cout <<"当前中位数："<< mf.findMedian()<< endl;// 输出：2.0 mf.addNum(4); cout <<"当前中位数："<< mf.findMedian()<< endl;// 输出：2.5return0;}

四、multiset 使用注意事项

1. 禁止直接修改元素：multiset的元素是红黑树排序的依据，直接修改元素值会破坏树的有序性，导致容器行为异常。若需修改元素，必须先删除旧元素（erase()），再插入新元素（insert()）。
2. 自定义比较函数的规则：自定义排序时，比较函数必须满足“严格弱序”（即不可传递的等价关系）。例如，自定义降序使用std::greater，若自定义函数，需确保对于任意a、b，!comp(a,b) && !comp(b,a) 表示a和b等价（可共存）。
3. 迭代器失效问题：插入元素时，红黑树的旋转调整不会导致迭代器失效；删除元素时，只有指向被删除元素的迭代器失效，其他迭代器（包括指向其他元素的迭代器、begin()、end()等）均有效。
4. 效率对比与选择：
   • 若需存储不重复的有序数据，优先使用set（set的查找、插入效率略高于multiset，因无需处理重复元素的冗余逻辑）；
   • 若需存储重复的有序数据，优先使用multiset；若无需有序，可使用unordered_multiset（哈希表实现，平均插入/查找效率O(1)，但无序）。
5. 处理重复元素的最佳实践：遍历某一重复元素的所有实例时，优先使用equal_range()接口，其效率高于“find() + 循环计数”，且代码更简洁。
6. 线程安全性：与所有STL容器一致，multiset不保证线程安全。多线程环境下并发读写时，需手动加锁（如使用std::mutex）保护容器操作。

五、总结

multiset是C++ STL中用于存储“有序重复元素”的关联容器，底层基于红黑树实现，兼具有序性和高效操作的特性。其核心优势在于支持重复元素的有序存储，通过equal_range()等接口可便捷地处理重复元素的遍历与统计，特别适合频率统计、有序数据流维护等场景。

使用时需注意：禁止直接修改元素、不支持下标访问，若无需重复元素应优先选择set。掌握multiset的核心接口（尤其是equal_range()）和适用场景，能帮助我们在处理有序重复数据时写出更高效、简洁的代码。