[C] realloc vs liste

[Dani]

Spesso ho la necessità di avere un array dinamico, che dovrà contenere un numero di elementi sempre variabile.
Ci sono due soluzioni: si puo' creare un array di base e allargarlo attraverso la funzione realloc() prima dell'inserimento di un nuovo elemento, oppure usare le liste. Quale delle due soluzioni è preferibile e perchè ?

[targzeta]

Il vantaggio dell'array è quello di accedere ad uno qualsiasi dei suoi elemente a costo zero, mentre la lista, in generale, la devi scorrere. Se ad esempio vuoi modificare l'elemento centrale, con l'array lo fai immediatamente, mentre se hai una lista, prima devi ricercare l'elemento centrale, e poi puoi modificarlo. Per dirla in altre parole, non puoi applicare l'aritmetica dei puntatori ad una lista come invece faresti con un array.

Quindi dipende da cosa vuoi, la struttura dati che si adatta meglio la scopri solo così .

Per quanto riguarda la realloc(), non ti preoccupare, non è un grosso problema. Generalmente io uso (in pseudocodice):

Codice: Seleziona tutto

int size=X;
malloc(size);
if ( num_elementi == size )
  realloc(size*=2);
inserisci();


in questo modo, le chiamate alla realloc() sono relativamente poche, se scegli bene X.

Spina

[paolo86]

Dipende...

Se ti serve che gli elementi siano accessibili in modo casuale (quindi indicizzati),
allora non sbagli se usi un'array dinamico.

Se invece non hai bisogno di avere un accesso casuale le liste possono andare benissimo;
a volte sono anche meglio perché se per esempio vuoi mantenere ordinati gli elementi,
con le liste non hai molti problemi in quanto puoi aggiungere un elemento nella posizione
che preferisci impostando massimo due puntatori, mentre con l'array è un po' più ostico.

Io ti suggerisco le liste.

[Dani]

Per quanto riguarda la funzione realloc, nel caso in cui non fosse possibile allargare il blocco di memoria nel punto in cui è stato inizializzato cosa accadrebbe ? I dati verrebbero copiati automaticamente altrove, se possibile, o la funzione si limiterebbe a restituire NULL ?

[absinthe]

http://linux.die.net/man/3/realloc

realloc fino alla morte imho. ho sempre odiato le liste

M

[Blizzard]

http://linux.die.net/man/3/realloc

realloc fino alla morte imho. ho sempre odiato le liste

M

Le liste sono il bene

Pensa a quando devi riallocare grandi strutture! e non hai memoria contigua per farlo.
realloc se non sbaglio deve trovare un blocco adatto, copiare il vecchio contenuto e liberare la memoria.
La cosa comincia ad essere pesante.
Non si preoccupa neanche, come i vector<T> del C++ di allocare un po di memoria in più per eventuali ingrandimenti.

Le liste ti consentono elasticità, anche se devi costruire strutture parecchio complesse e con sistemi di indicizzazione e ordinamento particolari magari riesci anche a velocizzare le operazioni di accesso.

Il tutto dipende da quanto ti pesa un accesso O(n) rispetto ad O(1)

Gio

[Blizzard]

P.S.
sto scrivendo un tutorial su come creare/gestire una lista per contenere elementi ibridi.
Lo scopo ovviamente non è di base avere interi, float e gatti nella stessa lista ma avere una lista *quasi generica*. Se poi impastate le cose è colpa del programmatore