Newsgroup: it.comp.lang.c++
Titolo: Puntatori e matrici (lungo)

Salve a tutti.
Ho scritto, a titolo di esercitazione, una piccola funzione per gestire 
array bidimensionali, che riporto qui sotto:
void stampa(int *a)
{
 
int i,j;
 
	cout<<"\n";
 
	for(i=0; i<MAX_N; i++)
		{
		for(j=0; j<MAX_N; j++)
			{
			cout<<"\t"<<*a;
			a++;
			}
		a++;   // ??????????????	
		cout<<"\n";
		}
 
 
}
Questa funzione riceve l'indirizzo del primo elemento di una matrice e
ne stampa il contenuto. La matrice e' definita come  
int **matrice 
ed e' allocata dinamicamente tramite new.
Il fatto e' che se tolgo la riga commentata con i ???, alla fine del
primo ciclo interno (j), quindi alla fine della prima riga, 'a' non punta
al primo elemento della seconda riga, ma ad un valore (25 per la
precisione) che non centra niente, e poi ricomincia con i valori
corretti.
Ma gli elementi dell'array non sono memorizzati tutti uno di seguito
all'altro?
Se invece definisco la matrice staticamente 
int matrice[MAX_N][MAX_N];
tutto funziona senza la linea commentata.
Quindi chiedo: cosa rappresenta quel valore in piu' che mi ritrovo
quando alloco dinamicamente la matrice?
Spero di essere stato chiaro.
Ringrazio e saluto.
-- 
Saluti 	 		      << Linux Powered >>			 
LIBRA               e-mail: metti "libero" al posto di "NOSPAM"  

 int matrice[MAX_N][MAX_N];
Questi due righe descrivono oggetti diversi. La prima è un puntatore a 
puntatori, che a loro volta puntano a dei vettori; la seconda è una zona 
_unica_ contigua di memoria.
Nel priomo caso quando io scrivo
matrice[i][j]
Praticamente dereferenzio l'elemento 'matrice+i', che è un puntatore ad 
un'altro array; con [j] dereferenzio anche quest'ultimo.
Nel secondo caso quando vado a scrivere
matrice[a][b]
viene "trasformata" in
*( ((int*)matrice)+a*MAX_N + b )

 int matrice[MAX_N][MAX_N];
questa matrice invece e' un array di array. Nota la differenza fra un array di
array e un array di puntatori ciascuno che punta ad un array.
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

fra loro. I puntatori agli array sono anch'essi consecutivi.
Ah, ecco, ora e' piu' chiaro. Pensavo invece che anche i vari array
fossero consecutivi.
Grazie.


 fossero consecutivi.
Vediamo di capire meglio cosa succede. La matrice la puoi dichiarare, come sai,
in due modi. Ma le due dichiarazioni non sono equivalenti.
int mat[K1][K2];
dichiara una matrice di K1 x K2 interi che sono consecutivi in memoria. Piu'
precisamente dichiara un array di K1 elementi ciascuno dei quali e' un array di
K2 elementi ciascuno dei quali e' un intero.
La chiamata "f(&mat[0][0])" passa l'indirizzo del primo intero. La funzione deve
essere del tipo "f(int* p)". All'interno della funzione il puntatore p e' un
puntatore a intero e, aritmeticamente, ha validità nel "range" cha va da "&p[0]"
a "&p[K1*k2]" (dove "&p[K1*k2]" e' calcolabile ma non dereferenziabile) che e'
appunto la "zona" di memoria allocata per la matrice. La sintassi "p[i][j]" non
e' ammessa perche' sarebbe come applicare operator[] ad un intero. L'indirizzo
del primo elemento della matrice e' "p" o, equivalemtnemente, "&p[0]".
La chiamata "f(mat)" fa uso del "decadimento" di un array in un puntatore.
Equivale alla chiamata "f(&mat[0])". La funzione sarà dichiarata del tipo "f(int
(*p)[K2])". All'interno della funzione il puntatore p e' un puntatore ad un
array di K2 interi e, aritmeticamente, ha validità nel "range" cha va da "&p[0]"
a "&p[K1]" (sempre con "&p[K1]" non dereferenziabile). Nota che trattandosi di
un puntatore ad un array non e' ammesso scrivere "p[i]=k" dato che non puoi
assegnare un intero ad un array di interi. Puoi pero' scrivere "p[i][j]=k". Se
vuoi l'indirizzo del primo intero della matrice devi scrivere "&p[0][0]".
La dichiarazione suddetta e' statica. Per avere una matrice dinamica devi
allocarla. Nota che in C/C++ in realtà la "matrice" non esiste. Esistono solo
gli array (con lunghezza fissa) e una aritmetica dei puntatori che permette
l'uso di array di lunghezza indefinita. Non esiste quindi una vera "matrice
dinamica". Neppure sotto forma di "array dinamico di array dinamici" dato che il
concetto di array dinamico non esiste in se ma e' ottenuto tramite l'aritmetica
dei puntatori. Quindi si usa la dichiarazione:
int **d_mat;
Questa va inizializzata con:
d_mat=new int*[K1];
for ( int i=0; i<K1; i++ )
    d_mat[i]=new int[k2];
e deinizializzata con:
for ( int i=0; i<K1; i++ )
    delete [] d_mat[i];
delete d_mat;
Ora vedi bene cosa hai fatto. "d_mat" e' un puntatore a puntatori a interi. La
prima parte dell'inizializzazione alloca dinamicamente K1 puntatori a interi
consecutivi (chiamalo un array dinamico di K1 int*). L'espressione "d_mat" non
fa uso di decadimento. Il suo tipo e' "int**". L'espressione "d_mat[i]" non fa
uso di decadimento e ha tipo "int*". La seconda parte dell'inizializzazione
inizializza proprio i K1 puntatori, ciascuno con l'indirizzo di un array di
interi anch'esso allocati dinamicamente. Gli interi in ciascuno di questi array
sono consecutivi. Ma gli array di per se sono allocati con chiamate diverse a
new. Non esiste nessuna garanzia che due chiamate consecutive a new
restituiscano indirizzi "consecutivi". Ed e' un caso che la distanza fra uno e
l'altro sia esattamente di un intero!
Una volta inizializzata completamente avrai:
"f(&d_mat[0][0])" che passa ad f l'indirizzo del primo intero del primo array.
La funzione deve essere del tipo "f(int* p)". All'interno della funzione il
puntatore p e' un puntatore a intero e, aritmeticamente, ha validità nel "range"
cha va da "&p[0]" a "&p[k2]" (dove "&p[k2]" e' calcolabile ma non
dereferenziabile) che e' appunto la "zona" di memoria allocata per IL PRIMO
VETTORE. Ogni accesso al di fuori di questo e' undefined.
La chiamata "f(d_mat)" NON fa uso del "decadimento" di un array in un puntatore.
Equivale alla chiamata "f(&mat[0])" e dato che "mat[0]" e' un puntatore ad
intero (non un array di interi) il tipo e' "int**". La funzione sarà dichiarata
del tipo "f(int **p)". All'interno della funzione il puntatore p e' un puntatore
ad un puntatore a interi e, aritmeticamente, ha validità nel "range" cha va da
"&p[0]" a "&p[K1]" (sempre con "&p[K1]" non dereferenziabile). Puoi scrivere
"p[i][j]=k". Se vuoi l'indirizzo del primo intero della matrice devi scrivere
"&p[0][0]". Nota pero' sempre che "p[i]" ha tipo "int*", mentre nel caso della
matrice statica avevi "p[i]" che aveva tipo "int[K2]" che eventualmente
"decadeva" in "int*".
HTH


comportamento di questo codice e' "undefined". Vedi sotto.
Gia'. Leggendo quanto hai postato e pensandoci un po' mi pare piu' che
logico.
Gia' che ci sono posso fare un'altra domanda?
Se io utilizzassi un array "lineare" per memorizzare una matrice, che
considerazioni posso fare sulle prestazioni?
Mi spiego. Ho una matrice n per m. Inizializzo un array nel seguente
modo:
	int * matrice = new int [n*m];
e accedo all'elemento (i,j) nel seguente modo:
	h = i*m + j;  		//m = numero di colonne
	*(matrice + h) = 10;
C'e' qualche convenienza ad usare questo metodo o ha validita' solo
didattica?
Grazie per l'esauriente spiegazione.


 didattica?
La convenienza e' dovuta alla possibilità di ridefinire le dimensioni della
matrice a tuo piacimento mantenendo gli elementi in un blocco contiguo unico.
La sconvenienza e' la leggibilità. Ovvio basandomi sui nomi usati nell'altro
reply mi pare evidente che "d_mat[i*K2+j]" e' meno leggibile di "mat[i][j]".
Dal punto di vista delle prestazioni ... sono praticamente le stesse.
L'unica differenza e' che per una matrice statica c'e' un livello di redirezione
in meno.
Mi spiego:
double mat[K1][K2];
...
mat[i][j];
corrisponde a questo calcolo "esteso" (nota: non e' standard a causa delle
regole di conversione, ma e' quello che "intuitivamente" succede):
*(double*)(j*sizeof(double)+(i*sizeof(double)*K2+(int)mat)
mentre
double (*mat)[K2];
mat=new double [K1][K2];
...
mat[i][j];
corrisponde a questo calcolo "esteso":
*(double*)(j*sizeof(double)+(i*sizeof(double)*K2+(int)(*mat))
che ha una ridirezione extra a livello di mat.
E il caso:
double *mat;
mat=new double [K1*K2];
...
mat[i*K2+j];
corrisponde a questo calcolo "esteso":
*(double*)((i*K2+j)*sizeof(double)+(int)(*mat))
E si puo' presumere che un compilatore appena decente sia in grado di
implementare identicamente queste tre espressioni (salva ovviamente la
redirezione su mat).
Se le formulette di cui sopra ti suonano ostiche prova a vedere le cose in
questo modo:
l'operatore [] e' definito in termini di aritmetica dei puntatori e ridirezione
in questa maniera:
"a[b]" corrisponde a "*(a+b)"
Il che e' tanto vero che ...
int v[4]={ 0,11,22,33 }
...
int i= 2[v];
non e' un syntax error ma assegna 22 a i!
Inoltre l'aritmetica dei puntatori (somma di un intero ad un puntatore)
prescrive che l'indirizzo sia aumentato in base alla dimensione dell'oggetto
puntato (infatti non si puo' sommare un intero ad un puntatore a void!). Il che
corrisponde piu' o meno a dire che (sempre con la nota che non e' standard ma e'
intuitivamente corretto):
"p+i" dove i e' intero e p e' puntatore a T,
corrisponde a "(T*)(i*sizeof(T)+(int)p)"
