跳到主要内容

C++ multiset

什么是 multiset​

multiset 是 C++ STL 库中的一个关联容器，它与 set 类似，都是用来存储有序数据的集合。不同之处在于 multiset 允许存储重复的元素，而 set 中所有元素都必须是唯一的。

multiset 具有以下主要特点：

  • 元素自动排序：元素按照特定的排序规则（默认是升序）进行存储
  • 允许重复值：可以存储多个相同的元素
  • 底层实现：通常采用红黑树实现，提供对数时间复杂度的操作效率
  • 不能直接修改元素：一旦元素被插入，不能直接修改它的值，只能删除再插入

基本用法​

包含头文件​

要使用 multiset，首先需要包含相应的头文件：

cpp
#include <set>  // multiset 定义在 set 头文件中

创建 multiset​

cpp
#include <iostream>
#include <set>

int main() {
    // 创建一个空的 multiset
    std::multiset<int> ms1;
    
    // 使用初始化列表
    std::multiset<int> ms2 = {5, 2, 4, 2, 5, 1};
    
    // 使用自定义排序（降序）
    std::multiset<int, std::greater<int>> ms3 = {5, 2, 4, 2, 5, 1};
    
    // 输出 ms2 的内容
    std::cout << "ms2 内容: ";
    for (const auto &elem : ms2) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // 输出 ms3 的内容
    std::cout << "ms3 内容 (降序): ";
    for (const auto &elem : ms3) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出：

ms2 内容: 1 2 2 4 5 5 
ms3 内容 (降序): 5 5 4 2 2 1

注意，即使我们插入的顺序是 {5, 2, 4, 2, 5, 1}，但在 ms2 中元素自动按升序排列，在 ms3 中按降序排列。

multiset 基本操作​

插入元素​

cpp
std::multiset<int> ms;
ms.insert(10);
ms.insert(20);
ms.insert(10);  // 可以插入重复元素

// 使用迭代器插入
std::vector<int> vec = {5, 15, 5};
ms.insert(vec.begin(), vec.end());

删除元素​

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

// 删除特定值的所有元素
ms.erase(3);  // 删除所有值为3的元素

// 删除特定值的一个元素
auto it = ms.find(2);
ms.erase(it);  // 只删除一个值为2的元素

// 删除范围
auto start = ms.lower_bound(2);
auto end = ms.upper_bound(4);
ms.erase(start, end);  // 删除 [2, 4) 范围内的所有元素

查找元素​

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

// 查找元素
auto it = ms.find(2);  // 返回第一个值为2的元素的迭代器
if (it != ms.end()) {
    std::cout << "找到元素: " << *it << std::endl;
}

// 计算特定值的元素个数
int count = ms.count(3);  // 返回3

// 找出小于等于给定值的第一个元素
auto lower = ms.lower_bound(3);  // 指向第一个3

// 找出大于给定值的第一个元素
auto upper = ms.upper_bound(3);  // 指向4

// 同时获取两个边界
auto range = ms.equal_range(3);  // 返回pair<lower_bound, upper_bound>

其他常用操作​

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

// 获取元素数量
std::cout << "大小: " << ms.size() << std::endl;  // 输出7

// 判断是否为空
bool isEmpty = ms.empty();  // false

// 清空容器
ms.clear();
std::cout << "清空后大小: " << ms.size() << std::endl;  // 输出0

multiset vs set​

为了更好地理解 multiset，让我们看看它与 set 的主要区别：

  1. 重复元素：

    • set 中的所有元素都必须唯一
    • multiset 允许存在重复元素

  2. 查找和删除：

    • 在 set 中，find() 和 erase() 只对应一个元素
    • 在 multiset 中，erase(value) 会删除所有匹配的元素，而 find() 只返回第一个匹配元素的迭代器

  3. 专用函数：

    • multiset 提供了 lower_bound()、upper_bound() 和 equal_range() 方法来处理重复元素

实际应用场景​

场景1：词频统计​

cpp
#include <iostream>
#include <set>
#include <string>
#include <map>

int main() {
    std::string text = "the quick brown fox jumps over the lazy dog the fox";
    std::multiset<std::string> words;
    
    // 解析文本
    std::string word;
    for (char c : text) {
        if (c == ' ') {
            if (!word.empty()) {
                words.insert(word);
                word.clear();
            }
        } else {
            word += c;
        }
    }
    if (!word.empty()) {
        words.insert(word);
    }
    
    // 输出词频
    std::map<std::string, int> wordFreq;
    for (const auto& w : words) {
        wordFreq[w]++;
    }
    
    for (const auto& pair : wordFreq) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}

输出：

brown: 1
dog: 1
fox: 2
jumps: 1
lazy: 1
over: 1
quick: 1
the: 3

场景2：多重排序待办事项​

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

// 任务结构体
struct Task {
    int priority;  // 优先级，越小越重要
    std::string description;
    
    // 重载小于运算符用于multiset排序
    bool operator<(const Task& other) const {
        return priority < other.priority;
    }
};

int main() {
    // 创建任务列表（按优先级排序）
    std::multiset<Task> taskList;
    
    // 添加任务
    taskList.insert({1, "完成项目提案"});
    taskList.insert({2, "回复邮件"});
    taskList.insert({1, "准备演示文稿"});
    taskList.insert({3, "整理文件"});
    taskList.insert({2, "预约会议"});
    
    // 显示任务（自动按优先级排序）
    std::cout << "待办事项列表（按优先级排序）：" << std::endl;
    for (const auto& task : taskList) {
        std::cout << "优先级 " << task.priority << ": " << task.description << std::endl;
    }
    
    return 0;
}

输出：

待办事项列表（按优先级排序）：
优先级 1: 完成项目提案
优先级 1: 准备演示文稿
优先级 2: 回复邮件
优先级 2: 预约会议
优先级 3: 整理文件

性能和复杂度​

multiset 的主要操作复杂度如下：

  • 插入：O(log n)
  • 删除：O(log n)
  • 查找：O(log n)
  • 获取大小：O(1)
  • 遍历：O(n)
提示

由于 multiset 使用平衡二叉搜索树实现，它在大多数操作上比 vector 或 list 更快，尤其是在需要频繁查找特定元素的情况下。

自定义比较函数​

可以通过提供自定义比较函数来改变 multiset 的排序规则：

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

// 自定义比较函数
struct StringLengthCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        // 首先按长度排序
        if (a.length() != b.length())
            return a.length() < b.length();
        // 长度相同则按字母顺序
        return a < b;
    }
};

int main() {
    // 使用自定义排序的multiset
    std::multiset<std::string, StringLengthCompare> words = {
        "apple", "cat", "banana", "dog", "elephant", "fox", "ant"
    };
    
    // 输出排序后的结果
    for (const auto& word : words) {
        std::cout << word << " (长度: " << word.length() << ")" << std::endl;
    }
    
    return 0;
}

输出：

ant (长度: 3)
cat (长度: 3)
dog (长度: 3)
fox (长度: 3)
apple (长度: 5)
banana (长度: 6)
elephant (长度: 8)

总结​

multiset 是 C++ STL 中一个强大的关联容器，它允许存储重复元素并保持元素的排序状态。主要特点包括：

  1. 元素自动排序（默认升序）
  2. 支持重复元素
  3. 高效的查找、插入和删除操作（O(log n)）
  4. 可以自定义排序规则

当你需要一个有序集合并且需要支持重复元素时，multiset 是一个理想的选择。它在需要频繁查找、统计元素频率的场景中特别有用。

练习​

  1. 创建一个 multiset<int>，插入一些数字，然后编写代码删除所有重复的元素，使其中只保留唯一的值。
  2. 编写一个函数，接受一个文本字符串，返回其中出现频率最高的三个单词。
  3. 使用 multiset 实现一个简单的优先级队列，每次取出最高优先级的任务。
  4. 创建一个程序，使用 multiset 按照学生成绩对学生进行排序，支持添加、删除学生及查询特定分数段的学生。

更多资源​

通过掌握 multiset，你已经向成为 C++ STL 专家迈出了重要一步！