C lunghezza stringa dinamica

Question

Esistono diversi modi per creare stringhe dinamiche in C (con una lunghezza che cambia costantemente). Dopo qualche ricerca su google, il modo principale per farlo è usare realloc().

Un modo in cui l'ho implementato è utilizzare elenchi collegati con 32 byte di blocchi per ogni nodo.

Mi chiedevo se ci sono modi migliori per affrontare questo oltre all'uso di liste realloc() e collegate, e quali sono i pro ei pro per ciascun metodo.

EDIT La ragione per cui sto facendo questo è perché sto ricevendo dati dinamici da un socket recv(), e stavo cercando un modo flessibile di riporlo, senza assegnazione di enormi quantità di dati che aren' t necessario.

Answer 1

È possibile riallocare a diverse dimensioni predefinite. Ad esempio, quando il buffer è pieno, raddoppiare le sue dimensioni.

L'utilizzo di un elenco collegato è una buona idea, ma i dati non sono continui (non è possibile passare l'intera struttura a printf, ad esempio) e l'indicizzazione richiede più calcoli (O (N)). Uno dei principali vantaggi è che le stringhe di accodamento (alle estremità) sono O (1).

Answer 2

Penso che stiate cercando Scatter-Gather I/O, la funzione che stavate cercando sarebbe readv().

Answer 3

Se si utilizza realloc(), non aggiungere una quantità costante di spazio su ogni realloc, poiché il costo di produzione di una stringa di lunghezza n sarà un O (n^2) (realloc probabilmente allocherà una nuova regione e copia i dati lì, cioè la sua complessità non è costante ma O (n)). Il modo più semplice per farlo è raddoppiare la dimensione del buffer su ogni realloc, quindi il costo ammortizzato sarà comunque O (n).

Answer 4

L'utilizzo di porzioni di 32 byte significa che il rapporto tra dati e sovraccarico è terribile: il puntatore si trova nell'elenco collegato e almeno (probabilmente molto di più) lo stesso di nuovo dall'allocatore di memoria. Suggerirei caldamente di allocare una parte molto più grande della memoria e farla crescere esponenzialmente per adattarla e vedere se questo causa problemi. Solo se incontri problemi dovrei seguire il percorso dell'elenco collegato.