我试图找出从 std::set 中删除多个元素的复杂性。我正在使用 this page作为来源。
它声称使用迭代器删除单个项目的复杂度是 O(1) 分摊的，但使用范围形式删除多个项目是 log(c.size()) + std::distance(first, last) (即 - 集合大小的日志 + 删除的元素数)。
从表面上看，如果要删除的元素数(n)远小于集合中的元素数(m)，这意味着循环遍历要删除的元素并一次删除它们时间更快 (O(n)) 比一次调用删除它们(O(log m) 假设 n< 显然，如果真的是这样的话，第二种形式的内部实现只会执行上述循环。 这是站点错误吗？规范中的错误？我只是错过了什么吗？ 谢谢，
沙查尔
最佳答案
集合的内部元素存储在平衡二叉树中。平衡树是任意节点的左右子树的最大高度差为1的树。
保持平衡的结构对于保证在最坏情况下搜索树中的任何元素(在集合中)很重要 O(log(n)) 步骤。
移除一个元素可能会破坏平衡。要恢复平衡，必须进行旋转。在某些情况下，一次删除会导致多次旋转，因此操作需要 O(log(n)) 步，但平均而言，一次删除需要 O(1) 步。
因此，当必须一个接一个地删除分散在集合中的多个元素时，每次删除的摊销成本很有可能是 O(1)。
删除范围内的几个元素(first, last，其中一个元素紧接着下一个元素)几乎肯定会破坏平衡，是什么导致了复杂度中的对数因子:log(n ) + std::distance(第一个，最后一个)
关于c++ - std::set 删除复杂性异常？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22143368/