Struttura dati efficiente per inserimento

Question

Sto cercando una struttura dati (tipo array) che consenta l'inserimento rapido di valori (più rapidi di O (N)) nella struttura. La struttura dati deve essere in grado di stampare i suoi elementi nel modo in cui sono stati inseriti. Questo è simile a qualcosa come List.Insert() (che è troppo lento in quanto deve spostare ogni elemento), tranne che non ho bisogno di accesso casuale o cancellazione. L'inserimento sarà sempre all'interno della dimensione dell'array. Tutti i valori sono unici Non sono necessarie altre operazioni

Ad esempio, se Inserisci (x, i) inserisce il valore x all'indice i (indicizzazione 0). Poi:

• Inserisci (1, 0) dà {1}
• Inserisci (3, 1) dà {1,3}
• inserto (2, 1) dà {1,2,3}
• Inserisci (5, 0) dà {5,1,2,3}

Ed avrà bisogno di essere in grado di stampare {5,1,2,3} alla fine.

Sto usando C++.

Answer 1

Utilizzare skip list. Un'altra opzione dovrebbe essere tiered vector. L'elenco dei salti esegue inserimenti su const O (log (n)) e mantiene i numeri in ordine. Il vettore a livelli supporta l'inserimento in O (sqrt (n)) e di nuovo può stampare gli elementi in ordine.

EDIT: per il commento di Amit vi spiegherò come si fa a trovare l'elemento k-esimo in una skip list:

Per ogni elemento si dispone di una torre sul link ai prossimi elementi e per ogni collegamento si sa quanti elementi fa saltare sopra. Quindi, cercando l'elemento k-esimo, inizi con la testa dell'elenco e vai giù per la torre finché non trovi un collegamento che salta su non più di k elementi. Vai al nodo puntato da questo nodo e diminuisci k con il numero di elementi saltati sopra. Continuare a farlo fino ad avere k = 0.

Answer 2

Hai pensato di utilizzare std::map o std::vector?

È possibile utilizzare un std::map con il rango di inserimento come chiave. E vector ha una funzione membro reserve.

Answer 3

in C++ si può semplicemente utilizzare una mappa di vettori, in questo modo:

int main() { 
    map<int, vector<int> > data; 
    data[0].push_back(1); 
    data[1].push_back(3); 
    data[1].push_back(2); 
    data[0].push_back(5); 
    map<int, vector<int> >::iterator it; 
    for (it = data.begin(); it != data.end(); it++) { 
    vector<int> v = it->second; 
    for (int i = v.size() - 1; i >= 0; i--) { 
     cout << v[i] << ' '; 
    } 
    } 
    cout << '\n'; 
} 

Questo stampa:

5 1 2 3 

Proprio come vuoi tu, e gli inserimenti sono O (log n).

Answer 4

È possibile utilizzare una coppia std::map mappatura (indice, inserimento-tempo) su valori, dove il tempo di inserimento è un numero intero "autoincremento" (in termini SQL).L'ordinamento sulle coppie dovrebbe essere

(i, t) < (i*, t*) 

se e solo se

i < i* or t > t* 

in codice:

struct lt { 
    bool operator()(std::pair<size_t, size_t> const &x, 
        std::pair<size_t, size_t> const &y) 
    { 
     return x.first < y.first || x.second > y.second; 
    } 
}; 

typedef std::map<std::pair<size_t, size_t>, int, lt> array_like; 

void insert(array_like &a, int value, size_t i) 
{ 
    a[std::make_pair(i, a.size())] = value; 
} 

Answer 5

Per quanto riguarda il tuo commento:

List.Insert() (che è troppo lento perché deve spostare ogni elemento),

Gli elenchi non spostano i loro valori, li iterano su di essi per trovare la posizione che si desidera inserire, fare attenzione a ciò che si dice. Questo può confondere i neofiti come me.

Answer 6

Una soluzione che è inclusa in GCC per impostazione predefinita è la struttura di dati corda. Ecco lo documentation. Tipicamente, le corde vengono in mente quando si lavora con lunghe stringhe di caratteri. Qui abbiamo int s anziché caratteri, ma funziona allo stesso modo. Basta usare int come parametro del modello. (Potrebbe anche essere pair s, ecc.)

Ecco lo description of rope on Wikipedia.

In sostanza, si tratta di un albero binario che mantiene quanti elementi sono nelle sottostrutture sinistra e destra (o informazioni equivalenti, che è ciò che è indicato come statistiche d'ordine), e questi conteggi vengono aggiornati in modo appropriato come sottostrutture sono ruotati quando gli elementi sono inseriti e rimossi. Ciò consente operazioni O (lg n).