如何找到在STL集合元素的秩为O（LOGN） [英] How to find rank of an element in stl set in O(logn)

问题描述

我想找到在STL集合元素的等级。我能够从一开始遍历该元素，并找出它的等级但正在为O（n）。有没有什么方法来查找在O（LOGN）的排名。

I want to find rank of an element in stl set. I am able to traverse from beginning to that element and find out its rank but that is taking O(n). Is there any method to find the rank in O(logn).

推荐答案

没有;平衡树并不需要存储的每个节点，这是需要更快速的计算距离（s.begin（），ITER）的后代的数量的std ::集合S 和迭代器 ITER （这是我想你的意思）。因此，信息根本就没有，除了由一个计数的项目之一存在。

No; a balanced tree does not need to store the number of descendants of each node, which is required to more quickly compute distance( s.begin(), iter ) for std::set s and iterator iter (which is what I suppose you mean). Therefore the information simply doesn't exist except by counting the items one by one.

如果您需要执行很多这样的计算，复制设置成排序，随机访问序列，例如向量或双端队列，但随后的序列的修改变得昂贵。

If you need to perform many such computations, copy the set into a sorted, random-access sequence such as vector or deque, but then modification of the sequence becomes expensive.

一个树数据结构，做你的要求可能存在于一个免费的图书馆的地方，但我不知道的人。

A tree data structure that does what you ask probably exists in a free library somewhere, but I don't know of one.

这篇关于如何找到在STL集合元素的秩为O（LOGN）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！