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

Question

我需要将一个元素插入排序范围，但我还需要知道它的索引（范围内小于该元素的元素数）。我想在 O(logN) 时间内完成。我可以使用基本的 C++ 容器执行此操作吗？

我正在考虑使用 std::multimap，有了这个容器，我可以将元素插入到它的位置，复杂度为 O(logN)。但是要获取索引，我需要调用 std::distance，这需要 O(N) 操作，因为 multimap 迭代器不是随机访问。

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

那么，有没有 std/boost 容器可以用来达到结果，或者我需要为此实现自己的结构？谢谢！

Answer 1

没有。我找了。

有一种方法可以实现这一点。从二叉树或跳过列表开始，并保持 subtrees/skips 的大小（有点额外的开销——当插入项目时，您必须回溯到 parents/skips 并递增，和类似的删除）。

然后你可以在lg n 时间获取索引，在lg n 时间随机访问（通过索引或偏移量），同时保持排序。

我试图找到一个预先编写的容器来执行此操作但没有结果，而且该项目已被取消，所以我没有时间编写它。

可以使用完整的数据库，将排序列编入索引，您可能能够相当快地获得小于的数字。

如果简单的线性排序向量不合理（具有昂贵的中间插入），那么您可能还是要考虑数据库。

作为一个看起来很有前途但失败的容器示例，Boost 的 MultiIndex 容器允许您以多种方式索引容器，但顺序索引和有序索引是独立的。所以你可以知道你插入项目的顺序，以及它在排序中的位置 before/after，但不是它在排序中的索引。

Answer 2

您可以使用 Boost.MultiIndex's ranked indices:

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";
}

输出

9 was inserted at position #5
14 is located at position #8

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

Most efficient way to insert an element into sorted array and find its index

c++

algorithm

boost

binary-search

binary-search-tree