C++ 概念: UnorderedAssociativeContainer
无序关联容器是提供基于关键的快速对象查找的容器 (Container
) 。最坏情况的复杂度为线性,但平均而言大多数操作更快。
无序关联容器为 Key
所参数化; Hash
,表现为 Key
上哈希函数的哈希 (Hash
) 函数对象;而 Pred
,是求值 Key
间等价性的二元谓词 (BinaryPredicate
) 。 std::unordered_map 与 std::unordered_multimap 也拥有关联到 Key
的被映射类型 T
。
若二个 Key
按照 Pred
比较相等,则 Hash
必须对两个关键返回相同值。
std::unordered_map 与 std::unordered_set 能容纳至多一个有给定关键的元素,而 std::unordered_multiset 与 std::unordered_multimap 能拥有带同一关键的多个元素(它们在迭代时必须相邻)。
对于 std::unordered_set 和 std::unordered_multiset , value_type 与关键类型相同,而 iterator 和 const_iterator 都是常迭代器。对于 std::unordered_map 与 std::unordered_multimap , value_type 是 std::pair<const Key, T> 。
无序关联容器中的元素被组织到桶中,拥有相同哈希的关键将归结于相同的桶。桶数在容器大小增加时增加,以保持每个桶中的平均元素数在确定值之下。
重哈希非法化迭代器,并可能导致元素重排到不同的桶,但它不非法化到元素的引用。
无序关联容器满足具分配器容器 (AllocatorAwareContainer
) 的要求。对于 std::unordered_map 与 std::unordered_multimap ,具分配器容器 (AllocatorAwareContainer
) 中 value_type
的要求应用到 key_type
和 mapped_type
(而非到 value_type
)。
[编辑] 要求
用例 | |
X
|
容器类型 |
a
|
X 类型对象
|
b
|
X 类型 const 对象
|
a_uniq
|
X 支持唯一关键时 X 中的对象
|
a_eq
|
X 支持多重关键时 X 中的对象
|
i , j
|
指代合法范围的输入迭代器 (InputIterator )
|
p , q2
|
指向 a 的合法 const_iterator
|
q , q1
|
指向 a 的指代合法范围的合法可解引用 const_iterator
|
il
|
std::initializer_list<X::value_type> 类型对象 |
t
|
X::value_type 类型对象
|
k
|
X::key_type 类型对象
|
hf
|
Object of type X::hasher 类型 const 对象
|
eq
|
X::key_equal 类型 const 对象
|
n
|
X::size_type 类型值
|
z
|
float 类型值 |
表达式 | 返回类型 | 前提/要求 | 后置/效果 | 复杂度 |
---|---|---|---|---|
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 ) |
编译时 | |
X::value_type | std::pair<const Key, T> | 仅 std::unordered_map 与 std::unordered_multimap 。于 X 可擦除 (Erasable ) |
编译时 | |
X::hasher | Hash |
哈希 (Hash ) |
编译时 | |
X::key_equal | Pred |
接收二个 Key 类型参数并表达等价关系的二元谓词 (BinaryPredicate ) 。 |
编译时 | |
X::local_iterator | 类别和类型与 X::iterator 相同的迭代器 (Iterator ) |
能用于在单个桶上迭代 | 编译时 | |
X::const_local_iterator | 类别和类型与 X::const_iterator 相同的迭代器 (Iterator ) |
能用于在单个桶上迭代 | 编译时 | |
X(n,hf,eq) | X |
hasher 与 key_equal 可复制构造 (CopyConstructible ) |
用给定的哈希函数和相等谓词,构造至少有 n 个桶的空容器 |
与 n 成线性
|
X(n,hf) | X |
hasher 可复制构造 (CopyConstructible ) , key_equal 可默认构造 (DefaultConstructible ) |
用给定的哈希函数并以 key_equal() 为相等谓词,构造至少有 n 个桶的空容器 |
与 n 成线性
|
X(n) | X |
hasher 与 key_equal 可默认构造 (DefaultConstructible ) |
以 hasher() 为哈希函数并以 key_equal() 为相等谓词构造,至少有 n 个桶的空容器 |
与 n 成线性
|
X() | X |
hasher 与 key_equal 可默认构造 (DefaultConstructible ) |
以 hasher() 为哈希函数并以 key_equal() 为相等谓词,构造有未指定桶数的空容器 |
常数 |
X(i,j,n,hf,eq) | X |
hasher 与 key_equal 可默认构造 (CopyConstructible ) , value_type 从 *i 可原位构造 (EmplaceConstructible ) 到 X |
用给定的哈希函数和相等谓词,构造至少有 n 个桶的空容器,并插入来自 [i,j) 的元素到它。 |
平均线性,最坏平方(对 i 与 j 间的的距离而言
|
X(i,j,n,hf) | X |
key_equal 可默认构造 (DefaultConstructible ) |
如上,有 eq=key_equal() | 同上 |
X(i,j,n) | X |
hasher 可默认构造 (DefaultConstructible ) |
如上,有 hf=hasher() | 同上 |
X(i,j) | X |
如上,拥有未指定的桶数 | 同上 | |
X(il) | X |
X(il.begin(),il.end() | 同上 | |
X(il,n) | X |
X(il.begin(),il.end(),n | 同上 | |
X(il,n,hf) | X |
X(il.begin(),il.end(),n,hf | 同上 | |
X(il,n,hf,eq) | X |
X(il.begin(),il.end(),n,hf,eq | 同上 | |
X(b) | X |
复制构造函数,亦复制哈希函数、谓词和最大加载因子 | 平均线性,最坏平方(就 b.size() 而言)
| |
a = b | X& |
复制赋值,亦复制哈希函数、谓词和最大加载因子 | 平均线性,最坏平方(就 b.size() 而言)
| |
a = il | X& |
value_type 可复制赋值 (CopyAssignable ) 且可复制插入 (CopyInsertable ) 到 X |
a = X(il) | 同上 |
本节未完成 原因:考虑成员函数的要求 |
[编辑] 标准库中的无序关联容器 (UnorderedAssociativeContainer)
(C++11 起) |
唯一键的集合,按照键生成散列 (类模板) |
(C++11 起) |
键的集合,按照键生成散列 (类模板) |
(C++11 起) |
键值对的集合,按照键生成散列,键是唯一的 (类模板) |
(C++11 起) |
键值对的集合,按照键生成散列 (类模板) |