C++ : Running time of next() and prev() in a multiset iterator?

Question

应用 next() 的时间复杂度是多少？和 prev() multiset<int>::iterator 上的函数类型对象，其中对应的多重集包含 N元素？

我知道在 STL 中，多重集被实现为平衡的二叉搜索树，因此我希望每次操作的时间复杂度为 O(log N)(在最坏的情况下)，以防我们只是遍历树直到我们找到合适的值，但我有预感这应该是平均 O(1)。

但是如果树的实现如下-插入元素时x在平衡二叉搜索树中，我们还可以检索到树中小于 x 的最大数和大于 x 的树中的最小数。在 O(log N) 中。因此理论上，我们可以让树中的每个节点都维护指向其next 的指针。和 prev元素，以便 next()和 prev()然后在每个查询中以恒定时间运行。

有人可以分享一下发生了什么吗？

Answer 1

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

迭代是很常见的事情，如果迭代器上的 operator++ (我猜这就是你的意思是下一个？)是 logN，那么在循环中遍历容器将是 NlogN。该标准使这成为不可能；由于 operator++ 是摊销常数，因此迭代标准中的任何数据结构总是 O(N)。

但是，我在 gcc5.4 上研究了 multiset 的实现，至少有一个例子。 set 和 multiset 都是根据相同的底层结构 _Rb_tree 实现的。深入研究一下这个结构，它的节点不仅有左右节点指针，还有父节点指针，而迭代器只是指向节点的指针。

给定二叉搜索树中包含指向其父节点的指针的节点，很容易找出树中的下一个节点是什么:

1. 如果它有一个右 child ，则下降到右 child 。然后尽可能下降左 child ；这是下一个节点。
2. 如果它没有右子节点，则上升到父节点，并确定原始节点是父节点的左子节点还是右子节点。如果节点是父节点的左子节点，则父节点是下一个节点。如果节点是父节点的右边，则父节点已经被处理，因此您需要在父节点与其祖父节点之间递归地应用相同的逻辑。

这个 SO 问题显示了具有核心逻辑的源代码:What is the definition of _Rb_tree_increment in bits/stl_tree.h? (由于某种原因很难找到)。

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

1. 曾经在它的左边 child 的路上。
2. 一旦它从左 child 那里回来，需要考虑自己。
3. 当它下降到它的右 child 时。
4. 从右 child 升序时一次。

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