C++ std::unordered_map
std::unordered_map 是 C++ STL 中无序键值对容器的核心成员，底层基于哈希表实现，存储唯一键（key）与对应值（value）的映射关系，且不保证键的顺序。其最大优势是插入、查找、删除操作的平均时间复杂度为 O(1)，适合对效率敏感且无需键有序的场景。1、底层数据结构与特性
1.1 底层数据结构与核心概念
[*]底层结构：哈希表（Hash Table）。
[*]核心特性：
[*]关联性：元素是键值对，即 std::pair。
[*]无序性：容器中的元素是无序的。元素的存储顺序取决于其键（Key） 的哈希值以及它们如何被映射到桶中。遍历顺序是不确定的。
[*]唯一性：集合中每个元素的键（Key） 都是唯一的。
[*]实现原理：
[*]容器维护一个桶数组（Array of Buckets）。
[*]通过一个哈希函数将元素的键转换成一个哈希值。
[*]根据哈希值计算出该元素应该属于哪个桶（通常是 hash_value % bucket_count）。
[*]采用链地址法解决哈希冲突，即每个桶是一个链表，所有映射到同一桶的键值对都放在这个链表中。
1.2 核心特性与原理
[*]平均常数时间复杂度 (O(1))
[*]在理想情况下，通过键进行的插入、删除和查找操作的平均时间复杂度是常数级的，即 O(1)。这是它最大的优势。
[*]最坏情况时间复杂度 (O(n))
[*]在最坏情况下（所有元素都哈希到同一个桶），整个哈希表退化为一个链表，所有操作的时间复杂度变为 O(n)。
[*]负载因子与重哈希（Rehashing）
[*]负载因子：load_factor = size() / bucket_count()。
[*]当 load_factor > max_load_factor 时，容器会自动执行重哈希（分配新桶数组，重新映射所有元素）。
[*]重哈希是一个开销很大的操作，会导致所有迭代器、指针和引用失效。
[*]键不可修改，值可修改
[*]元素的键是 const 的，一旦插入就不能修改。
[*]元素的值是非 const 的，可以随时修改。
2、操作指导与代码示例
2.1 初始化与构造函数
#include <unordered_map>
#include <string>
// 1. 空unordered_map
std::unordered_map<int, std::string> umap1;
// 2. 使用初始化列表 (C++11)
std::unordered_map<int, std::string> umap2 = {
{1, "Alice"},
{2, "Bob"},
{3, "Charlie"} // 顺序是不确定的！
};
// 3. 指定初始桶数量（用于性能调优）
std::unordered_map<std::string, int> umap3(100); // 创建时约有100个桶
// 4. 拷贝构造函数
std::unordered_map<int, std::string> umap4(umap2);2.2 元素访问与查找（最核心的操作）
std::unordered_map m = {{1, "Apple"}, {2, "Banana"}};// --- 最常用的访问操作：operator[] ---// 特性：如果键存在，返回对应的值的引用。// 如果键不存在，则会插入一个具有该键的新元素，并将其值进行值初始化，然后返回这个新值的引用。m = "Apricot"; // 修改已存在的键值对：{1, "Apricot"}std::cout 这个有用。 感谢分享，学习下。 谢谢楼主提供！
页:
[1]