Geek asks and answers

Iterator ++ complexity for stl map

What is the complexity of the iterator ++ operation for stl RB-Tree (set or map)? I always thought they would use indexes, so the answer should be O (1), but lately I read the vc10 implementation and was surprised to find that they did not. To find the next element in an ordered RB-Tree, it will take time to find the smallest element in the right subtree, or if node is a left child and does not have the right of a child, the smallest element in the right relationship. This leads to a recursive process, and I suppose the ++ operator takes O (lgn) time. I'm right? And in this case, for all implementations of stl or just visual C ++?

Is it really hard to maintain indexes for RB-Tree? As long as I see, holding two additional pointers in the node structure, we can maintain a doubly linked list, while RB-Tree. Why don't they do it?

+3
source share
1 answer

The amortized complexity of adding an iterator over the entire container is O(1)per step, which is a required standard. You are right that one increment is only O(log n)because the depth of the tree has this class of complexity.

It seems to me that other RB tree implementations mapwill be similar. As you said, the worst case complexity for operator++can be improved, but the cost is not trivial.

, , , node, , .

+3

More articles:


All Articles