C++ 具名要求：无序关联容器 (UnorderedAssociativeContainer) (C++11 起)

来自cppreference.com
< cpp‎ | named req


 
C++
 
C++ 具名要求
 

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

无序关联容器基于以下各项参数化：Key；Hash，表现为 Key 上散列函数的散列 (Hash) 函数对象；Pred，评估 Key 间的等价性的二元谓词 (BinaryPredicate) 。 std::unordered_map 与 std::unordered_multimap 还拥有与 Key 关联的被映射类型 T。

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

若 Hash::is_transparent 与 Pred::is_transparent 均存在且均代表类型，则成员函数 find、contains、count 与 equal_range 接受异于 Key 的实参类型并期待 Hash 能以那些类型调用，而 Pred 是如 std::equal_to<> 的透明比较函数。

(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>。

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

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

无序关联容器满足知分配器容器 (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 都有效且代表类型时，

为 X 或 const X 类型的值

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 的元素的键时，满足
  • eq(r1, ke) == eq(ke, r1),
  • hf(r1) == hf(ke) 当 eq(r1, ke) 是 true，且
  • 如果 eq(r1, ke)、eq(r2, ke) 和 eq(r1, r2) 中有两个是 true，那么三个都是 true
kx (C++23 起) 值，当 r1 和 r2 是 a_tran 的元素的键时，满足
  • eq(r1, kx) == eq(kx, r1),
  • hf(r1) == hf(kx) 当 eq(r1, kx) 是 true，
  • 如果 eq(r1, kx)、eq(r2, kx) 和 eq(r1, r2) 中有两个是 true，那么三个都是 true 且
  • kx 不能转换到 iterator 或者 const_iterator
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 为空，或

a_uniq.get_allocator()
==
nh.get_allocator() 是 true

如果 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.get_allocator() 是 true

如果 nh 为空，则无效并返回 a_eq.end()。否则，插入 nh 拥有的元素并返回指向新插入元素的迭代器。确保：nh 为空 平均 O(1)，最坏 O(a_eq.size())
a.insert(q, nh)
(C++17 起) 		iterator nh 为空，或

a.get_allocator()
==
nh.get_allocator() 是 true

如果 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<
  const_iterator,
  const_iterator>

包含键等于 k 的所有元素的范围。不存在这样的元素时返回

std::make_pair(
  b.end(), b.end())

平均 O(b.count(k))，最坏 O(b.size())
a_tran.equal_range(ke)
(C++20 起)? 		std::pair<
  iterator,
  iterator>;

对于常量 a_tran 为 std::pair<
  const_iterator,
  const_iterator>

包含键等于 ke 的所有元素的范围。不存在这样的元素时返回

std::make_pair(
  a_tran.end(),
  a_tran.end())

平均 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() / a.max_load_factor() 且 a.bucket_count() >= n

平均为与 a.size() 成线性，最坏 O(N2)
a.reserve(n) a.rehash(std::ceil(
  n / a.max_load_factor()))
本节未完成
原因：考虑成员函数的要求

标准库中的无序关联容器

(C++11 起)
 唯一键的集合，按照键生成散列
(类模板)
(C++11 起)
 键的集合，按照键生成散列
(类模板)
(C++11 起)
 键值对的集合，按照键生成散列，键是唯一的
(类模板)
(C++11 起)
 键值对的集合，按照键生成散列
(类模板)
来自“https://zh.cppreference.com/mwiki/index.php?title=cpp/named_req/UnorderedAssociativeContainer&oldid=93013”