std::unordered_set::erase 复杂性

Question

我不明白，为什么在最坏的情况下（其中 N 是元素数）有std::unordered_set O(N) 复杂度的擦除方法？标准 (n4296) 说明了所有三个版本的擦除方法在最坏情况下的复杂度为 O(a.size())（a是容器），并且仅使指向已擦除元素的迭代器无效，而不是所有迭代器（即重新散列不t 发生）。即使对于采用一个迭代器参数并且在平均情况下具有恒定复杂性的版本也是如此。我想是因为那抹version 返回一个迭代器到下一个元素，这需要找到擦除元素后的第一个非空桶，它给出了 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方法被调用时，它会寻找下一个非空的bucket，可以放在最后，即复杂度是O(a.bucket_count())，但是不是 O(a.size())。标准给出 O(a.size()) 复杂度的原因是什么？

Answer 1

即使对于采用一个迭代器参数并且在平均情况下具有恒定复杂性的版本也是如此。

无序关联容器具有前向迭代器——它们可以通过单向链表实现。

擦除节点涉及将它之前的节点重新链接到它之后的节点。O(N)在基于单链表的实现中找到迭代器指向的节点之前的节点可能是最坏的情况，因为您基本上必须遍历存储桶（在完全碰撞的情况下，它可以包含容器中的每个元素）。