我试图弄清楚从 std::set 中擦除多个元素的复杂性。我使用这个页面作为来源。
它声称使用迭代器擦除单个项目的复杂性摊销为 O(1)，但使用范围形式擦除多个项目是 log(c.size()) + std::distance(first, last) （即 -集合大小的日志 + 删除元素的数量）。
从表面上看，如果要擦除的元素数 (n) 远小于集合中的元素数 (m)，这意味着循环遍历要擦除的元素并一次擦除它们会更快（O（n））而不是通过一次调用（O（log m）假设n <<m）擦除它们。
显然，如果真的是这样的话，第二种形式的内部实现只会执行上述循环。
这是网站的错误吗？规格中的错误？我只是错过了什么吗？
谢谢，沙查尔
集合的内部元素存储在平衡二叉树中。平衡树是任何节点的任何左右子树之间的最大高度差为 1 的树。
保持平衡的结构对于保证在树中（在集合中）的任何元素的搜索采取最坏情况下的O(log(n))步骤是很重要的。
移除元素可能会破坏平衡。要恢复平衡，必须进行旋转。在某些情况下，一次移除会导致多次旋转，以便操作采取O(log(n))步骤，但平均而言，移除需要O(1)步骤。
因此，当必须逐个删除分散在集合中的几个元素时，很有可能的摊销成本将是O(1) 每次删除。
删除范围内的几个元素（first, last，其中一个元素紧随其后）几乎肯定会破坏平衡，这是导致复杂性中的对数因素的原因：log(n) + std::distance(first, last)
似乎问题隐藏在“摊销”（有点狡猾）这个词的背后。单项擦除具有 log(c.size()) 的 O 复杂度，但 O(1) 的摊销复杂度。
因此，在循环中执行多个单次擦除将花费 log(c.size()) + 擦除次数，这正是范围形式的复杂性。
沙查尔