14

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

  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)[对于set::find()] )。

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

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

4

3 回答 3

5

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

如果您真的需要这个，建议使用一个计数器树实现来满足您的要求（并且它至少支持一些 C++11 功能）。

于 2013-02-04T18:13:58.323 回答
4

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

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

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

此外，迭代器的分类不包括这种情况的类别。您有双向迭代器（ 、 、 和 的那些list）set，它们multiset需要O(N) 时间才能跳转到随机位置，下一个类别是随机访问迭代器（和的那些）。没有中间类别。mapmultimapvectordequestring

添加一个新类别一点也不简单。该库还实现了许多for_each适用于容器的算法（如 ）。每个迭代器类别都有一个实现。

顺序统计树已经在Boost上多次提出。据我所知：

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

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

于 2013-02-05T16:04:57.093 回答
0

尽管我同意在 C++ 中没有完全内置的方法来执行此操作，但有一个很好的解决方法：使用段树。让段树表示遇到的每个元素的频率。插入元素基本上是将计数更新 1，而查询只是从索引0到的段求和操作element - 1。这两个都可以在O(logn). 我知道缺点是您需要知道可以存在的元素数量，但在许多实际问题中，一个好的上限就足够了。

于 2016-12-24T13:56:23.707 回答