std::unordered_set::erase 复杂度

Question

我不明白，为什么 erase 方法的 std::unordered_set O(N) 复杂度最坏情况（其中 N 是元素数）？标准 (n4296) 说明了 erase 方法的所有三个版本在最坏情况下的复杂度为 O(a.size()) (a 是容器），并且仅使指向已删除元素的迭代器无效，而不是所有迭代器（即不会发生重新散列）。即使对于采用一个迭代器参数并且在一般情况下具有恒定复杂性的版本也是如此。我认为这是因为 erase 版本 returns 是下一个元素的迭代器，这需要在擦除元素之后找到第一个非空桶，它给出了 O(a.bucket_count()) 复杂度，但不是 O(a.size())!。元素的数量与桶的数量不成正比。例如：

#include <iostream>
#include <unordered_set>
using namespace std;

int main()
{
    std::unordered_set<int> aSet;
    aSet.insert ({125, 126});
    aSet.rehash (1000);
    cout << aSet.size() << endl;
    cout << aSet.bucket_count() << endl;
}

输出是

Size: 2
Bucket count: 1031

一个容器的大小只有2，bucket_count是1031。当调用erase方法时，会寻找下一个非空桶，可以放在最后，即复杂度为 O(a.bucket_count())，但不是 O(a.size())。标准给出 O(a.size()) 复杂度的原因是什么？

Answer 1

最明显的原因是退化的哈希函数可能对所有元素产生相同的值。结果他们都被分到同一个桶里。尽管不太可能，但即使使用相当好的哈希函数，同样的 也可能 发生，尤其是在将值映射到桶之后。由于对散列函数的质量没有合理的规范，因此标准无法规定更好的时间复杂度。

Answer 2

This is true even for a version which takes one iterator argument and have constant complexity in average case.

无序关联容器具有前向迭代器 - 它们允许通过单链表实现。

擦除节点涉及将它之前的节点重新链接到它之后的节点。在 singly-linked-list-based 实现中找到迭代器指向的节点之前的节点可以是 worst-case O(N)，因为你基本上必须遍历桶（它可以包含容器中的每个元素在完全碰撞的情况下）。

Answer 3

What is reason for which Standard gives O(a.size()) complexity?

std::unordered_set 是一个哈希容器。如果提供的散列函数为每个插入容器的元素映射到相同的值，那么它们将被链接在一起（大概在链表中）。所以在最坏的情况下，单个 'list' 可以包含容器中的所有项目，就像任何 'find' 操作一样，erase 是元素数量线性的最坏情况。

std::unordered_set::erase 复杂度

std::unordered_set::erase complexity

c++

c++11

stl

containers

unordered