命名空间
变体
操作

C++ 命名要求： UnorderedAssociativeContainer (自 C++11 起)

来自 cppreference.cn
 
C++
 
C++ 命名要求
 

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

无序关联容器由 Key、Hash（一个 Hash 函数对象，充当 Key 上的哈希函数）和 Pred（一个 BinaryPredicate，用于评估 Key 之间的等价性）参数化。std::unordered_map 和 std::unordered_multimap 还有一个与 Key 关联的映射类型 T。

如果根据 Pred 两个 Key 相等，则 Hash 必须为这两个键返回相同的值。

如果 Hash::is_transparent 和 Pred::is_transparent 都存在并且各自命名一个类型，则成员函数 find、contains、count、equal_range 和 bucket 接受类型不是 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>。

无序关联容器中的元素组织成桶，具有相同哈希值的键将最终在同一个桶中。当容器的大小增加时，桶的数量会增加，以保持每个桶中的平均元素数量低于某个值。

重新哈希会使迭代器失效，并可能导致元素在不同的桶中重新排列，但它不会使对元素的引用失效。

无序关联容器满足 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 满足以下条件的值
  • 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，

其中 r1 和 r2 是 a_tran 中元素的键

kx (自 C++23 起) 满足以下条件的值
  • 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，

其中 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；BinaryPredicate，它接受两个 Key 类型的参数并表达等价关系
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 就地构造 到 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 就地构造 到 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 就地构造 到 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 就地构造 到 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) 就地构造 到 X 中 构造一个至少有 n 个桶的空容器，使用 hf 作为哈希函数，eq 作为键相等谓词，并将来自 rg 的元素插入其中 平均情况 O(N)（N 是 ranges::distance(rg)），最坏情况 O(N2)
X(std::from_range,
  rg, n, hf)
(自 C++23 起) 		key_equal 是 DefaultConstructible。value_type 可从 *ranges::begin(rg) 就地构造 到 X 中 构造一个至少有 n 个桶的空容器，使用 hf 作为哈希函数，key_equal() 作为键相等谓词，并将来自 rg 的元素插入其中 平均情况 O(N)（N 是 ranges::distance(rg)），最坏情况 O(N2)
X(std::from_range,
  rg, n)
(自 C++23 起) 		hasher 和 key_equal 都是 DefaultConstructible。value_type 可从 *ranges::begin(rg) 就地构造 到 X 中 构造一个至少有 n 个桶的空容器，使用 hasher() 作为哈希函数，key_equal() 作为键相等谓词，并将来自 rg 的元素插入其中 平均情况 O(N)（N 是 ranges::distance(rg)），最坏情况 O(N2)
X(std::from_range,
  rg)
(自 C++23 起) 		hasher 和 key_equal 都是 DefaultConstructible。value_type 可从 *ranges::begin(rg) 就地构造 到 X 中 构造一个具有未指定数量的桶的空容器，使用 hasher() 作为哈希函数，key_equal() 作为键相等谓词，并将来自 rg 的元素插入其中 平均情况 O(N)（N 是 ranges::distance(rg)），最坏情况 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 可 复制插入 到 X 中，并且 可复制赋值 将范围 [il.begin(), il.end()) 赋值给 a。a 的所有现有元素要么被赋值，要么被销毁 平均情况线性于 il.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 就地构造 到 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 就地构造 到 X 中 插入使用 std::forward<Args>(args)... 构造的 value_type 对象 t 指向新插入元素的迭代器 平均情况 O(1)，最坏情况 O(a_eq.size())
a.emplace_hint(p, args) iterator value_type 可从 args 就地构造 到 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 返回的 pair 的 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 的迭代器 对每个元素执行 a.insert(t)
[i, j) 		平均情况 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 不变 指向键等价于 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 中的每个元素，并使用 a 的哈希函数和键相等谓词将其插入到 a 中。在具有唯一键的容器中，如果 a 中有一个元素的键等价于来自 a2 的元素的键，则不会从 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>;

std::pair<
  const_iterator,
  const_iterator> 对于常量 b

 包含所有键等价于 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>;

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

 包含所有键等价于 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()) 范围内 作为桶的 past-the-end 值的迭代器 常数
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()) 范围内 作为桶的 past-the-end 值的迭代器 常数
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()))
本节内容不完整
原因：关于成员函数的要求。

[编辑] 标准库

以下标准库容器满足 无序关联容器 (UnorderedAssociativeContainer) 的要求

(C++11)
 唯一键的集合，通过键哈希
(类模板) [编辑]
(C++11)
 键的集合，通过键哈希
(类模板) [编辑]
(C++11)
 键值对的集合，通过键哈希，键是唯一的
(类模板) [编辑]
(C++11)
 键值对的集合，通过键哈希
(类模板) [编辑]

[编辑] 缺陷报告

以下行为变更缺陷报告被追溯应用于之前发布的 C++ 标准。

DR 应用于 已发布行为 正确行为
LWG 2156 C++11 重新哈希后的负载因子可能只
严格低于最大负载因子		 允许等于
已从“https://cppreference.cn/mwiki/index.php?title=cpp/named_req/UnorderedAssociativeContainer&oldid=177778”检索