stl RB-Tree（set或map）的iterator ++操作的复杂性是什么？我一直认为它们会使用索引，因此答案应该是O（1），但是最近我阅读了vc10实现，震惊地发现它们没有。要在有序的RB-Tree中查找下一个元素，需要花费一些时间来搜索右侧子树中的最小元素，或者如果节点是左子节点且没有右子节点，则该节点将是右兄弟中的最小元素。这引入了递归过程，我相信++运算符需要O（lgn）时间。我对吗？所有的stl实现还是仅Visual C ++都是这种情况？
维护RB-Tree的索引真的困难吗？只要我看到，通过在节点结构中保留两个额外的指针，我们就可以维护一个与RB-Tree一样的双向链接列表。他们为什么不这样做呢？