Implementazione vettoriale Pure C

5

Sto implementando un vettore in C. Lo sto facendo per il divertimento della programmazione, per il divertimento dell'apprendimento e per l'uso della struttura dei dati nei progetti successivi. Questo non è compito a casa. La mia domanda riguarda la metodologia, non necessariamente l'implementazione, quindi non sto davvero cercando una revisione del codice.

Ora ho letto molti esempi di implementazione e molti di loro prendono la dimensione di un singolo elemento come argomento per la funzione Vector_create() , e la usano per chiamate memmove() / memcpy() successive e cosa no e più o meno mantenere (per esempio) gli elementi del vettore nella memoria contigua. In altre parole, l'array sottostante è essenzialmente un singolo void* .

Nell'implementazione che ho scritto prima di osservare molto in che modo gli altri lo hanno fatto, autorizzo (forza) il codice client ad allocare un "oggetto" e a passarlo come puntatore alla funzione Vector_append() . Quindi il mio array sottostante è un void** . Quindi immagino che la vera domanda che sto ponendo sia se è sbagliato. Sbagliato come nelle migliori pratiche sbagliate.

Vedo che il modo "normale" per farlo non usa una schiera di puntatori e invece copia semplicemente la memoria di una struct (ad esempio) nell'array void* sottostante e mantenendo così i dati effettivi del elementi contigui, come accennato in precedenza. La mia strada evita un carico schifoso di memmove() / memcpy() perché copio solo i valori del puntatore, tuttavia, sto forzando il client a malloc() tutto ciò che viene inviato al vettore, e quindi faccio un sacco di avvitamenti sul mucchio.

Lungo queste linee, richiamo free() sull'elemento di dati sottostante quando l'elemento viene rimosso, quindi la libreria vettoriale fa un free() che la libreria vettoriale non ha mai fatto su malloc() originale. Anche questa è una cattiva pratica? L'unico problema che mi sembra di capire è se ci fosse una variabile membro (per mancanza di un termine migliore) che punti alla memoria dinamica all'interno della struttura. Diventa quindi la responsabilità del cliente a free() di quei dati, ma, di nuovo, la struttura stessa viene liberata dall'interno della chiamata della libreria vettoriale Vector_remove() .

    
posta isolier 31.07.2013 - 05:28
fonte

1 risposta

7

Sì, il design del tuo Vector è 'sbagliato'.

  • Un vettore di questo tipo viene solitamente considerato come un array resizable, con l'aspettativa associata che, come un array, contiene direttamente gli elementi. Il tuo requisito che Vector memorizza i puntatori agli elementi allocati interrompe tale aspettativa.
  • La memorizzazione dei puntatori è inefficiente se gli elementi da memorizzare sono piccoli (ad esempio, interi o doppi), perché il sovraccarico dell'allocazione dinamica diventa significativo (da 2 a 3 volte la dimensione dei dati) ed è necessario memorizzare sia il puntatore che i dati reali, in cui nella progettazione tradizionale, è necessario memorizzare solo pochi byte per i dati effettivi. Inoltre, nel design tradizionale, tutti gli elementi si trovano in posizioni di memoria adiacenti, il che rende gli schemi di accesso tipici (che si sovrappongono agli elementi) molto più cache-friendly per la CPU rispetto al progetto, in cui gli elementi sono sparsi nella memoria. / li>
  • A volte è necessario archiviare concettualmente gli oggetti in più contenitori. Con il design convenzionale, questo può essere sistemato memorizzando i puntatori nei contenitori e gestendo autonomamente gli oggetti reali. Questa tecnica può anche essere utilizzata per limitare la quantità di copie che è necessario eseguire, se l'utente del contenitore ritiene che sia un compromesso ragionevole. Con il tuo design, dovresti allocare dinamicamente i puntatori che vengono memorizzati nel contenitore, che è tutt'altro che conveniente e completamente contro-intuitivo per la maggior parte degli sviluppatori.
  • Qualsiasi interfaccia che richiede un puntatore alla memoria allocata è soggetta a un uso improprio, perché il compilatore non può vedere che Vector_append(&a) è un errore e che anche a un revisore umano non è immediatamente evidente. Se sei fortunato, questo viene rilevato durante i test, ma in alcuni casi non verrà rilevato per molto tempo.
  • Il fatto che Vector_remove() cancelli l'elemento di dati non si adatta anche alla maggior parte delle cerchie di sviluppo, perché
    • Molte linee guida di codifica richiedono che le corrispondenti chiamate malloc e free debbano essere fatte dallo stesso modulo. Il tuo design rende impossibile mantenere quel requisito.
    • È pratica comune creare, per strutture complesse che contengono puntatori alla memoria allocata, creare una coppia di funzioni 'costruttore' / 'distruttore' che si occupano di tutte le allocazioni / ripulitura in una volta, inclusa la 'radice' 'struct. Anche questo non funziona correttamente con Vector_remove chiamando free .
risposta data 31.07.2013 - 10:47
fonte

Leggi altre domande sui tag