stl映射的迭代器++复杂性

stl RB-Tree（set或map）的迭代器++操作的复杂性是什么？我一直以为他们会使用索引，因此答案应该是O（1），但最近我读了vc10的实现，并且震惊地发现他们没有。要在有序RB树中查找下一个元素，需要花时间搜索右侧子树中的最小元素，或者如果该节点是左侧子元素，并且没有右侧子元素（右侧子元素中的最小元素）。这引入了递归过程，我相信++运算符需要O（lgn）时间。我对不对？这是所有stl实现的情况还是只是visual C++？stl映射的迭代器++复杂性

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

来源

2014-02-25 user3351095

请不要咆哮。编译器实现者比他们的实现更为乐观，并且比我们以往任何时候都更加正确。 – DumbCoder

这种问题不适合堆栈溢出。堆栈溢出显然不利于讨论或意见，而是主观事实。也许堆栈交换网络中的另一个站点更适合这个问题。 – mah

递增迭代器遍历整个容器时的分期复杂度为每增量O(1)，这是标准所要求的。你说得对，单个增量只有O(log n)，因为树的深度有这个复杂等级。

我似乎很可能会发现map的其他RB树实现类似。正如你所说，operator++的最坏情况下的复杂性可以改善，但成本并不是微不足道的。

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

来源

2014-02-25 12:22:35

stl映射的迭代器++复杂性

回答

相关问题