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

Think about it. What steps would you do if you were writing the insertion method? What steps would you do if you needed to rebalance the tree? Are the steps dependent on the number of nodes? — George Houpis, Dec 11 '14 at 14:44
Here's a bunch of answers that could be helpful: [stl-map-performance](http://stackoverflow.com/questions/10165708/stl-map-performance), [why-is-stdmap-implemented-as-red-black-tree](http://stackoverflow.com/questions/5288320/why-is-stdmap-implemented-as-red-black-tree), [difference-between-red-black-trees-and-avl-trees](http://stackoverflow.com/questions/16257761/difference-between-red-black-trees-and-avl-trees) — nouney, Dec 11 '14 at 14:48

score 5 · Accepted Answer · answered Dec 11 '14 at 15:48

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

Here is how this issue evolved from C++03 to C++11: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html — Howard Hinnant, Dec 11 '14 at 19:27

nouney · Answer 2 · 2014-12-11T15:40:16.737

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.

edited Dec 11 '14 at 15:40

answered Dec 11 '14 at 14:46

nouney

4,363
19
31

"complexity of that operation for a RB tree is O(1)." -- ? – n. m. could be an AI Dec 11 '14 at 15:36
1

Where do you get this complexity from? – n. m. could be an AI Dec 11 '14 at 15:46
@n.m. I get it from [here](http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948). – nouney Dec 11 '14 at 15:53
From your link: " (though it may have to examine O(log n) nodes to decide where the rotations are necessary)." – n. m. could be an AI Dec 11 '14 at 15:56
No worry, amortized complexity is O(1) anyway. – n. m. could be an AI Dec 12 '14 at 07:27

score 0 · Answer 3 · answered Dec 11 '14 at 14:46

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.

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

3 Answers3