C++ 第34题：std::multimap 一对多键值映射与 equal_range 范围区间检索

题目

编写程序，模拟字典或系统标签分类系统，使用 std::multimap 容纳允许重复 Key 的“一对多”映射关系（一个作者名对应多篇学术论文）。展示如何利用 equal_range() 成员函数一次性返回一对迭代器 [first, second)，圈定指定作者名下的所有论文，并在 O(log N + K) 复杂度内安全遍历与统计。

输入格式：无需外部输入。

输出格式：输出指定作者名下检索匹配到的所有论文列表及计数。

数据范围与约定：多重键关联容器与区间迭代器操作。

思路与算法

1. 为什么 multimap 没有 operator[]
因为 multimap 允许同一个键对应多个不同的值，如果支持 m[key] 无法确定究竟返回哪一个对象的引用，因此从接口层面彻底禁用了下标重载。

2. equal_range 算法优势
multimap.equal_range(k) 在红黑树中执行两次二分或单次组合查找，返回 std::pair<iterator, iterator>，等价于 make_pair(lower_bound(k), upper_bound(k))，是检索同键区间最高效且地道的写法。

3. 多重键的相对次序
在 C++11 及更高标准中，具有相同键的元素在 multimap 中按照它们的插入先后顺序保持稳定性（Insertion Order Preservation）。

完整程序

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

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

    // 插入一对多映射（同一作者发表多篇论文）
    library.insert({"Knuth", "The Art of Computer Programming Vol 1"});
    library.insert({"Turing", "On Computable Numbers"});
    library.insert({"Knuth", "The Art of Computer Programming Vol 2"});
    library.insert({"Lamport", "Time, Clocks, and the Ordering of Events"});
    library.insert({"Knuth", "Structured Programming with go to Statements"});

    std::cout << "文库总论文记录条数: " << library.size() << "\n\n";

    // 使用 equal_range 精确检索 "Knuth" 的所有作品
    std::string author = "Knuth";
    auto [rangeBegin, rangeEnd] = library.equal_range(author);

    std::cout << "--- 检索作者 [" << author << "] 名下的所有学术著作 ---\n";
    int count = 0;
    for (auto it = rangeBegin; it != rangeEnd; ++it) {
        std::cout << "  (" << ++count << ") " << it->second << "\n";
    }

    if (count == 0) {
        std::cout << "未检索到该作者任何收录文献。\n";
    } else {
        std::cout << "合计命中文献: " << count << " 篇。\n";
    }

    return 0;
}

运行示例

输出：

文库总论文记录条数: 5

--- 检索作者 [Knuth] 名下的所有学术著作 ---
  (1) The Art of Computer Programming Vol 1
  (2) The Art of Computer Programming Vol 2
  (3) Structured Programming with go to Statements
合计命中文献: 3 篇。