如何在 C++ 中找到存储在多重集的特定索引中的值? [英] How to find the value stored in a particular index of a multiset in C++?

问题描述

假设我有一个多重集 {1,3,5,7,9}.我想使用 C++ 找到这个多重集中的第三个元素是什么.如何在不使用循环的情况下做到这一点?

Assume I have a multiset as {1,3,5,7,9}. I want to find what is the 3rd element in this multiset using C++. How can I do that without using a loop?

推荐答案

多重集通常以树的形式实现，因此您必须逐个节点遍历它以按顺序找到特定节点.换句话说，无论您如何表达(循环或其他方式)，它都需要进行 N 次操作才能到达树中的第 N 项.

A multiset is normally implemented as a tree, so you have to traverse through it node by node to find a particular node in order. In other words, regardless of how you express it (loop or otherwise) it's going to take N operations to get to the N^th item in the tree.

如果您的兴趣纯粹是避免编写循环，您可以...使用类似的东西来掩饰它:

If your interest is purely in avoiding writing the loop, you can...disguise it by using something like:

auto p = mySet.begin();
std::advance(p, 2);

...但这只会隐藏 advance 内部的循环，而不是真正消除它.std::next 也可以完成这项工作，但(再次)只是隐藏了循环，并没有消除它.

...but that will only hide the loop inside of advance, not really eliminate it. std::next will do the job as well, but (again) just hides the loop, doesn't eliminate it.

虽然 std::set/std::multiset 没有提供它，如果你需要这样做很多，树的特殊变体支持在 O(log N) 时间内(O(N) 空间开销)查找 N^th 元素.

Although std::set/std::multiset don't provide it, if you need to do this a lot, there is specialized variant of a tree that supports finding the N^th element in O(log N) time (with O(N) space overhead).

与通常在树中的数据一起，在每个节点中，您存储该节点的子树中的元素数量.你首先通过从它自己的大小中减去它的左子树的大小来找到根的索引.如果您要查找的索引大于该值，则向右下降.如果小于，则向左下降(如果相等，则已找到要查找的节点).

Along with the data normally in the tree, in each node, you store the number of elements in that node's sub-trees. You start by finding the index of the root by subtracting the size of its left sub-tree from its own size. If the index you're looking for is greater than that, you descend to the right. If it's less, you descend to the left (and if its equal, you've found the node you're looking for).

当您下降时，您需要对您所在的位置进行计数.您已经计算出根的索引，因此将其保留在运行计数中.然后当您下降到一个节点时，如果您向右下降，则添加新节点左子树的 1 + 大小.如果向左下降，则减去 1 + 右子树的大小.

As you descend, you need to keep a running count of your location. You've already figured out the index of the root, so you keep that in the running count. Then when you descend into a node, if you're descending to the right you add the 1 + size of new node's left sub-tree. If you're descending to the left, you subtract 1 + size of right sub-tree.

为了保持计数，当您在任何时候通过一个节点向下插入时，您都会增加其计数(并且在您删除时，您会减少其计数——但只有在验证要删除的值存在之后).

To maintain the counts, as you're inserting anytime you descend through a node you increment its count (and as you're deleting, you decrement its count--but only after verifying that the value to be deleted was present).

如果您想搜索更多详细信息，这通常称为订单统计树".

If you want to search for more details, this is normally called an "order statistic tree".

这篇关于如何在 C++ 中找到存储在多重集的特定索引中的值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！