命名空间
变体
操作

C++ 命名需求： 无序关联容器 (自 C++11 起)

来自 cppreference.com
 
C++
 
C++ 命名需求
 

无序关联容器是 容器s，它们根据键提供对对象的快速查找。最坏情况下的复杂度是线性的，但在大多数情况下，平均速度要快得多。

无序关联容器由 Key 参数化；Hash，一个 Hash 函数对象，它充当 Key 的哈希函数；以及 Pred，一个 二元谓词，评估 Key 之间的等价性。std::unordered_map 和 std::unordered_multimap 还具有与 Key 关联的映射类型 T。

如果两个 Key 根据 Pred 相等，则 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>.

无序关联容器中的元素被组织成桶，具有相同哈希值的键将位于同一个桶中。当容器的大小增加时，桶的数量也会增加，以使每个桶中的平均元素数量保持在一个特定值之下。

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

无序关联容器满足 分配器感知容器 的要求。对于 std::unordered_map 和 std::unordered_multimap，分配器感知容器 中 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 的值，该类型模拟 容器兼容范围<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 类型的右值

[edit] 成员类型

名称 类型 要求 说明
X::key_type 键
X::mapped_type T 仅限于 std::unordered_map 和 std::unordered_multimap
X::value_type 键 仅限于 std::unordered_set 和 std::unordered_multiset。 X 中的 可擦除
std::pair<const Key, T> 仅限于 std::unordered_map 和 std::unordered_multimap。 X 中的 可擦除
X::hasher 哈希 哈希
X::key_equal Pred 可复制构造； 二元谓词，它接受两个类型为 Key 的参数，并表达等价关系
X::local_iterator 传统迭代器 类别和类型与 X::iterator 相同 可用于遍历单个桶，但不能跨桶遍历
X::const_local_iterator 传统迭代器 类别和类型与 X::const_iterator 相同
X::node_type (自 C++17 起) node-handle 类模板的专用化 公共嵌套类型与 X 中的相应类型相同

[edit] 成员函数和运算符

表达式 结果 先决条件 效果 返回 复杂度
X(n, hf, eq) 使用 hf 作为哈希函数和 eq 作为键相等谓词构造一个至少具有 n 个桶的空容器 O(n)
X(n, hf) key_equal 是 可默认构造 使用 hf 作为哈希函数和 key_equal() 作为键相等谓词构造一个至少具有 n 个桶的空容器 O(n)
X(n) hasher 和 key_equal 是 可默认构造 使用 hasher() 作为哈希函数和 key_equal() 作为键相等谓词构造一个至少具有 n 个桶的空容器 O(n)
X a = X();
X a; 		hasher 和 key_equal 是 可默认构造 使用 hasher() 作为哈希函数和 key_equal() 作为键相等谓词构造一个具有未指定数量桶的空容器 常量
X(i, j, n, hf, eq) value_type 可从 *i 到 X 中 就地构造 使用 hf 作为哈希函数和 eq 作为键相等谓词构造一个至少具有 n 个桶的空容器，并将 [i, j) 中的元素插入其中 平均情况 O(N) (N 是 std::distance(i, j))，最坏情况 O(N2)
X(i, j, n, hf) key_equal 是 可默认构造。 value_type 可从 *i 到 X 中 就地构造 使用 hf 作为哈希函数和 key_equal() 作为键相等谓词构造一个至少具有 n 个桶的空容器，并将 [i, j) 中的元素插入其中 平均情况 O(N) (N 是 std::distance(i, j))，最坏情况 O(N2)
X(i, j, n) hasher 和 key_equal 是 可默认构造。 value_type 可从 *i 到 X 中 就地构造 使用 hasher() 作为哈希函数和 key_equal() 作为键相等谓词构造一个至少具有 n 个桶的空容器，并将 [i, j) 中的元素插入其中 平均情况 O(N) (N 是 std::distance(i, j))，最坏情况 O(N2)
X(i, j) hasher 和 key_equal 是 可默认构造。 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 中 就地构造 使用 hf 作为哈希函数和 eq 作为键相等谓词构造一个至少具有 n 个桶的空容器，并将 rg 中的元素插入其中 平均情况 O(N) (N 是 ranges::distance(rg))，最坏情况 O(N2)
X(std::from_range,
  rg, n, hf)
(自 C++23 起) 		key_equal 是 可默认构造。 value_type 可从 *ranges::begin(rg) 到 X 中 就地构造 使用 hf 作为哈希函数和 key_equal() 作为键相等谓词构造一个至少具有 n 个桶的空容器，并将 rg 中的元素插入其中 平均情况 O(N) (N 是 ranges::distance(rg))，最坏情况 O(N2)
X(std::from_range,
  rg, n)
(自 C++23 起) 		hasher 和 key_equal 是 DefaultConstructible。value_type 是 EmplaceConstructible 到 X 中，来自 *ranges::begin(rg) 使用至少 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 是 EmplaceConstructible 到 X 中，来自 *ranges::begin(rg) 使用不确定的桶数构造一个空容器，使用 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 是 CopyInsertable 到 X 中，并且是 CopyAssignable。 将范围 [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 是 EmplaceConstructible 到 X 中，来自 args 仅当容器中没有与 t 的键等效的键的元素时，才会插入一个使用 std::forward<Args>(args)... 构造的 value_type 对象 t。 返回的 pair 的 bool 分量仅当插入发生时才为 true，并且 pair 的迭代器分量指向与 t 的键等效的键的元素。 平均情况下时间复杂度为 O(1)，最坏情况下时间复杂度为 O(a_uniq.size())
a_eq.emplace(args) iterator value_type 是 EmplaceConstructible 到 X 中，来自 args 插入一个使用 std::forward<Args>(args)... 构造的 value_type 对象 t。 指向新插入元素的迭代器。 平均情况下时间复杂度为 O(1)，最坏情况下时间复杂度为 O(a_eq.size())
a.emplace_hint(p, args) iterator value_type 是 EmplaceConstructible 到 X 中，来自 args a.emplace(
  std::forward<Args>(args)...) 		指向与新插入元素的键等效的键的元素的迭代器。const_iterator p 是一个指向搜索应该开始位置的提示。实现可以忽略提示。 平均情况下时间复杂度为 O(1)，最坏情况下时间复杂度为 O(a.size())
a_uniq.insert(t) std::pair<
  iterator,
  bool> 		如果 t 是一个非常量右值，则 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 是一个非常量右值，则 value_type 是 MoveInsertable 到 X 中；否则，value_type 是 CopyInsertable 到 X 中。 插入 t。 指向新插入元素的迭代器。 平均情况下时间复杂度为 O(1)，最坏情况下时间复杂度为 O(a_eq.size())
a.insert(p, t) iterator 如果 t 是一个非常量右值，则 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 是 EmplaceConstructible 到 X 中，来自 *i。 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 是 EmplaceConstructible 到 X 中，来自 *ranges::begin(rg)。 rg 和 a 不重叠。 a.insert(t) 对于 rg 中的每个元素 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 中提取每个元素，并使用 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()) 中 第 n 个桶中的元素数量 O(b.bucket_size(n))
b.begin(n) local_iterator; const_local_iterator 对于常量 b n 在 [​0​, b.bucket_count()) 中 引用指向桶中第一个元素的迭代器。如果桶为空，则 b.begin(n) == b.end(n) 常量
b.end(n) local_iterator; const_local_iterator 对于常量 b 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)
 键值对的集合，按键散列
(类模板) [编辑]

[编辑] 缺陷报告

以下更改行为的缺陷报告已追溯应用于先前发布的 C++ 标准。

DR 应用于 已发布的行为 正确的行为
LWG 2156 C++11 重新散列后的负载因子只能
严格低于最大负载因子		 允许等于
从 "https://cppreference.cn/mwiki/index.php?title=cpp/named_req/UnorderedAssociativeContainer&oldid=177204" 获取