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

Question

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

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

• 找到合适的地方 - O(logN)
• 做实际插入 - ？
• 必要时重新平衡树 - ？

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

Answer 1

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