C++ 具名要求: UnorderedAssociativeContainer

来自cppreference.com
< cpp‎ | named req
 
 
 

无序关联容器是提供基于关键的快速对象查找的容器 (Container) 。最坏情况的复杂度为线性,但平均而言大多数操作更快。

无序关联容器为 Key 所参数化; Hash ,表现为 Key 上哈希函数的哈希 (Hash) 函数对象;而 Pred ,是求值 Key 间等价性的二元谓词 (BinaryPredicate) 。 std::unordered_mapstd::unordered_multimap 也拥有关联到 Key 的被映射类型 T

若二个 Key 按照 Pred 比较相等,则 Hash 必须对两个关键返回相同值。

Hash::transparent_key_equal 存在并指名类型,则 Hash::transparent_key_equal::is_transparent 必须合法且指名类型,而 Pred 必须是 Hash::transparent_key_equalstd::equal_to<Key> 之一(否则程序为病式)。

处于这种情况时,成员函数 findcontainscountequal_range 接受类型异于 Key 的参数,并期待可以那些类型的值调用 Hash ,以及 Hash::transparent_key_equal 是如 std::equal_to<> 的通透比较函数。

(C++20 起)

std::unordered_mapstd::unordered_set 能容纳至多一个有给定关键的元素,而 std::unordered_multisetstd::unordered_multimap 能拥有带同一关键的多个元素(它们在迭代时必须相邻)。

对于 std::unordered_setstd::unordered_multiset , value_type 与关键类型相同,而 iteratorconst_iterator 都是常迭代器。对于 std::unordered_mapstd::unordered_multimap , value_type 是 std::pair<const Key, T>

无序关联容器中的元素被组织到桶中,拥有相同哈希的关键将归结于相同的桶。桶数在容器大小增加时增加,以保持每个桶中的平均元素数在确定值之下。

重哈希非法化迭代器,并可能导致元素重排到不同的桶,但它不非法化到元素的引用。

无序关联容器满足具分配器容器 (AllocatorAwareContainer) 的要求。对于 std::unordered_mapstd::unordered_multimap具分配器容器 (AllocatorAwareContainer) 中 value_type 的要求应用到 key_typemapped_type (而非到 value_type )。

[编辑] 要求

用例

X 容器类型
a X 类型对象
b X 类型 const 对象
a_uniq X 支持唯一关键时 X 中的对象
a_eq X 支持多重关键时 X 中的对象
i, j 指代合法范围的输入迭代器 (LegacyInputIterator)
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_mapstd::unordered_multimap 编译时
X::value_type Key std::unordered_setstd::unordered_multiset 。于 X 可擦除 (Erasable) 编译时
X::value_type std::pair<const Key, T> std::unordered_mapstd::unordered_multimap 。于 X 可擦除 (Erasable) 编译时
X::hasher Hash 哈希 (Hash) 编译时
X::key_equal

Pred

(C++20 前)

Hash::transparent_key_equal 合法且指名类型则为它,否则为 Pred

(C++20 起)
接收二个 Key 类型参数并表达等价关系的二元谓词 (BinaryPredicate) 。 编译时
X::local_iterator 类别和类型与 X::iterator 相同的迭代器 (LegacyIterator) 能用于在单个桶上迭代 编译时
X::const_local_iterator 类别和类型与 X::const_iterator 相同的迭代器 (LegacyIterator) 能用于在单个桶上迭代 编译时
X(n,hf,eq) X hasherkey_equal 可复制构造 (CopyConstructible) 用给定的哈希函数和相等谓词,构造至少有 n 个桶的空容器 n 成线性
X(n,hf) X hasher 可复制构造 (CopyConstructible) , key_equal 可默认构造 (DefaultConstructible) 用给定的哈希函数并以 key_equal() 为相等谓词,构造至少有 n 个桶的空容器 n 成线性
X(n) X hasherkey_equal 可默认构造 (DefaultConstructible) hasher() 为哈希函数并以 key_equal() 为相等谓词构造,至少有 n 个桶的空容器 n 成线性
X() X hasherkey_equal 可默认构造 (DefaultConstructible) hasher() 为哈希函数并以 key_equal() 为相等谓词,构造有未指定桶数的空容器 常数
X(i,j,n,hf,eq) X hasherkey_equal 可默认构造 (CopyConstructible) , value_type*i 可原位构造 (EmplaceConstructible) 到 X 用给定的哈希函数和相等谓词,构造至少有 n 个桶的空容器,并插入来自 [i,j) 的元素到它。 平均线性,最坏平方(对 ij 间的的距离而言
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) 同上

[编辑] 标准库中的无序关联容器

(C++11 起)
唯一键的集合,按照键生成散列
(类模板) [编辑]
键的集合,按照键生成散列
(类模板) [编辑]
(C++11 起)
键值对的集合,按照键生成散列,键是唯一的
(类模板) [编辑]
键值对的集合,按照键生成散列
(类模板) [编辑]