Il modo più efficace per inserire un elemento nell'array ordinato e trovare il suo indice

Question

Ho bisogno di inserire un elemento nell'intervallo ordinato, ma ho anche bisogno di conoscere il suo indice (numero di elementi nell'intervallo che sono inferiori all'elemento). Voglio farlo in tempo O (logN). Posso farlo con contenitori C++ di base?

Stavo pensando di utilizzare std :: multimap, con questo contenitore posso inserire l'elemento al suo posto con O (logN) complessità. Ma per ottenere l'indice, ho bisogno di chiamare std :: distance, che richiede operazioni O (N), poiché l'iteratore multimap non è un accesso casuale.

Un altro modo è quello di utilizzare ordinato std :: vector e std :: binary_search algoritmo. In questo caso la ricerca prende O (logN), ma l'inserimento richiederà operazioni O (N), poiché l'inserimento nel mezzo del vettore è un'operazione lineare.

Quindi, c'è un contenitore std/boost che posso utilizzare per raggiungere il risultato oppure devo implementare la mia propria struttura per questo? Grazie!

Answer 1

È possibile utilizzare 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"; 
} 

uscita

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

Answer 2

No. L'ho cercato.

Esiste un modo per implementarlo. Inizia con un albero binario o skip-list e mantieni la dimensione dei sottostrutture/salti (un po 'di overhead in più - quando gli articoli sono inseriti, devi tornare indietro ai genitori/salta e incrementare, e simili per le eliminazioni).

Quindi è possibile ottenere indici in lg n time, accesso casuale (per indice o offset) in lg n time e tenerlo ordinato allo stesso tempo.

I miei tentativi di trovare un contenitore pre-scritto che lo ha fatto sono stati infruttuosi, e il progetto era in scatola, quindi non sono riuscito a scriverlo.

Un database completo può essere utilizzato, con la colonna ordinata indicizzata, e si potrebbe essere in grado di ottenere il numero inferiore a quello ragionevolmente rapidamente.

Le probabilità sono che se un vettore lineare ordinato semplice non è ragionevole (con il suo costoso insert-in-middle), si potrebbe comunque voler considerare un database.

Come esempio di contenitore che sembra promettente ma non riuscito, il contenitore MultiIndex di Boost consente di indicizzare un contenitore in più modi, ma gli indici sequenziali e ordinati sono indipendenti. In questo modo puoi stabilire quale ordine hai inserito l'articolo e dove va prima/dopo in ordine, ma non l'indice che ha nell'ordinamento.