std::unordered_set::erase复杂度

Question

我不理解为什么std :: unordered_set的erase方法在最坏情况下（其中N是元素数量）具有O（N）复杂度。标准（n4296）指出，所有三个版本的erase方法在最坏情况下具有O（a.size（））复杂度（a是容器），并且仅使指向已删除元素的迭代器无效，而不是所有迭代器（即重新哈希不会发生）。这甚至适用于使用一个迭代器参数且平均复杂度为常数的版本。我认为这是因为erase版本返回到下一个元素的迭代器，这需要查找已删除元素后第一个非空bucket，并且它给出了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())的复杂度？

- Denis

---

我认为现有的答案误解了问题。一个好的实现不必查找每个桶以查找要删除的元素，除了最坏的情况，即所有桶都已满。因此，除非a.bucket_count()与a.size()相同或更大，否则复杂度小于O(a.bucket_count())。 - kfx

O(bucket_count()) 部分是不正确的。请参见LWG 579。 - T.C.

Answer 1

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

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

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

- T.C.

Answer 2

最明显的原因是退化的哈希函数可能会为所有元素产生相同的值。结果，它们都将被排序到同一个桶中。虽然这种情况不太可能发生，但即使使用一个相当好的哈希函数，在将值映射到桶后，也可能发生相同的情况。由于哈希函数质量没有合理的规范，因此标准不能强制规定更好的时间复杂度。

- Dietmar Kühl

---

我认为，如果我们使用基于双向链表的实现方式，对于 erase(iterator) 而言，它完全可以达到常数复杂度。 - T.C.

Answer 3

为什么标准库中erase的时间复杂度是O(a.size())？

std::unordered_set是一个哈希容器。如果提供的哈希函数将每个插入到容器中的元素映射到相同的值，则它们将被链接在一起（可能是一个链表）。因此，在最坏的情况下，单个“列表”可能包含容器中的所有项目，并且像任何“查找”操作一样，erase的时间复杂度是线性的，与元素数量成正比。

- Daniel