C++ multimap
multimap介绍
multimap是C++ STL（标准模板库）中的一个关联容器，它允许存储键值对（key-value对），并且支持同一个键关联多个值。与map容器不同的是，multimap允许重复的键值存在，而map只允许唯一的键值。
multimap的主要特性包括：
- 元素按照键（key）自动排序
- 允许键重复
- 通过键来查找元素
- 不支持通过下标访问元素
- 内部实现通常基于红黑树
备注
multimap和map都是有序容器，默认使用less<Key>比较键的大小，可以自定义比较函数。
multimap的声明和初始化
要使用multimap，首先需要包含相应的头文件：
cpp
#include <map>
创建一个multimap的基本语法：
cpp
std::multimap<KeyType, ValueType> multimap_name;
其中：
KeyType是键的类型ValueType是值的类型
下面是一些初始化multimap的例子：
cpp
#include <iostream>
#include <map>
#include <string>
int main() {
// 创建空multimap
std::multimap<int, std::string> mm1;
// 使用初始化列表
std::multimap<int, std::string> mm2 = {
{1, "apple"},
{2, "banana"},
{1, "orange"}, // 注意这里键"1"重复了
{3, "grape"}
};
// 从另一个multimap复制
std::multimap<int, std::string> mm3(mm2);
return 0;
}
multimap的常用操作
插入元素
multimap提供了几种插入元素的方法：
cpp
#include <iostream>
#include <map>
#include <string>
int main() {
std::multimap<int, std::string> fruits;
// 方法1：使用insert方法插入std::pair
fruits.insert(std::pair<int, std::string>(1, "apple"));
// 方法2：使用make_pair函数
fruits.insert(std::make_pair(2, "banana"));
// 方法3：使用初始化列表
fruits.insert({1, "orange"}); // 键"1"重复
fruits.insert({3, "grape"});
// 输出multimap中的所有元素
std::cout << "Multimap内容：" << std::endl;
for(const auto& pair : fruits) {
std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
}
return 0;
}
输出结果：
Multimap内容：
Key: 1, Value: apple
Key: 1, Value: orange
Key: 2, Value: banana
Key: 3, Value: grape
注意观察输出结果，两个键为1的元素都被保留了，而且它们按照插入顺序排列。
查找元素
查找multimap中的元素可以使用find()方法，但由于multimap允许键重复，查找特定键的所有值需要使用额外的方法：
cpp
#include <iostream>
#include <map>
#include <string>
int main() {
std::multimap<int, std::string> fruits = {
{1, "apple"},
{2, "banana"},
{1, "orange"},
{3, "grape"},
{1, "mango"}
};
// 查找单个元素
auto it = fruits.find(1);
if(it != fruits.end()) {
std::cout << "找到键1的一个值: " << it->second << std::endl;
}
// 查找具有相同键的所有元素
std::cout << "\n查找键1的所有值:" << std::endl;
// 方法1：使用equal_range
auto range = fruits.equal_range(1);
for(auto it = range.first; it != range.second; ++it) {
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}
// 方法2：使用count和find
std::cout << "\n键1出现的次数: " << fruits.count(1) << std::endl;
return 0;
}
输出结果：
找到键1的一个值: apple
查找键1的所有值:
Key: 1, Value: apple
Key: 1, Value: orange
Key: 1, Value: mango
键1出现的次数: 3
删除元素
删除multimap中的元素可以通过几种方式：
cpp
#include <iostream>
#include <map>
#include <string>
int main() {
std::multimap<int, std::string> fruits = {
{1, "apple"},
{2, "banana"},
{1, "orange"},
{3, "grape"},
{1, "mango"}
};
// 删除单个元素(删除第一个找到的键为2的元素)
fruits.erase(2);
// 删除迭代器指向的元素
auto it = fruits.find(3);
if(it != fruits.end()) {
fruits.erase(it);
}
// 删除特定键的所有元素
fruits.erase(1);
std::cout << "删除后的multimap内容：" << std::endl;
for(const auto& pair : fruits) {
std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
}
return 0;
}
输出结果：
删除后的multimap内容：
所有元素都被删除了，因为我们先删除了键为2和3的元素，然后删除了所有键为1的元素。
multimap的其他重要操作
获取multimap的大小
cpp
#include <iostream>
#include <map>
int main() {
std::multimap<int, std::string> mm = {
{1, "one"},
{2, "two"},
{1, "uno"},
{3, "three"}
};
std::cout << "multimap的大小: " << mm.size() << std::endl;
std::cout << "multimap是否为空: " << (mm.empty() ? "是" : "否") << std::endl;
return 0;
}
输出结果：
multimap的大小: 4
multimap是否为空: 否
遍历multimap
遍历multimap的几种方式：
cpp
#include <iostream>
#include <map>
#include <string>
int main() {
std::multimap<int, std::string> mm = {
{1, "one"},
{2, "two"},
{1, "uno"},
{3, "three"}
};
// 方法1：使用迭代器
std::cout << "使用迭代器遍历：" << std::endl;
for(auto it = mm.begin(); it != mm.end(); ++it) {
std::cout << it->first << ": " << it->second << std::endl;
}
// 方法2：使用范围for循环（C++11及以上）
std::cout << "\n使用范围for循环遍历：" << std::endl;
for(const auto& pair : mm) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
输出结果：
使用迭代器遍历：
1: one
1: uno
2: two
3: three
使用范围for循环遍历：
1: one
1: uno
2: two
3: three
自定义比较函数
默认情况下，multimap使用std::less<Key>来比较键并排序。你可以提供自己的比较函数来改变排序规则：
cpp
#include <iostream>
#include <map>
#include <string>
// 自定义比较函数，实现降序排序
struct DescendingOrder {
bool operator()(int a, int b) const {
return a > b; // 降序排序
}
};
int main() {
// 使用自定义比较函数创建multimap
std::multimap<int, std::string, DescendingOrder> mm = {
{1, "one"},
{2, "two"},
{1, "uno"},
{3, "three"}
};
std::cout << "使用降序比较函数的multimap：" << std::endl;
for(const auto& pair : mm) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
输出结果：
使用降序比较函数的multimap：
3: three
2: two
1: one
1: uno
multimap的实际应用场景
multimap在实际编程中有许多应用场景，特别是当一个键需要关联多个值时。以下是几个实际应用例子：
1. 学生成绩管理系统
一个班级中，多个学生可能获得相同的分数，使用multimap可以轻松按分数查找所有学生：
cpp
#include <iostream>
#include <map>
#include <string>
int main() {
// 创建一个multimap来存储学生成绩，键为成绩，值为学生姓名
std::multimap<int, std::string, std::greater<int>> grades;
// 添加学生成绩
grades.insert({95, "张三"});
grades.insert({88, "李四"});
grades.insert({95, "王五"}); // 张三和王五同分
grades.insert({76, "赵六"});
grades.insert({88, "钱七"}); // 李四和钱七同分
// 打印所有学生成绩（按成绩从高到低排序）
std::cout << "学生成绩榜单（从高到低）：" << std::endl;
for(const auto& entry : grades) {
std::cout << entry.second << ": " << entry.first << "分" << std::endl;
}
// 查找所有获得95分的学生
std::cout << "\n获得95分的学生：" << std::endl;
auto range = grades.equal_range(95);
for(auto it = range.first; it != range.second; ++it) {
std::cout << it->second << std::endl;
}
return 0;
}
输出结果：
学生成绩榜单（从高到低）：
张三: 95分
王五: 95分
李四: 88分
钱七: 88分
赵六: 76分
获得95分的学生：
张三
王五
2. 单词出现频率统计
分析文本中单词出现的位置，一个单词可能在文本中多次出现：
cpp
#include <iostream>
#include <map>
#include <string>
#include <sstream>
#include <vector>
int main() {
std::string text = "the quick brown fox jumps over the lazy dog fox jumps high";
std::multimap<std::string, int> wordPositions;
// 将文本分割为单词并记录位置
std::istringstream iss(text);
std::string word;
int position = 0;
while(iss >> word) {
wordPositions.insert({word, position});
position++;
}
// 打印每个单词及其出现的位置
std::cout << "单词在文本中的位置：" << std::endl;
std::string currentWord = "";
for(const auto& entry : wordPositions) {
if(currentWord != entry.first) {
currentWord = entry.first;
std::cout << "\n" << currentWord << " 出现在位置: ";
} else {
std::cout << ", ";
}
std::cout << entry.second;
}
return 0;
}
输出结果：
单词在文本中的位置：
brown 出现在位置: 2
dog 出现在位置: 8
fox 出现在位置: 3, 9
high 出现在位置: 11
jumps 出现在位置: 4, 10
lazy 出现在位置: 7
over 出现在位置: 5
quick 出现在位置: 1
the 出现在位置: 0, 6
3. 事件调度系统
一个事件调度系统中，可能在同一时间点需要处理多个事件：
cpp
#include <iostream>
#include <map>
#include <string>
#include <functional>
#include <iomanip>
// 简单的事件类
class Event {
public:
Event(std::string name) : name_(name) {}
void execute() const {
std::cout << "执行事件: " << name_ << std::endl;
}
std::string getName() const {
return name_;
}
private:
std::string name_;
};
int main() {
// 事件调度器，键为时间点，值为事件
std::multimap<int, Event> scheduler;
// 添加事件
scheduler.insert({1000, Event("发送邮件")});
scheduler.insert({2000, Event("备份数据")});
scheduler.insert({1000, Event("更新数据库")}); // 与发送邮件在同一时间点
scheduler.insert({1500, Event("检查日志")});
scheduler.insert({2000, Event("生成报告")}); // 与备份数据在同一时间点
// 模拟事件调度
std::cout << "事件调度模拟：" << std::endl;
int currentTime = 0;
for(const auto& event : scheduler) {
// 如果时间变化，显示时间戳
if(currentTime != event.first) {
currentTime = event.first;
std::cout << "\n时间: " << std::setw(4) << currentTime << " ms" << std::endl;
}
// 执行事件
event.second.execute();
}
return 0;
}
输出结果：
事件调度模拟：
时间: 1000 ms
执行事件: 发送邮件
执行事件: 更新数据库
时间: 1500 ms
执行事件: 检查日志
时间: 2000 ms
执行事件: 备份数据
执行事件: 生成报告
multimap和map的比较
下表总结了multimap和map的主要区别：
| 特性 | map | multimap |
|---|---|---|
| 键唯一性 | 键必须唯一 | 允许键重复 |
| 访问元素 | 可以使用[]运算符 | 不能使用[]运算符 |
| 插入重复键 | 插入失败 | 成功插入 |
| 查找元素 | find()返回唯一结果 | 需要使用equal_range()查找所有匹配项 |
| 内部实现 | 红黑树 | 红黑树 |
multimap的性能特性
了解multimap的性能特性对于正确使用它非常重要：
总结
multimap是C++ STL中一个强大的关联容器，它允许在一个有序集合中存储键值对，并且支持键重复。其主要特点包括：
- 自动按键排序
- 支持相同键关联多个值
- 通过键进行高效查找
- 基于红黑树实现，提供稳定的性能特性
multimap在需要处理一对多关系时特别有用，例如学生成绩管理、单词索引、事件调度等场景。
对于初学者来说，掌握multimap的基本操作和使用场景是在C++编程道路上的重要一步。
练习题
为了巩固你对multimap的理解，试着完成以下练习：
- 创建一个电话簿程序，一个人可能有多个电话号码。
- 实现一个简单的课程管理系统，一个老师可能教授多个课程。
- 编写一个程序，统计一段文本中每个单词出现的次数和位置。
- 实现一个日程表程序，允许在同一时间安排多个事件，并按时间顺序显示所有事件。
更多资源
- C++ 参考手册 - multimap
- 《C++ Primer》第11章：关联容器
- 《Effective STL》Item 19：理解相等和等价的区别