multimap

std::multimap 是 C++ 标准库中的有序关联容器，与 std::map 类似，但允许同一个键对应多个值。它基于平衡二叉搜索树实现，元素按键的排序规则保持有序。

典型应用包括：一个学生对应多门课程的成绩、一个单词对应多个定义、一个作者对应多本书等。

头文件与基本特征

使用 multimap 时，需要包含头文件：

#include <map>

常见特征如下：

特征	说明
元素类型	std::pair<const Key, T>
键是否允许重复	是，允许多个相同键
是否有序	是，按键排序
底层结构	通常为平衡二叉搜索树
查找复杂度	O(log n)
插入复杂度	O(log n)
是否有 operator[]	没有，因为键不唯一，语义不明确

基本用法

#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<std::string, int> scores;

    scores.insert(std::make_pair(std::string("Alice"), 85));
    scores.insert(std::make_pair(std::string("Bob"), 90));
    scores.insert(std::make_pair(std::string("Alice"), 92));  // Alice 的第二个成绩

    for (std::multimap<std::string, int>::iterator it = scores.begin(); it != scores.end(); ++it) {
        std::cout << it->first << " : " << it->second << '\n';
    }
    // 输出按键排序，Alice 出现两次

    return 0;
}

注意：multimap 没有 operator[]（因为同一键可能有多个值，下标访问语义不清），必须使用 insert() 插入。

常用成员函数

函数	作用
insert()	插入元素，始终成功，返回迭代器
erase()	删除元素
find()	查找键，返回第一个匹配的迭代器
count()	统计指定键出现的次数
lower_bound()	第一个不小于目标键的元素
upper_bound()	第一个大于目标键的元素
equal_range()	同时返回上下界
size()	元素数量
empty()	是否为空
clear()	清空

插入元素

与 map 不同，multimap::insert() 总是成功，不会因键已存在而失败，返回值也只是迭代器（不是 pair<iterator, bool>）：

#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<std::string, int> scores;

    scores.insert(std::make_pair(std::string("Tom"), 70));
    scores.insert(std::make_pair(std::string("Tom"), 85));
    scores.insert(std::make_pair(std::string("Tom"), 92));

    std::cout << scores.count("Tom") << '\n';  // 3

    return 0;
}

查找与遍历

find()

find() 返回第一个匹配键的迭代器。如果键不存在，返回 end()：

#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<std::string, int> data;
    data.insert(std::make_pair(std::string("apple"), 3));
    data.insert(std::make_pair(std::string("apple"), 5));
    data.insert(std::make_pair(std::string("banana"), 2));

    std::multimap<std::string, int>::iterator it = data.find("apple");
    if (it != data.end()) {
        std::cout << it->first << " = " << it->second << '\n';  // 第一个 apple
    }

    return 0;
}

equal_range()：遍历同一键的所有值

这是 multimap 最常用的操作模式，用来遍历某个键的全部映射值：

#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<std::string, int> scores;
    scores.insert(std::make_pair(std::string("Alice"), 85));
    scores.insert(std::make_pair(std::string("Alice"), 92));
    scores.insert(std::make_pair(std::string("Alice"), 78));

    typedef std::multimap<std::string, int>::iterator Iter;
    std::pair<Iter, Iter> range = scores.equal_range("Alice");

    for (Iter it = range.first; it != range.second; ++it) {
        std::cout << it->second << ' ';
    }
    // 输出 Alice 的所有成绩

    return 0;
}

删除元素

按值删除会移除所有匹配的键值对：

#include <map>
#include <string>

int main() {
    std::multimap<std::string, int> mm;
    mm.insert(std::make_pair(std::string("x"), 1));
    mm.insert(std::make_pair(std::string("x"), 2));
    mm.insert(std::make_pair(std::string("x"), 3));

    mm.erase("x");  // 删除所有键为 "x" 的元素

    return 0;
}

如果只想删除某一个，使用迭代器删除：

std::multimap<std::string, int>::iterator it = mm.find("x");
if (it != mm.end()) {
    mm.erase(it);  // 只删一个
}

典型场景

1. 一对多关系映射：班级到学生、作者到书籍、类别到产品等。
2. 词典/索引：一个词条对应多条释义或多次出现位置。
3. 分组统计：将数据按某字段分组，后续对每组做聚合计算。
4. 有序日志：时间戳到事件，同一时刻可能有多个事件。

一对多映射示例：

#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<std::string, std::string> library;

    library.insert(std::make_pair(std::string("金庸"), std::string("射雕英雄传")));
    library.insert(std::make_pair(std::string("金庸"), std::string("天龙八部")));
    library.insert(std::make_pair(std::string("金庸"), std::string("笑傲江湖")));
    library.insert(std::make_pair(std::string("古龙"), std::string("多情剑客无情剑")));
    library.insert(std::make_pair(std::string("古龙"), std::string("陆小凤传奇")));

    typedef std::multimap<std::string, std::string>::iterator Iter;

    std::pair<Iter, Iter> range = library.equal_range("金庸");
    std::cout << "金庸作品：\n";
    for (Iter it = range.first; it != range.second; ++it) {
        std::cout << "  " << it->second << '\n';
    }

    return 0;
}

使用注意

1. multimap 没有 operator[]，不要用它来做类似 map 的单键访问。
2. find() 只返回第一个匹配的迭代器；要遍历全部匹配，用 equal_range()。
3. 按值 erase(key) 会删除所有匹配元素。
4. 键部分是 const，不能修改。（同 map）
5. 等值键之间的迭代顺序未严格规定，不要依赖。

小结

std::multimap 是 map 的可重复键版本，适合一对多映射场景。它的 API 核心差别在于：没有 operator[]、insert() 始终成功、操作重点从"单键访问"转移到 equal_range() 等区间遍历。掌握这些后，处理分组数据和词典索引类需求就很顺手了。