1 概述
std::unordered_map 是 C++ 标准模板库（STL）中的一个关联容器，它存储的元素是键值对，且每个键在容器中唯一。这个容器的特点是它基于哈希表实现，因此具有非常快的查找、插入和删除操作的平均时间复杂度，即 O(1)。
std::unordered_map 与 std::map 的主要区别体现在以下几个方面：
（1）底层数据结构： std::unordered_map 底层是哈希表，通过哈希函数计算元素的存储位置。而 std::map 的底层则是红黑树，一种自平衡的二叉搜索树。
（2）性能： 由于哈希表的特性，std::unordered_map 在查找、插入和删除操作上的平均时间复杂度为O(1)，这在处理大量数据时效率非常高。而 std::map 的查找、插入和删除操作的时间复杂度为 O(log n)，其中 n 是元素的数量。因此，在大多数情况下，std::unordered_map 会比 std::map 更快。
（3）有序性： std::map 的元素会按照键的顺序进行排序，因此可以方便地进行有序性操作，如范围遍历和查找。而 std::unordered_map 不会保持元素的插入顺序，遍历时元素的顺序是不确定的。
（4）空间占用： 虽然 std::unordered_map 在查找、插入和删除操作上性能优越，但由于哈希表的特性，它在内存消耗上可能会稍大一些。而 std::map 由于需要维护红黑树的平衡，因此在空间占用上可能稍小一些。
std::unordered_map 的实现原理主要基于哈希表。哈希表通过哈希函数将键映射到数组的某个索引位置，从而快速找到对应的值。哈希表的每个槽位（bucket）可以存储一个链表或其他动态数据结构，用于处理哈希冲突（即不同键映射到同一索引位置的情况）。当进行查找、插入或删除操作时，std::unordered_map 首先使用哈希函数计算键的哈希值，然后定位到对应的槽位，最后在槽位中的链表或其他数据结构中查找、插入或删除元素。
2 声明与初始化
2.1 声明
首先，需要包含 <unordered_map> 头文件，然后声明一个 std::unordered_map 变量，并指定键和值的类型。
#include <unordered_map>
std::unordered_map<KeyType, ValueType> mapName;
其中 KeyType 是键的类型，ValueType 是值的类型，mapName 是你为该 unordered_map 变量选择的名称。
2.2 初始化
std::unordered_map 可以通过多种方式初始化。以下是一些常见的初始化方法：
（1）默认初始化
可以声明一个 std::unordered_map 变量而不进行任何初始化，它会是空的。
std::unordered_map<std::string, int> myMap; // 默认初始化，空的unordered_map
（2）使用初始化列表
在声明时，可以使用初始化列表来插入一些初始元素。
std::unordered_map<std::string, int> myMap = {
{"apple", 5},
{"banana", 3},
{"orange", 2}
};
（4）使用构造函数和迭代器范围
如果有另一个容器（如 std::pair 的数组或 std::vector），并且想要用它的内容来初始化 std::unordered_map，则可以使用构造函数和迭代器范围。
std::vector<std::pair<std::string, int>> vec = {
{"apple", 5},
{"banana", 3}
};
std::unordered_map<std::string, int> myMap(vec.begin(), vec.end());
3 插入元素
3.1 插入方法
（1）使用 insert 成员函数
insert 是 std::unordered_map 的一个成员函数，用于向容器中插入一个或多个元素。它有多种重载形式，以适应不同的插入需求。
单个元素插入
可以使用 insert 函数插入一个单独的键值对。这通常通过创建一个 std::pair 对象或使用 std::make_pair 函数来完成，然后将其作为 insert 函数的参数。
std::unordered_map<int, std::string> myMap;
myMap.insert(std::make_pair(1, "one"));
// 或者使用 std::pair 的构造函数
myMap.insert(std::pair<int, std::string>(2, "two"));
从 C++11 开始，还可以使用列表初始化语法来更简洁地插入元素：
myMap.insert({3, "three"});
插入一个元素范围
可以使用 insert 函数插入一个元素范围，这通常是从另一个 unordered_map 或其他兼容的容器中复制元素。
std::unordered_map<int, std::string> otherMap = {{4, "four"}, {5, "five"}};
myMap.insert(otherMap.begin(), otherMap.end());
这将把 otherMap 中的所有元素插入到 myMap 中。
（2）使用下标运算符 []
尽管下标运算符 [] 主要用于访问元素，但如果尝试访问一个不存在的键，它实际上会创建一个新的元素，并将其初始化为默认值。因此，也可以使用它来“插入”元素，尽管这不是其设计的主要目的，并且在键已存在时会替换现有值。
std::unordered_map<int, std::string> myMap;
myMap[1] = "one"; // 如果键 1 不存在，则插入它
使用 [] 运算符插入元素时要小心，因为它会替换已存在的键的值，而不是仅仅插入新元素。
（3）使用 emplace 成员函数
emplace 是 C++11 引入的一个更高效的插入方法，它直接在容器中构造元素，避免了不必要的复制或移动操作。它接受构造元素所需的参数，并在容器内部直接构造元素。
std::unordered_map<int, std::string> myMap;
myMap.emplace(1, "one"); // 直接在容器中构造键值对 (1, "one")
（4）插入的返回值
对于 insert 和 emplace 函数，如果插入成功（即键在插入前不存在于容器中），它们会返回一个指向新插入元素的迭代器。如果键已经存在，则 insert 不会插入新元素，并返回一个指向现有元素的迭代器。
3.2 时间复杂度
在平均情况下，std::unordered_map 的插入操作具有常数时间复杂度 O(1)，因为哈希表允许直接定位到存储元素的位置。然而，在最坏情况下（例如哈希冲突很多时），插入操作的时间复杂度可能会退化到 O(n)，其中 n 是容器中元素的数量。因此，虽然哈希表通常提供非常快的插入性能，但在设计哈希函数时需要小心以避免最坏情况的发生。
3.3 综合示例
下面是一个完整的示例，展示了如何使用 insert 和 emplace 函数向 std::unordered_map 中插入元素：
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<int, std::string> myMap;
// 使用 insert 插入元素
myMap.insert(std::make_pair(1, "one"));
myMap.insert({2, "two"});
// 使用 emplace 插入元素
myMap.emplace(3, "three");
// 遍历并打印元素
for (const auto& pair : myMap) {
std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
}
return 0;
}
上面代码的输出为：
Key: 1, Value: one
Key: 2, Value: two
Key: 3, Value: three
这个示例创建了一个 std::unordered_map，使用 insert 和 emplace 函数向其中插入了几个元素，然后遍历并打印了容器中的所有元素。
3.4 注意事项
- 当使用 insert 或 emplace 函数时，如果插入的键已经存在于 std::unordered_map 中，则不会插入新的键值对，而是会保留原有的键值对不变。
- 插入操作的性能受到哈希函数质量的影响。一个好的哈希函数应该能够均匀分布键到哈希表的各个桶中，从而避免哈希冲突。如果哈希函数设计得不好，可能导致性能下降，特别是在插入大量元素时。
- std::unordered_map 不保证元素的顺序。每次插入元素时，它们可能会被放置到哈希表的任何位置，这取决于哈希函数和当前的哈希表状态。因此，如果你需要保持元素的插入顺序，应该考虑使用 std::map 或其他有序的容器。
4 访问元素
4.1 使用下标运算符 []
下标运算符 [] 是访问 std::unordered_map 中元素最常用的方法之一。通过提供键作为下标，可以获取或设置与该键关联的值。
std::unordered_map<int, std::string> myMap;
myMap[1] = "one"; // 设置键为 1 的值为 "one"
std::string value = myMap[1]; // 获取键为 1 的值，存储在 value 中
使用 [] 运算符的一个重要特点是，如果键不存在于 unordered_map 中，它会插入该键，并将其值初始化为默认值（对于基本数据类型，通常是 0 或空值）。因此，如果你只是想要检查一个键是否存在并获取其值，而不希望插入新键，那么使用 find 或 count 方法可能更为合适。
4.2 使用 at 成员函数
at 成员函数是另一种访问 std::unordered_map 中元素的方法。与 [] 运算符不同，at 不会插入新元素；如果键不存在，它会抛出一个 std::out_of_range 异常。
std::unordered_map<int, std::string> myMap;
myMap[1] = "one"; // 设置键为 1 的值为 "one"
std::string value = myMap.at(1); // 获取键为 1 的值，存储在 value 中
// myMap.at(2); // 这会抛出 std::out_of_range 异常，因为键 2 不存在
由于 at 在键不存在时会抛出异常，因此它更适合于那些确定键一定存在的情况，或者想要通过异常处理机制来处理键不存在的情况。
4.3 使用 find 成员函数
find 成员函数用于在 std::unordered_map 中查找一个键，并返回一个指向该键对应元素的迭代器。如果键不存在，则返回 end() 迭代器。
std::unordered_map<int, std::string> myMap;
myMap[1] = "one";
auto it = myMap.find(1); // 查找键为 1 的元素
if (it != myMap.end()) {
std::string value = it->second; // 获取键为 1 的值，存储在 value 中
} else {
std::cout << "Key not found." << std::endl;
}
使用 find 方法的一个优势是，它不会在键不存在时插入新元素或抛出异常。因此，它更适用于那些需要检查键是否存在，并且不希望改变 unordered_map 的情况。
4.4 访问键值对
一旦通过某种方式（如 []、at 或 find）获取了指向 unordered_map 中元素的迭代器或引用，那么就可以访问该键值对的键和值。对于迭代器 it，可以使用 it->first 来访问键，使用 it->second 来访问值。对于通过引用直接获取的元素，可以使用 .first 和 .second 成员来访问键和值。
std::unordered_map<int, std::string> myMap;
myMap[1] = "one";
auto it = myMap.find(1); // 查找键为 1 的元素
int key = it->first; // 访问键
std::string value = it->second; // 访问值
// 或者通过引用直接访问
const std::pair<int, std::string>& kvPair = *it;
int key = kvPair.first; // 访问键
std::string value = kvPair.second; // 访问值
5 删除元素
5.1 使用 erase 成员函数删除单个元素
erase 成员函数是 std::unordered_map 中用于删除元素的主要方法。它接受一个迭代器参数，指向要删除的元素，并返回指向下一个元素的迭代器。通过 find 成员函数，你可以获得要删除元素的迭代器，并将其传递给 erase。
std::unordered_map<int, std::string> myMap;
myMap[1] = "one";
myMap[2] = "two";
myMap[3] = "three";
// 使用 find 查找键为 2 的元素，并使用 erase 删除它
auto it = myMap.find(2);
if (it != myMap.end()) {
it = myMap.erase(it); // 删除元素，并返回指向下一个元素的迭代器
}
注意：在调用 erase 之后，原来的迭代器 it 会失效，因此上面的代码将 erase 的返回值重新赋给 it，以便它可以继续用于遍历（如果有需要的话）。
5.2 使用 erase 成员函数删除指定范围内的元素
erase 成员函数还有一个重载版本，它接受两个迭代器参数，表示要删除的范围（包括起始迭代器指向的元素，但不包括结束迭代器指向的元素）。这可以用于删除多个连续的元素。
std::unordered_map<int, std::string> myMap;
// 假设 myMap 中已经填充了一些元素
// 删除键在 [2, 4) 范围内的所有元素（包括键为 2 的元素，但不包括键为 4 的元素）
auto range_start = myMap.lower_bound(2); // 第一个不小于 2 的元素的迭代器
auto range_end = myMap.upper_bound(4); // 第一个大于 4 的元素的迭代器
myMap.erase(range_start, range_end);
5.3 使用 clear 成员函数删除所有元素
如果想要删除 std::unordered_map 中的所有元素，可以使用 clear 成员函数。这将移除容器中的所有键值对，并将容器的大小变为 0。
std::unordered_map<int, std::string> myMap;
// 假设 myMap 中已经填充了一些元素
myMap.clear(); // 删除所有元素，myMap 现在为空
5.4 遍历删除
（1）使用迭代器遍历并手动管理迭代器（推荐）
最安全的方法是使用迭代器遍历 unordered_map，并在删除元素后更新迭代器。一种常见的方法是使用 erase 的返回值，它返回指向下一个有效元素的迭代器。
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<std::string, int> myMap = {
{"apple", 5},
{"banana", 6},
{"orange", 2}
};
for (auto it = myMap.begin(); it != myMap.end(); ) {
// 检查是否需要删除当前元素
if (it->second %2 == 0) {
// 使用 erase 删除元素，并获取下一个有效元素的迭代器
it = myMap.erase(it);
}
else {
// 否则，继续到下一个元素
++it;
}
}
return 0;
}
这个例子使用了 it = myMap.erase(it); 来更新迭代器。如果当前元素满足删除条件，erase 会删除它并返回指向下一个元素的迭代器；否则，将迭代器递增到下一个元素。
（2）复制到临时容器并交换（如果删除大量元素，可能更高效）
如果预计会删除大量元素，一种更高效的方法可能是将不需要删除的元素复制到另一个 unordered_map 中，然后交换两个容器的内容。这样可以避免在原始容器中多次重新分配和哈希。
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<std::string, int> myMap = {
{"apple", 5},
{"banana", 6},
{"orange", 2}
};
std::unordered_map<std::string, int> tempMap;
// 复制不需要删除的元素到临时容器
for (const auto& kvPair : myMap) {
if (kvPair.second % 2 != 0) {
tempMap.insert(kvPair);
}
}
// 交换两个容器的内容
myMap.swap(tempMap);
return 0;
}
这种方法的好处是它在删除大量元素时通常更高效，因为它避免了在原始容器中频繁地重新分配和哈希。然而，它也需要额外的内存来存储临时容器。
（3）注意事项
- 当在循环中删除 std::unordered_map 的元素时，需要特别注意迭代器的有效性。一旦使用 erase 删除了一个元素，指向该元素的迭代器就会失效，因此不应再使用该迭代器。如果需要继续遍历容器，应该使用 erase 的返回值（指向下一个元素的迭代器）来更新你的迭代器。
- erase 成员函数不会抛出异常（除非在自定义的哈希函数或相等性比较函数中发生了异常）。
- erase 的时间复杂度通常与哈希表的性能相关，平均情况下是常数时间，但在最坏情况下可能是线性时间，这取决于哈希函数的质量和哈希表的当前状态。
6 使用自定义键类型
在 C++ 的 std::unordered_map 中，可以使用自定义键类型。当使用自定义类型作为键时，需要确保该类型可以正确地计算哈希值，并且提供了相等性比较的方式。这通常涉及到两个重要的方面：
- 自定义哈希函数：需要提供一个哈希函数，它将自定义类型映射到一个 size_t 类型的哈希值。这可以通过定义一个函数对象（也称为仿函数或 Functor）来实现，该函数对象重载了 operator()。
- 相等性比较：std::unordered_map 需要知道如何比较两个键是否相等。这通常是通过重载 operator== 来实现的，但也可以提供一个自定义的相等性比较函数对象。
下面是一个使用自定义键类型的 std::unordered_map 的示例：
#include <iostream>
#include <unordered_map>
#include <string>
#include <functional> // 用于 std::hash 和 std::equal_to
// 自定义键类型
struct CustomKey {
std::string id;
int value;
// 重载 == 运算符以比较两个 CustomKey 对象是否相等
bool operator==(const CustomKey& other) const {
return id == other.id && value == other.value;
}
};
// 自定义哈希函数对象
struct CustomKeyHash {
size_t operator()(const CustomKey& key) const {
// 使用 std::hash 特化版本来分别计算 id 和 value 的哈希值
// 然后将它们组合成一个最终的哈希值
size_t h1 = std::hash<std::string>()(key.id);
size_t h2 = std::hash<int>()(key.value);
return h1 ^ (h2 << 1); // 使用异或和左移来组合哈希值
}
};
int main()
{
// 使用自定义键类型和哈希函数对象的 unordered_map
std::unordered_map<CustomKey, std::string, CustomKeyHash> myMap;
// 插入元素
myMap[{"key1", 10}] = "Value for key1";
myMap[{"key2", 20}] = "Value for key2";
// 查找元素
CustomKey searchKey = {"key1", 10};
auto it = myMap.find(searchKey);
if (it != myMap.end()) {
std::cout << "Found: " << it->second << std::endl;
} else {
std::cout << "Not found" << std::endl;
}
return 0;
}
上面代码的输出为：
Found: Value for key1
这个例子定义了一个 CustomKey 结构体作为键类型，并重载了 operator== 来比较两个 CustomKey 对象是否相等。然后，定义了一个名为 CustomKeyHash 的自定义哈希函数对象，它接受一个 CustomKey 对象并返回一个 size_t 类型的哈希值。在哈希函数中，使用 std::hash 特化版本来分别计算 id 和 value 成员的哈希值，并将它们组合起来。
当创建 std::unordered_map 实例时，将 CustomKey 作为键类型，并传入 CustomKeyHash 作为哈希函数对象。这样，std::unordered_map 就知道如何计算 CustomKey 类型的哈希值，并使用它来存储和查找元素了。
注意：自定义哈希函数应该尽量使得不同的键产生不同的哈希值，以减少哈希冲突并提高性能。在实际应用中，可能需要根据键类型的特性来设计更复杂的哈希函数。此外，如果没有特殊的相等性比较需求，并且已经正确地重载了 operator==，那么通常不需要提供自定义的相等性比较函数对象，因为 std::unordered_map 会自动使用重载的 operator==。