std::unordered_map
定义在头文件 <unordered_map> 中 |
||
template< class Key, |
(1) | (自 C++11 起) |
namespace pmr { template< |
(2) | (自 C++17 起) |
std::unordered_map
是一个关联容器,它包含具有唯一键的键值对。元素的搜索、插入和删除的平均时间复杂度为常数。
在内部,元素不会以任何特定顺序排序,而是组织到桶中。将元素放置到哪个桶中完全取决于其键的哈希值。具有相同哈希码的键出现在同一个桶中。这允许快速访问单个元素,因为一旦计算出哈希值,它就会引用放置元素的确切桶。
如果映射的键相等谓词在传递给这些键时返回 true,则两个键被认为是等效的。如果两个键等效,则哈希函数必须为这两个键返回相同的值。
std::unordered_map
满足 Container、AllocatorAwareContainer、UnorderedAssociativeContainer 的要求。
内容 |
[编辑] 迭代器失效
操作 | 失效 |
---|---|
所有只读操作,交换,std::swap | 从不 |
清除,重新哈希,保留,运算符= | 总是 |
插入,放置,放置提示,运算符[] | 只有在导致重新哈希时 |
擦除 | 仅擦除元素 |
[编辑] 注意
- 交换函数不会使容器内的任何迭代器失效,但它们会使标记交换区域末尾的迭代器失效。
- 即使对应的迭代器失效,对存储在容器中的键或数据的引用和指针也只会被擦除该元素所使失效。
[编辑] 模板参数
本节不完整 原因:添加模板参数的描述。 |
[编辑] 成员类型
成员类型 | 定义 |
key_type
|
Key |
mapped_type
|
T |
value_type
|
std::pair<const Key, T> |
size_type
|
无符号整数类型(通常为 std::size_t) |
difference_type
|
带符号整数类型(通常为 std::ptrdiff_t) |
哈希函数
|
Hash |
键比较函数
|
KeyEqual |
分配器类型
|
Allocator |
引用
|
value_type& |
常量引用
|
const value_type& |
指针
|
std::allocator_traits<Allocator>::pointer |
常量指针
|
std::allocator_traits<Allocator>::const_pointer |
迭代器
|
LegacyForwardIterator 到 value_type |
常量迭代器
|
LegacyForwardIterator 到 const value_type |
本地迭代器
|
一种迭代器类型,其类别、值、差值、指针和 引用类型与 iterator 相同。此迭代器可用于遍历单个桶,但不能跨桶遍历 |
常量本地迭代器
|
一种迭代器类型,其类别、值、差值、指针和 引用类型与 const_iterator 相同。此迭代器可用于遍历单个桶,但不能跨桶遍历 |
node_type (自 C++17 起) |
一个 节点句柄 的特化,表示一个容器节点 |
insert_return_type (自 C++17 起) |
描述插入 node_type 结果的类型,一个template<class Iter, class NodeType> |
[edit] 成员函数
构造 unordered_map (公有成员函数) | |
析构 unordered_map (公有成员函数) | |
将值分配给容器 (公有成员函数) | |
返回关联的分配器 (公有成员函数) | |
迭代器 | |
返回指向开头的迭代器 (公有成员函数) | |
返回指向结尾的迭代器 (公有成员函数) | |
容量 | |
检查容器是否为空 (公有成员函数) | |
返回元素数量 (公有成员函数) | |
返回最大可能的元素数量 (公有成员函数) | |
修饰符 | |
清除内容 (公有成员函数) | |
插入元素 或节点(自 C++17 起) (公有成员函数) | |
(C++23) |
插入一系列元素 (公有成员函数) |
(C++17) |
插入元素,如果键已存在,则分配给当前元素 (公有成员函数) |
在容器中就地构造元素 (公有成员函数) | |
使用提示在容器中就地构造元素 (公有成员函数) | |
(C++17) |
如果键不存在,则在容器中就地构造元素,如果键存在,则不执行任何操作 (公有成员函数) |
擦除元素 (公有成员函数) | |
交换容器的内容 (公有成员函数) | |
(C++17) |
从容器中提取节点 (公有成员函数) |
(C++17) |
从另一个容器中拼接节点 (公有成员函数) |
查找 | |
访问指定元素,并进行边界检查 (公有成员函数) | |
访问或插入指定元素 (公有成员函数) | |
返回与特定键匹配的元素数量 (公有成员函数) | |
查找具有特定键的元素 (公有成员函数) | |
(C++20) |
检查容器是否包含具有特定键的元素 (公有成员函数) |
返回与特定键匹配的元素范围 (公有成员函数) | |
桶接口 | |
返回指向指定桶开头的迭代器 (公有成员函数) | |
返回指向指定桶结尾的迭代器 (公有成员函数) | |
返回桶的数量 (公共成员函数) | |
返回最大桶数 (公共成员函数) | |
返回特定桶中的元素数量 (公共成员函数) | |
返回特定键的桶 (公共成员函数) | |
哈希策略 | |
返回每个桶的平均元素数 (公共成员函数) | |
管理每个桶的最大平均元素数 (公共成员函数) | |
保留至少指定的桶数,并重新生成哈希表 (公共成员函数) | |
为至少指定的元素数量保留空间,并重新生成哈希表 (公共成员函数) | |
观察者 | |
返回用于对键进行哈希处理的函数 (公共成员函数) | |
返回用于比较键是否相等的函数 (公共成员函数) |
[编辑] 非成员函数
(C++11)(C++11)(C++20 中已移除) |
比较无序映射中的值 (函数模板) |
专门化 std::swap 算法 (函数模板) | |
(C++20) |
擦除满足特定条件的所有元素 (函数模板) |
推断指南 |
(自 C++17 起) |
[编辑] 备注
特性测试 宏 | 值 | Std | 特性 |
---|---|---|---|
__cpp_lib_containers_ranges |
202202L | (C++23) | 容器的范围构造和插入 |
[编辑] 示例
#include <iostream> #include <string> #include <unordered_map> int main() { // Create an unordered_map of three strings (that map to strings) std::unordered_map<std::string, std::string> u = { {"RED", "#FF0000"}, {"GREEN", "#00FF00"}, {"BLUE", "#0000FF"} }; // Helper lambda function to print key-value pairs auto print_key_value = [](const auto& key, const auto& value) { std::cout << "Key:[" << key << "] Value:[" << value << "]\n"; }; std::cout << "Iterate and print key-value pairs of unordered_map, being\n" "explicit with their types:\n"; for (const std::pair<const std::string, std::string>& n : u) print_key_value(n.first, n.second); std::cout << "\nIterate and print key-value pairs using C++17 structured binding:\n"; for (const auto& [key, value] : u) print_key_value(key, value); // Add two new entries to the unordered_map u["BLACK"] = "#000000"; u["WHITE"] = "#FFFFFF"; std::cout << "\nOutput values by key:\n" "The HEX of color RED is:[" << u["RED"] << "]\n" "The HEX of color BLACK is:[" << u["BLACK"] << "]\n\n"; std::cout << "Use operator[] with non-existent key to insert a new key-value pair:\n"; print_key_value("new_key", u["new_key"]); std::cout << "\nIterate and print key-value pairs, using `auto`;\n" "new_key is now one of the keys in the map:\n"; for (const auto& n : u) print_key_value(n.first, n.second); }
可能的输出
Iterate and print key-value pairs of unordered_map, being explicit with their types: Key:[BLUE] Value:[#0000FF] Key:[GREEN] Value:[#00FF00] Key:[RED] Value:[#FF0000] Iterate and print key-value pairs using C++17 structured binding: Key:[BLUE] Value:[#0000FF] Key:[GREEN] Value:[#00FF00] Key:[RED] Value:[#FF0000] Output values by key: The HEX of color RED is:[#FF0000] The HEX of color BLACK is:[#000000] Use operator[] with non-existent key to insert a new key-value pair: Key:[new_key] Value:[] Iterate and print key-value pairs, using `auto`; new_key is now one of the keys in the map: Key:[new_key] Value:[] Key:[WHITE] Value:[#FFFFFF] Key:[BLACK] Value:[#000000] Key:[BLUE] Value:[#0000FF] Key:[GREEN] Value:[#00FF00] Key:[RED] Value:[#FF0000]
[编辑] 错误报告
以下行为更改的错误报告被追溯地应用于以前发布的 C++ 标准。
DR | 应用于 | 已发布的行为 | 正确的行为 |
---|---|---|---|
LWG 2050 | C++11 | reference 、const_reference 、pointer 和 const_pointer 的定义基于 allocator_type |
基于 value_type 和std::allocator_traits |
[编辑] 另请参见
(C++11) |
键值对集合,按键进行哈希处理 (类模板) |
键值对集合,按键排序,键是唯一的 (类模板) | |
(C++23) |
适配两个容器以提供键值对集合,按唯一键排序 (类模板) |