使用C++的STL进行订单统计

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)[为distance()[+ O(log(n)[for set::find()]).

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

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

Answer 1

我不认为使用标准库的容器是可行的,因为支持索引访问需要更改实现(向每个节点添加一个计数器).这会增加每个节点的大小.而C++的哲学是"不付你不用的东西".

如果你真的需要这个,那么有一个反向实现建议用于提升(它至少支持一些C++ 11特性),它们可以满足你的要求.

Answer 2

不。这是不可能的（使用预定义的容器）。C++ 标准库的序列容器具有：

• O(1) 随机访问和 O(N) 插入/删除或
• O(N) 随机访问和 O(1) 插入/删除

请注意，这deque是一个例外，但仅当插入/删除发生在数组末尾时才有效。一般情况仍然是 O(N)。

此外，迭代器的分类不包括这种情况的类别。您有双向迭代器（list、set、multiset和map的迭代器multimap），需要 O(N) 时间跳转到随机位置，下一类是随机访问迭代器（vector、deque和 的迭代器string）。没有中间类别。

添加一个新类别绝非易事。该库还实现了许多与for_each容器一起使用的算法（例如 ）。每个迭代器类别都有一个实现。

阶次统计树在Boost中已被多次提出。据我所知：

1. 2004年：第一个建议（不知道有没有实施）
2. 2006：“分层数据结构”
3. 2006：AVL Array（在Boost中更名为“Rank List”）
4. 2012：计数器树

它们被接受的主要困难是普遍认为它们不是好处，而是危险。今天的程序员习惯于使用典型的容器来解决他们所知道的所有问题。有经验的程序员担心新手可能会盲目地使用建议的容器来完成所有事情，而不是仔细选择。