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

Question

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

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

Answer 1

"通过一定距离"访问元素意味着有一些有意义的方法来测量该距离.麻烦的std::unordered_set是,这是无序的.因此,没有任何有意义的方式以非任意的方式解释"与起点有一定距离".

如果要按距离访问,请将数据复制到矢量中:

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

Answer 2

unordered_set实现为哈希表,其中存在随机可访问的"桶",其中每个桶实际上包含0个或更多个元素的链表.因此,unordered_set存储数字1到7 的快照可能看起来像这样(元素的确切位置取决于所使用的散列函数,所以这只是说明性的):

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()操作不能返回一个+ n移动O(1)次的随机访问迭代器(它只提供一个前向迭代器)....

所以当你问......

unordered_set,平均随机访问具有恒定的时间复杂度

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

(注意:C++ 11标准不会让实现自由选择封闭散列(也就是开放寻址)来实现unordered_set......这一点从max_load_factor后续构造中可以看出1.0,并且insert/ emplaceiterator invalidation 期间的规则只能max_load_factor超过时发生.)