如何在O（logn）中的stl中查找元素的排名

Question

我想在stl集合中查找元素的等级。我能够从头开始遍历该元素并找出其排名，但是这需要O（n）。有什么方法可以找到O（logn）中的排名。

Answer 1

不; 平衡树并不需要存储的每个节点，这是需要的后代的数量更快速地计算distance( s.begin(), iter )了std::set s和迭代器iter（这是我想你的意思）。因此，除非通过一项一项地计算项目，否则信息根本不存在。

如果您需要执行许多此类计算，请将 复制set到已排序的随机访问序列中，例如vector或deque，但随后修改序列会变得昂贵。

可以执行您要求的树数据结构可能存在于某处的免费图书馆中，但我不知道。