The most efficient way to insert an element into a sorted array and find its index

Question

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

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

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

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

Answer 1

You can use Boost.MultiIndex ranked indexes :

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

Answer 2

No. I was looking for him.

There is a way you can implement this. Start with a binary tree or skip list and save the subtree / skip size (a bit of extra overhead - when the elements are inserted, you need to go back to the parents / skip and increment, and similarly for deletions).

Then you can get indexes at lg n time, random access (by index or offset) at lg n time and save it at the same time.

My attempts to find a pre-written container that did this were fruitless, and the project was mothballed, so I did not write it.

You can use a full database with an indexed sorted column, and you could get a number less than reasonably fast.

Coefficients, if a simple linear sorted vector is not reasonable (with its expensive insert in the middle), you can generally consider the database.

As an example of a container that looks promising but failed, the Boost MultiIndex container allows you to index a container in several ways, but sequential and ordered indexes are independent. Thus, you can indicate which order you entered the item, and where it goes before / after in sorting, but not the index that it has in sorting.