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

Question

I need to insert an element into sorted range, but I also need to know its index (number of elements in range that are less then the element). I want to do this in O(logN) time. Can I do this with basic C++ containers?

I was thinking to use std::multimap, with this container I can insert the element into its place with O(logN) complexity. But to get the index, I need to call std::distance, which takes O(N) operations, since multimap iterator is not random access.

Another way is to use sorted std::vector and std::binary_search algorithm. In this case the search takes O(logN), but the insertion will take O(N) operations, since the insertion to the middle of vector is linear operation.

So, is there std/boost container that I can use to reach the result, or I need to implement my own struct for this? Thanks!

Answer 1

You can use 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";
}

Output

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