C++ 具名要求: UnorderedAssociativeContainer

来自cppreference.com
< cpp‎ | named req
 
 
 

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

无序关联容器基于以下各项参数化:KeyHash,表现为 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,其值类型与键类型相同,而 iteratorconst_iterator 都是常量迭代器。对于 std::unordered_mapstd::unordered_multimap,值类型是 std::pair<const Key, T>

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

重散列会使迭代器失效,并可能导致元素被重排到不同的桶中,但它不使元素的引用失效。

无序关联容器满足具分配器容器 (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 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 起)
键值对的集合,按照键生成散列,键是唯一的
(类模板) [编辑]
键值对的集合,按照键生成散列
(类模板) [编辑]