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

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

1. std::multiset 的基本特性

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

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 是处理 允许重复元素的有序数据 的理想选择，适用于需要 按顺序存储多个相同值 的场景。