What is the complexity of map / set :: insert if you provided the correct iterator hint?

Question

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

If this is not indicated, I would at least like to know the answer based on a reasonable assumption that the map / set is implemented using red-black or AVL-tree. The general algorithm for inserting an element, I think, looks something like this:

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

Now, if we give the correct hint to the iterator, then the first step will be O (1). Are the other steps also O (1) or O (logN)?

Answer 1

The standard does not specify how containers should be implemented, so you cannot count on RB or the AVL tree. In practice ... the complexity of the constraint is such that I don’t know of any other implementations that would fit the bill. But this is due to the complexity constraints, which you will find the answer: "logarithmic in general, but amortized constant if t is inserted directly in front of p." Therefore, if the prompt is correct, the implementation should be such that the insert is O (1).

Answer 2

• find the right place - O (logN)
• do the actual installation - O (1), whether it is an AVL or RB tree
• if necessary, rebalance the tree - I do not know the exact BIG-O-notation for the AVL tree, but for the RB tree it is O (1).

With an iterator prompt, step 2 (insert) and step No. 3 (balancing) are not affected. By providing an iterator, you simply follow the first step (“find the right place”), the overall complexity remains the same.

Answer 3

The first standard never said exactly what data structure it uses to implement the set. It’s just the complexity of the operations on them that help us navigate some kind of self-balanced binary search tree.

Yes, if you provide the correct hint for insertion by placing the correct iterator, then all steps will be amortized by O (1) as steps 2 and 3 and will not depend on anything.