[C++] Consiglio rappresentazione di un grafo

[shodan]

https://baptiste-wicht.com/posts/201...r-vs-list.html
qui c'è una comparazione di list vs vector.

Che l'insert sia O(1) è una mezza bugia perché prima devi ottenere un'iteratore alla posizione che è un'operazione (in generale) O(n)

Ok, ma la ricerca dell'iteratore è O(n), l'inserimento in mezzo no, quello è O(1). Per testa/coda bastano due puntatori fissi a testa e coda per avere l'inserimento in O(1).

Non capito invece il discorso dell'O(1) amortizzato del vector, a me risulta che che sia O(1) nell'intervallo di esistenza (a meno che non ti riferisca a una possibile riallocazione interna).

[MItaly]

Non capito invece il discorso dell'O(1) amortizzato del vector, a me risulta che che sia O(1) nell'intervallo di esistenza (a meno che non ti riferisca a una possibile riallocazione interna).

In genere si parla di O(1) ammortizzato per la push_back di un vector perché è O(1) finché size() <= capacity(), mentre quando deve riallocare hai un O(n); il vector però ha una crescita della capacity esponenziale (ad ogni riallocazione si ha che capacity_nuova = k*capacity_vecchia, con k in genere attorno ad 1.5); la push_back "costosa" avviene una volta ogni k^n push_back, ergo si ha che in media una push_back è O(1 + n/k^n), che quindi è O(1) (l'esponenziale a denominatore uccide il termine lineare).

[Scara95]

Ok, ma la ricerca dell'iteratore è O(n), l'inserimento in mezzo no, quello è O(1). Per testa/coda bastano due puntatori fissi a testa e coda per avere l'inserimento in O(1).

Non ho mica detto che è una bugia, ho detto che è una mezza bugia. Quando vai a cercare qualcosa in mezzo di rado capita di avere già un iteratore bello e posizionato così dal nulla. L'inserimento è O(1), quando hai già la posizione, che è un dettaglio che molti si perdono. Era solo una precisazione e un invito a stare in guardia.