C++ STL容器适合在动态有序列表中查找第n个元素？

Question

使用平衡的BST,如AVL或Red-Black-Tree,我们可以轻松维护一组值:

1. 插入/删除/查询给定值.
2. 计算小于/大于给定值的元素.
3. 排序后找到排名为k的元素.

以上所有内容都可以O(log N)复杂化存档.

我的问题是,是否有任何STL容器以相同的复杂性支持上述所有3个操作？

我知道STL set/multiset可以用于1和2.我检查了基于_Rb_tree的容器map/set/multiset,但没有提供对3的支持.有没有办法子类化ext/rb_tree来解决这个问题？

Answer 1

您要查找的数据结构是顺序统计树，它是二叉搜索树，其中每个节点存储以该节点为根的子树的大小。

这支持 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;
}

现场演示。

^{[源自这个答案]}