Aggiunta o eliminazione di elementi di una matrice dinamica

Il consenso di cui sono a conoscenza (conosco solo un paio di lingue, non tutte) è il seguente:

Se l'uso dell'array è piuttosto complesso, come nel caso dell'accesso multithread all'array, l'array viene inserito in una classe wrapper. La classe wrapper espone quindi la quantità minima necessaria di operazioni che possono essere eseguite sull'array.

Se l'uso è semplice e l'array viene utilizzato in modo sincrono, non importa fino a quando il codice ha un buon equilibrio in termini di prestazioni e leggibilità. Laddove tale equilibrio dipende dai requisiti, di solito è "Il più leggibile possibile pur essendo abbastanza veloce".

Ci sono molti modi per affrontarlo e ognuno ha vantaggi e svantaggi. Devi scegliere l'approccio giusto in base a come dovrebbe funzionare la struttura dei dati.

1. Usa accesso a thread singolo. Questo rimuove una vasta classe di problemi ma non è sempre fattibile. In particolare, se si salvano offset, iteratori, ecc., Possono essere invalidati anche da un singolo thread. Per esempio. salva l'indice 7, quindi elimina l'indice 4, ora l'elemento che era all'indice 7 è ora a 6. Questo può essere risolto refactoring il codice per funzionare meglio e in modo più coerente, ad esempio non cercando l'elemento finché non ne hai bisogno .

2. Controlla l'accesso all'array usando un meccanismo di blocco. Vuoi accedere o modificare l'array? Utilizzare un semaforo o un altro meccanismo per assicurarsi che solo un thread possa accedervi. Ciò è molto importante per garantire la sicurezza, ma non del tutto. Ha gli stessi potenziali bug a thread singolo del punto precedente.

3. Avvolge la matrice in una struttura dati sicura per i thread. Un esempio è un elenco copy-on-write . Ciò garantisce che le scritture di un thread (o riferimento) vengano viste solo dallo stesso riferimento all'oggetto. Il vantaggio è che due processi che modificano la stessa struttura non si sovrappongono alle dita degli altri, con l'ovvio inconveniente che diversi thread non possono realmente condividere i dati perché una volta che un thread modifica l'elenco, riceve la propria copia che ora non è sincronizzata con altri le discussioni.

4. Utilizza una struttura dati diversa. Ad esempio, una tabella hash che utilizza gli interi come chiavi funziona come un array, ma non ha il problema "Ho eliminato o inserito e spostato tutto". Questo può o non può essere appropriato per un determinato compito, ma può valerne la pena. Questa è anche una buona alternativa se hai bisogno di un array sparse .

Solo le convenzioni che conosco per le situazioni in cui hai un sacco di inserimento e cancellazione in una lista è di non usare un array.

Utilizza invece un elenco collegato o un albero binario. Queste strutture di dati sono fatte per l'inserimento e l'eliminazione.