云子量化

c++中multiset使用方法

作者：yunjinqi 类别：编程日期：2025-04-27 18:23:14 阅读：71 次消耗积分：0 分

C++ std::multiset 详细使用指南

std::multiset 是 C++ STL 提供的一个有序关联容器，允许存储多个相同值的元素，并自动按照升序（默认）排序。它基于红黑树（Red-Black Tree）实现，因此插入、删除和查找操作的时间复杂度均为 O(log n)。

1. std::multiset 的基本特性

特性	说明
存储方式	允许存储重复元素
排序方式	默认升序（可自定义比较函数）
底层实现	红黑树（平衡二叉搜索树）
时间复杂度
- 插入 `insert()`	O(log n)
- 删除 `erase()`	O(log n)
- 查找 `find()`	O(log n)
是否允许重复元素	✅ 允许
是否有序	✅ 自动排序
是否允许修改元素	❌ 不能直接修改（需先删除再插入）

2. 头文件与声明

#include <set>  // 包含 multiset 的头文件

std::multiset<T> ms;  // 默认升序排列
std::multiset<T, Compare> ms;  // 使用自定义比较函数

• T：存储的元素类型（必须支持 < 比较运算符）。

• Compare：自定义比较函数（如 std::greater<T> 实现降序）。

3. 基本操作
(1) 插入元素
std::multiset 支持多种插入方式：

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    // 方式 1: insert(value)
    ms.insert(3);
    ms.insert(1);
    ms.insert(2);

    // 方式 2: emplace（C++11，直接构造元素）
    ms.emplace(4);
    ms.emplace(2);  // 允许重复

    // 输出所有元素（自动排序）
    for (int x : ms) {
        std::cout<< x << " ";  // 输出: 1 2 2 3 4
    }
    std::cout << std::endl;

    return 0;
}

输出：

1 2 2 3 4

(2) 访问元素
std::multiset 没有 operator[]（因为可能有多个相同值），只能通过迭代器访问：

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms = {3, 1, 2, 2, 4};

    // 遍历所有元素
    for (int x : ms) {
        std::cout<< x << " ";  // 输出: 1 2 2 3 4
    }
    std::cout << std::endl;

    // 访问第一个元素
    auto it = ms.begin();
    std::cout << "First element: " << *it << std::endl;  // 输出: 1

    return 0;
}

(3) 查找元素
std::multiset 提供多种查找方式：

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms = {1, 2, 2, 3, 4};

    // 方式 1: find(key) - 返回第一个匹配的迭代器
    auto it = ms.find(2);
    if (it != ms.end()) {
        std::cout << "First 2 found at: " << *it << std::endl;  // 输出: 2
    }

    // 方式 2: count(key) - 返回 key 的出现次数
    std::cout << "Count of 2: " << ms.count(2) << std::endl;  // 输出: 2

    // 方式 3: lower_bound(key) - 返回第一个 >= key 的迭代器
    auto lb = ms.lower_bound(2);
    std::cout << "First >= 2: " << *lb << std::endl;  // 输出: 2

    // 方式 4: upper_bound(key) - 返回第一个 > key 的迭代器
    auto ub = ms.upper_bound(2);
    std::cout << "First > 2: " << *ub << std::endl;  // 输出: 3

    // 方式 5: equal_range(key) - 返回 [first, last) 范围
    auto range = ms.equal_range(2);
    std::cout << "All 2s: ";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << *it << " ";  // 输出: 2 2
    }
    std::cout << std::endl;

    return 0;
}

输出：

First 2 found at: 2
Count of 2: 2
First >= 2: 2
First > 2: 3
All 2s: 2 2

(4) 删除元素
std::multiset 支持多种删除方式：

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms = {1, 2, 2, 3, 4};

    // 方式 1: erase(it) - 删除指定迭代器的元素
    auto it = ms.find(2);
    if (it != ms.end()) {
        ms.erase(it);  // 删除第一个 2
    }

    // 方式 2: erase(key) - 删除所有匹配的 key
    ms.erase(2);  // 删除所有 2

    // 方式 3: erase(first, last) - 删除 [first, last) 范围内的元素
    auto range = ms.equal_range(3);
    ms.erase(range.first, range.second);  // 删除 3（如果存在多个，需调整）

    // 输出剩余元素
    for (int x : ms) {
        std::cout<< x << " ";  // 输出: 1 4
    }
    std::cout << std::endl;

    return 0;
}

注意：
• erase(key) 会删除所有匹配 key 的元素。

• erase(it) 只删除单个元素（迭代器指向的元素）。

• erase(first, last) 删除 [first, last) 范围内的元素。

(5) 自定义排序规则
默认按升序排列，但可以自定义比较函数（如降序）：

#include <iostream>
#include <set>
#include <functional>  // std::greater

int main() {
    // 使用 std::greater<int> 实现降序排列
    std::multiset<int, std::greater<int>> ms = {3, 1, 2, 2, 4};

    for (int x : ms) {
        std::cout<< x << " ";  // 输出: 4 3 2 2 1
    }
    std::cout << std::endl;

    return 0;
}

4. std::multiset vs std::set

特性	`std::multiset`	`std::set`
是否允许重复元素	✅ 允许	❌ 不允许
查找方式	`find()` 返回第一个匹配项 `count()` 返回出现次数 `equal_range()` 返回所有匹配项	`find()` 返回唯一匹配项（或 `end()`）
插入方式	可插入重复元素	插入重复元素会忽略
删除方式	`erase(it)` 删除单个 `erase(key)` 删除所有匹配项	`erase(it)` 删除单个 `erase(key)` 删除唯一匹配项
适用场景	需要存储多个相同值的有序数据（如单词频率统计）	需要唯一值的有序数据（如字典）

5. 典型应用场景
(1) 统计单词出现次数（允许重复元素）

#include <iostream>
#include <set>
#include <string>

int main() {
    std::multiset<std::string> wordCount;

    // 模拟单词出现
    wordCount.insert("apple");
    wordCount.insert("banana");
    wordCount.insert("apple");
    wordCount.insert("cherry");

    // 统计每个单词的出现次数
    for (const auto& word : wordCount) {
        std::cout << word << std::endl;
    }

    // 注意：std::multiset 不直接提供计数功能，需结合其他方法
    // 更推荐使用 std::map<std::string, int> 或 unordered_map

    return 0;
}

注意：std::multiset 适合存储重复元素，但统计频率更推荐 std::map<std::string, int>。

(2) 按分数分组学生（允许重复分数）

#include <iostream>
#include <set>
#include <string>

int main() {
    std::multiset<int> studentScores;

    // 学生分数（可能有多个学生同分）
    studentScores.insert(90);
    studentScores.insert(85);
    studentScores.insert(90);
    studentScores.insert(80);

    // 按分数分组输出
    for (int score : studentScores) {
        std::cout << score << " ";  // 输出: 80 85 90 90
    }
    std::cout << std::endl;

    return 0;
}

6. 总结

特性	说明
允许重复元素	✅ `std::multiset` 允许存储多个相同值的元素
自动排序	默认按升序排列，可自定义比较函数（如降序）
查找方式	`find()` 返回第一个匹配项 `count()` 返回出现次数 `equal_range()` 返回所有匹配项
插入方式	支持 `insert()`, `emplace()`
删除方式	`erase(it)` 删除单个 `erase(key)` 删除所有匹配项
适用场景	需要存储多个相同值的有序数据（如单词频率、分组数据）

std::multiset 是处理允许重复元素的有序数据的理想选择，适用于需要按顺序存储多个相同值的场景。