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>usingnamespacestd;intmain(){// 构造multiset，包含重复元素，默认升序multiset<int>ms={2,1,3,2,4,1};// 正向遍历（升序）cout<<"正向遍历（升序）：";for(autoit=ms.begin();it!=ms.end();++it){cout<<*it<<" ";// 输出：1 1 2 2 3 4}cout<<endl;// 反向遍历（降序）cout<<"反向遍历（降序）：";for(autoit=ms.rbegin();it!=ms.rend();++it){cout<<*it<<" ";// 输出：4 3 2 2 1 1}cout<<endl;// 自定义降序的multisetmultiset<int,greater<int>>ms_desc={2,1,3,2,4,1};cout<<"自定义降序遍历：";for(autox:ms_desc){cout<<x<<" ";// 输出：4 3 2 2 1 1}cout<<endl;return0;}

2.3 容量相关

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

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

#include<set>#include<iostream>usingnamespacestd;intmain(){multiset<int>ms;// 1. 插入单个元素ms.insert(2);ms.insert(2);// 插入重复元素，成功ms.emplace(1);// emplace直接构造，效率更高cout<<"插入后size："<<ms.size()<<endl;// 输出：3cout<<"插入后元素：";for(autox:ms)cout<<x<<" ";// 输出：1 2 2cout<<endl;// 2. 插入区间元素intarr[]={3,2,4};ms.insert(arr,arr+3);cout<<"插入区间后元素：";for(autox:ms)cout<<x<<" ";// 输出：1 2 2 2 3 4cout<<endl;// 3. 按元素值删除（删除所有2）size_t delCount=ms.erase(2);cout<<"删除元素2的个数："<<delCount<<endl;// 输出：3cout<<"删除后元素：";for(autox:ms)cout<<x<<" ";// 输出：1 3 4cout<<endl;// 4. 按迭代器删除（删除第一个元素）autoit=ms.begin();ms.erase(it);cout<<"按迭代器删除后元素：";for(autox:ms)cout<<x<<" ";// 输出：3 4cout<<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>usingnamespacestd;intmain(){multiset<int>ms={1,2,2,3,2,4,1};// 1. 查找第一个值为2的元素autofindIt=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的元素autolowIt=ms.lower_bound(2);autoupIt=ms.upper_bound(2);cout<<"lower_bound & upper_bound遍历值为2的元素：";for(autoit=lowIt;it!=upIt;++it){cout<<*it<<" ";// 输出：2 2 2}cout<<endl;// 4. 用equal_range遍历所有值为2的元素（更简洁）autorange=ms.equal_range(2);cout<<"equal_range遍历值为2的元素：";for(autoit=range.first;it!=range.second;++it){cout<<*it<<" ";// 输出：2 2 2}cout<<endl;// 5. 查找不存在的元素autonoIt=ms.find(5);if(noIt==ms.end()){cout<<"值为5的元素不存在"<<endl;}return0;}

三、multiset 实战案例

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

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

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

#include<set>#include<iostream>#include<vector>usingnamespacestd;voidcountAndSortElements(constvector<int>&arr){// 1. 插入数组元素到multiset（自动排序+保留重复）multiset<int>ms(arr.begin(),arr.end());// 2. 遍历统计每个元素的出现次数autoit=ms.begin();while(it!=ms.end()){intval=*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>usingnamespacestd;classMedianFinder{private:// 左半部分：大根堆（用greater排序，最大元素在末尾）multiset<int,greater<int>>left;// 右半部分：小根堆（默认升序，最小元素在开头）multiset<int>right;public:// 插入元素voidaddNum(intnum){// 先插入左半部分，再调整平衡left.insert(num);// 确保左半部分的最大元素 ≤ 右半部分的最小元素if(!left.empty()&&!right.empty()&&*left.begin()>*right.begin()){intval=*left.begin();left.erase(left.begin());right.insert(val);}// 确保左半部分元素个数最多比右半部分多1if(left.size()>right.size()+1){intval=*left.begin();left.erase(left.begin());right.insert(val);}// 确保右半部分元素个数不超过左半部分if(right.size()>left.size()){intval=*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.5mf.addNum(3);cout<<"当前中位数："<<mf.findMedian()<<endl;// 输出：2.0mf.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()）和适用场景，能帮助我们在处理有序重复数据时写出更高效、简洁的代码。