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_iterator p 是一个提示，指向搜索应该开始的位置。允许实现忽略提示
|
平均 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 为空，或
|
如果 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 为空，或
|
如果 nh 为空，则无效并返回 a_eq.end()。否则，插入 nh 拥有的元素并返回指向新插入元素的迭代器。确保：nh 为空
|
平均 O(1)，最坏 O(a_eq.size())
| |
a.insert(q, nh)(C++17 起) |
iterator
|
nh 为空，或
|
如果 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>;
对于常量 |
包含键等于 k 的所有元素的范围。不存在这样的元素时返回
|
平均 O(b.count(k))，最坏 O(b.size())
| ||
a_tran.equal_range(ke)(C++20 起)? |
std::pair<iterator,iterator>;
对于常量 |
包含键等于 ke 的所有元素的范围。不存在这样的元素时返回
|
平均 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.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 | 重散列后负载系数只能严格小于最大负载系数 | 可以等于最大负载系数 |