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

Question

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

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

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

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

Answer 1

您可以使用 Boost.MultiIndex的 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 #514 is located at position #8