编辑“︁C++multimap”︁

{{Note|本条目是C++标准模板库(STL)容器系列的一部分，重点讲解'''multimap'''容器的特性与使用方法。}}

== 概述 ==
'''multimap'''是C++标准模板库(STL)中的关联容器，允许存储'''键值对(key-value pairs)'''，其中：
* 键(key)可重复出现（区别于<code>map</code>）
* 元素按键的'''严格弱序'''自动排序（默认<code>std::less<Key></code>）
* 基于红黑树实现，插入/删除操作时间复杂度为<math>O(\log n)</math>

== 声明与初始化 ==
需包含头文件<code><map></code>，基本语法：
<syntaxhighlight lang="cpp">
#include <map>
std::multimap<KeyType, ValueType> myMultimap;
</syntaxhighlight>

'''初始化示例'''：
<syntaxhighlight lang="cpp">
// 空multimap
std::multimap<std::string, int> mm1;

// 初始化列表
std::multimap<char, float> mm2 {
    {'a', 1.1}, {'b', 2.2}, {'a', 1.5}
};

// 拷贝构造
std::multimap<char, float> mm3(mm2);
</syntaxhighlight>

== 核心操作 ==
=== 插入元素 ===
提供三种主要方式：
<syntaxhighlight lang="cpp">
std::multimap<std::string, int> scores;

// 1. insert() 成员函数
scores.insert({"Alice", 90});
scores.insert(std::make_pair("Bob", 85));

// 2. emplace() 直接构造
scores.emplace("Alice", 92);  // 允许重复键

// 3. 范围插入
std::vector<std::pair<std::string, int>> v {{"Charlie", 78}, {"Alice", 88}};
scores.insert(v.begin(), v.end());
</syntaxhighlight>

=== 访问元素 ===
由于键可重复，不能直接用<code>operator[]</code>（与<code>map</code>关键区别）。常用方法：

<syntaxhighlight lang="cpp">
std::multimap<char, int> mm {{'a',1}, {'b',2}, {'a',3}};

// 1. 迭代器访问
for(auto it = mm.begin(); it != mm.end(); ++it) {
    std::cout << it->first << ": " << it->second << '\n';
}

// 2. 范围查询（等键元素）
auto range = mm.equal_range('a');
for(auto it = range.first; it != range.second; ++it) {
    std::cout << "Found: " << it->second << '\n';
}
</syntaxhighlight>
'''输出'''：
<pre>
a: 1
a: 3
b: 2
Found: 1
Found: 3
</pre>

=== 删除元素 ===
<syntaxhighlight lang="cpp">
std::multimap<int, std::string> emp {
    {101, "John"}, {102, "Mary"}, {101, "Steve"}
};

// 1. 通过迭代器删除
auto it = emp.find(102);
if(it != emp.end()) emp.erase(it);

// 2. 删除所有匹配键的元素
size_t n = emp.erase(101);  // n=2

// 3. 清空容器
emp.clear();
</syntaxhighlight>

== 特性分析 ==
=== 复杂度对比 ===
{| class="wikitable"
|+ 操作复杂度对比
! 操作 !! 复杂度 !! 备注
|-
| <code>insert()</code> || <math>O(\log n)</math> || 红黑树插入
|-
| <code>find()</code> || <math>O(\log n)</math> || 二分查找
|-
| <code>erase(key)</code> || <math>O(\log n + k)</math> || k为删除元素数量
|}

=== 与map的差异 ===
<mermaid>
flowchart LR
    A[multimap] -->|允许| B(重复键)
    C[map] -->|禁止| B
    A -->|无| D[operator[]]
    C -->|提供| D
</mermaid>

== 实际应用案例 ==
'''场景'''：电话簿中一个人名对应多个号码
<syntaxhighlight lang="cpp">
#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<std::string, std::string> phonebook;
    phonebook.emplace("Alice", "123-4567");
    phonebook.emplace("Bob", "555-1234");
    phonebook.emplace("Alice", "999-8765");

    // 查询Alice的所有号码
    std::cout << "Alice's numbers:\n";
    auto [begin, end] = phonebook.equal_range("Alice");
    for(auto it = begin; it != end; ++it) {
        std::cout << " - " << it->second << '\n';
    }
}
</syntaxhighlight>
'''输出'''：
<pre>
Alice's numbers:
 - 123-4567
 - 999-8765
</pre>

== 进阶技巧 ==
=== 自定义排序 ===
通过提供比较函数对象实现：
<syntaxhighlight lang="cpp">
struct CaseInsensitiveCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(), b.begin(), b.end(),
            [](char x, char y) { return tolower(x) < tolower(y); }
        );
    }
};

std::multimap<std::string, int, CaseInsensitiveCompare> mm;
mm.emplace("Apple", 10);
mm.emplace("apple", 20);  // 视为相同键
</syntaxhighlight>

=== 性能优化 ===
* 批量插入时使用<code>insert</code>带提示迭代器版本
* 频繁查询时考虑使用<code>unordered_multimap</code>（哈希表实现）

{{Warning|multimap的遍历顺序始终按照键排序，与插入顺序无关}}

== 参见 ==
* [[C++ STL容器]]
* [[C++ map容器]]
* [[C++ unordered_multimap容器]]

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 容器]]