C++：多重集迭代器中 next() 和 prev() 的 运行 时间？
C++ : Running time of next() and prev() in a multiset iterator?
将 next() 和 prev() 函数应用于 multiset<int>::iterator 类型对象的时间复杂度是多少，其中对应的多重集包含 N 元素？
我知道在 STL 中，多重集被实现为平衡的二叉搜索树，因此我希望每次操作的时间复杂度为 O(log N)（在最坏的情况下），以防我们只是遍历树直到我们找到合适的值，但我有预感这应该是平均 O(1)。
但是如果这棵树是这样实现的呢——在平衡二叉搜索树中插入元素x的时候，我们也可以检索树中小于x的最大数和x中最小的数在 O(log N) 中大于 x 的树。因此理论上，我们可以让树中的每个节点都维护指向其 next 和 prev 元素的指针，以便 next() 和 prev() 然后 运行 在常数时间内每个查询。
任何人都可以分享一些情况吗？
标准要求迭代器上的所有操作 运行 在摊销常数时间内：http://www.eel.is/c++draft/iterator.requirements#general-10。基本思想是每个迭代器类别只定义可以在摊销时间内实现的操作。
迭代是一件很常见的事情，如果迭代器上的 operator++（我想这就是你接下来的意思？）是 logN，那么在循环中遍历容器就是 NlogN。该标准使这成为不可能；因为 operator++ 是摊销常数，所以迭代标准中的任何数据结构总是 O(N)。
然而，我深入研究了 multiset 在 gcc5.4 上的实现，至少有一个例子。 set 和 multiset 都是根据相同的底层结构 _Rb_tree 实现的。稍微研究一下这个结构，它的节点不仅有左节点指针和右节点指针，还有一个 parent 节点指针，而迭代器只是一个指向节点的指针。
给定一个包含指向其 parent 的指针的二叉搜索树中的节点，很容易找出树中的下一个节点是什么：
- 如果它有右边 child，请向右下降 child。然后尽可能向左 child 下降；那是下一个节点。
- 如果没有右child，上升到你的parent，判断原节点是parent的左还是右child .如果节点是parent的左边child，那么parent就是下一个节点。如果节点在parent的右边，那么parent已经处理过了，所以你需要在parent和它的grandparent之间递归应用相同的逻辑。
这个 SO 问题显示了具有核心逻辑的源代码：What is the definition of _Rb_tree_increment in bits/stl_tree.h?（由于某种原因很难找到）。
这没有恒定的时间，特别是在 1. 和 2 中。我们有下降或上升的循环，最多需要 log(N) 时间。然而，你可以很容易地相信摊销时间是常数，因为当你用这个算法遍历树时，每个节点最多被触及 4 次：
- 曾经在它左边的路上child。
- 有一次从左边回来child需要考虑自己
- 一次当它向右下降时child。
- 从右侧上升时一次child。
回想起来我会说这是 fairly-obvious 的选择。迭代整个数据结构是一个常见的操作，因此性能非常重要。向节点添加第三个指针并不是微不足道的 space，但它也不是世界末日；最多它会将数据结构从 3 个字膨胀到 4 个字（2 个指针 + 数据，对齐最少为 3 个，对比 3 个指针 + 数据）。如果您使用范围而不是两个迭代器，则另一种方法是维护一个堆栈，然后您不需要 parent 指针，但这仅在您从头到尾迭代时才有效；它不允许从中间的迭代器迭代到末尾（这也是 BST 的重要操作）。
我认为 next() 和 prev() 将取 1 和 h 之间的任何值，其中 h 是树的高度，大约为 O(log N)。如果你使用 next() 从头到尾遍历 N 个节点，迭代器应该访问整棵树，大约是 2N（2 因为迭代器必须向下遍历然后向上遍历 link节点）。总遍历不是 O(N * log N) 因为有些步骤比其他步骤更好。在最坏的情况下，next() 可能是从叶节点到头节点的 h 大约 O(log N)。但这只会发生两次（一次到达 begin()，第二次到达左树的最右边节点到头节点）。所以平均来说 next() 和 prev() 是 2 也就是 O(1).
将 next() 和 prev() 函数应用于 multiset<int>::iterator 类型对象的时间复杂度是多少，其中对应的多重集包含 N 元素？
我知道在 STL 中，多重集被实现为平衡的二叉搜索树，因此我希望每次操作的时间复杂度为 O(log N)（在最坏的情况下），以防我们只是遍历树直到我们找到合适的值，但我有预感这应该是平均 O(1)。
但是如果这棵树是这样实现的呢——在平衡二叉搜索树中插入元素x的时候，我们也可以检索树中小于x的最大数和x中最小的数在 O(log N) 中大于 x 的树。因此理论上，我们可以让树中的每个节点都维护指向其 next 和 prev 元素的指针，以便 next() 和 prev() 然后 运行 在常数时间内每个查询。
任何人都可以分享一些情况吗？
标准要求迭代器上的所有操作 运行 在摊销常数时间内：http://www.eel.is/c++draft/iterator.requirements#general-10。基本思想是每个迭代器类别只定义可以在摊销时间内实现的操作。
迭代是一件很常见的事情，如果迭代器上的 operator++（我想这就是你接下来的意思？）是 logN，那么在循环中遍历容器就是 NlogN。该标准使这成为不可能；因为 operator++ 是摊销常数，所以迭代标准中的任何数据结构总是 O(N)。
然而，我深入研究了 multiset 在 gcc5.4 上的实现，至少有一个例子。 set 和 multiset 都是根据相同的底层结构 _Rb_tree 实现的。稍微研究一下这个结构，它的节点不仅有左节点指针和右节点指针，还有一个 parent 节点指针，而迭代器只是一个指向节点的指针。
给定一个包含指向其 parent 的指针的二叉搜索树中的节点，很容易找出树中的下一个节点是什么：
- 如果它有右边 child，请向右下降 child。然后尽可能向左 child 下降；那是下一个节点。
- 如果没有右child，上升到你的parent，判断原节点是parent的左还是右child .如果节点是parent的左边child，那么parent就是下一个节点。如果节点在parent的右边，那么parent已经处理过了，所以你需要在parent和它的grandparent之间递归应用相同的逻辑。
这个 SO 问题显示了具有核心逻辑的源代码：What is the definition of _Rb_tree_increment in bits/stl_tree.h?（由于某种原因很难找到）。
这没有恒定的时间，特别是在 1. 和 2 中。我们有下降或上升的循环，最多需要 log(N) 时间。然而，你可以很容易地相信摊销时间是常数，因为当你用这个算法遍历树时，每个节点最多被触及 4 次：
- 曾经在它左边的路上child。
- 有一次从左边回来child需要考虑自己
- 一次当它向右下降时child。
- 从右侧上升时一次child。
回想起来我会说这是 fairly-obvious 的选择。迭代整个数据结构是一个常见的操作，因此性能非常重要。向节点添加第三个指针并不是微不足道的 space，但它也不是世界末日；最多它会将数据结构从 3 个字膨胀到 4 个字（2 个指针 + 数据，对齐最少为 3 个，对比 3 个指针 + 数据）。如果您使用范围而不是两个迭代器，则另一种方法是维护一个堆栈，然后您不需要 parent 指针，但这仅在您从头到尾迭代时才有效；它不允许从中间的迭代器迭代到末尾（这也是 BST 的重要操作）。
我认为 next() 和 prev() 将取 1 和 h 之间的任何值，其中 h 是树的高度，大约为 O(log N)。如果你使用 next() 从头到尾遍历 N 个节点，迭代器应该访问整棵树，大约是 2N（2 因为迭代器必须向下遍历然后向上遍历 link节点）。总遍历不是 O(N * log N) 因为有些步骤比其他步骤更好。在最坏的情况下，next() 可能是从叶节点到头节点的 h 大约 O(log N)。但这只会发生两次（一次到达 begin()，第二次到达左树的最右边节点到头节点）。所以平均来说 next() 和 prev() 是 2 也就是 O(1).