C++:在multiset迭代器中运行next()和prev()的时间？

Question

在相应的多集包含元素的类型对象上应用next()和prev()函数的时间复杂度是多少？multiset<int>::iteratorN

据我所知,在STL中,多集合被实现为一个平衡的二进制搜索树,因此我希望每次操作时的复杂度为O(log N)(在最坏的情况下),以防我们遍历树直到找到合适的价值,但我有预感,这应该是平均O(1).

但是,如果树实现如下 - 当x在平衡二叉搜索树中插入元素时,我们还可以检索树中小于x的最大数字,并且树中的最小数字大于xO(log N).因此在理论上,我们可以让树中的每个节点都保持指向它next和prev元素的指针next(),prev()然后在每个查询的恒定时间内运行.

什么人可以分享一些关于什么的光？

Answer 1

标准规定迭代器上的所有操作都以分摊的常量时间运行:http://www.eel.is/c++draft/iterator.requirements#general-10.基本思想是每个迭代器类别仅定义可以在摊销时间内实现的操作.

迭代是常见的事情,如果operator++在迭代器上(我猜这是你接下来的意思？)是logN,那么遍历循环中的容器将是NlogN.标准使这不可能; 因为operator++是摊销常数,所以迭代标准中的任何数据结构总是O(N).

但是,我挖到了multisetgcc5.4 的实现,至少有一个例子.二者set并multiset在相同的基本结构方面来实现,_Rb_tree.稍微研究一下这个结构,它的节点不仅有左右节点指针,还有父节点指针,而迭代器只是指向节点的指针.

给定二进制搜索树中包含指向其父节点的指针的节点,很容易弄清楚树中的下一个节点是什么:

1. 如果它有一个正确的孩子,则下降到正确的孩子.然后尽可能地让左孩子下降; 这是下一个节点.
2. 如果它没有正确的子项,则提升到您的父项,并确定原始节点是父项的左子项还是右项.如果节点是父节点的左子节点,则父节点是下一节点.如果节点是父节点的右侧,则父节点已经处理,因此您需要在父节点和祖父节点之间递归地应用相同的逻辑.

这个SO问题显示了核心逻辑的源代码:_/bit_stree.h中_Rb_tree_increment的定义是什么？(出于某种原因,很难找到它).

这没有恒定的时间,特别是在1和2中.我们有循环,可以下降或上升,并且最多可以占用log(N)时间.但是,您可以轻松地说服自己,摊销时间是不变的,因为当您使用此算法遍历树时,每个节点最多触摸4次:

1. 一旦到了左边的孩子的路上.
2. 一旦它从左边的孩子回来并需要考虑自己.
3. 一旦它下降到正确的孩子.
4. 一旦从正确的孩子上升.

回想起来,我会说这是一个相当明显的选择.迭代整个数据结构是一种常见的操作,因此性能非常重要.向节点添加第三个指针并不是一个微不足道的空间,但它也不是世界末日; 它最多会使数据结构膨胀3到4个字(2个指针+数据,这个对齐最少3个,3个指针+数据).如果你使用范围,而不是两个迭代器,另一种方法是维护一个堆栈然后你不需要父指针,但这只有从你从头到尾迭代时才有效.它不允许从中间到结尾的迭代器迭代(这也是BST的一个重要操作).