9

我想在 stl 集中找到一个元素的等级。我能够从头遍历到那个元素并找出它的等级，但这需要 O(n)。有什么方法可以在 O(logn) 中找到排名。

4

5 回答 5

6

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

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

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

于 2013-08-07T03:11:58.930 回答
4

您正在寻找的东西称为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. 有关更多示例，您可以查看此文件。

于 2013-08-09T06:34:11.157 回答
2

@Potatoswatter 建议的排序向量的功能由flat_setBoost.Container提供。该文档列出了以下权衡

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

如果您使用的是 GCC，实际上有一个内置的解决方案，但 Subhasis Das 的答案有些过时，并且由于更新而无法与较新版本的 GCC 一起使用。标题现在是

#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>。

这是按等级查找的演示：

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

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

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

    for(int i=24; i<=26; i++) std::cout << "Rank of " << i << ": " << s.order_of_key(i) << std::endl;
}
于 2019-12-07T07:20:38.250 回答
0

我认为 C++ 中的 STL 集中有一个 lower_bound 函数，它可以用来查找集合中元素的等级。看看https://www.geeksforgeeks.org/set-lower_bound-function-in-c-stl/。

于 2020-11-29T13:51:36.917 回答