C++11 新特性：std::unordered

本文主要是介绍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)。
装载因子和哈希函数的选择对性能有重要影响。较低的装载因子可以减少哈希冲突但会增加内存使用，而一个好的哈希函数可以减少哈希冲突，提高性能。