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