目录
在 C++ 标准库的关联容器中，multimap 是一种特殊的存在。它允许键（Key）重复，能够存储多个具有相同键的键值对，同时保持键的有序性。这种特性使得 multimap 在处理 “一对多” 关系（如课程与学生、标签与文章）时高效且便捷。
一、multimap 基础概念与底层实现
1.1 定义与核心特性
multimap 是 map 的 “兄弟” 容器，二者的核心区别在于：
- 键的唯一性：
map要求键唯一，multimap允许键重复 - 插入行为：
map插入重复键时会被忽略，multimap会直接插入新元素 - 操作接口：
multimap不提供operator[]（因键不唯一，无法直接通过键访问唯一值）
典型应用场景：
- 学生管理系统：同一个班级（键）对应多个学生（值）
- 日志系统：同一个时间戳（键）对应多条日志记录（值）
- 索引系统：同一个关键词（键）对应多个文档编号（值）
1.2 底层数据结构
multimap 与 map 一样，底层基于 红黑树（Red-Black Tree） 实现。红黑树是平衡二叉搜索树，保证插入、删除、查找的时间复杂度均为 O(log n)。与 map 的区别在于，multimap 允许红黑树节点存储相同键的元素，插入时不会检查键是否已存在，而是直接按顺序插入到合适位置（保持中序遍历的有序性）。
红黑树节点结构示意图:
1.3 类模板定义
template <
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T>>
> class multimap;1.4 与其他容器的对比
| 容器 | 键唯一性 | 有序性 | 底层结构 | 查找时间 | 典型场景 |
|---|---|---|---|---|---|
map |
唯一 | 有序 | 红黑树 | O(log n) | 一对一映射 |
multimap |
允许重复 | 有序 | 红黑树 | O(log n) | 一对多映射（有序） |
unordered_map |
唯一 | 无序 | 哈希表 | O (1)（平均） | 高速查找（无需顺序） |
unordered_multimap |
允许重复 | 无序 | 哈希表 | O (1)（平均） | 高速一对多映射（无序） |
二、multimap 核心操作详解
2.1 定义与初始化
#include <iostream>
#include <map>
#include <string>
// 基本定义：键为 int，值为 string
std::multimap<int, std::string> mm;
// 初始化方式 1：插入多个键值对
std::multimap<int, std::string> scores = {
{100, "Alice"},
{100, "Bob"}, // 键重复，合法
{200, "Charlie"}
};
// 初始化方式 2：通过迭代器范围
std::multimap<int, std::string> copyScores(scores.begin(), scores.end());2.2 插入元素
multimap 提供多种插入方式，均允许键重复：
方式一：insert 函数
// 插入单个键值对（推荐）
mm.insert(std::make_pair(300, "David"));
mm.insert({300, "Eve"}); // C++11 统一初始化语法
// 插入另一个 multimap 的元素
mm.insert(copyScores.begin(), copyScores.end());方式二：emplace 就地构造
// 直接构造对象，避免临时对象拷贝
mm.emplace(400, "Frank");2.3 查找元素
由于键可能重复，multimap 的查找需返回键的范围：
方法一：find 查找第一个匹配键
auto it = mm.find(100);
if (it != mm.end()) {
std::cout << "First entry for key 100: " << it->second << std::endl; // 输出 Alice
}方法二：equal_range 查找键的完整范围
auto range = mm.equal_range(100);
for (auto it = range.first; it != range.second; ++it) {
std::cout << "Key 100 value: " << it->second << std::endl;
}
// 输出：
// Key 100 value: Alice
// Key 100 value: Bob方法三：lower_bound 和 upper_bound
auto lower = mm.lower_bound(100); // 第一个 >= 100 的键
auto upper = mm.upper_bound(100); // 第一个 > 100 的键
for (auto it = lower; it != upper; ++it) {
// 遍历键为 100 的所有元素
}2.4 删除元素
删除指定键的所有元素
size_t count = mm.erase(100); // 返回删除的元素个数（此处为 2）
std::cout << "Erased " << count << " entries for key 100" << std::endl;删除单个元素（通过迭代器）
auto it = mm.find(200);
if (it != mm.end()) {
mm.erase(it); // 删除键为 200 的第一个元素
}2.5 遍历元素
// 正向遍历（按键的升序排列）
for (const auto& entry : mm) {
std::cout << entry.first << ": " << entry.second << std::endl;
}
// 反向遍历（按键的降序排列）
for (auto it = mm.rbegin(); it != mm.rend(); ++it) {
std::cout << it->first << ": " << it->second << std::endl;
}三、性能分析与适用场景
3.1 时间复杂度分析
| 操作 | 平均复杂度 | 最坏复杂度 |
|---|---|---|
| 插入(insert) | O(log n) | O(n) |
| 删除(erase) | O(log n) | O(n) |
| 查找(find) | O(log n) | O(n) |
注意：红黑树的性能在极端情况下可能退化为O(n)，但通过自动平衡机制，这种情况发生的概率极低。
3.2 适用场景
- 一对多关系存储：如学生成绩管理（同名学生不同分数）、电话簿（同名多号码）。
- 范围查询需求：需要频繁按键范围查询数据（如时间区间内的日志记录）。
- 有序性要求：数据需要按键自动排序，且支持高效插入/删除。
对比其他容器：
- map：键唯一，适合一对一映射。
- unordered_multimap：基于哈希表，无序但平均O(1)查找，适合高频查询场景。
- vector/list：无序容器，需手动维护排序。
四、高级应用与进阶技巧
4.1 自定义比较函数
默认情况下，multimap 使用 std::less<Key> 进行键的排序。若需自定义排序规则（如降序、自定义结构体比较），需在声明时指定比较函子。
示例：降序排序
struct DescCompare {
bool operator()(int a, int b) const {
return a > b; // 降序排列
}
};
std::multimap<int, std::string, DescCompare> reversedMm;
reversedMm.insert({100, "A"});
reversedMm.insert({200, "B"});
// 遍历顺序：200, 100示例：结构体键的比较
struct Student {
int grade;
std::string name;
// 自定义比较：先按成绩降序，同成绩按姓名升序
bool operator<(const Student& other) const {
if (grade != other.grade) {
return grade > other.grade;
}
return name < other.name;
}
};
// 使用 Student 作为键类型
std::multimap<Student, int> studentScores;
studentScores.insert({{90, "Alice"}, 1001});
studentScores.insert({{90, "Bob"}, 1002}); // 键相同，允许插入4.2 处理 “一对多” 关系
multimap 的核心价值在于高效存储同一键的多个值，典型场景如下：
场景：课程与学生管理
// 课程编号为键，学生姓名为值
std::multimap<int, std::string> courseStudents;
// 插入数据：课程 101 有多个学生
courseStudents.insert({101, "Alice"});
courseStudents.insert({101, "Bob"});
courseStudents.insert({102, "Charlie"});
// 查询课程 101 的所有学生
auto [lower, upper] = courseStudents.equal_range(101);
std::cout << "Course 101 students:" << std::endl;
for (auto it = lower; it != upper; ++it) {
std::cout << "- " << it->second << std::endl;
}4.3 性能优化建议
批量插入：使用
insert插入迭代器范围或初始化列表，减少红黑树旋转次数预分配内存：通过
reserve预分配空间（虽然红黑树无容量概念，但可减少重新分配次数）避免频繁修改键：键是
const类型，修改键需先删除旧元素再插入新元素
4.4 与 map 的协同使用
当需要 “键 - 值列表” 映射时，可使用 map<Key, vector<Value>>，但 multimap 在插入时更便捷：
// 使用 map + vector 实现一对多
std::map<int, std::vector<std::string>> mapWithVector;
mapWithVector[100].push_back("Alice");
mapWithVector[100].push_back("Bob"); // 需要手动管理 vector
// 使用 multimap 更简洁
std::multimap<int, std::string> mm;
mm.insert({100, "Alice"});
mm.insert({100, "Bob"}); // 直接插入，无需预分配 vector五、常见问题与陷阱
5.1 为什么没有 operator []？
map 的 operator[] 通过键访问唯一值，而 multimap 中键可能对应多个值，无法通过单一值返回，因此未提供该接口。若需模拟类似功能，需手动插入：
// map 的用法（唯一值）
map[100] = "Alice"; // 若键不存在则插入，存在则覆盖
// multimap 需用 insert
mm.insert({100, "Alice"}); // 允许重复插入5.2 自定义比较函数的严格弱序
比较函数必须满足 严格弱序（Strict Weak Ordering）：
- 非自反性：
!(a < a) - 传递性：若
a < b且b < c，则a < c - 反对称性：若
a < b，则b < a不成立
错误示例（非严格弱序，导致未定义行为）：
// 错误：比较函数不满足非自反性
struct BadCompare {
bool operator()(int a, int b) const { return a <= b; } // a <= b 允许 a==b，导致自反
};5.3 迭代器失效问题
- 插入、删除操作不会使其他迭代器失效（红黑树节点替换而非销毁）
- 但删除元素后，指向该元素的迭代器会失效
六、实战案例：文件关键词索引系统
6.1 需求描述
实现一个学生课程管理系统，支持：
- 添加学生选课记录（允许同一学生选择多门课程）。
- 按学生姓名查询所有选课记录。
- 按课程名称查询所有选课学生。
6.2 代码实现
#include <iostream>
#include <map>
#include <string>
int main() {
// 使用multimap存储学生-课程关系（允许重复）
std::multimap<std::string, std::string> studentCourses;
// 添加选课记录
studentCourses.insert({"Alice", "Math"});
studentCourses.insert({"Alice", "Physics"});
studentCourses.insert({"Bob", "Chemistry"});
studentCourses.insert({"Alice", "Biology"});
// 按学生查询课程
std::string targetStudent = "Alice";
auto range = studentCourses.equal_range(targetStudent);
std::cout << targetStudent << "'s courses:" << std::endl;
for (auto it = range.first; it != range.second; ++it) {
std::cout << "- " << it->second << std::endl;
}
// 按课程查询学生（需反向multimap）
std::multimap<std::string, std::string> courseStudents;
for (const auto& pair : studentCourses) {
courseStudents.insert({pair.second, pair.first});
}
std::string targetCourse = "Physics";
auto courseRange = courseStudents.equal_range(targetCourse);
std::cout << "\nStudents in " << targetCourse << ":" << std::endl;
for (auto it = courseRange.first; it != courseRange.second; ++it) {
std::cout << "- " << it->second << std::endl;
}
return 0;
}
七、总结与最佳实践
7.1 使用场景总结
- 键可重复且需有序：如日志系统、索引系统、分类系统
- 简化 “一对多” 操作：避免手动管理
map + vector的嵌套结构 - 范围查询需求：利用
lower_bound/upper_bound进行高效区间操作
7.2 最佳实践
- 优先使用
insert插入：避免依赖operator[]（multimap不支持） - 处理重复键时使用范围迭代：通过
equal_range或lower_bound/upper_bound遍历所有相关元素 - 自定义比较函数时严格遵循严格弱序：确保红黑树的有序性不受破坏
- 对比选择容器：
- 若需要键唯一且有序：用
map - 若需要键可重复但无需有序：用
unordered_multimap - 若需要值可重复且键值相同：用
multiset
- 若需要键唯一且有序：用
7.3 未来扩展
C++ 标准库不断进化，虽然 multimap 的接口相对稳定，但结合 Lambda 表达式可更简洁地定义比较函数（C++14 起）：
// 使用 Lambda 作为比较函数（C++14+）
auto lambdaCompare = [](int a, int b) { return a > b; };
std::multimap<int, std::string, decltype(lambdaCompare)> mm(lambdaCompare);八、完整代码示例
示例 1：基本操作演示
#include <iostream>
#include <map>
#include <string>
int main() {
std::multimap<int, std::string> mm;
// 插入元素
mm.insert({100, "Alice"});
mm.insert({100, "Bob"});
mm.insert({200, "Charlie"});
// 查找键 100 的所有值
auto range = mm.equal_range(100);
std::cout << "Values for key 100:" << std::endl;
for (auto it = range.first; it != range.second; ++it) {
std::cout << "- " << it->second << std::endl;
}
// 删除键 100 的所有元素
mm.erase(100);
std::cout << "Size after erase: " << mm.size() << std::endl; // 输出 1
return 0;
} 
示例 2：自定义比较函数
#include <iostream>
#include <map>
struct DescCompare {
bool operator()(int a, int b) const { return a > b; }
};
int main() {
std::multimap<int, std::string, DescCompare> reversedMm;
reversedMm.insert({100, "A"});
reversedMm.insert({200, "B"});
// 反向遍历输出（实际存储顺序为 200, 100）
for (const auto& entry : reversedMm) {
std::cout << entry.first << ": " << entry.second << std::endl;
}
return 0;
} 
九、结语
multimap 是处理 “有序重复键” 场景的利器，其红黑树底层保证了高效的插入、删除和查找操作。通过合理使用范围查询接口和自定义比较函数，能轻松构建复杂的数据映射系统。在实际项目中，需根据键的唯一性、有序性和性能需求，灵活选择 map、multimap、unordered_map 等容器，以实现代码的高效与优雅。
十、参考资料
- 《C++ Primer（第 5 版）》这本书是 C++ 领域的经典之作，对 C++ 的基础语法和高级特性都有深入讲解。
- 《Effective C++（第 3 版）》书中包含了很多 C++ 编程的实用建议和最佳实践。
- 《C++ Templates: The Complete Guide（第 2 版）》该书聚焦于 C++ 模板编程，而
using声明在模板编程中有着重要应用，如定义模板类型别名等。 - C++ 官方标准文档：C++ 标准文档是最权威的参考资料，可以查阅最新的 C++ 标准（如 C++11、C++14、C++17、C++20 等）文档。例如，ISO/IEC 14882:2020 是 C++20 标准的文档，可从相关渠道获取其详细内容。