C++ 具名要求：无序关联容器(UnorderedAssociativeContainer) (C++11 起)
来自cppreference.com
无序关联容器 是提供基于键的快速对象查找的容器(Container) 。 最坏情况的复杂度为线性，但平均而言大多数操作则快得多。
无序关联容器基于以下各项参数化：Key；Hash，表现为 Key 上散列函数的散列(Hash) 函数对象；Pred，评估 Key 间的等价性的二元谓词(BinaryPredicate) 。 std::unordered_map 与 std::unordered_multimap 还拥有与 Key 关联的被映射类型 T。
如果两个 Key 按照 Pred 比较为相等，那么 Hash 必须对两个键返回相同值。
如果 | (C++20 起) |
std::unordered_map 与 std::unordered_set 能容纳至多一个带给定键的元素，而 std::unordered_multiset 与 std::unordered_multimap 能拥有带同一键的多个元素（它们在迭代时必然相邻）。
对于 std::unordered_set 和 std::unordered_multiset，它们的值类型与键类型相同，且 iterator 和 const_iterator 都是常量迭代器。对于 std::unordered_map 与 std::unordered_multimap，值类型是 std::pair<const Key, T>。
无序关联容器中的元素被组织到桶中，拥有相同散列值的键将归于相同的桶中。 桶数在容器大小增加时增加，以保持每个桶中的平均元素数在某个确定值之下。
重散列会使迭代器失效，并可能导致元素被重排到不同的桶中，但不会使元素的引用失效。
无序关联容器满足知分配器容器(AllocatorAwareContainer) 的要求。对于 std::unordered_map 与 std::unordered_multimap，知分配器容器(AllocatorAwareContainer) 中 value_type 的要求应用到 key_type 和 mapped_type（而非到 value_type）。
目录 |
[编辑]要求
凡例 | |
X | 无序关联容器类 |
| a | X 类型的值 |
| a2 | 一个与 X节点兼容 的类型的值 |
| b | 类型为 X 或 const X 的值 |
| a_uniq | X 支持唯一键时，X 类型的值 |
| a_eq | X 支持等价键时，X 类型的值 |
| a_tran | 当有限定标识符 X::key_equal::is_transparent 和 X::hasher::is_transparent 都有效且代表类型时， 为 |
| i, j | 引用 value_type 的输入迭代器 |
[i, j) | 合法范围 |
| rg(C++23 起) | R 类型的值，实现 container-compatible-range<value_type> |
| p, q2 | a 的合法常量迭代器 |
| q, q1 | a 的合法且可解引用的常量迭代器 |
| r | a 的合法且可解引用的迭代器 |
[q1, q2) | a 的合法范围 |
| il | std::initializer_list<value_type> 类型的值 |
| t | X::value_type 类型的值 |
| k | key_type 类型的值 |
| hf | hasher 或 const hasher 类型的值 |
| eq | key_equal 或 const key_equal 类型的值 |
| ke | 值，当 r1 和 r2 是 a_tran 的元素的键时，满足
|
| kx(C++23 起) | 值，当 r1 和 r2 是 a_tran 的元素的键时，满足
|
| n | size_type 类型的值 |
| z | float 类型的值 |
| nh(C++17 起) | X::node_type 类型的右值 |
[编辑]成员类型
| 名字 | 类型 | 要求 | 注解 |
|---|---|---|---|
X::key_type | Key | ||
X::mapped_type | T | 仅 std::unordered_map 和 std::unordered_multimap | |
X::value_type | Key | 仅 std::unordered_set 和 std::unordered_multiset。X可擦除(Erasable) | |
| std::pair<const Key, T> | 仅 std::unordered_map 和 std::unordered_multimap。X可擦除(Erasable) | ||
X::hasher | Hash | 散列(Hash) | |
X::key_equal | Pred | 可复制构造(CopyConstructible) ；接受两个 Key 类型的参数，并表达等价关系的二元谓词(BinaryPredicate) | |
X::local_iterator | 老式迭代器(LegacyIterator) | 具有和 X::iterator 相同的类别和类型 | 可用于遍历单个桶，但不能遍历所有桶 |
X::const_local_iterator | 老式迭代器(LegacyIterator) | 具有和 X::const_iterator 相同的类别和类型 | |
X::node_type(C++17 起) | node-handle 类模板的特化 | 其公开嵌套类型与 X 中的对应类型相同。 |
[编辑]成员函数和运算符
| 表达式 | 结果 | 前条件 | 效果 | 返回值 | 复杂度 |
|---|---|---|---|---|---|
| X(n, hf, eq) | 构造一个至少包含 n 个桶的空容器，使用 hf 作为散列函数，使用 eq 作为键相等性谓词 | O(n) | |||
| X(n, hf) | key_equal 满足可默认构造(DefaultConstructible) | 构造一个至少包含 n 个桶的空容器，使用 hf 作为散列函数，使用 key_equal() 作为键相等性谓词 | O(n) | ||
| X(n) | hasher 和 key_equal 满足可默认构造(DefaultConstructible) | 构造一个至少包含 n 个桶的空容器，使用 hasher() 作为散列函数，使用 key_equal() 作为键相等性谓词 | O(n) | ||
| X a = X(); X a; | hasher 和 key_equal 满足可默认构造(DefaultConstructible) | 构造一个具有未指定数量的桶的空容器，使用 hasher() 作为散列函数，使用 key_equal() 作为键相等性谓词 | 常数 | ||
| X(i, j, n, hf, eq) | value_type 满足从 *i可就位构造(EmplaceConstructible) 到 X | 构造一个至少具有 n 个桶的空容器，使用 hf 作为散列函数，使用 eq 作为键相等性谓词，并向其插入 [i, j) 的元素 | 平均 O(N)（N 为 std::distance(i, j)），最坏 O(N2) | ||
| X(i, j, n, hf) | key_equal 满足可默认构造(DefaultConstructible) 。value_type 满足从 *i可就位构造(EmplaceConstructible) 到 X | 构造一个至少具有 n 个桶的空容器，使用 hf 作为散列函数，使用 key_equal() 作为键相等性谓词，并向其插入 [i, j) 的元素 | 平均 O(N)（N 为 std::distance(i, j)），最坏 O(N2) | ||
| X(i, j, n) | hasher 和 key_equal 满足可默认构造(DefaultConstructible) 。value_type 满足从 *i可就位构造(EmplaceConstructible) 到 X | 构造一个至少具有 n 个桶的空容器，使用 hasher() 作为散列函数，使用 key_equal() 作为键相等性谓词，并向其插入 [i, j) 的元素 | 平均 O(N)（N 为 std::distance(i, j)），最坏 O(N2) | ||
| X(i, j) | hasher 和 key_equal 满足可默认构造(DefaultConstructible) 。value_type 满足从 *i可就位构造(EmplaceConstructible) 到 X | 构造一个未指定数量的桶的空容器，使用 hasher() 作为散列函数，使用 key_equal() 作为键相等性谓词，并向其插入 [i, j) 的元素 | 平均 O(N)（N 为 std::distance(i, j)），最坏 O(N2) | ||
| X(std::from_range, rg, n, hf, eq) (C++23 起) | value_type 满足从 *ranges::begin(rg)可就位构造(EmplaceConstructible) 到 X | 构造一个至少具有 n 个桶的空容器，使用 hf 作为散列函数，使用 eq 作为键相等性谓词，并向其插入 rg 的元素 | 平均 O(N)（N 为 std::distance(i, j)），最坏 O(N2) | ||
| X(std::from_range, rg, n, hf) (C++23 起) | key_equal 满足可默认构造(DefaultConstructible) 。value_type 满足从 *ranges::begin(rg)可就位构造(EmplaceConstructible) 到 X | 构造一个至少具有 n 个桶的空容器，使用 hf 作为散列函数，使用 key_equal() 作为键相等性谓词，并向其插入 rg 的元素 | 平均 O(N)（N 为 std::distance(i, j)），最坏 O(N2) | ||
| X(std::from_range, rg, n) (C++23 起) | hasher 和 key_equal 满足可默认构造(DefaultConstructible) 。value_type 满足从 *ranges::begin(rg)可就位构造(EmplaceConstructible) 到 X | 构造一个至少具有 n 个桶的空容器，使用 hasher() 作为散列函数，使用 key_equal() 作为键相等性谓词，并向其插入 rg 的元素 | 平均 O(N)（N 为 std::distance(i, j)），最坏 O(N2) | ||
| X(std::from_range, rg) (C++23 起) | hasher 和 key_equal 满足可默认构造(DefaultConstructible) 。value_type 满足从 *ranges::begin(rg)可就位构造(EmplaceConstructible) 到 X | 构造一个未指定数量的桶的空容器，使用 hasher() 作为散列函数，使用 key_equal() 作为键相等性谓词，并向其插入 rg 的元素 | 平均 O(N)（N 为 std::distance(i, j)），最坏 O(N2) | ||
| X(il) | X(il.begin(), il.end()) | ||||
| X(il, n) | X(il.begin(), il.end(), n) | ||||
| X(il, n, hf) | X(il.begin(), il.end(), n, hf) | ||||
| X(il, n, hf, eq) | X(il.begin(), il.end(), n, hf, eq) | ||||
| X(b) | 容器(Container) ；复制散列函数、谓词和最大负载因子 | 平均为与 b.size() 成线性，最坏 O(N2) | |||
| a = b | X& | 容器(Container) ；复制哈希函数、谓词和最大负载因子 | 平均为与 b.size() 成线性，最坏 O(N2) | ||
| a = il | X& | value_type 满足可复制插入(CopyInsertable) 到 X 且可复制赋值(CopyAssignable) | 使用 [il.begin(), il.end()) 赋值给 a。a 的所有元素都或被赋值或被销毁 | 平均为与 li.size() 成线性，最坏 O(N2) | |
| b.hash_function() | hasher | b 的散列函数 | 常数 | ||
| b.key_eq() | key_equal | b 的键相等性谓词 | 常数 | ||
| a_uniq.emplace(args) | std::pair< iterator, bool> | value_type 满足从 args可就位构造(EmplaceConstructible) 到 X | 当且仅当容器中不存在具有与 t 的键等价的键的元素时，插入一个使用 std::forward<Args>(args)... 构造的 value_type 类型的对象 t | 当且仅当发生插入时，返回的对偶的 bool 组分为 true，并且该对偶的迭代器组分指向具有的键等价于 t 的键的元素 | 平均 O(1)，最坏 O(a_uniq.size()) |
| a_eq.emplace(args) | iterator | value_type 满足从 args可就位构造(EmplaceConstructible) 到 X | 插入一个使用 std::forward<Args>(args)... 构造的 value_type 类型的对象 t | 指向新插入元素的迭代器 | 平均 O(1)，最坏 O(a_eq.size()) |
| a.emplace_hint(p, args) | iterator | value_type 满足从 args可就位构造(EmplaceConstructible) 到 X | a.emplace( std::forward<Args>(args)...) | 指向具有与新插入元素等价的键的元素的迭代器。const_iteratorp 是一个提示，指向搜索应该开始的位置。允许实现忽略提示 | 平均 O(1)，最坏 O(a.size()) |
| a_uniq.insert(t) | std::pair< iterator, bool> | 如果 t 是非 const 右值，则 value_type可移动插入(MoveInsertable) 到 X；否则，value_type可复制插入(CopyInsertable) 到 X | 当且仅当容器中不存在键与 t 的键相同的元素时，插入 t | 返回的对偶中的 bool 组分指示是否发生插入，而 iterator 组分则指向键与 t 的键等价的元素 | 平均 O(1)，最坏 O(a_uniq.size()) |
| a_eq.insert(t) | iterator | 如果 t 是非 const 右值，则 value_type可移动插入(MoveInsertable) 到 X；否则，value_type可复制插入(CopyInsertable) 到 X | 插入 t | 指向新插入元素的迭代器 | 平均 O(1)，最坏 O(a_eq.size()) |
| a.insert(p, t) | iterator | 如果 t 是非 const 右值，则 value_type可移动插入(MoveInsertable) 到 X；否则，value_type可复制插入(CopyInsertable) 到 X | a.insert(t)。迭代器 p 是一个提示，指向搜索应该开始的位置。允许实现忽略提示 | 指向键与 t 相等的元素的迭代器 | 平均 O(1)，最坏 O(a.size()) |
| a.insert(i, j) | void | value_type 满足从 *i可就位构造(EmplaceConstructible) 到 X，i 和 j 都不是 a 的迭代器 | 对于 [i, j) 中的每个元素 t，a.insert(t) | 平均 O(N)，其中 N 为 std::distance(i, j)，最坏 O(N·(a.size()+1)) | |
| a.insert_range(rg) (C++23 起) | void | value_type 满足从 *ranges::begin(rg)可就位构造(EmplaceConstructible) 到 X。rg 和 a 不重叠 | 对于 rg 中的每个元素 t，a.insert(t) | 平均 O(N)，其中 N 为 ranges::distance(rg)，最坏 O(N·(a.size()+1)) | |
| a.insert(il) | a.insert(il.begin(), il.end()) | ||||
| a_uniq.insert(nh) (C++17 起) | insert_return_type | nh 为空，或 a_uniq.get_allocator() | 如果 nh 为空，则无效。否则，当且仅当容器中不存在键等于 nh.key() 的元素时，插入 nh 拥有的元素。确保：如果 nh 为空，则 inserted 为 false，position 为 end()，并且 node 为空。否则，如果发生插入，则 inserted 为 true，position 指向插入的元素，而 node 为空；如果插入失败，则 inserted 为 false，node 具有 nh 的先前值，并且 position 指向键相当于 nh.key() 的元素 | 平均 O(1)，最坏 O(a_uniq.size()) | |
| a_eq.insert(nh) (C++17 起) | iterator | nh 为空，或 a_eq.get_allocator() | 如果 nh 为空，则无效并返回 a_eq.end()。否则，插入 nh 拥有的元素并返回指向新插入元素的迭代器。确保：nh 为空 | 平均 O(1)，最坏 O(a_eq.size()) | |
| a.insert(q, nh) (C++17 起) | iterator | nh 为空，或 a.get_allocator() | 如果 nh 为空，则无效并返回 a.end()。否则，当且仅当在具有唯一键的容器中不存在键等于 nh.key() 的元素时，插入 nh 拥有的元素；始终将 nh 拥有的元素插入具有相同键的容器中。迭代器 q 是一个提示，指向搜索应该开始的位置。允许实现忽略提示。确保：如果插入成功，nh 为空；如果插入失败，则保持不变 | 指向键等于 nh.key() 的元素的迭代器 | 平均 O(1)，最坏 O(a.size()) |
| a.extract(k) (C++17 起) | node_type | 移除容器中键等于 k 的元素 | 如果找到，则为拥有该元素的 node_type，否则为空 node_type | 平均 O(1)，最坏 O(a.size()) | |
| a_tran.extract(kx) (C++23 起) | node_type | 移除容器中键等于 kx 的元素 | 如果找到，则为拥有该元素的 node_type，否则为空 node_type | 平均 O(1)，最坏 O(a_tran.size()) | |
| a.extract(q) (C++17 起) | node_type | 移除 q 指向的元素 | 拥有该元素的 node_type | 平均 O(1)，最坏 O(a.size()) | |
| a.merge(a2) (C++17 起) | void | a.get_allocator() == a2.get_allocator() | a2} 中提取该元素}。确保：指代被传输 a2 元素的指针和引用仍指代相同的这些元素，但将作为 a 的成员。指代已传输元素的迭代器和指代 a 的所有迭代器都将失效，但指向 a2 中剩余元素的迭代器将保持有效 | 平均 O(N)，其中 N 为 a2.size()，最坏 O(N· (a.size()+1)) | |
| a.erase(k) | size_type | 擦除键等于 k 的所有元素 | 擦除的元素数量 | 平均 O(a.count(k))，最坏 O(a.size()) | |
| a_tran.erase(kx) (C++23 起) | size_type | 擦除键等于 kx 的所有元素 | 擦除的元素数量 | 平均 O(a_tran.count(kx))，最坏 O(a_tran.size()) | |
| a.erase(q) | iterator | 擦除 q 指向的元素 | 擦除之前，紧跟在 q 之后的迭代器 | 平均 O(1)，最坏 O(a.size()) | |
| a.erase(r) (C++17 起) | iterator | 擦除 r 指向的元素 | 擦除之前紧跟在 r 之后的迭代器 | 平均 O(1)，最坏 O(a.size()) | |
| a.erase(q1, q2) | iterator | 擦除范围 [q1, q2) 内的所有元素 | 擦除之前紧随所擦除元素的迭代器 | 平均为线性 std::distance(q1, q2)，最坏 O(a.size()) | |
| a.clear() | void | 擦除容器中的所有元素。确保：a.empty() 为 true | 与 a.size() 成线性 | ||
| b.find(k) | iterator；对于常量 b 为 const_iterator | 指向键等价于 k 的元素的迭代器，或当不存在这种元素时为 b.end() | 平均 O(1)，最坏 O(b.size()) | ||
| a_tran.find(ke) (C++17 起)? | iterator；对于常量 a_tran 为 const_iterator | 指向键等价于 ke 的元素的迭代器，或当不存在这种元素时为 a_tran.end() | 平均 O(1)，最坏 O(a_tran.size()) | ||
| b.count(k) | size_type | 键等于 k 的元素数量 | 平均 O(b.count(k))，最坏 O(b.size()) | ||
| a_tran.count(ke) (C++17 起)? | size_type | 键等于 ke 的元素数量 | 平均 O(a_tran.count(ke))，最坏 O(a_tran.size()) | ||
| b.contains(k) (C++20 起)? | b.find(k)!= b.end() | ||||
| a_tran.contains(ke) (C++20 起)? | a_tran.find(ke)!= a_tran.end() | ||||
| b.equal_range(k) | std::pair< iterator, iterator>; 对于常量 b 为 std::pair< | 包含键等于 k 的所有元素的范围。不存在这样的元素时返回 std::make_pair( | 平均 O(b.count(k))，最坏 O(b.size()) | ||
| a_tran.equal_range(ke) (C++20 起)? | std::pair< iterator, iterator>; 对于常量 a_tran 为 std::pair< | 包含键等于 ke 的所有元素的范围。不存在这样的元素时返回 std::make_pair( | 平均 O(a_tran.count(ke))，最坏 O(a_tran.size()) | ||
| b.bucket_count() | size_type | b 包含的桶数 | 常数 | ||
| b.max_bucket_count() | size_type | b 可以包含的存储桶数量的上限 | 常数 | ||
| b.bucket(k) | size_type | b.bucket_count()>0 | 如果存在任何具有等价于 k 的键的元素，则为在其中找到此类元素的桶的索引。返回值在 [0, b.bucket_count()) 中 | 常数 | |
| a_tran.bucket(ke) | size_type | a_tran. bucket_count()>0 | 如果存在任何具有等价于 ke 的键的元素，则为在其中找到此类元素的桶的索引。返回值必然在 [0, a_tran.bucket_count()) 范围内 | 常数 | |
| b.bucket_size(n) | size_type | n 在范围 [0, b.bucket_count()) 内 | nth 桶中的元素数量 | O(b.bucket_size(n)) | |
| b.begin(n) | local_iterator；对于常量 b 为 const_local_iterator | n 在范围 [0, b.bucket_count()) 内 | 指向桶中第一个元素的迭代器。如果桶是空的，则 b.begin(n)== b.end(n) | 常数 | |
| b.end(n) | local_iterator；对于常量 b 为 const_local_iterator | n 在范围 [0, b.bucket_count()) 内 | 迭代器，它是桶的末尾后值 | 常数 | |
| b.cbegin(n) | const_local_iterator | n 在范围 [0, b.bucket_count()) 内 | 指向桶中第一个元素的迭代器。如果桶是空的，则 b.cbegin(n)== b.cend(n) | 常数 | |
| b.cend(n) | const_local_iterator | n 在范围 [0, b.bucket_count()) 内 | 迭代器，它是桶的末尾后值 | 常数 | |
| b.load_factor() | float | 每个桶的平均元素数量 | 常数 | ||
| b.max_load_factor() | float | 容器尝试保持负载系数小于或等于的正数。容器根据需要自动增加桶的数量，以将负载系数保持在该数值以下 | 常数 | ||
| a.max_load_factor(z) | void | z 为正。可以使用 z 作为提示来更改容器的最大负载系数 | 常数 | ||
| a.rehash(n) | void | 保证： a.bucket_count()>= | 平均为与 a.size() 成线性，最坏 O(N2) | ||
| a.reserve(n) | a.rehash(std::ceil( n / a.max_load_factor())) |
| 本节未完成 原因：考虑成员函数的要求 |
[编辑]标准库
下列标准库容器均满足无序关联容器(UnorderedAssociativeContainer) ：
(C++11 起) | 唯一键的集合，按照键生成散列 (类模板) |
(C++11 起) | 键的集合，按照键生成散列 (类模板) |
(C++11 起) | 键值对的集合，按照键生成散列，键是唯一的 (类模板) |
(C++11 起) | 键值对的集合，按照键生成散列 (类模板) |
[编辑]缺陷报告
下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。
| 缺陷报告 | 应用于 | 出版时的行为 | 正确行为 |
|---|---|---|---|
| LWG 2156 | C++11 | 重散列后负载系数只能严格小于最大负载系数 | 可以等于最大负载系数 |
