STL Map中iterator++的复杂度是多少？

Question

6

stl RB-Tree(set或map)中的iterator++操作的复杂度是多少？

我一直认为它们会使用索引，因此答案应该是O(1)，但最近我阅读了vc10实现并惊讶地发现他们没有这样做。

要在有序的RB-Tree中查找下一个元素，需要花费时间搜索右子树中最小的元素，或者如果节点是左子节点且没有右子节点，则在右兄弟中搜索最小元素。这引入了一个递归过程，因此我认为++运算符需要花费O(lgn)的时间。

我的观点正确吗？所有stl实现都是这种情况还是只有visual C++？

维护RB-Tree的索引真的很难吗？只要在节点结构中保持两个额外指针，我们就可以像RB-Tree一样维护双向链表。他们为什么不这样做呢？

- user3351095

2

编译器实现者对他们的实现比我们能够做到的更加乐观，这是正确的。 - DumbCoder

1

这种问题不适合在Stack Overflow上提问。Stack Overflow明确不支持讨论或意见，而是针对主观事实的。也许在Stack Exchange网络中的另一个站点更适合这个问题。 - mah

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Steve Jessop · Accepted Answer

当遍历整个容器迭代器时，摊销复杂度为每次增量的 O(1)，这是标准所要求的。您是正确的，单个增量仅为 O(log n)，因为树的深度具有该复杂度类。

我认为其他 map 的红黑树实现可能会类似。正如您所说，operator++ 的最坏情况复杂度可以得到改进，但代价并不小。

使用链表可能会改善迭代整个容器的总时间，但这并不确定，因为更大的节点结构往往会导致更多的缓存未命中。