C++中的multiset容器详解

1. multiset概述

multiset是C++ STL中的关联容器，允许存储重复的元素，并按照特定排序准则自动排序。它基于红黑树实现，提供高效的查找、插入和删除操作。

2. 基本特性

• 自动排序：元素总是按排序准则排序
• 允许重复：可以存储多个相同值的元素
• 高效操作：查找、插入、删除都是$O({\log }_{2}n)$时间复杂度
• 不可修改元素：元素值不可直接修改(会破坏排序)
• 双向迭代器：支持正向和反向遍历

3. 头文件与声明

#include <set>  // multiset和set在同一头文件中
using namespace std;

multiset<int> ms1;                     // 默认升序排列的空multiset
multiset<string, greater<string>> ms2; // 降序排列的multiset
multiset<double> ms3 = {3.14, 2.71};   // 初始化列表

4. 构造函数与初始化

4.1 默认构造

multiset<int> ms;

4.2 比较函数构造

struct CaseInsensitiveCompare {
    bool operator()(const string& a, const string& b) const {
        return strcasecmp(a.c_str(), b.c_str()) < 0;
    }
};
multiset<string, CaseInsensitiveCompare> ms;

4.3 范围构造

int arr[] = {5, 2, 7, 2, 5};
multiset<int> ms(arr, arr+5);

4.4 拷贝构造

multiset<int> ms2(ms1);

5. 容量操作

5.1 size()

cout << ms.size();  // 返回元素数量

5.2 empty()

if(ms.empty()) {
    cout << "Multiset is empty";
}

5.3 max_size()

cout << ms.max_size();  // 返回multiset可容纳的最大元素数

6. 元素访问

6.1 迭代器访问

for(auto it = ms.begin(); it != ms.end(); ++it) {
    cout << *it << " ";
}

7. 修改操作

7.1 insert()

ms.insert(10);                   // 插入单个元素
ms.insert({5, 15, 5});           // 插入初始化列表
ms.insert(arr, arr+3);           // 插入范围
auto it = ms.insert(20);         // 返回指向插入元素的迭代器

7.2 emplace()

ms.emplace(30);                  // 原地构造元素

7.3 erase()

ms.erase(5);                     // 删除所有值为5的元素
auto it = ms.find(10);
if(it != ms.end()) {
    ms.erase(it);                // 删除单个元素
}
ms.erase(ms.begin(), ms.end());  // 删除范围

7.4 clear()

ms.clear();  // 清空所有元素

7.5 swap()

multiset<int> ms2;
ms.swap(ms2);  // 交换两个multiset的内容

8. 查找操作

8.1 find()

auto it = ms.find(10);  // 返回指向第一个10的迭代器
if(it != ms.end()) {
    cout << "Found: " << *it;
}

8.2 count()

cout << ms.count(5);  // 返回值为5的元素个数

8.3 lower_bound()

auto it = ms.lower_bound(15);  // 返回第一个不小于15的元素

8.4 upper_bound()

auto it = ms.upper_bound(15);  // 返回第一个大于15的元素

8.5 equal_range()

auto range = ms.equal_range(5);  // 返回等于5的元素范围
for(auto it = range.first; it != range.second; ++it) {
    cout << *it << " ";
}

9. 观察器

9.1 key_comp()

auto comp = ms.key_comp();
cout << "Compare 5 and 10: " << comp(5, 10);

9.2 value_comp()

auto comp = ms.value_comp();
cout << "Compare 5 and 10: " << comp(5, 10);

10. 完整示例

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

int main() {
    // 创建并初始化multiset
    multiset<int> ms = {5, 2, 8, 2, 5, 10, 5};
    
    // 插入元素
    ms.insert(7);
    ms.insert({3, 3, 12});
    
    // 遍历multiset (自动排序)
    cout << "All elements: ";
    for(int num : ms) {
        cout << num << " ";
    }
    cout << endl;
    
    // 查找操作
    cout << "Count of 5: " << ms.count(5) << endl;
    
    auto it = ms.find(8);
    if(it != ms.end()) {
        cout << "Found 8 in multiset" << endl;
    }
    
    // 删除操作
    ms.erase(2);  // 删除所有2
    ms.erase(ms.find(5));  // 只删除一个5
    
    // 范围查找
    cout << "Elements between 5 and 10: ";
    auto low = ms.lower_bound(5);
    auto up = ms.upper_bound(10);
    for(auto it = low; it != up; ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 相等范围
    auto range = ms.equal_range(5);
    cout << "All 5s: ";
    for(auto it = range.first; it != range.second; ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 容量信息
    cout << "Size: " << ms.size() << endl;
    cout << "Is empty: " << (ms.empty() ? "Yes" : "No") << endl;
    
    return 0;
}

11. 性能提示

1. 插入、删除、查找都是$O({\log }_{2}n)$时间复杂度
2. 遍历操作是$O(n)$时间复杂度
3. 适合需要自动排序且允许重复元素的场景
4. 比unordered_multiset有更好的内存局部性
5. 迭代器在插入/删除操作后仍然有效(除非删除的是迭代器指向的元素)