stl映射的iterator ++复杂度 [英] iterator++ complexity for stl map

问题描述

stl RB-Tree(集合或映射)的迭代器++操作的复杂性是什么?我一直认为它们会使用索引，因此答案应该是O(1)，但是最近我阅读了vc10实现，震惊地发现它们没有.要在有序的RB-Tree中找到下一个元素，需要花费一些时间来搜索右子树中的最小元素，或者如果节点是左子节点且没有右子节点，则是右兄弟节点中的最小元素.这引入了递归过程，我相信++运算符需要O(lgn)时间.我对吗?所有的stl实现还是仅Visual C ++都是这种情况?

What's the complexity of iterator++ operation for stl RB-Tree(set or map)? I always thought they would use indices thus the answer should be O(1), but recently I read the vc10 implementation and shockly found that they did not. To find the next element in an ordered RB-Tree, it would take time to search the smallest element in the right subtree, or if the node is a left child and has no right child, the smallest element in the right sibling. This introduce a recursive process and I believe the ++ operator takes O(lgn) time. Am I right? And is this the case for all stl implementations or just visual C++?

维护RB-Tree的索引真的困难吗?只要我知道，通过在节点结构中保留两个额外的指针，我们就可以维护一个与RB-Tree一样的双向链接列表.他们为什么不这样做?

Is it really difficult to maintain indices for an RB-Tree? As long as I see, by holding two extra pointers in the node structure we can maintain a doubly linked list as long as the RB-Tree. Why don't they do that?

推荐答案

在整个容器上增加迭代器时，分摊的复杂度为每增量 O(1)，这是标准.没错，单个增量仅是 O(log n)，因为树的深度具有该复杂度等级.

The amortized complexity when incrementing the iterator over the whole container is O(1) per increment, which is all that's required by the standard. You're right that a single increment is only O(log n), since the depth of the tree has that complexity class.

在我看来， map 的其他RB树实现将是相似的.如您所说， operator ++ 的最坏情况下的复杂性可以改善，但代价并不小.

It seems likely to me that other RB-tree implementations of map will be similar. As you've said, the worst-case complexity for operator++ could be improved, but the cost isn't trivial.

链接列表可能会改善迭代整个容器的总时间，但是由于较大的节点结构往往会导致更多的高速缓存未命中，因此尚不确定.

It quite possible that the total time to iterate the whole container would be improved by the linked list, but it's not certain since bigger node structures tend to result in more cache misses.

这篇关于stl映射的iterator ++复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！