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

Question

为什么 std::unordered_multiset 插入的最坏情况复杂度是线性的？我明白为什么 std::unordered_set 会这样(你必须检查插入的值不在集合中)但对于 multiset 我不明白。我是否遗漏了一些明显的东西？

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() 确定在何处插入元素以进行等效键分组。在最坏的情况下，当插入最后一个 13 时，桶包含 [5, 13]，并且在遍历所有元素时，桶包含 [5, 13 , 13]。随着对所有元素的迭代，复杂度在 size() 中呈线性。

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