c++ - 如果提供了正确的迭代器提示，map/set :: insert 的复杂性是多少？

Question

是O(1)还是O(logN)但系数较小？

如果未指定，我至少想知道答案是基于一个合理的假设，即地图/集合是使用红黑或 AVL 树实现的。我认为插入元素的一般算法类似于：

• 找到正确的地方 - O(logN)
• 做实际插入 - ？
• 如有必要，重新平衡树 - ？

现在，如果我们提供正确的迭代器提示，那么第一步就变成了O(1)。其他步骤也是O(1)还是O(logN)？

Answer 1

该标准没有说明如何实现容器，因此您不能指望 RB 或 AVL 树。在实践中......复杂性限制使得我不知道任何其他适合该法案的实现。但是您会在复杂性约束中找到答案：“通常是对数，但如果 t 正好插入 p 之前，则为摊销常数。” 因此，如果提示是正确的，则实现必须使得插入为 O(1)。

Answer 2

• 找到正确的地方 - O(logN)
• 进行实际插入 - O(1)，无论它是 AVL 还是 RB 树
• 如有必要，重新平衡树 - 我不知道 AVL 树的确切 BIG-O 表示法，但对于 RB 树，它是O(1)。

使用迭代器提示，步骤#2（插入）和步骤#3（重新平衡）不受影响。通过提供迭代器，您只需自己执行步骤#1（“找到正确的位置”），一般复杂性是相同的。

Answer 3

第一个标准从未明确说明它使用哪种数据结构来实现集合。正是对它们的操作的复杂性帮助我们指向某种自平衡二叉搜索树。

是的，如果您通过放置正确的迭代器来提供正确的插入提示，那么所有步骤都将作为第 2 步和第 3 步摊销 O(1)，并且不依赖于任何东西。