深入解析 C++ STL 多重映射 (Multimap)：掌握允许重复键的高级容器

2026-02-07 05:34:15 0条评论 2次阅读 0人点赞

在 C++ 标准模板库 (STL) 的浩瀚海洋中，关联容器是我们处理键值对数据不可或缺的工具。你可能已经很熟悉 std::map，它通过唯一的键来维护数据，提供了快速的查找能力。但是，在实际的软件开发场景中，我们经常会遇到这样的情况：一个键需要对应多个值。例如，在一个图书馆系统中，按“作者”查找“书籍”，或者在一个电话簿中，一个名字对应多个号码。

如果我们强行使用普通的 INLINECODEcb6594a4，就需要手动维护复杂的逻辑（比如让键对应一个 vector），这不仅繁琐，还容易出错。这时候，INLINECODEe9296ee9 就像一把瑞士军刀，完美地解决了这个问题。作为一种关联容器，它允许一个键对应多个元素，并且会根据键自动排序。

在这篇文章中，我们将深入探讨 multimap 的内部机制、核心用法以及一些实用的代码示例，帮助你彻底掌握这一强大的数据结构。

什么是 Multimap？

简单来说，多重映射（Multimap） 是 C++ STL 中的一种关联容器，用于存储由键和值组合而成的元素。它与 map 的核心区别在于：它允许键的重复。

这意味着你可以在同一个 multimap 实例中插入多个具有相同键的元素。默认情况下，容器会根据键的升序对元素进行排序。当然，作为模板类，我们也可以自定义排序规则。

它的底层通常是通过红黑树实现的，这使得大多数操作（如插入、删除、查找）的时间复杂度都能保持在对数时间 O(log n)。

语法与基本定义

要使用 INLINECODE6039792a，我们需要包含头文件 INLINECODE3b0bc441。

其定义语法如下：

template <
    class Key,
    class T,
    class Compare = std::less,
    class Alloc = std::allocator<std::pair>
> class multimap;

在一般开发中，我们最常用的声明方式是：

std::multimap mm;

keytype: 键的数据类型（例如 INLINECODEebbfe0d6, string）。
value_type: 值的数据类型。
comparator: 可选的比较函数对象。如果省略，默认使用 std::less，即按键升序排列。

声明与初始化实战

让我们通过代码来看看如何以不同方式初始化一个 multimap。

#include 
#include 
#include 
using namespace std;

int main() {
    // 1. 创建一个空的 multimap，键为 int，值为 string
    multimap mm1;

    // 2. 使用初始化列表直接赋值
    // 注意：我们插入了两个键为 1 的元素，这在 map 中是不允许的，但在 multimap 中完全没问题
    multimap mm2 = {
        {1, "Geeks"},
        {2, "For"}, 
        {1, "C++"}, // 重复键
        {3, "Example"}
    };

    // 遍历并打印，你会发现相同的键会排在一起
    cout << "初始化后的内容：" << endl;
    for (auto i : mm2) {
        cout << i.first << ": " << i.second << endl;
    }
    
    return 0;
}

输出：

初始化后的内容：
1: Geeks
1: C++
2: For
3: Example

核心操作详解

#### 1. 插入元素

向 INLINECODEf34af8d7 添加数据非常直观。我们可以使用 INLINECODE09b964af 成员函数。

注意： 不同于 INLINECODEbd558d04，INLINECODEfbb2502a 不支持使用 INLINECODE6377c48b 运算符进行插入或访问。这是因为 INLINECODEc9193de2 运算符的设计初衷是确保键的唯一性，用于访问或创建唯一键对应的值。在多重映射中，一个键对应多个值，[] 无法确定具体要操作哪一个值。

#include 
#include 
#include 
using namespace std;

int main() {
    multimap mm;

    // 方法 1：使用 insert 插入 pair 对象
    mm.insert(make_pair(1, "Python"));

    // 方法 2：使用初始化列表语法 (C++11 及以上)
    mm.insert({2, "Java"});
    mm.insert({1, "C++"}); // 再次插入键为 1 的元素

    cout << "插入后的结果：" << endl;
    for (auto x : mm) {
        cout << x.first << ": " << x.second << endl;
    }
    return 0;
}

输出：

插入后的结果：
1: Python
1: C++
2: Java

#### 2. 访问元素

由于不支持 INLINECODE88694918，我们必须依赖迭代器来访问元素。我们可以使用 INLINECODEab5acaf8, INLINECODE80c8e13a, INLINECODE3c0a6aca, rend() 等函数获取迭代器。

让我们看一个稍微复杂的例子，了解如何精确访问特定的位置：

#include 
#include 
#include 
#include  // 用于 advance
using namespace std;

int main() {
    multimap mm = {{1, "One"}, {2, "Two"}, {1, "Uno"}};

    // 获取指向第一个元素的迭代器
    multimap::iterator it = mm.begin();

    cout << "第一个元素: " <first < " <second << endl;

    // 使用 std::advance 将迭代器向前移动 2 个位置
    advance(it, 2);
    
    if (it != mm.end()) {
        cout << "移动两个位置后的元素: " <first < " <second << endl;
    }

    return 0;
}

#### 3. 更新元素值

在 INLINECODE1af09429 中，元素的键是 INLINECODE80858fc1 属性的，也就是说一旦插入，键就不能被修改（这会破坏排序结构）。但是，我们可以修改值。

#include 
#include 
using namespace std;

int main() {
    multimap mm = {{10, "OldValue"}, {20, "Fixed"}};

    // 找到键为 10 的元素
    auto it = mm.find(10);

    // 修改其值
    if (it != mm.end()) {
        it->second = "NewValue";
    }

    for (auto& x : mm) {
        cout << x.first << ": " << x.second << endl;
    }
    return 0;
}

#### 4. 遍历 Multimap

遍历是查看所有数据最常用的方式。我们推荐使用基于范围的 for 循环（Range-based for loop），代码更加简洁。

#include 
#include 
using namespace std;

int main() {
    multimap grades = {
        {‘A‘, 90},
        {‘B‘, 80},
        {‘A‘, 95}, // 另一个 A
        {‘C‘, 70}
    };

    cout << "成绩单遍历：" << endl;
    // 使用 const 引用以避免不必要的拷贝，提高性能
    for (const auto& entry : grades) {
        cout << "Grade " << entry.first << ": " << entry.second << endl;
    }

    return 0;
}

#### 5. 查找元素

查找是关联容器的强项。我们可以使用 find() 函数。

find(key): 返回指向第一个具有该键的元素的迭代器。如果找不到，返回 end()。
count(key): 返回特定键的出现次数（在 multimap 中通常大于 1）。

#include 
#include 
using namespace std;

int main() {
    multimap bookAuthors = {
        {"Scott Meyers", "Effective C++"},
        {"Scott Meyers", "Effective Modern C++"},
        {"Bjarne Stroustrup", "The C++ Programming Language"}
    };

    string searchAuthor = "Scott Meyers";
    
    // 查找该作者的第一本书
    auto it = bookAuthors.find(searchAuthor);

    if (it != bookAuthors.end()) {
        cout << "找到书籍: " <second << endl;
        
        // 这里有两本书，我们如何一次性获取所有“Scott Meyers”的书？
        // 结合 count 和 advance 可以手动遍历，但 C++ 提供了更好的方法：equal_range
    } else {
        cout << "未找到该作者" << endl;
    }

    return 0;
}

进阶技巧：使用 equal_range()

如果你想获取某个键对应的所有元素，INLINECODE61c2d494 是最优雅的解决方案。它返回一个 INLINECODE628e669c，包含两个迭代器：第一个指向该键的第一个元素，第二个指向该键范围之后的下一个位置。

#include 
#include 
using namespace std;

int main() {
    multimap mm = {{1, "A"}, {2, "B"}, {1, "C"}, {1, "D"}};
    int key = 1;

    // 获取键为 1 的所有元素的范围
    auto range = mm.equal_range(key);

    cout << "键 " << key << " 对应的所有值:" << endl;
    // 遍历这个范围
    for (auto it = range.first; it != range.second; ++it) {
        cout <second << " ";
    }
    cout << endl;

    return 0;
}

#### 6. 删除元素

我们可以使用 erase() 函数。

按键删除: 传入一个键值，会删除容器中所有具有该键的元素。返回删除的数量。
按迭代器删除: 传入一个迭代器，只删除迭代器指向的那一个特定元素。

#include 
#include 
using namespace std;

int main() {
    multimap mm = {{1, "One"}, {2, "Two"}, {1, "Uno"}, {3, "Three"}};

    // 场景 1: 删除键为 1 的所有元素
    size_t count = mm.erase(1);
    cout << "删除了 " << count << " 个键为 1 的元素" << endl;

    // 此时容器中只剩下 2 和 3
    // 假设我们只想删除键为 2 的元素，我们可以先找到它再删
    auto it = mm.find(2);
    if (it != mm.end()) {
        mm.erase(it); // 删除迭代器指向的单个元素
    }

    cout << "最终剩余内容：" << endl;
    for (auto x : mm) {
        cout << x.first << ": " << x.second << endl;
    }

    return 0;
}

性能考虑与最佳实践

当我们谈论 C++ 容器时，性能永远是核心话题。

时间复杂度: INLINECODE15e57105 基于红黑树。插入、删除和查找操作都是 O(log n)。这比 vector 的 O(n) 要快得多（针对大数据集），但比哈希表（如 INLINECODEc2b39a6a）的 O(1) 稍慢。
开销: 每个节点通常需要存储三个指针（父节点、左子节点、右子节点）以及颜色位，这比 vector 占用更多的内存。
何时使用:

– 当你需要键有序时（例如需要按字母顺序打印电话簿）。

– 当你需要频繁插入和删除，并且需要保持数据有序时。

– 当必须允许键重复时。

常见错误与解决方案

错误：尝试修改键

it->first = 5; // 编译错误！

解决: 如果需要修改键，必须先删除旧元素，然后插入新元素（新键，旧值）。

错误：混淆 INLINECODE02594116 和 INLINECODEdbb28835

试图用 INLINECODEbf2d44b1 来查找元素。请记住 INLINECODE9e3d165f 没有 [] 运算符重载。

陷阱：只查找第一个元素

使用 INLINECODE06feb4fc 只会得到第一个匹配的元素。如果业务逻辑需要处理该键下的所有数据，务必配合 INLINECODE8847acee 使用，或者直接使用 equal_range()。

总结

C++ STL 的 multimap 是一个功能强大且设计严谨的容器。它填补了标准映射无法处理重复键的空白。虽然在某些极端性能场景下哈希表可能更具优势，但在需要维持排序关系且允许键重复的应用场景下，它是首选方案。

通过掌握 INLINECODEf029dbc5, INLINECODEe6fe1a2d, INLINECODEda1d516f 和 INLINECODE22f62486 这些核心操作，结合迭代器的高效使用，你将能够编写出既简洁又高效的 C++ 代码来解决复杂的数据存储问题。下次当你面临“一对多”的数据建模时，不妨试试 multimap。

投稿给我们	如何建站？
vps是什么？	如何安装宝塔？
如何通过博客赚钱？	便宜wordpress托管方案
免费wordpress主题	这些都是免费方案

豆丁博客