使用平衡的BST(例如AVL或Red-Black-Tree),我们可以轻松地维护一组值:
以上所有内容都可以很O(log N)
复杂地存档。
我的问题是,是否有STL容器以相同的复杂性支持上述所有3种操作?
我知道STL集/多集可用于1和2。我检查了基于_Rb_tree的容器映射/集/多集,但没有一个提供对3的支持。是否可以通过子类化ext / rb_tree来解决此问题?
您要查找的数据结构是一个顺序统计树,它是一个二进制搜索树,其中每个节点都存储以该节点为根的子树的大小。
这支持O(log n)中列出的所有操作。
在基于GNU政策的数据结构(GNU C ++的一部分)中存在一个顺序统计树。
代码看起来像这样:
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef
tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
set_t;
int main()
{
set_t s;
s.insert(12);
s.insert(50);
s.insert(30);
s.insert(20);
cout << "1st element: " << *s.find_by_order(1) << '\n'; // 20
cout << "Position of 30: " << s.order_of_key(30) << '\n'; // 2
return 0;
}
现场演示。
[从这个答案派生]
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句