What's the complexity of map/set :: insert if one has provided a correct iterator hint?

Question

Is it O(1) or O(logN) but with a smaller coefficient?

If this is unspecified, I'd at least like to know the answer based on a reasonable supposition that the map/set is implemented using a red-black or AVL tree. The general algorithm to insert an element, I think, is something like:

• find the right place - O(logN)
• do the actual insertion - ?
• rebalance the tree if necessary - ?

Now if we provide the correct iterator hint, then the first step becomes O(1). Are the other steps also O(1) or O(logN)?

Answer 1

The standard doesn't say how the containers are to be implemented, so you can't count on an RB or a AVL tree. In practice... the complexity constraints are such that I don't know of any other implementations which would fit the bill. But it's in the complexity constraints that you will find the answer: “logarithmic in general, but amortized constant if t is inserted right before p.” So if the hint is correct, the implementation must be such that the insertion is O(1).

Answer 2

First standard never said exactly what kind of data structure it uses to implement set. It's just the complexity of operations on them which help us direct towards some sort of self-balanced binary search tree.

Yes, if you provide correct hint to insert by placing right iterator, then all steps would be amortized O(1) as step 2 and 3 and not dependent on anything.

Answer 3

• find the right place - O(logN)
• do the actual insertion - O(1), no matter if it is a AVL or RB tree
• rebalance the tree if necessary - I don't know the exact BIG-O notation for the AVL tree, but for a RB tree it is O(1).

With an iterator hint, the step #2 (insertion) and step #3 (rebalance) are not impacted. By providing an iterator, you're just doing the step #1 ("find the right place") by yourself, the general complexity is the same.