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

std::unordered_multimap 是 C++ STL 提供的一个 无序关联容器，允许存储 多个具有相同键（key）的键值对，并基于哈希表实现。它支持平均时间复杂度为 O(1) 的插入、删除和查找操作，适用于需要快速访问且允许键重复的场景。

1. 基本特性

2. 头文件与声明

#include <unordered_map>  // 必须包含此头文件

// 声明语法
std::unordered_multimap<Key, Value> umm;  // 默认哈希函数和比较规则
std::unordered_multimap<Key, Value, Hash, KeyEqual> umm;  // 自定义哈希和比较

• Key：键的类型（需支持哈希函数和相等比较）。

• Value：值的类型。

• Hash：自定义哈希函数（默认 std::hash<Key>）。

• KeyEqual：自定义键比较函数（默认 std::equal_to<Key>）。

3. 基本操作
(1) 插入元素

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<std::string, int> umm;

    // 方式 1: insert()
    umm.insert({"apple", 1});
    umm.insert({"banana", 2});
    umm.insert({"apple", 3});  // 允许重复键

    // 方式 2: emplace()（直接构造元素）
    umm.emplace("orange", 4);
    umm.emplace("apple", 5);

    // 输出所有元素（顺序不固定）
    for (const auto& [key, value] : umm) {
        std::cout << key << ": " << value << " ";
    }
    // 可能的输出: apple: 1 apple: 3 orange: 4 banana: 2 apple: 5
    return 0;
}

(2) 访问元素
std::unordered_multimap 不支持 operator[] 和 at()（因键可重复），需通过迭代器或范围查询访问：

// 查找键为 "apple" 的所有元素
auto range = umm.equal_range("apple");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}
// 输出:
// apple: 1
// apple: 3
// apple: 5

(3) 删除元素

// 删除键为 "apple" 的所有元素
size_t count = umm.erase("apple");  // 返回删除的元素数量

// 删除指定迭代器的元素
auto it = umm.find("banana");
if (it != umm.end()) {
    umm.erase(it);
}

// 删除迭代器范围 [first, last)
umm.erase(umm.begin(), umm.find("orange"));

(4) 遍历元素

// 遍历所有元素
for (const auto& pair : umm) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

// 通过桶遍历（高级用法）
size_t bucket_count = umm.bucket_count();
for (size_t i = 0; i < bucket_count; ++i) {
    std::cout << "Bucket "<< i << ": ";
    for (auto it = umm.begin(i); it != umm.end(i); ++it) {
        std::cout << "{" << it->first << ", " << it->second << "} ";
    }
    std::cout << std::endl;
}

4. 自定义哈希函数与比较规则
当键为自定义类型时，需提供哈希函数和比较函数：

#include <string>
#include <functional>

struct Person {
    std::string name;
    int age;

    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

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

// 自定义比较函数（可选，默认使用 operator==）
struct PersonEqual {
    bool operator()(const Person& lhs, const Person& rhs) const {
        return lhs.name == rhs.name && lhs.age == rhs.age;
    }
};

// 声明容器
std::unordered_multimap<Person, std::string, PersonHash, PersonEqual> ump;

5. 桶相关操作
std::unordered_multimap 的底层哈希表由多个桶组成，相同键的元素存储在同一个桶中：

// 获取桶的数量
size_t bucket_count = umm.bucket_count();

// 获取键对应的桶编号
size_t bucket_index = umm.bucket("apple");

// 获取桶的大小
size_t bucket_size = umm.bucket_size(bucket_index);

6. 性能调优参数

// 设置最大负载因子
umm.max_load_factor(0.5);

// 预分配 200 个桶
umm.rehash(200);

7. 典型应用场景
(1) 分组数据存储

// 存储学生姓名与成绩（允许同名学生）
std::unordered_multimap<std::string, int> scores;
scores.insert({"Alice", 90});
scores.insert({"Bob", 85});
scores.insert({"Alice", 95});

// 查找 Alice 的所有成绩
auto range = scores.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << "Alice's score: " << it->second << std::endl;
}

(2) 多值映射

// 存储单词及其多个含义
std::unordered_multimap<std::string, std::string> wordMap;
wordMap.insert({"C++", "编程语言"});
wordMap.insert({"C++", "高效"});
wordMap.insert({"Java", "面向对象"});

// 遍历所有单词及其含义
for (const auto& [word, meaning] : wordMap) {
    std::cout << word << ": " << meaning << std::endl;
}

8. 与 std::multimap 的区别

9. 注意事项

1. 无序性：元素存储顺序与插入顺序无关，仅由哈希函数决定。

2. 桶的分布：相同键的元素集中在同一桶中，遍历时可能连续出现。

3. 自定义类型：必须提供哈希函数和比较函数，否则编译错误。

4. 性能瓶颈：哈希冲突严重时性能下降，需合理设计哈希函数。

10. 总结
std::unordered_multimap 是处理 允许重复键的无序数据 的高效工具，适用于需要快速插入、删除和查找的场景。通过合理使用哈希函数和桶操作，可以进一步优化性能。以下是其核心优势：
• ✅ 允许重复键，灵活性高。

• ✅ 平均 O(1) 时间复杂度，适合高频操作。

• ✅ 支持自定义哈希和比较规则，扩展性强。

示例代码：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<std::string, int> umm;
    umm.insert({"apple", 1});
    umm.insert({"apple", 2});
    umm.insert({"banana", 3});

    // 遍历输出
    for (const auto& [key, value] : umm) {
        std::cout << key << ": " << value << std::endl;
    }

    return 0;
}

输出（顺序可能变化）：

apple: 1
banana: 3
apple: 2

通过灵活运用 std::unordered_multimap，可以高效解决需要键值重复映射的实际问题。