如何在O（logn）中设置的stl中查找元素的等级

Question

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

Answer 1

否；平衡树不需要存储每个节点的后代数目，这对于更快地为distance( s.begin(), iter )和迭代器std::set s计算iter是必需的（这是我想是您的意思）。因此，除了逐个计数项之外，信息根本不存在。

如果需要执行许多这样的计算，请将set复制到排序的随机访问序列中，例如vector或deque，但是对该序列的修改会变得很昂贵。

一种执行您要求的树数据结构可能存在于某个地方的免费库中，但我不知道该结构。

Answer 2

您正在寻找的被称为Order Statistic Tree。如果您使用的是GNU C ++库，则应该具有一个可用于构建订单统计树的扩展。下面是一个简短的示例：

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <cstdio>
using namespace std;
using namespace pb_ds;

typedef tree<
int, /* key type */
null_mapped_type, /* value type */
less<int>, /* comparison */
rb_tree_tag, /* for having an rb tree */
tree_order_statistics_node_update> order_set;

int main()
{
    order_set s;
    s.insert(10);
    s.insert(20);
    s.insert(50);
    s.insert(25);

    printf("rank of 25 = %d\n", s.order_of_key(25));
}

输出应为rank of 25 = 2。有关更多示例，请参见this file。

Answer 3

@ Potatoswatter建议的排序矢量的功能由flat_set中的flat_set提供。该文档列出了以下折衷方案

• 比标准关联容器更快的查找
• 比标准关联容器快得多的迭代
• 较小的对象（如果使用shrink_to_fit，则较大的对象）的内存消耗较少]
• 提高的缓存性能（数据存储在连续的内存中）
• 非稳定迭代器（插入和擦除元素时迭代器无效）
• 不可复制和不可移动的值类型无法存储
• 比标准关联容器更弱的异常安全性（在擦除和插入中移动值时，复制/移动构造函数可能会抛出）
• 比标准关联容器（特别是不可移动的类型）插入和擦除的速度慢

Answer 4

如果您使用的是GCC，实际上是一个内置的解决方案，但是Subhasis Das的答案有些过时了，由于更新，它不适用于较新版本的GCC。标头现在是

Boost.Container

并且集合结构为

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

或者，如果需要多重集，则可以用

typedef tree<
int, 
null_type, 
std::less<int>, 
rb_tree_tag, 
tree_order_statistics_node_update> ordered_set;

代替std::less<int>。

这是按等级查找的演示：

std::less_equal<int>