【C++容器和算法】关联容器：multimap类型

byte轻骑兵

发布于 2026-01-21 16:30:49

1300

在 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 标准的文档，可从相关渠道获取其详细内容。
：这是一个非常全面的 C++ 在线参考网站，提供了详细的 C++ 语言和标准库文档。
：该网站提供了系统的 C++ 教程，配有丰富的示例代码和清晰的解释，适合初学者学习和理解相关知识。
《Effective STL》Scott Meyers
开源项目STL源码分析