In risposta a veri e propri hotspot, a volte può essere utile un'ottimizzazione per applicare in particolare la terza soluzione che hai proposto che crea un insieme contiguo di elementi che vengono memorizzati per valore (es: numeri, non sotto-sequenze di dimensioni variabili come stringhe), e ancor più se la matrice risultante non ha bisogno di memorizzare tutti i dati della lista originale (alcuni campi potrebbero essere irrilevanti per l'uso successivo).
Per le sottosequenze di dimensioni variabili può essere utile talvolta anche trasferirle in un contenitore piatto, come std::vector<char> , con terminatori null per terminare una stringa da quella successiva se i modelli di accesso successivi e ripetitivi sono sequenziali. Oggi potrebbe non essere così utile che le stringhe utilizzino le SBO, ma c'è stato molto tempo fa, almeno nei casi in cui ciò è stato di enorme aiuto nei miei casi che implicava l'elaborazione ripetitiva di stringhe UTF8 per appiattire tutto su un'unica gigantesca serie di caratteri.
Detto questo, i casi in cui ho beneficiato di tali ottimizzazioni non hanno attraversato la struttura collegata (albero nel nostro caso) 2 o 3 volte. Era più o meno 100 volte al secondo, con i dati originali nella struttura collegata che non cambiavano molto frequentemente (non invalidando i dati memorizzati in una matrice contigua), e per di più ci permetteva di fare cose come l'elaborazione di SIMD con la matrice risultante mentre ripetutamente la si scorre attraverso.
Uno degli esempi più grandi che riesco a ricordare dove quella sorta di ottimizzazione era utile era una valutazione della gerarchia del moto. Per calcolare le matrici risultanti di matrici di bambini lungo una gerarchia, abbiamo dovuto attraversare la gerarchia del moto (albero) in ordine di larghezza / livello per trasferire movimenti da genitore a figlio. In questo caso, è stato molto utile incorniciare le velocità per afferrare una serie di elementi da quel livello - prima attraversamento e utilizzare quell'array in sequenza invece di attraversare l'albero più e più volte su ogni singolo fotogramma. In quel caso il movimento degli oggetti era dinamico e cambiava frequentemente, ma non la struttura dell'albero (molto raramente cambiata). E lo abbiamo fatto solo dopo aver visto gli hotspot e le cache mancanti in VTune.
Inoltre, come indicato, le strutture collegate non devono necessariamente comportare una perdita di località spaziale. Puoi anche scrivere elenchi collegati utilizzando array in cui gli elementi dell'array vengono memorizzati come un indice next a 32 bit per saltare alla parte successiva dell'array che memorizza l'elemento successivo e utilizzare come -1 al posto di nullptr . Ovviamente l'indice next per l'elemento 40 potrebbe saltare alla 35.000ª posizione dell'array se si inizia a inserire e rimuovere tutto il posto nel mezzo dell'elenco, ma è possibile ripristinare la località spaziale con una semplice copia passare che attraversa la lista originale usando quei collegamenti e quindi inserisce la nuova lista in ordine (nel qual caso tutti i nodi vicini si troverebbero uno accanto all'altro nella memoria / matrice nella nuova copia). Di solito uso quel rappresentante in questi giorni perché lo trovo molto meno ingombrante di dover gestire allocatori separati come le liste libere; in generale non mi piace gestire l'allocatore di memoria e la struttura dei dati come due cose distinte da trattare nell'uso se posso aiutarlo.
Finalmente ho potuto immaginare anche un caso in cui attraversare la lista una volta per copiare in array solo per attraversare la matrice una volta potrebbe essere utile se il lavoro svolto per iterazione è pesante e capace di essere fatto in parallelo. L'array, con il suo accesso casuale, consente a quel loop di essere parallelizzato, mentre l'attraversamento dell'elenco collegato è di natura seriale.