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

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

您可以使用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";
}

输出

9 被插入到位置#5
14 位于位置#8