std :: unordered_multiset插入的复杂度

Question

为什么最差情况下std::unordered_multiset插入件的复杂度是线性的？我知道为什么会这样std::unordered_set（您必须检查插入的值不在集合中），但是对于多集我却不明白。我是否缺少明显的东西？

Answer 1

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

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

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

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

虽然unordered_set::insert()在插入过程中检查以防止重复，但unordered_multiset::insert()标识了插入元素的位置以进行等效键分组。在最坏的情况下，bucket 包含[5, 13]在插入 final 时13，并且在迭代所有元素时，bucket 包含[5, 13, 13]。当对所有元素进行迭代时，复杂度是线性的size()。

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