我不明白，为什么在最坏的情况下（其中N是元素数），擦除std :: unordered_set O（N）复杂度的方法为何？Standard（n4296）表示在最坏的情况下（a为容器），这三种擦除方法的版本都具有O（a.size（））复杂度，并且仅使指向被擦除元素的迭代器无效，而不是使所有迭代器无效（即，重新哈希没有）发生）。即使对于使用一个迭代器参数并且在平均情况下具有恒定复杂度的版本，也是如此。我认为是因为擦除版本将迭代器返回到下一个元素，这需要在被擦除的元素之后找到第一个非空存储桶，这会带来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。将调用擦除方法时，它将查找下一个非空存储桶，该存储桶可以放在末尾，即复杂度为O（a.bucket_count（）），但是不是O（a.size（））。标准使O（a.size（））复杂性的原因是什么？
即使对于使用一个迭代器参数并且在平均情况下具有恒定复杂度的版本，也是如此。
无序关联容器具有正向迭代器-允许通过单个链接列表来实现它们。
擦除节点包括将其前面的节点重新链接到它之后的节点。O(N)在基于单链列表的实现中，在迭代器指向的节点之前找到节点可能是最坏的情况，因为您基本上必须遍历存储桶（在完全冲突的情况下，存储桶可以包含容器中的每个元素）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句