std :: set erase复杂度异常？

Question

我试图弄清楚从std :: set中删除多个元素的复杂性.我正在使用此页面作为来源.

它声称使用迭代器擦除单个项目的复杂性是分摊O(1),但使用范围形式擦除多个项目是log(c.size())+ std :: distance(first,last)(即 - 集合大小的日志+删除的元素数量).

从面值来看,如果要擦除的元素的数量(n)远小于集合(m)中的元素的数量,则这意味着在要擦除的元素上循环并且一次擦除它们的速度更快(O(n))比用一次调用擦除它们(假设n << m)为O(log m).

显然,如果真的如此,第二种形式的内部实现只会做上述循环.

这是网站上的错误吗？规格中的错误？我只是错过了一些东西吗？

谢谢,Shachar

Answer 1

集合的内部元素存储在平衡二叉树中。平衡树是任意节点的左右子树的最大高度差为1的树。

保持平衡的结构对于保证对树（集合中）的任何元素的搜索都采取最坏情况的O(log(n))步骤非常重要。

移除一个元素可能会破坏平衡。为了恢复平衡，必须进行旋转。在某些情况下，单次移除会导致多次旋转，因此操作需要采取O(log(n))步骤，但平均而言，移除需要采取O(1)步骤。

因此，当必须逐一删除分散在集合中的多个元素时，高概率的摊销成本将是每次O(1) 删除。

删除范围中的多个元素（first, last，其中一个元素跟随下一个元素）几乎肯定会破坏平衡，这会导致复杂性中的对数因子：log(n) + std::distance(first, last)

Answer 2

问题似乎隐藏在（有点狡猾的）“摊销”一词后面。单个项目擦除的复杂度为 O(c.size())，但摊余复杂度为 O(1)。

因此，在循环中执行多个单个擦除将花费 log(c.size()) + 擦除次数，这正是范围形式的复杂性。

沙查尔