c++ - 为什么 cppreference.com 没有列出无序容器的 insert() 的分摊时间复杂度？

Question

为什么 cppreference.com 会列出 vectors' push_back() 的分摊时间复杂度但是 unordered containers' insert() 的平均和最差时间复杂度？是否有不需要重新哈希的实现？

Answer 1

分摊的复杂性对于无序关联容器没有意义。

对于 vector ，特定插入的复杂性不取决于被插入元素的值，而仅取决于先前插入和删除的历史记录。因此可以计算摊销复杂度:插入 N 个元素，取整体复杂度并除以 N。其中一些插入非常快，而一些需要重新分配，即 O(size())。摊销复杂度是它们的平均值，不依赖于插入值的分布。

对于无序容器，复杂度可能取决于插入元素的值和容器中已经存在的元素的值。作为一种边缘情况，考虑一个 n 无序集合，其中所有元素的哈希值都相等，并且正在添加另一个具有相同哈希值的元素。该操作是 O(size()) 并且将始终保持 O(size())，无论您添加多少元素。 OTOH 如果插入的元素落入空桶中，则复杂度为 O(1)。在不知道插入值的分布的情况下，您无法对这些情况取平均值。