我有这段代码:
unordered_multiset<int> t;
for (int i = 0; i < 1000000; i++) {
if (i % 10000 == 0)
cout << i << endl;
t.insert(10);
}
所以它只是在一个unordered_multiset
. 但是我发现我在哈希中的元素越多,这个工作的速度就越慢?我无法理解原因。在我看来,在应用哈希函数并找到相等元素的桶之后(因为所有相等的元素都组合在一起)stl 只需将它们放在桶的末尾。
那么这里有什么问题呢?
udp:我找到了 unordered_multiset::insert 函数的描述
单个元素插入:平均情况:常数。最坏的情况:容器大小呈线性关系。
所以现在的问题可以改写为:“为什么最坏的情况是线性的”