stl映射的iterator ++复杂度

Question

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

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

Answer 1

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

在我看来，的其他RB树实现map将类似。正如您已经说过的那样，operator++可以改善最坏情况下的复杂性，但代价并不小。

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