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