C++ std::multimap 详细使用指南

std::multimap 是 C++ STL 提供的一个 关联容器，允许存储 多个具有相同键（key）的元素，并按照键的顺序自动排序。它基于红黑树（Red-Black Tree）实现，因此插入、删除和查找操作的时间复杂度为 O(log n)。

1. std::multimap 的基本特性

2. 头文件与声明

#include <map>  // 包含 multimap 的头文件

std::multimap<Key, Value> mmap;  // 默认按 Key 升序排列
std::multimap<Key, Value, Compare> mmap;  // 使用自定义比较函数

• Key：键的类型（必须支持 < 比较运算符）。

• Value：值的类型。

• Compare：自定义比较函数（如 std::greater<Key> 实现降序）。

3. 基本操作
(1) 插入元素
std::multimap 提供多种插入方式：

#include <iostream>
#include <map>

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

    // 方式 1: insert(pair)
    mmap.insert({1, "Apple"});
    mmap.insert(std::make_pair(2, "Banana"));
    mmap.insert(std::pair<int, std::string>(3, "Cherry"));

    // 方式 2: insert(value_type)
    mmap.insert(std::multimap<int, std::string>::value_type(4, "Date"));

    // 方式 3: emplace（C++11，直接构造元素）
    mmap.emplace(5, "Elderberry");

    // 输出所有元素
    for (const auto& [key, value] : mmap) {
        std::cout << key << ": " << value << std::endl;
    }

    return 0;
}

输出：

1: Apple
2: Banana
3: Cherry
4: Date
5: Elderberry

(2) 访问元素
std::multimap 没有 operator[]（因为可能有多个相同键），只能用 find() 或遍历访问：

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mmap = {
        {1, "Apple"},
        {2, "Banana"},
        {2, "Blueberry"},
        {3, "Cherry"}
    };

    // 查找 key=2 的第一个元素
    auto it = mmap.find(2);
    if (it != mmap.end()) {
        std::cout << "First '2': " << it->second << std::endl;  // Banana
    }

    // 遍历所有 key=2 的元素
    for (auto range = mmap.equal_range(2); range.first != range.second; ++range.first) {
        std::cout << "Key=2: " << range.first->second << std::endl;
    }
    // 输出:
    // Key=2: Banana
    // Key=2: Blueberry

    return 0;
}

关键函数：
• find(key)：返回第一个匹配 key 的迭代器（如果没有则返回 end()）。

• equal_range(key)：返回一个 pair<iterator, iterator>，表示所有 key 对应的范围。

(3) 删除元素

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mmap = {
        {1, "Apple"},
        {2, "Banana"},
        {2, "Blueberry"},
        {3, "Cherry"}
    };

    // 方式 1: 删除单个元素（按迭代器）
    auto it = mmap.find(2);
    if (it != mmap.end()) {
        mmap.erase(it);  // 删除第一个 key=2 的元素
    }

    // 方式 2: 删除所有 key=2 的元素
    mmap.erase(2);  // 删除所有 key=2 的元素

    // 方式 3: 删除指定范围的元素
    auto range = mmap.equal_range(1);
    mmap.erase(range.first, range.second);  // 删除 key=1 的所有元素

    // 输出剩余元素
    for (const auto& [key, value] : mmap) {
        std::cout << key << ": " << value << std::endl;
    }

    return 0;
}

注意：
• erase(key) 会删除 所有匹配 key 的元素。

• erase(it) 只删除 单个元素（迭代器指向的元素）。

• erase(first, last) 删除 [first, last) 范围内的元素。

(4) 遍历 std::multimap

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mmap = {
        {1, "Apple"},
        {2, "Banana"},
        {2, "Blueberry"},
        {3, "Cherry"}
    };

    // 方式 1: 范围 for 循环（C++11）
    for (const auto& [key, value] : mmap) {
        std::cout << key << ": " << value << std::endl;
    }

    // 方式 2: 迭代器
    for (auto it = mmap.begin(); it != mmap.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    return 0;
}

输出：

1: Apple
2: Banana
2: Blueberry
3: Cherry

(5) 自定义排序规则
默认按 key 升序排列，但可以自定义比较函数（如降序）：

#include <iostream>
#include <map>
#include <functional>  // std::greater

int main() {
    // 使用 std::greater<int> 实现降序排列
    std::multimap<int, std::string, std::greater<int>> mmap = {
        {1, "Apple"},
        {3, "Cherry"},
        {2, "Banana"}
    };

    for (const auto& [key, value] : mmap) {
        std::cout << key << ": " << value << std::endl;
    }

    // 输出:
    // 3: Cherry
    // 2: Banana
    // 1: Apple

    return 0;
}

4. std::multimap vs std::map

5. 典型应用场景
(1) 统计单词出现次数（允许重复键）

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

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

    // 模拟单词出现位置
    wordCount.insert({"apple", 1});
    wordCount.insert({"banana", 2});
    wordCount.insert({"apple", 3});
    wordCount.insert({"cherry", 4});

    // 统计每个单词的出现次数
    for (const auto& [word, pos] : wordCount) {
        std::cout << word << " appears at position " << pos << std::endl;
    }

    return 0;
}

输出：

apple appears at position 1
apple appears at position 3
banana appears at position 2
cherry appears at position 4

(2) 按分数分组学生（允许重复键）

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

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

    // 学生分数（可能有多个学生同分）
    studentScores.insert({90, "Alice"});
    studentScores.insert({85, "Bob"});
    studentScores.insert({90, "Charlie"});
    studentScores.insert({80, "David"});

    // 按分数分组输出
    for (const auto& [score, name] : studentScores) {
        std::cout << name << ": " << score << std::endl;
    }

    return 0;
}

输出：

Alice: 90
Charlie: 90
Bob: 85
David: 80

6. 总结

std::multimap 是处理 允许重复键的有序数据 的理想选择，适用于需要 按顺序存储多个相同键值对 的场景。