C++multimap

概述[编辑 | 编辑源代码]

multimap是C++标准模板库(STL)中的关联容器，允许存储键值对(key-value pairs)，其中：

键(key)可重复出现（区别于map）
元素按键的严格弱序自动排序（默认std::less<Key>）
基于红黑树实现，插入/删除操作时间复杂度为 $O (\log n)$

声明与初始化[编辑 | 编辑源代码]

需包含头文件<map>，基本语法：

#include <map>
std::multimap<KeyType, ValueType> myMultimap;

初始化示例：

// 空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);

核心操作[编辑 | 编辑源代码]

插入元素[编辑 | 编辑源代码]

提供三种主要方式：

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());

访问元素[编辑 | 编辑源代码]

由于键可重复，不能直接用operator[]（与map关键区别）。常用方法：

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';
}

输出：

a: 1
a: 3
b: 2
Found: 1
Found: 3

删除元素[编辑 | 编辑源代码]

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();

特性分析[编辑 | 编辑源代码]

复杂度对比[编辑 | 编辑源代码]

操作复杂度对比
操作	复杂度	备注
`insert()`	$O (\log n)$	红黑树插入
`find()`	$O (\log n)$	二分查找
`erase(key)`	$O (\log n + k)$	k为删除元素数量

与map的差异[编辑 | 编辑源代码]

实际应用案例[编辑 | 编辑源代码]

场景：电话簿中一个人名对应多个号码

#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';
    }
}

输出：

Alice's numbers:
 - 123-4567
 - 999-8765

进阶技巧[编辑 | 编辑源代码]

自定义排序[编辑 | 编辑源代码]

通过提供比较函数对象实现：

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);  // 视为相同键

性能优化[编辑 | 编辑源代码]

批量插入时使用insert带提示迭代器版本
频繁查询时考虑使用unordered_multimap（哈希表实现）

页面模块:Message box/ambox.css没有内容。

参见[编辑 | 编辑源代码]