Repository 32bit  Forum
Repository 64bit  Wiki

[C] realloc vs liste

Forum dedicato alla programmazione.

Moderatore: Staff

Regole del forum
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.

La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.

[C] realloc vs liste

Messaggioda Dani » gio ott 02, 2008 18:04

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è ?
Dani
Linux 3.x
Linux 3.x
 
Messaggi: 1447
Iscritto il: mer apr 26, 2006 0:52
Desktop: gnome
Distribuzione: arch

Re: [C] realloc vs liste

Messaggioda targzeta » gio ott 02, 2008 20:31

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
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6164
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: [C] realloc vs liste

Messaggioda paolo86 » gio ott 02, 2008 20:36

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.
Avatar utente
paolo86
Linux 1.0
Linux 1.0
 
Messaggi: 73
Iscritto il: lun lug 14, 2008 18:22
Località: Cagliari
Nome Cognome: Paolo Cortis
Slackware: Slackware64 current
Kernel: 3.4.1-jiraiya
Desktop: KDE 4.8.2

Re: [C] realloc vs liste

Messaggioda Dani » ven ott 03, 2008 2:28

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 ?
Dani
Linux 3.x
Linux 3.x
 
Messaggi: 1447
Iscritto il: mer apr 26, 2006 0:52
Desktop: gnome
Distribuzione: arch

Re: [C] realloc vs liste

Messaggioda absinthe » ven ott 03, 2008 8:14

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

realloc fino alla morte imho. ho sempre odiato le liste :-)

M
Avatar utente
absinthe
Iper Master
Iper Master
 
Messaggi: 2354
Iscritto il: sab mag 14, 2005 23:00
Località: Prato
Nome Cognome: Matteo Nunziati
Slackware: 12.1 - defunct
Kernel: 2.6.32-5-amd64
Desktop: gnome
Distribuzione: debian squeeze

Re: [C] realloc vs liste

Messaggioda Blizzard » ven ott 03, 2008 8:56

absinthe ha scritto:http://linux.die.net/man/3/realloc

realloc fino alla morte imho. ho sempre odiato le liste :-)

M

Le liste sono il bene :D

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
Avatar utente
Blizzard
Master
Master
 
Messaggi: 1509
Iscritto il: mar gen 02, 2007 22:53
Nome Cognome: Giovanni Santostefano
Slackware: 12.2
Kernel: 2.6.27.7-smp
Desktop: Fluxbox

Re: [C] realloc vs liste

Messaggioda Blizzard » ven ott 03, 2008 9:22

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 :D
Avatar utente
Blizzard
Master
Master
 
Messaggi: 1509
Iscritto il: mar gen 02, 2007 22:53
Nome Cognome: Giovanni Santostefano
Slackware: 12.2
Kernel: 2.6.27.7-smp
Desktop: Fluxbox


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite