本文主要是介绍C++11 新特性：std::unordered_map 无序映射，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
std::unordered_map是 C++11 标准库中引入的一种关联容器，它提供了键值对的存储能力。
与std::map相比，std::unordered_map内部使用哈希表实现，因此它支持平均常数时间复杂度的查找、插入和删除操作，而std::map使用红黑树实现，提供对数时间复杂度的操作。
由于std::unordered_map是基于哈希表，它不是按任何顺序存储元素。
基本原理
std::unordered_map内部主要是通过一个动态数组（通常称为 bucket 数组）来维护元素，每个数组元素（或称为 bucket）包含一个指向链表（或其他形式的容器，如小型向量）的指针。
这些链表用于存储具有相同哈希值的元素（键值对）。当发生哈希冲突时（即不同的键产生相同的哈希值），std::unordered_map会将具有相同哈希值的元素存储在同一个 bucket 的链表中。
关键组成部分
-
哈希函数：
std::unordered_map使用一个哈希函数将键映射到 bucket 的索引。哈希函数的质量直接影响到容器的性能，理想情况下，哈希函数应该将键均匀分布到所有的 buckets 上，以减少哈希冲突。 -
哈希表：内部数据结构，通常是一个动态数组，其中的每个元素指向一个链表（或其他容器），用于解决哈希冲突。
-
键值对：存储在链表中的元素，每个元素包含一个键和一个值。
-
装载因子：
std::unordered_map的装载因子是一个浮点数，定义为元素个数 / bucket 数量。当装载因子超过特定阈值（默认为1.0）时，哈希表会进行重新哈希（rehashing），即增加 bucket 数量并重新分配所有元素，以保持操作的效率。
操作过程
-
插入：当插入一个新的键值对时，
std::unordered_map首先使用哈希函数计算键的哈希值，然后根据哈希值确定对应的 bucket 索引，将新元素插入到该 bucket 的链表中。如果导致装载因子超过设定阈值，则会进行重新哈希。 -
查找：查找操作同样先计算键的哈希值，然后定位到对应的 bucket，最后在 bucket 的链表中线性搜索具有相应键的元素。
-
删除：删除操作首先找到包含该键的 bucket，然后在 bucket 的链表中找到并删除该元素。
使用场景
std::unordered_map适用于以下场景：
-
需要快速查找的场景：当你需要快速地根据键查找值时，
std::unordered_map是一个很好的选择，因为它提供了平均常数时间的查找性能。 -
不关心元素顺序的场景：如果你不需要元素以特定顺序（如升序或降序）存储，
std::unordered_map可以提供更优的性能。 -
键值对存储：当你需要存储和管理一组键值对，并且每个键都是唯一的，使用
std::unordered_map可以方便地通过键来访问对应的值。
常用方法
std::unordered_map提供了一系列方法来管理键值对，包括：
insert()：向容器中插入新的键值对。emplace()：原地构造一个新的键值对元素，通常比insert更高效。erase()：删除指定位置或键的元素。clear()：清空容器。find()：查找具有指定键的元素，如果找到，则返回一个指向该元素的迭代器；否则，返回end()迭代器。count()：返回具有指定键的元素的数量，由于std::unordered_map的键是唯一的，返回值只能是0或1。operator[]：访问指定键关联的值，如果键不存在，则会插入一个具有该键的新元素，并返回其值的引用。at()：访问指定键关联的值，如果键不存在，抛出std::out_of_range异常。size()：返回容器中元素的数量。empty()：检查容器是否为空。
示例代码
#include <iostream>
#include <unordered_map>
#include <string>int main() {std::unordered_map<std::string, int> map;// 插入元素map.insert({"apple", 5});map["banana"] = 3;// 访问元素std::cout << "apple has " << map["apple"] << " units.\n";// 使用find查找元素auto search = map.find("banana");if (search != map.end()) {std::cout << "Found banana, count = " << search->second << '\n';} else {std::cout << "Banana not found.\n";}// 遍历元素for (const auto& pair : map) {std::cout << pair.first << " has " << pair.second << " units.\n";}// 删除元素map.erase("apple");// 检查大小std::cout << "The map has " << map.size() << " elements.\n";return 0;
}
输出：
apple has 5 units.
Found banana, count = 3
banana has 3 units.
apple has 5 units.
The map has 1 elements.
性能考虑
std::unordered_map的平均时间复杂度为常数时间 O(1)，但最坏情况下（所有元素都映射到同一个 bucket 中）时间复杂度会退化到 O(n)。- 装载因子和哈希函数的选择对性能有重要影响。较低的装载因子可以减少哈希冲突但会增加内存使用，而一个好的哈希函数可以减少哈希冲突，提高性能。
总结
std::unordered_map是 C++11 中引入的一个非常有用的容器，特别是在需要快速查找、插入和删除键值对的场景下。
它通过提供平均常数时间复杂度的操作，帮助开发者编写更高效的代码。不过，使用时需要注意，由于其基于哈希表实现，元素的存储顺序是不确定的。
这篇关于C++11 新特性：std::unordered_map 无序映射的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
