C++ unordered_multimap

什么是 unordered_multimap?

unordered_multimap 是 C++ 标准模板库 (STL) 中的一个关联容器，它具有以下特点：

• 存储键值对（key-value pairs）
• 允许多个元素拥有相同的键（key）
• 元素不按任何特定顺序排序
• 通过哈希表实现，提供常数时间的平均查找复杂度

与 map 和 multimap 不同，unordered_multimap 不会对元素进行排序，而是根据键的哈希值组织数据，这使得它的查找、插入和删除操作通常比有序容器更快。

备注

unordered_multimap 是在 C++11 标准中引入的容器。

头文件和命名空间

使用 unordered_multimap 需要包含对应的头文件：

cpp

#include <unordered_map>

// 使用标准命名空间
using namespace std;

基本操作

创建和初始化

让我们看看如何创建和初始化 unordered_multimap：

cpp

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    // 创建空的 unordered_multimap
    unordered_multimap<string, int> umm1;
    
    // 使用初始化列表创建
    unordered_multimap<string, int> umm2 = {
        {"apple", 5},
        {"banana", 8},
        {"apple", 7},  // 重复的键
        {"orange", 10}
    };
    
    // 输出 umm2 中的所有元素
    for (const auto& pair : umm2) {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    return 0;
}

输出结果（可能的一种顺序，因为元素不是有序的）：

orange: 10
banana: 8
apple: 7
apple: 5

主要操作函数

unordered_multimap 提供了多种操作元素的函数：

插入元素

cpp

unordered_multimap<string, int> fruit_counts;

// 使用 insert 方法
fruit_counts.insert({"apple", 5});
fruit_counts.insert(make_pair("banana", 3));

// 使用 emplace 方法（原地构造）
fruit_counts.emplace("cherry", 7);

访问元素

由于 unordered_multimap 允许重复键，所以访问元素与 unordered_map 略有不同：

cpp

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_multimap<string, int> umm = {
        {"apple", 5},
        {"apple", 7},
        {"banana", 8}
    };
    
    // 查找特定键的所有值
    string key = "apple";
    auto range = umm.equal_range(key);
    
    cout << "Values for key '" << key << "':" << endl;
    for (auto it = range.first; it != range.second; ++it) {
        cout << it->second << endl;
    }
    
    // 检查键是否存在
    if (umm.count("grape") == 0) {
        cout << "No grapes found!" << endl;
    }
    
    return 0;
}

输出：

Values for key 'apple':
5
7
No grapes found!

删除元素

cpp

unordered_multimap<string, int> umm = {
    {"apple", 5},
    {"apple", 7},
    {"banana", 8},
    {"cherry", 10}
};

// 删除特定键的所有元素
umm.erase("apple");  // 删除所有键为 "apple" 的元素

// 删除特定位置的元素
auto it = umm.find("banana");
if (it != umm.end()) {
    umm.erase(it);  // 只删除找到的那个元素
}

// 通过迭代器范围删除元素
auto range = umm.equal_range("cherry");
umm.erase(range.first, range.second);

// 清空容器
umm.clear();

其他常用成员函数

以下是一些其他常用的成员函数：

• size(): 返回容器中的元素数量
• empty(): 检查容器是否为空
• count(key): 返回具有指定键的元素数量
• find(key): 查找具有特定键的元素并返回迭代器
• bucket_count(): 返回哈希表中桶的数量
• load_factor(): 返回容器的当前负载因子（元素数量/桶数量）
• max_load_factor(): 获取或设置容器的最大负载因子

哈希和比较函数

unordered_multimap 使用哈希函数来确定元素在桶中的位置。对于自定义类型，你需要提供自己的哈希函数：

cpp

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

// 自定义类型
struct Person {
    string name;
    int age;
    
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 为 Person 定义哈希函数
struct PersonHash {
    size_t operator()(const Person& p) const {
        return hash<string>()(p.name) ^ hash<int>()(p.age);
    }
};

int main() {
    // 使用自定义类型作为键
    unordered_multimap<Person, string, PersonHash> person_map;
    
    Person p1 = {"Alice", 25};
    Person p2 = {"Bob", 30};
    Person p3 = {"Alice", 25};  // 与 p1 相同
    
    person_map.insert({p1, "Engineer"});
    person_map.insert({p2, "Doctor"});
    person_map.insert({p3, "Designer"});  // 重复键
    
    for (const auto& pair : person_map) {
        cout << "Name: " << pair.first.name 
             << ", Age: " << pair.first.age
             << ", Occupation: " << pair.second << endl;
    }
    
    return 0;
}

输出（顺序可能不同）：

Name: Bob, Age: 30, Occupation: Doctor
Name: Alice, Age: 25, Occupation: Designer
Name: Alice, Age: 25, Occupation: Engineer

性能特性

unordered_multimap 的主要性能特性：

警告

当哈希冲突严重或负载因子过高时，unordered_multimap 的性能会明显下降。

实际应用场景

1. 多值映射

当你需要将一个键映射到多个值时，unordered_multimap 非常有用：

cpp

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    // 存储学生和他们的选修课程
    unordered_multimap<string, string> student_courses;
    
    // 添加学生和课程
    student_courses.insert({"Alice", "Math"});
    student_courses.insert({"Alice", "Physics"});
    student_courses.insert({"Alice", "Computer Science"});
    student_courses.insert({"Bob", "Biology"});
    student_courses.insert({"Bob", "Chemistry"});
    
    // 显示每个学生的所有课程
    for (const string& student : {"Alice", "Bob"}) {
        cout << student << "'s courses:" << endl;
        auto range = student_courses.equal_range(student);
        for (auto it = range.first; it != range.second; ++it) {
            cout << "- " << it->second << endl;
        }
        cout << endl;
    }
    
    return 0;
}

输出：

Alice's courses:
- Computer Science
- Physics
- Math

Bob's courses:
- Chemistry
- Biology

2. 单词频率分析

使用 unordered_multimap 来分析文本中单词出现的位置：

cpp

#include <iostream>
#include <unordered_map>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

int main() {
    string text = "the cat sat on the mat the cat was happy";
    unordered_multimap<string, int> word_positions;
    
    stringstream ss(text);
    string word;
    int position = 0;
    
    // 记录每个单词出现的位置
    while (ss >> word) {
        word_positions.insert({word, position});
        position++;
    }
    
    // 显示每个单词的所有出现位置
    vector<string> unique_words = {"the", "cat", "mat"};
    for (const auto& word : unique_words) {
        cout << "Word '" << word << "' appears at positions: ";
        auto range = word_positions.equal_range(word);
        for (auto it = range.first; it != range.second; ++it) {
            cout << it->second << " ";
        }
        cout << endl;
    }
    
    return 0;
}

输出：

Word 'the' appears at positions: 0 4 6 
Word 'cat' appears at positions: 1 7 
Word 'mat' appears at positions: 5 

unordered_multimap vs 其他容器

比较 unordered_multimap 与相关容器的特性：

特性	unordered_multimap	multimap	unordered_map	map
键的唯一性	允许重复	允许重复	唯一	唯一
元素排序	无序	有序	无序	有序
实现方式	哈希表	红黑树	哈希表	红黑树
查找复杂度	O(1) 平均	O(log n)	O(1) 平均	O(log n)
C++11之前可用	否	是	否	是

总结

unordered_multimap 是一个强大的关联容器，适用于需要多键值映射且优先考虑查找性能的场景。它的主要优点是：

1. 允许多个元素拥有相同的键
2. 提供常数时间的平均查找复杂度
3. 对于无需排序的大量数据处理非常高效

主要缺点是无法保证元素的顺序，以及在极端情况下可能的性能下降。

练习

1. 创建一个 unordered_multimap，存储电影类别和电影名称，然后输出每个类别的所有电影。
2. 实现一个程序，统计文本中每个单词出现的次数，使用 unordered_multimap。
3. 创建一个自定义类作为 unordered_multimap 的键，并为其提供适当的哈希函数和相等比较运算符。
4. 比较 unordered_multimap 和 multimap 在大数据集上的性能差异。

其他资源

• C++ Reference - unordered_multimap
• C++ Standard Library - The Unordered Containers
• C++11 教程 - unordered_multimap