为什么 unordered_set 不提供数组访问运算符

Question

我很好奇为什么 STL 容器 unordered_set 对于随机访问平均具有恒定的时间复杂度，却没有提供一种方法来访问距离容器中第一个元素一定距离的元素.例如：

T& unordered_set::operator[](size_t index)
{
    return *(begin() + index);
}

Answer 1

unordered_set 根据定义是 无序的 ，因此通过索引访问它并不是很有用。任何特定元素的索引都可能在您进行插入时随时更改。

此外，根据 this reference，unordered_set 的迭代器是前向迭代器，而不是随机访问。

Answer 2

访问一个元素"by some distance"意味着有一些有意义的方法来测量该距离。 std::unordered_set 的问题在于，好吧，无序。因此，没有以非任意方式解释 "some distance from the beginning" 的有意义的方式。

如果要按距离访问，将数据复制到向量中：

std::vector tmp(unordered.begin(), unordered.end());

Answer 3

为了为项目成员检查提供恒定的摊销时间，这是无序集的优势，对于某些任意项目类型的一般情况，必须实施它作为散列 table.

不难保证，在常数时间内，散列table中的每个键（项）也被链表的节点引用。这提供了一种以未指定顺序迭代 table 中的项目的方法。但是，转到链表中的第 i 项是线性时间。

有一个折衷的解决方案，当每个项目被添加到哈希 table 时，它也被添加到排序树中。这要求项目具有可比性，并且它增加了对数的添加和删除复杂性（保持恒定的检查时间）。但是虽然这支持以对数时间访问第 i-th 项，但第 i-th 项会有所不同，而且确实存在对此功能的需求不大。

关键是 C++11 要求在无序容器中插入的平均时间为 O(1)，这与有序树不兼容。

因此，由于直接索引不切实际（线性时间）并且没有需求，因此不提供，但您始终可以使用 *std::next( s.begin(), i ) 作为假设的 s[i] 的线性时间替代方案。原则上，您可以通过将其复制到 std::vector 来针对不变的集合对其进行优化。但在大多数情况下，使用迭代器会更好。

Answer 4

unordered_set 实现为散列 table，其中有可随机访问的 "buckets"，每个有效地包含 0 个或更多元素的链表。因此，存储数字 1 到 7 的 unordered_set 的快照可能看起来像这样（元素的确切位置取决于所使用的哈希函数，因此这只是说明性的）：

buckets    linked-list of elements
[0]        1 --> 5 --> nullptr
[1]        nullptr
[2]        4 --> nullptr
[3]        nullptr
[4]        nullptr
[5]        7 --> nullptr
[6]        6 --> 3 --> 2 --> nullptr
[7]        nullptr

如您所见，没有简单的方法来推进 n 个元素...您基本上必须遵循链表，在找到 nullptr 时跳到下一个桶。这就是为什么 begin() 操作不能 return 具有 O(1) 次的随机访问迭代器 + n 移动（它只提供一个前向迭代器）...

所以当你问...

unordered_set, which has constant time complexity for random access on average

...我认为您混淆了按键随机访问和索引随机访问。您可以在 O(1) 摊销常数时间内找到任何给定的键，但找到第 n 个元素是 O(n)。

（注意：C++11 标准并没有让实现自由选择 closed hashing (aka open addressing) 来实现 unordered_set...从需要构造后的 max_load_factor 可以明显看出这一点为 1.0，并且在 insert/emplace 期间迭代器失效的规则只能在超过 max_load_factor 时发生。）

为什么 unordered_set 不提供数组访问运算符

Why doesn't unordered_set provide an array access operator

c++

stl

unordered-set