C++ multiset 核心原理与实战指南

2.2 迭代器相关

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

#include <set>
#include <iostream>
using namespace std;

int main() {
    // 构造 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;
    return 0;
}

2.3 容量相关

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

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

#include <set>
#include <iostream>
using namespace std;

int main() {
    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）
    return 0;
}

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

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

#include <set>
#include <iostream>
using namespace std;

int main() {
    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;
    }
    return 0;
}

三、multiset 实战案例

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

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

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

#include <set>
#include <iostream>
#include <vector>
using namespace std;

void countAndSortElements(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);
    }
}

int main() {
    vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    cout << "数组元素频率统计（按元素升序）：" << endl;
    countAndSortElements(arr);
    return 0;
}

输出结果：

数组元素频率统计（按元素升序）：
元素 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>
using namespace std;

class MedianFinder {
private:
    // 左半部分：大根堆（用 greater 排序，最大元素在末尾）
    multiset<int, greater<int>> left;
    // 右半部分：小根堆（默认升序，最小元素在开头）
    multiset<int> right;

public:
    // 插入元素
    void addNum(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);
        }
        
        // 确保左半部分元素个数最多比右半部分多 1
        if (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);
        }
    }
    
    // 查询中位数
    double findMedian() {
        if (left.size() > right.size()) {
            // 奇数个元素，左半部分最大值为中位数
            return *left.begin();
        } else {
            // 偶数个元素，取两部分顶元素的平均值
            return (*left.begin() + *right.begin()) / 2.0;
        }
    }
};

int main() {
    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.5
    return 0;
}

四、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()）和适用场景，能帮助我们在处理有序重复数据时写出更高效、简洁的代码。