c++ - std::unordered_multiset 插入的复杂性

Question

为什么std::unordered_multiset插入的最坏情况复杂度是线性的？我理解为什么会出现这种情况std::unordered_set（您必须检查插入的值不在集合中）但对于多集我不明白。我错过了一些明显的东西吗？

Answer 1

最坏情况的复杂度std::unordered_multiset::insert()是线性的，因为：

• 支持非唯一键的无序关联容器被称为支持等效键。在迭代这些容器时，具有等效键的元素在迭代中彼此相邻，形成等效键组。
• 迭代器函数需要恒定的摊销时间。

例如，考虑将5、13和13插入到unordered_multiset具有4存储桶的 an 中并unordered_multiset::key_eq(5, 13)返回的情况false。在这种情况下，为和unordered_multiset::hash_function(5)都返回不同的哈希码。尽管具有不同的哈希码，这些元素仍可能被插入到同一个桶中。如果一个整数的哈希函数返回整数本身，并且桶索引是哈希码模数桶数的结果，那么：513

• 元素5被散列到5，并且使用4桶，它被放置在桶中1。
• 元素13被散列到13，并且使用4桶，它也被放入桶1中。

在unordered_set::insert()插入期间检查以防止重复，unordered_multiset::insert()确定在哪里插入元素以进行等效键分组。在最坏的情况下，[5, 13]当插入 final 时，桶包含13，并且在遍历所有元素时，桶包含[5, 13, 13]。随着对所有元素的迭代发生，复杂性在 中是线性的size()。

值得注意的是，在 期间可能发生重新散列unordered_multiset::insert()，并且unordered_multiset::rehash()被指定为具有平均情况线性的复杂度，size()最坏情况是二次的。在重新哈希期间，原始哈希表中的所有元素都被迭代并插入到新的哈希表中。由于迭代具有线性 in 的复杂性size()，并且如上所述，每次插入都有线性 insize()的最坏情况，因此产生的最坏情况是O(size()*size())。