c++ - 使用 C++ 的 STL 进行第 i 个顺序统计

Question

给定一个空数组，我需要进行两种类型的查询

1. 在数组中插入一个元素

2. 查找某个元素的索引k(显然数组必须保持排序)

这可以通过使用 set 容器来完成

set<int> st;
set.insert(t);

这将在 O(log(n)) 中插入我的元素。

对于第二个查询

set<int>::iterator it;
it = st.find(k);
idx = distance(st.begin(), it);

这需要 O(n) 时间。 (O(n) [for distance()[ + O(log(n) [for set::find() ])。

有没有办法在 O(log(n)) 中使用预定义的 C++ 容器来执行这两个查询？

http://www.cplusplus.com/reference/stl/

Answer 1

我认为标准库的容器不可能做到这一点，因为支持按索引访问需要更改实现(为每个节点添加一个计数器)。这将增加每个节点的大小。而 C++ 的理念是“不要为不使用的东西付费”。

如果你真的需要这个，这里有 countertree为 boost 建议的实现(并且它至少支持一些 C++11 功能)满足您的要求。