0. 概述

在 C++11 引入 unordered_map 与 unordered_multimap 前，标准库中已有 map 与 multimap 两种有序关联容器，但二者底层基于红黑树实现，虽能保证键的有序性，却需付出 O (log n) 的时间复杂度代价。而实际开发中，大量场景更关注 “快速操作” 而非 “元素有序”—— 比如通过用户 ID 查询信息、按关键词统计日志等，此时哈希表的平均 O (1) 效率优势显著。因此 C++11 新增这两种无序关联容器：它们底层均基于哈希表，继承了无序容器的高效特性，同时延续 “键唯一 / 键可重复” 的分化设计（unordered_map 键唯一适配 “一对一” 映射，unordered_multimap 键可重复适配 “一对多” 映射），形成与 map/multimap “有序 vs 无序、效率 vs 排序需求” 的互补。本文将先剖析 “有序容器的局限性” 与 “无序容器的补充价值”，再系统讲解两种无序容器的共性特性（构造、哈希实现）、核心差异（键唯一性）、操作方法（插入 / 查找 / 删除的差异化逻辑），并结合实际场景对比四类容器的选型标准，帮助开发者理解 “为何需要两类映射容器”，并根据需求精准选择工具。

1. 为何需要新增：有序容器 map/multimap 的局限性

map 与 multimap 作为 C++98 就存在的有序关联容器，底层依赖红黑树（一种自平衡二叉搜索树）实现，核心特点是 “按键升序排列”，但这一特性也带来了不可忽视的局限，成为 C++11 新增无序容器的核心动因：

1.1 时间复杂度瓶颈：O (log n) 难满足高频操作需求

红黑树的结构决定了其插入、查找、删除操作均需通过树的遍历完成，时间复杂度固定为 O (log n)。对于数据量较小的场景，这一开销可忽略，但在高频操作场景（如每秒百万级的用户 ID 查询、日志关键词匹配）中，O (log n) 与 O (1) 的效率差距会被无限放大 —— 例如当数据量为 100 万时，log₂(10⁶)≈20，意味着无序容器的操作效率理论上是有序容器的 20 倍，能显著降低系统响应延迟。

1.2 排序功能的 “冗余性”：多数场景无需有序存储

map/multimap 的 “有序性” 是一把双刃剑：仅当需要按键排序遍历（如 “获取所有用户 ID 按升序展示”“统计成绩后按分数排序输出”）时，有序性才有价值；但更多场景下，开发者仅需 “通过键快速找到对应值”，无需关心元素存储顺序。例如：

电商系统中，通过订单号（键）查询订单详情（值），无需订单号按顺序存储；
缓存系统中，通过缓存键（如 URL）获取缓存数据，排序无意义。

此时，红黑树为维护有序性付出的性能成本，完全成为不必要的开销。

1.3 内存占用更高：红黑树的结构开销

红黑树的每个节点除了存储键值对外，还需维护父节点、左子节点、右子节点指针及颜色标记（共 4 个额外指针 / 标记），内存占用比哈希表更紧凑的 “桶 + 元素” 结构更高。对于内存敏感场景（如嵌入式开发、高并发缓存），这种额外开销会进一步限制容器的使用场景。

2. 无序容器的补充价值：哈希表带来的 “效率革命”

unordered_map 与 unordered_multimap 底层基于哈希表实现，核心目标是 “舍弃有序性，换取极致效率”，恰好弥补了 map/multimap 的上述局限，形成 “有序与无序” 的互补：

2.1平均 O (1) 时间复杂度：高频操作的 “性能救星”

哈希表通过 “哈希函数将键映射到桶（bucket）” 的方式存储元素，理想情况下，只需一次哈希计算即可定位到键所在的桶，进而找到对应元素，插入、查找、删除的平均时间复杂度均为 O (1)。即使存在哈希冲突（多个键映射到同一桶），通过链表或红黑树优化后，最坏情况也能控制在 O (log k)（k 为桶内元素数），远优于红黑树的 O (log n)。

2.2 无排序开销：按需选择 “有序与否”

无序容器不维护元素的顺序，插入时无需调整树结构，删除时无需重新平衡红黑树，进一步降低了操作的额外成本。开发者可根据需求灵活选择：需要排序时用 map/multimap，追求效率时用 unordered_map/unordered_multimap，避免 “为不需要的功能买单”。

2.3 延续 “键唯一 / 可重复” 分化：适配不同映射场景

与 map（键唯一）和 multimap（键可重复）的分化逻辑一致，unordered_map 保持键的唯一性，适合 “一对一” 映射（如用户 ID 与用户信息一一对应，ID 不可重复）；unordered_multimap 允许键重复，适合 “一对多” 映射（如一个用户 ID 对应多个订单记录，一个关键词对应多条日志）。这种设计确保无序容器能完全覆盖有序容器的应用场景，只是用 “效率” 替换了 “有序性”。

3. 四类容器对比：精准选型的核心依据

通过对比 map/multimap 与 unordered_map/unordered_multimap 的核心特性，可清晰看到 “为何需要两类容器”—— 它们针对不同需求场景设计，无绝对优劣，仅需按需选择：

容器类型	底层实现	键唯一性	元素顺序	平均操作复杂度（插入 / 查找 / 删除）	核心适用场景
map	红黑树	唯一	键升序	O(log n)	需要有序遍历、范围查询（如按键区间筛选）
multimap	红黑树	可重复	键升序	O(log n)	需要有序遍历且一对多映射（如按分数排序展示多个学生）
unordered_map	哈希表	唯一	无序（哈希决定）	O(1)	高频单键查询、无需排序（如用户 ID 查信息）
unordered_multimap	哈希表	可重复	无序（哈希决定）	O(1)	高频单键查询且一对多映射（如用户 ID 查所有订单）

示例选型场景：

若需 “按用户注册时间（键）升序展示用户信息”，选择 map；
若需 “按分数（键）升序展示所有学生（同一分数多个学生）”，选择 multimap；
若需 “通过用户 ID 快速查询用户昵称”，选择 unordered_map；
若需 “通过用户 ID 快速获取该用户的所有历史订单”，选择 unordered_multimap。

1. unordered_map

在 C++ 标准库的容器家族里，std::unordered_map 是个 “性能黑马”—— 它同样以键值对（Key/Value Pair）的形式存储数据，凭借哈希表的底层实现，在平均情况下能提供常数时间的查找、插入和删除操作，在高频数据访问、快速键值匹配等场景中表现出色（比如缓存存储、哈希索引等）。接下来，我们就从 unordered_map 的核心特性入手，逐步解析它的用法、语法特点，以及与 map 的差异，助你轻松掌握这个高效工具。

特点：

不允许有重复的 Key
存储的键需要支持哈希计算（需提供哈希函数）
元素无序排列（不同于 map 的有序性）
可以自定义哈希函数和相等性判断（通过仿函数）

1.1 初始化

初始化 std::unordered_map，可直接使用 {} 初始化列表，简洁明了。示例代码如下：

#include <iostream>
#include <unordered_map>
#include <string>

struct Student {
    std::string Name;
    Student(const std::string& name) : Name(name) {}
};

// 自定义哈希函数（针对int类型，仅作示例）
struct MyHash {
    size_t operator()(const int& key) const {
        return std::hash<int>()(key) ^ 0x55555555;
    }
};

int main() {
    // 使用初始化列表初始化std::unordered_map
    std::unordered_map<int, Student, MyHash> umap1 = {
        {1, Student("张三")},
        {2, Student("李四")},
        {3, Student("王五")}
    };

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

    return 0;
}

上述代码中，通过 { {键值对1}, {键值对2}, ... } 的形式直接初始化 std::unordered_map，相比早期的方式更直观。

在 C++17 中，std::unordered_map 也能享受模板参数自动推导（CTAD）的便利。对于简单的键值类型场景，无需显式指定模板参数：

#include <unordered_map>
#include <string>

int main() {
    // 编译器自动推导键值类型
    std::unordered_map um = { {1, "苹果"}, {2, "香蕉"}, {3, "橙子"} };
    return 0;
}

但如果需要自定义哈希函数或相等性判断器，仍需显式指定模板参数。

总之，C++11 及之后的标准为 std::unordered_map 提供了多种简化的初始化方式，提高了代码的编写效率和可读性。

1.2 插入元素

（1）insert()函数：安全且支持批量插入

insert() 是 unordered_map 插入的标准接口，支持单个插入和批量插入，遇到重复键会忽略插入（不覆盖现有值），适合需要去重的场景：

#include <unordered_map>
#include <string>

std::unordered_map<int, std::string> fruitMap = { {1, "苹果"}, {2, "香蕉"} };

// 1. 插入单个键值对（两种写法）
fruitMap.insert(std::make_pair(3, "橙子")); // C++98风格
fruitMap.insert({4, "葡萄"});               // C++11+列表风格，更简洁

// 2. 批量插入（初始化列表）
fruitMap.insert({
    {5, "西瓜"},
    {6, "草莓"}
});

// 3. 检查插入结果（insert返回pair<iterator, bool>，bool表示是否插入成功）
auto result = fruitMap.insert({1, "红苹果"}); // 键1已存在，插入失败
if (!result.second) {
    std::cout << "键 " << result.first->first << " 已存在，值为：" << result.first->second << std::endl;
}

（2）operator[]：简洁但有陷阱

[] 是 unordered_map 存取的快捷方式，插入时直接通过键赋值，代码简洁，但要注意陷阱：

如果键不存在，[] 会自动插入一个默认构造的值（比如 std::string 默认是空字符串，int 默认是 0），可能导致意外的数据插入。

std::unordered_map<int, std::string> fruitMap = { {1, "苹果"} };

// 1. 插入新键（键2不存在，自动插入）
fruitMap[2] = "香蕉";

// 2. 修改已有键的值（键1存在，直接覆盖）
fruitMap[1] = "青苹果";

// 3. 陷阱：误插入默认值
std::cout << fruitMap[3]; // 键3不存在，自动插入 {3, ""}，输出空字符串

适用场景：确认键存在时修改值，或明确需要 “不存在则插入” 的场景。

（3）emplace()：C++11+ 高效插入，避免拷贝

emplace() 是 C++11 新增的插入方式，直接在 unordered_map 内部构造 pair 对象，避免了 insert() 中可能的临时对象拷贝，效率更高：

std::unordered_map<int, Student> studentMap;

// emplace直接传入构造Student的参数，内部构造pair
studentMap.emplace(1, "张三"); // 等价于 insert({1, Student("张三")})
studentMap.emplace(2, "李四");

1.3 存取元素

（1）operator[]：快捷但有陷阱（前面已提及）

Student& s = umap1[2];
s.Name = "赵六";
...

（2）at()：C++11+ 安全存取，不存在键抛异常

at() 是 C++11 新增的存取接口， 只访问已存在的键新增的存取接口，只访问已存在的键**，如果键不存在会抛出 std::out_of_range 异常，避免了 [] 的 “误插入” 陷阱，适合需要严格检查键存在性的场景：

#include <unordered_map>
#include <string>
#include <stdexcept>

std::unordered_map<int, std::string> fruitMap = { {1, "苹果"}, {2, "香蕉"} };

// 1. 访问已存在的键（正常返回值）
std::string& name = fruitMap.at(1);
name = "红苹果"; // 修改值

// 2. 访问不存在的键（抛异常）
try {
    fruitMap.at(3); // 键3不存在，抛出std::out_of_range
} catch (const std::out_of_range& e) {
    std::cout << "访问失败：" << e.what() << std::endl;
}

1.4 查找元素

（1）find()：返回迭代器，快速定位键

find() 是 unordered_map 查找的首选接口，根据键查找，返回指向该键的迭代器；如果不存在，返回 end() 迭代器。由于底层是哈希表，find() 的平均时间复杂度是 O(1)，非常高效：

#include <unordered_map>
#include <string>
#include <iostream>

std::unordered_map<int, std::string> fruitMap = { {1, "苹果"}, {2, "香蕉"}, {3, "橙子"} };

// 查找键2
auto it = fruitMap.find(2);
if (it != fruitMap.end()) {
    std::cout << "找到键 " << it->first << "，值为：" << it->second << std::endl;
} else {
    std::cout << "未找到该键" << std::endl;
}

（2）count()：返回键的个数，适合检查存在性

unordered_map 的键唯一，所以 count() 的返回值只有 0 或 1——0 表示键不存在，1 表示存在。用法比 find() 更简洁，适合只需判断键是否存在的场景：

if (fruitMap.count(3)) {
    std::cout << "键3存在" << std::endl;
} else {
    std::cout << "键3不存在" << std::endl;
}

1.5 遍历

std::unordered_map 的遍历方式与 std::map 类似，但由于其无序性，遍历结果不会按键排序。

C++11 之前（C++98/03）的遍历方式

没有范围循环和 auto，需显式声明迭代器类型，通过 begin()/end() 控制循环范围，且需通过 ->first/->second 访问键值：

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<int, std::string> myUmap;
    myUmap.insert(std::make_pair(1, "苹果"));
    myUmap.insert(std::make_pair(2, "香蕉"));
    myUmap.insert(std::make_pair(3, "橙子"));

    // 方式1：普通迭代器遍历
    for (std::unordered_map<int, std::string>::iterator it = myUmap.begin();
         it != myUmap.end(); ++it) {
        int key = it->first;
        std::string value = it->second;
        std::cout << "Key: " << key << ", Value: " << value << std::endl;
    }

    // 方式2：常量迭代器（只读）
    for (std::unordered_map<int, std::string>::const_iterator it = myUmap.begin();
         it != myUmap.end(); ++it) {
        // 此时不能修改it->second，编译会报错
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    return 0;
}

缺点：

迭代器类型声明冗长（std::unordered_map<int, std::string>::iterator）
必须手动控制迭代器的起始（begin()）和终止（end()）
访问键值需要通过 ->first/->second，不够直观

C++11 的遍历方式

引入了范围循环（range-based for loop） 和 auto 关键字，简化了迭代器声明和循环控制，但仍需通过 first/second 访问键值：

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<int, std::string> myUmap = {
        {1, "苹果"},    // C++11初始化列表，比insert更简洁
        {2, "香蕉"},
        {3, "橙子"}
    };

    // 方式1：通过auto简化迭代器类型，配合范围循环
    for (auto it = myUmap.begin(); it != myUmap.end(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    // 方式2：范围循环直接遍历元素（最常用）
    for (const auto& element : myUmap) {  // element类型是std::pair<const int, std::string>
        std::cout << "Key: " << element.first << ", Value: " << element.second << std::endl;
    }

    return 0;
}

改进点：

auto 自动推导迭代器 / 元素类型，避免冗长声明
范围循环 for (const auto& element : myUmap) 无需手动控制 begin()/end()，更简洁
初始化列表 { {1, "苹果"}, ... } 比 insert 更直观

局限性：

仍需通过 element.first/element.second 访问键值，不够直接

C++17 的遍历方式

在 C++11 基础上，引入结构化绑定（structured binding），可以直接将键值对解包为两个变量：

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<int, std::string> myUmap = {
        {1, "苹果"},
        {2, "香蕉"},
        {3, "橙子"}
    };

    // 结构化绑定直接解包键和值
    for (const auto& [key, value] : myUmap) {  // [key, value]对应pair的first和second
        std::cout << "Key: " << key << ", Value: " << value << std::endl;
    }

    return 0;
}

通过 [key, value] 直接绑定 std::pair 的两个成员，无需 first/second
代码可读性大幅提升，直观反映 “遍历键值对” 的意图

总结

从 C++98 到 C++17，std::unordered_map 的遍历语法同样朝着 “简洁化、直观化” 发展，C++17 的结构化绑定让代码更贴近自然语言表达。

1.6 删除元素

erase() 是 unordered_map 删除的核心函数，支持按 “迭代器”“键”“范围” 删除，灵活度高：

std::unordered_map<int, std::string> fruitMap = { {1, "苹果"}, {2, "香蕉"}, {3, "橙子"}, {4, "葡萄"} };

// 1. 按迭代器删除（删除第一个元素）
auto it = fruitMap.begin();
fruitMap.erase(it); // 删除 {1, "苹果"}

// 2. 按键删除（删除键3的元素）
size_t deletedCount = fruitMap.erase(3); // 返回删除的元素个数（unordered_map中0或1）
std::cout << "删除了 " << deletedCount << " 个元素" << std::endl; // 输出1

// 3. 按范围删除（删除从迭代器it到末尾的元素）
auto startIt = fruitMap.find(2); // 找到键2的迭代器
fruitMap.erase(startIt, fruitMap.end()); // 删除 {2, "香蕉"}, {4, "葡萄"}

注意：删除迭代器后，该迭代器会失效，不能再使用（比如 ++it），需重新获取。

1.6.1 遍历删除元素

一、遍历删除 unordered_map 特定元素

std::unordered_map 是无序关联容器，底层为哈希表。删除元素时，被删除的迭代器会失效，但其他迭代器通常不受影响（桶数量变化时可能有例外）。正确的做法是利用 erase 方法的返回值（下一个有效的迭代器）更新当前迭代器。

方法 1：使用erase 的返回值（C++11 及以上推荐）

unordered_map::erase(iterator) 会返回被删除元素的下一个迭代器，可直接用于更新当前迭代器：

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

int main() {
    unordered_map<int, string> myUmap = {
        {1, "a"}, {2, "b"}, {3, "c"}, {4, "d"}
    };

    // 目标：删除键为偶数的元素
    auto it = myUmap.begin();
    while (it != myUmap.end()) {
        if (it->first % 2 == 0) { // 满足删除条件（键为偶数）
            // erase返回下一个有效迭代器，直接赋值给it
            it = myUmap.erase(it);
        } else {
            // 不删除则正常递增迭代器
            ++it;
        }
    }

    // 打印结果：{1:"a", 3:"c"}（顺序可能不同，因无序性）
    for (const auto& pair : myUmap) {
        cout << pair.first << ":" << pair.second << " ";
    }

    return 0;
}

方法 2：先保存下一个迭代器（兼容 C++11 之前版本）

C++11 之前，unordered_map::erase 不返回迭代器，需先通过 it++ 保存下一个迭代器，再删除当前元素：

auto it = myUmap.begin();
while (it != myUmap.end()) {
    if (it->first % 2 == 0) {
        // 先通过it++获取下一个迭代器，再删除当前元素
        myUmap.erase(it++);
    } else {
        ++it;
    }
}

原理：it++ 会先返回当前迭代器的副本，再递增迭代器，因此删除的是 “旧” 迭代器，而 it 已指向下一步。

1.6.2 遍历删除错误做法及原因

1. 直接删除后递增迭代器：

// 错误示例！可能导致崩溃或未定义行为
auto it = myUmap.begin();
while (it != myUmap.end()) {
    if (it->first % 2 == 0) {
        myUmap.erase(it); // 删除当前迭代器指向的元素
    }
    ++it; // 危险！被删除的迭代器已失效，递增操作未定义
}

错误原因：

erase(it) 会使迭代器 it 失效（指向已释放的内存），此时执行 ++it 属于未定义行为（可能崩溃、跳过元素或陷入死循环）。

2. 在 C++11 前使用 erase 后直接复用迭代器：

C++11 之前的 unordered_map::erase 不返回下一个迭代器，若删除后直接使用原迭代器，会导致同样的失效问题：

// C++11 前的错误示例
auto it = myUmap.begin();
while (it != myUmap.end()) {
    if (it->first % 2 == 0) {
        myUmap.erase(it); // 迭代器 it 已失效
    } else {
        ++it;
    }
    // 若执行了 erase，此处 it 已失效，循环条件判断可能出错
}

1.7 清空容器

clear() 方法可一键清空 unordered_map 中的所有元素，释放内存（但可能保留部分底层哈希表的容量）：

std::unordered_map<int, std::string> fruitMap = { {1, "苹果"}, {2, "香蕉"} };
fruitMap.clear(); // 清空所有元素，size() 变为 0
std::cout << "清空后元素数量：" << fruitMap.size() << std::endl; // 输出 0

若需彻底释放内存，可结合 “swap 技巧”（C++11 前常用，C++11 后可使用 shrink_to_fit()）：

// 彻底释放内存（C++11 前）
std::unordered_map<int, std::string>().swap(fruitMap);

// C++11 及以上：请求容器收缩至匹配实际元素数量
fruitMap.shrink_to_fit();

1.8 unordered_map 与 map 的核心差异

特性	std::unordered_map	std::map
底层实现	哈希表（Hash Table）	红黑树（Red-Black Tree，一种平衡二叉树）
元素顺序	无序（按哈希值存储）	按键升序排列（可自定义比较器）
查找 / 插入 / 删除效率	平均 O (1)，最坏 O (n)（哈希冲突严重时）	稳定 O (log n)
内存占用	较高（哈希表需要额外空间解决冲突）	较低（红黑树结构紧凑）
键的要求	需支持哈希函数（std::hash）和相等性判断（std::equal_to）	需支持比较运算符（如 <，或自定义比较器）
迭代器稳定性	插入时可能失效（哈希表扩容时），删除时仅被删迭代器失效	插入 / 删除时其他迭代器通常有效

适用场景选择：

若需快速查找且不关心顺序 → 选 unordered_map（如缓存、字典）。
若需元素有序或对最坏情况性能有要求 → 选 map（如范围查询、排序输出）。

1.9 自定义哈希函数与相等性判断

unordered_map 默认使用 std::hash 计算哈希值，用 std::equal_to 判断键是否相等。对于自定义类型（如结构体），需手动提供哈希函数和相等性判断器。

1.9.1 为自定义类型实现哈希与相等性

#include <unordered_map>
#include <string>

// 自定义类型：表示学生信息
struct Student {
    int id;
    std::string name;

    Student(int id, const std::string& name) : id(id), name(name) {}
};

// 1. 自定义哈希函数（需满足：若 a == b，则 hash(a) == hash(b)）
struct StudentHash {
    size_t operator()(const Student& s) const {
        // 组合 id 和 name 的哈希值（简单示例，实际可优化）
        return std::hash<int>()(s.id) ^ std::hash<std::string>()(s.name);
    }
};

// 2. 自定义相等性判断器
struct StudentEqual {
    bool operator()(const Student& a, const Student& b) const {
        // 定义两个 Student 相等的条件：id 和 name 都相同
        return a.id == b.id && a.name == b.name;
    }
};

// 3. 使用自定义类型作为键
int main() {
    std::unordered_map<Student, int, StudentHash, StudentEqual> studentScores;

    // 插入元素
    studentScores.emplace(Student(1, "张三"), 90);
    studentScores.emplace(Student(2, "李四"), 85);

    // 查找
    auto it = studentScores.find(Student(1, "张三"));
    if (it != studentScores.end()) {
        std::cout << "张三的分数：" << it->second << std::endl; // 输出 90
    }

    return 0;
}

1.9.2 为标准类型扩展哈希（谨慎使用）

可通过特化 std::hash 为标准类型（如 std::pair）添加哈希支持（需注意：C++ 标准不允许在 std 命名空间中添加非标准库类型的特化，但部分编译器支持对标准类型的扩展）：

#include <unordered_map>
#include <utility> // for std::pair

// 为 std::pair<int, int> 特化 std::hash
namespace std {
    template<> struct hash<std::pair<int, int>> {
        size_t operator()(const std::pair<int, int>& p) const {
            return hash<int>()(p.first) ^ hash<int>()(p.second);
        }
    };
}

// 使用 pair 作为键
std::unordered_map<std::pair<int, int>, std::string> coordMap;
coordMap[{0, 0}] = "原点";

1.10 性能优化技巧

1. 预分配容量：

若已知元素数量，使用 reserve(n) 提前分配足够容量，避免哈希表多次扩容（扩容会触发重新哈希，耗时较高）：

std::unordered_map<int, std::string> umap;
umap.reserve(1000); // 预留至少存储 1000 个元素的空间

2. 合理设置负载因子：

负载因子 = 元素数量 / 桶数量，默认值通常为 1.0。负载因子越小，哈希冲突概率越低，但内存占用越高。可通过 max_load_factor(f) 调整：

umap.max_load_factor(0.7); // 降低负载因子，减少冲突

3. 避免哈希函数质量差：

哈希函数若容易产生碰撞（如对不同键返回相同哈希值），会导致 unordered_map 退化为链表，性能骤降。设计时需保证哈希值分布均匀。

1.11 总结

std::unordered_map 凭借哈希表的特性，在平均情况下提供 O (1) 的查找、插入和删除效率，是高频数据访问场景的理想选择。其核心特点包括：

元素无序，键唯一，支持自定义哈希和相等性判断。
提供 insert()、emplace()、[] 等插入方式，find()、count() 等查找接口，erase() 多种删除形式。
与 map 相比，更适合追求查找速度且不关心顺序的场景。

掌握 unordered_map 的用法和特性，能帮助你在 C++ 开发中更灵活地处理键值对数据，平衡性能与需求。

2. unordered_multimap

在 C++ 标准库的关联容器家族中，unordered_multimap 是一个特殊的存在 —— 它允许键（key）重复，同时保持了哈希表带来的高效操作性能。本文将详细介绍 unordered_multimap 的特性、用法及适用场景，帮助你在实际开发中合理选择容器。

2.1 什么是 unordered_multimap？

unordered_multimap 是 C++11 引入的无序关联容器，用于存储键值对（key-value pairs），其核心特性如下：

键可重复：允许插入多个相同的键（与 unordered_map 的最大区别，后者键唯一）。
无序性：元素存储顺序与插入顺序无关，也不会按键排序（与 multimap 对比，后者是有序的）。
哈希实现：底层基于哈希表，通过哈希函数将键映射到桶（bucket）中，支持平均 O (1) 时间复杂度的插入、查找和删除。

头文件与命名空间：需包含，定义在 std 命名空间中。

模板定义：

template<
    class Key,                // 键的类型
    class T,                  // 值的类型
    class Hash = std::hash<Key>,  // 哈希函数（默认 std::hash<Key>）
    class KeyEqual = std::equal_to<Key>  // 键的相等比较器（默认 ==）
> class unordered_multimap;

2.2 与其他关联容器的对比

为了更好理解 unordered_multimap，我们将其与相似容器对比：

容器	键是否可重复	元素是否有序	底层实现	平均操作复杂度（插入 / 查找 / 删除）
unordered_map	不可重复	无序	哈希表	O(1)
unordered_multimap	可重复	无序	哈希表	O(1)
map	不可重复	有序（键升序）	红黑树	O(log n)
multimap	可重复	有序（键升序）	红黑树	O(log n)

核心差异：unordered_multimap 以 “无序” 为代价，换取了比 multimap 更高的平均操作效率；同时以 “允许键重复” 为特点，区别于 unordered_map。

2.3 unordered_multimap 常用操作

1. 构造与初始化

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

// 1. 默认构造
unordered_multimap<int, string> umm1;

// 2. 初始化列表构造（可包含重复键）
unordered_multimap<int, string> umm2 = {
    {1, "apple"},
    {2, "banana"},
    {1, "apricot"},  // 键1重复
    {3, "orange"},
    {2, "berry"}     // 键2重复
};

// 3. 拷贝构造
unordered_multimap<int, string> umm3(umm2);

// 4. 范围构造（从迭代器范围复制元素）
unordered_multimap<int, string> umm4(umm2.begin(), umm2.end());

2. 插入元素

unordered_multimap 仅支持 insert 和 emplace 插入（不支持 operator[]，因为键可能重复，无法确定赋值给哪个元素）。

// 1. insert 插入键值对（可直接传 pair 或初始化列表）
umm1.insert({1, "cat"});  // 插入 {1, "cat"}
umm1.insert(make_pair(1, "dog"));  // 插入 {1, "dog"}（键1重复）

// 2. emplace 直接构造元素（参数传递给键值对的构造函数，效率更高）
umm1.emplace(2, "bird");  // 构造并插入 {2, "bird"}

// 3. 插入另一个容器的范围元素
umm1.insert(umm2.begin(), umm2.end());

插入后，umm1 中键为 1 的元素可能有多个（如 "cat"、"dog" 等）。

3. 访问与查找元素

由于键可重复，unordered_multimap 不提供 operator[] 和 at() 方法（无法唯一确定元素）。需通过以下方式查找：

find(key)：返回第一个键为 key 的元素迭代器（若不存在则返回 end()）。
count(key)：返回键为 key 的元素个数。
equal_range(key)：返回一个迭代器对（pair<iterator, iterator>），表示所有键为 key 的元素范围（左闭右开区间）。

// 示例：基于 umm2（包含 {1,"apple"}, {1,"apricot"}, {2,"banana"}, ...）
// 1. find 查找第一个键为1的元素
auto it = umm2.find(1);
if (it != umm2.end()) {
    cout << "第一个键为1的元素：" << it->first << ":" << it->second << endl; 
    // 输出：1:apple（顺序取决于哈希表实现，不保证插入顺序）
}

// 2. count 统计键为2的元素个数
cout << "键为2的元素个数：" << umm2.count(2) << endl;  // 输出：2

// 3. equal_range 获取所有键为1的元素范围（最常用）
auto range = umm2.equal_range(1);
cout << "键为1的所有元素：" << endl;
for (auto it = range.first; it != range.second; ++it) {
    cout << it->first << ":" << it->second << endl; 
    // 输出：1:apple 和 1:apricot（顺序不确定）
}

注意：equal_range 是遍历相同键元素的最优方式，避免了多次查找的开销。

4. 删除元素

unordered_multimap 的删除操作支持三种方式，需注意迭代器的有效性：

erase(key)：删除所有键为 key 的元素，返回删除的个数。
erase(iterator)：删除迭代器指向的单个元素，返回下一个有效迭代器。
erase(first, last)：删除迭代器范围 [first, last) 内的元素，返回下一个有效迭代器。

// 示例：基于 umm2
// 1. 按键删除所有元素（删除键为1的元素）
size_t deleted = umm2.erase(1);
cout << "删除了" << deleted << "个键为1的元素" << endl;  // 输出：2

// 2. 按迭代器删除单个元素（删除第一个键为2的元素）
auto it = umm2.find(2);
if (it != umm2.end()) {
    it = umm2.erase(it);  // 用返回值更新迭代器
}

// 3. 按范围删除（删除所有键为2的元素）
auto range = umm2.equal_range(2);
umm2.erase(range.first, range.second);  // 删除范围[range.first, range.second)

迭代器失效规则：删除元素时，只有被删除的迭代器失效，其他迭代器（包括指向其他桶的迭代器）仍然有效。

5. 遍历元素

遍历 unordered_multimap 需使用迭代器，元素顺序与插入顺序无关（由哈希函数决定）：

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

// 遍历特定键的所有元素（结合 equal_range）
int target = 2;
auto range = umm1.equal_range(target);
for (auto it = range.first; it != range.second; ++it) {
    cout << "键" << target << "的元素：" << it->second << endl;
}

6. 其他常用方法

size()：返回元素总个数。
empty()：判断容器是否为空。
clear()：清空所有元素。
bucket_count()：返回哈希表的桶数量。
load_factor()：返回负载因子（元素数 / 桶数量）。

cout << "元素总数：" << umm1.size() << endl;
cout << "是否为空：" << (umm1.empty() ? "是" : "否") << endl;
umm1.clear();  // 清空容器

2.4 注意事项

键不可修改：unordered_multimap 中的键是 const 类型（pair<const Key, T>），无法直接修改。若需修改键，需先删除旧元素，再插入新元素。

// 错误：键是const，不能修改
auto it = umm1.find(1);
if (it != umm1.end()) {
    it->first = 10;  // 编译错误！
}

// 正确：删除旧元素，插入新元素
if (it != umm1.end()) {
    string val = it->second;
    umm1.erase(it);
    umm1.insert({10, val});
}

哈希函数的重要性：若使用自定义类型作为键，需提供合适的哈希函数和相等比较器，否则可能导致哈希冲突严重，性能退化到 O (n)。
无序性的影响：元素顺序不确定，不能依赖顺序进行逻辑处理（如需有序，应使用 multimap）。
内存开销：哈希表需要预留一定空间以减少冲突，内存占用通常高于 multimap。

2.5 适用场景

unordered_multimap 适合以下场景：

需要存储一对多映射关系（如一个用户 ID 对应多个订单）。
无需元素有序，但要求快速插入、查找和删除（平均 O (1) 复杂度）。
需要统计或遍历相同键的所有关联值（如按关键词分组的多个数据）。

示例场景：

日志系统中，按 “错误类型”（键）存储多条日志（值），需快速查询某类错误的所有日志；电商系统中，按 “用户 ID” 存储多个订单信息。

2.6总结

unordered_multimap 是 C++ 中处理 “无序 + 键可重复” 映射关系的高效容器，其核心优势在于平均 O (1) 的操作性能。使用时需注意：

通过 equal_range 遍历相同键的元素。
避免修改键，如需修改需先删后插。
自定义键类型时需确保哈希函数质量。

根据场景灵活选择 unordered_multimap、multimap、unordered_map 或 map，才能发挥 STL 容器的最大效能。

3. 文章总结

本文系统介绍了 C++11 引入的无序关联容器 unordered_map 与 unordered_multimap，核心围绕其设计价值、特性及使用场景展开，可概括为以下要点：

1. 设计背景与价值

针对传统有序容器（map/multimap）基于红黑树实现带来的 O (log n) 时间复杂度、排序冗余及内存开销问题，无序容器以哈希表为底层，通过牺牲有序性换取平均 O (1) 的操作效率，填补了 “高频操作且无需排序” 场景的需求空白。

2. 核心特性对比

键唯一性：unordered_map 键唯一，适用于 “一对一” 映射；unordered_multimap 键可重复，适配 “一对多” 场景。
无序性：元素存储顺序由哈希函数决定，与插入顺序无关，区别于有序容器的键升序特性。
性能：插入、查找、删除平均复杂度为 O (1)（哈希冲突严重时最坏为 O (n)），优于红黑树的稳定 O (log n)，但内存占用更高。

3. 关键操作与用法

初始化：支持初始化列表、CTAD 自动推导（C++17）及自定义哈希 / 相等性判断器。
插入：insert()（去重）、emplace()（高效构造）为 unordered_map 常用方式；unordered_multimap 不支持 operator[]，仅用 insert()/emplace()。
查找：find() 定位单个元素，count() 检查存在性；unordered_multimap 需用 equal_range() 获取相同键的元素范围。
删除：支持按迭代器、键或范围删除，需注意迭代器失效规则（仅被删迭代器失效）。

4. 与有序容器的选型标准

需快速单键查询、无需排序 → 选 unordered_map/unordered_multimap。
需有序遍历或范围查询 → 选 map/multimap。
键唯一用 unordered_map/map，键可重用 unordered_multimap/multimap。

5. 最佳实践

预分配容量（reserve()）、调整负载因子减少哈希冲突。
自定义类型作为键时，需确保哈希函数均匀性和相等性判断逻辑正确。
遍历删除元素时，利用 erase() 返回值更新迭代器避免失效。

综上，unordered_map 与 unordered_multimap 为 C++ 开发者提供了 “效率优先” 的键值对存储方案，与有序容器形成互补，掌握其特性可根据场景精准选型，平衡性能与功能需求。