使用 C++ 的 STL 进行 i 阶统计

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

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

有什么办法可以同时进行这两个查询O(log(n))使用 C++ 的预定义容器？

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

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

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

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

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

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

阶次统计树已被提出于Boost http://boost.org几次。据我所知：

1. 2004: 第一个建议 http://lists.boost.org/Archives/boost/2004/03/62823.php（不知道有没有实现）
2. 2006: 《分层数据结构》 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html#tr.hierarchy.augment
3. 2006: AVL阵列 http://sourceforge.net/projects/avl-array（在Boost中更名为“排行榜”）
4. 2012: 计数器树 http://dl.dropbox.com/u/8437476/works/countertree/doc/index.html

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