将元素插入已排序数组并找到其索引的最有效方法

Question

我需要将一个元素插入到有序范围中，并且我还需要知道它的索引（小于该元素的范围内元素数量）。我想在 O(logN) 时间内完成此操作。我可以使用基本的 C++ 容器来做到这一点吗？

我考虑使用 std::multimap，因为这个容器能够以 O(logN) 的复杂度将元素插入到其正确的位置。但是，要获得索引，我需要调用 std::distance，这需要进行 O(N) 次操作，因为 multimap 迭代器不是随机访问的。

另一种方法是使用排序后的 std::vector 和 std::binary_search 算法。在这种情况下，搜索需要 O(logN) 的时间，但插入将需要 O(N) 次操作，因为向向量中间插入元素是线性操作。

所以，是否有 std/boost 容器可以用于实现此结果，或者我需要自己实现一个结构体？谢谢！

- ALEXANDER KONSTANTINOV

---

我对Boost MultiIndex的复杂性保证不是很了解，但你可以看一下。 - sehe

我猜使用自定义树/跳表实现是可能的，需要跟踪每个（内部）节点所表示的元素数量。但是您知道一旦插入另一个项，这样的索引就会失效吗？ - leemes

我们需要考虑的索引范围有多大？如果不是很大（几百万），您可以使用Fenwick树，这相当容易编码。否则，您可以编写一个平衡二叉树并记住每个子树中节点的数量。据我所知，标准容器在这里没有太大帮助。不过，我想知道Boost中是否有类似的东西。 - ead

{btsdaf} - phuclv

Answer 1

你可以使用 Boost.MultiIndex 的 有序索引:

Live Coliru Demo

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ranked_index.hpp>
#include <boost/multi_index/identity.hpp>

using namespace boost::multi_index;
using ranked_int_set=multi_index_container<
  int,
  indexed_by<
    ranked_unique<identity<int>>
  >
>;

#include <iostream>

int main()
{
  ranked_int_set s={0,2,4,6,8,10,12,14,16};

  auto it=s.insert(9).first;
  std::cout<<"9 was inserted at position #"<<s.rank(it)<<"\n";
  std::cout<<"14 is located at position #"<<s.find_rank(14)<<"\n";
}

输出

在位置#5插入了9
14位于位置#8

- Joaquín M López Muñoz

Answer 2

不行，我找过了。

有一种方法可以实现这个功能。从二叉树或跳表开始，并维护子树/跳的大小（需要一些额外开销--当插入项目时，您必须回溯到父项/跳并递增，删除也类似）。

然后，您可以在lg n时间内获得索引，在lg n时间内进行随机访问（按索引或偏移量），同时保持排序。

我尝试寻找一个预先编写的容器来完成此操作，但徒劳无功，该项目已被搁置，因此我没有时间写它。

完整的数据库可以用于此目的，对排序列进行索引，您可能能够快速获取少于指定数字的数量。

如果简单的线性排序向量不可行（由于其昂贵的中间插入），那么您可能需要考虑使用数据库。

作为一个看起来很有希望但失败的容器示例，Boost的MultiIndex容器允许您以多种方式索引容器，但顺序和有序索引是独立的。因此，您可以知道插入项目的顺序以及其在排序中的前后位置，但无法知道它在排序中的索引。

- Yakk - Adam Nevraumont

---

相关内容：https://stackoverflow.com/search?q=user%3A85371+multi_index_container+distance - sehe

从Boost 1.59开始，Boost.MultiIndex提供了[排名索引]（http://www.boost.org/libs/multi_index/doc/tutorial/indices.html#rnk_indices），完全适合这里的要求。 - Joaquín M López Muñoz

@joaq 哈哈！那是在我上次寻找它之后的2015年8月。 - Yakk - Adam Nevraumont