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

• 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.