Discussion :

[Adiren]

Bonjour, j'aimerais faire une fonction qui alloue dynamiquement un tableau 2D mais en seulement 2 malloc et la même fonction en seulement 1 malloc. J'ai déjà tenté ça mais le programme crash et je ne sais pas pourquoi. Merci d'avance.

En 1 malloc

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
int** initTab(int N, int M){
 
    int** tab = (int**) malloc( (sizeof(int*)*N*M );
 
    return tab;
}

En 2 malloc

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
int** initTab(int N, int M){
 
    int** tab = (int**) malloc(sizeof(int*)*N);
 
    int** tab2 = (int*) malloc(sizeof(int)*M);
 
   return tab; 
}

[LittleWhite]

Bonjour,

Déjà, il est difficile de savoir pourquoi cela crashe, car le seul code que vous donnez, c'est celui de l'allocation (qui d'après moi, ne va pas crasher, sauf cas très improbable).

Dans le premier cas, vous alliez N * M int*, alors qu'il faudrait plutôt allouer N * M intDans le second cas, il me semble qu'il faille une boucle for. Du coup, il faut écrire deux malloc, toutefois, à l'exécution, ce sont plus de deux mallocs qui vont être réalisés.

[Adiren]

C'est des exercices que je dois faire en cours donc je n'ai pas accès au reste du code, je ne dois écrire que la fonction demandé. Voici l'intitulé de l'exercice :

Complétez la fonction pour qu'elle alloue et retourne un tableau de NxM cases.

Chaque case (i,j), telle que 0<=i<N, et 0<=j<M, sera accessible via tab[i][j] si tab est le nom donné au tableau retourné, et sera initialisée à i+j.

L'allocation devra se faire en 2 mallocs.

Et j'ai fait que tu m'as conseillé, mais ce n'est pas ce qui est demandé

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int** initMatrix(int N, int M){
 
    int** tab = (int**) malloc(sizeof(int*)*N);
 
    for(int i=0; i<N; i++){
 
        tab[i] = (int*) malloc(sizeof(int)*M);
 
        for(int j=0; j<M; j++){
            tab[i][j]=i+j;
        }
    }
 
   return tab; 
}

Résultat :


Au vu de l'indication, je comprend bien qu'il faut enlever la boucle et faire qu'un malloc de N*M, mais je ne sais pas où la faire pointer. J'ai tenté ça mais ça crash :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int** initMatrix(int N, int M){
 
    int** tab = (int**) malloc(sizeof(int*)*N);
 
    *tab = (int*) malloc(N*M);
 
     for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            tab[i][j]=i+j;
        }
    }    
 
 
 
   return tab; 
}

[Sve@r]

Bonjour

Complétez la fonction pour qu'elle alloue et retourne un tableau de NxM cases.

Chaque case (i,j), telle que 0<=i<N, et 0<=j<M, sera accessible via tab[i][j] si tab est le nom donné au tableau retourné, et sera initialisée à i+j.

L'allocation devra se faire en 2 mallocs.

Et j'ai fait que tu m'as conseillé, mais ce n'est pas ce qui est demandé

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int** initMatrix(int N, int M){
 
    int** tab = (int**) malloc(sizeof(int*)*N);
 
    for(int i=0; i<N; i++){
 
        tab[i] = (int*) malloc(sizeof(int)*M);
 
        for(int j=0; j<M; j++){
            tab[i][j]=i+j;
        }
    }
 
   return tab; 
}

Mais si. Il y a bien 2 malloc dans cette fonction !!!

Au vu de l'indication, je comprend bien qu'il faut enlever la boucle et faire qu'un malloc de N*M, mais je ne sais pas où la faire pointer. J'ai tenté ça mais ça crash :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int** initMatrix(int N, int M){
 
    int** tab = (int**) malloc(sizeof(int*)*N);
 
    *tab = (int*) malloc(N*M);
 
     for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            tab[i][j]=i+j;
        }
    }    
 
 
 
   return tab; 
}

Normal. Il ne faut pas perdre de vue que tu dois obtenir en final des cases. La première méthode te fait allouer N pointeurs puis chaque pointeur te fait allouer M cases. Donc tu as bien des cases au final (et en 2 malloc comme demandé)
La seconde méthode doit te faire allouer aussi des cases mais en une seule opération. Comme un jeu d'échecs de N*M cases (et non N*M pointeurs). Bref dans cette seconde méthode, tu n'as droit qu'à un malloc donc tu dois partr d'un int * et non d'un int **. Ton tout premier essai sur cet exo était presque ça.

[Adiren]

Je ne montrais que la fonction avec 2 malloc, et comme un malloc est dans une boucle, ce n'est pas 2 malloc mais en N+1.

Et merci, pour les indications avec qu'1 malloc, je vais retenter

[emixam16]

Bonjour,

Alors, pour la version avec un seul malloc, il faut que tu utilises un tableau 1D comme un tableau 2D.

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
#define WIDTH 10
#define HEIGHT 10
int* matrix = malloc(WIDTH * HEIGHT  * sizeof(int));
// [...]
// Exemple mise a 42 de l'élément matrix[i][j]
matrix[i*WIDTH +j] = 42;

Tu peux éventuellement utiliser des defines pour simplifier les écritures/lectures.


Pour la version a 2 mallocs c'est un peu plus subtil. Tu alloues tout en une fois comme un tableau contigu et tu fais pointer sur les bons éléments.

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
int** matrix= malloc(WIDTH *sizeof(int*));
int* tmpptr = malloc(WIDTH * HEIGHT *sizeof(int))
for(int i=0;i<WIDTH ;++i) {
   matrix[i] = tmpptr;
   tmpptr += HEIGHT;
}

(On peut faire beaucoup plus cours que ce code, mais cette version me semble pédagogique. Attention je n'ai pas testé ces codes).


En réutilisant la deuxième approche tu peux passer très simplement à un seul malloc tout en gardant un int**. Si tu as compris le principe tu dois être capable de l'adapter tout seul!

[Adiren]

Merci beaucoup, je comprend pour tu fais ça comme ça mais a quoi sert le tmpptr += HEIGHT;, il sert à décaler l'endroit où l'ont pointe sur tmpptr pour qu'on soit sur la bonne "partition" ?

[Sve@r]

Alors, pour la version avec un seul malloc, il faut que tu utilises un tableau 1D comme un tableau 2D.

Ca tu aurais pu le lui laisser trouver tout seul...

Pour la version a 2 mallocs c'est un peu plus subtil. Tu alloues tout en une fois comme un tableau contigu et tu fais pointer sur les bons éléments.

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
int** matrix= malloc(WIDTH *sizeof(int*));
int* tmpptr = malloc(WIDTH * HEIGHT *sizeof(int))
for(int i=0;i<WIDTH ;++i) {
   matrix[i] = tmpptr;
   tmpptr += HEIGHT;
}

Joli

Je ne montrais que la fonction avec 2 malloc, et comme un malloc est dans une boucle, ce n'est pas 2 malloc mais en N+1.

Comme j'avais pas pensé à la solution de emixam16, je me disais qu'on pouvait jouer sur les mots avec l'énoncé en parlant du code source (qui effectivement contient 2 malloc) et non de son exécution (qui effectivement en comporte N). D'autant plus que sa solution est loin d'un niveau débutant.

Merci beaucoup, je comprend pour tu fais ça comme ça mais a quoi sert le tmpptr += HEIGHT;, il sert à décaler l'endroit où l'ont pointe sur tmpptr pour qu'on soit sur la bonne "partition" ?

Exact. C'est un peu le un mélange de ton tout premier exemple (avec les malloc dans la boucle) et de celui de l'échiquier. Il définit d'abord l'échiquier en un coup puis il place différents pointeurs (dont le tableau a été lui-aussi alloué) aux endroits clefs dudit échiquier (les têtes de ligne). Et donc quand tu es sur un échiquier numéroté de 0 à 63 et que tu te trouves en début de ligne "l", il faut ajouter "8" pour te retrouver au début de la ligne "l+1".

[LittleWhite]

Bravo pour la version en deux malloc, je n'arrivais pas à la trouver. Toutefois, je me demande l'utilité d'un tel exercice. Est-ce qu'en pratique vous avez déjà rencontré un tel besoin ? Après, on peut toujours dire que c'est pour forcer à manipuler les pointeurs, mais... quand même, ça me semble faire du code tordu pour rien .

[Adiren]

Effectivement c'est pour me forcer à utiliser les pointeurs. Et oui c'est du code tordu

Pour la version du tableau 2D en 1 malloc j'ai tenté cela, en me basant sur la méthode avec 2 malloc

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int** initMatrix(int N, int M){
 
    int** tab= malloc(N * N * M * sizeof(int*));
 
    for(int i=0;i<N ;++i) {
 
        tab[i] = tab[(M*i) +N];
 
        for(int j=0; j<M; j++){
            tab[(i*M) + N + j]= i+j;
        }
        tab += M;
    }
   return tab; 
}

ça n'abouti pas à quelque chose de concluant, j'ai mal compris un truc ?

[emixam16]

Bravo pour la version en deux malloc, je n'arrivais pas à la trouver. Toutefois, je me demande l'utilité d'un tel exercice. Est-ce qu'en pratique vous avez déjà rencontré un tel besoin ? Après, on peut toujours dire que c'est pour forcer à manipuler les pointeurs, mais... quand même, ça me semble faire du code tordu pour rien .

Effectivement c'est un peu overkill comme approche mais oui, j'ai déjà vu ce type de code utilisé en pratique sur des systèmes Temps Réels (propriétaires) où les allocations étaient longues dans le pire des cas donc ils faisaient toutes leurs allocations d'un "bloc de traitement" en une fois pour être sur que le pire cas reste dans l'enveloppe temporelle. Y compris quand ils avaient des matrices.

Après clairement pour le cas général ça reste de l'optimisation de bout de chandelle... Mais pour un étudiant ça fait quand même travailler les pointeurs à la dure!

ça n'abouti pas à quelque chose de concluant, j'ai mal compris un truc ?

Oui, tu as plusieurs erreurs. Certaines de ces erreurs pourraient corrigées facilement en regardant ton compilateur!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int** tab= malloc(N * N * M * sizeof(int));

D'ou sort ce N * N * M * sizeof(int)? Que veut tu allouer ici?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

tab[i] = tab[(M*i) +N];

Là c'est encore plus faux. tab est un int** pas un int* sers t'en comme tel.

--

Ce schéma devrait t'aider à comprendre l'allocation à 2 mallocs, et comment l'adapter pour passer à 1.

[Sve@r]

ça n'abouti pas à quelque chose de concluant, j'ai mal compris un truc ?

Oui. Avec un malloc faut voir ton tableau juste comme une longue suite de cases. Donc un "int *". Tout comme un échiquier que tu découperais lignes à lignes et que tu alignerais ensuite bout à bout. Et c'est quoi ce "N * N * N" ??? Tu veux allouer un cube ??? (remarque, même pour un cube, bien écrit ça fonctionnera aussi).

[Adiren]

Après avoir un peu (beaucoup) cherché, j'ai fait cela. ça ne crash, je n'arrive juste plus à le remplir.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
int** initMatrix(int N, int M){
 
    int** tab = (int**) malloc(N*sizeof(int*) + N*M*sizeof(int));
 
    for(int i=0;i<N ;++i){
        tab[i] = tab  +M;
 
        for(int j=0; j<M; j++){
            tab[i][j] = i+j;
        }
    }
   return tab; 
}

Et voila ma sortie :

Je sens que j'y suis presque !!

[emixam16]

Pour l'allocation, c'est bien!

par contre pour l'initialisation des pointeurs sur les colonnes tu ne sembles pas avoir compris...

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for(int i=0;i<N ;++i)
    tab[i] = tab  +M;

??? Pourquoi tab+M? Ici toutes les cases pointent vers le même endroit (puisque M est constant). Cela ne peut pas fonctionner. Indice: tab[i] doit dépendre de i, comme dans mon schéma!

[Adiren]

De base j'avais mis tab[i] = tab + N + M*i;
Mais ça me sortait des choses bizarres.



Ok j'ai fait cela et ça a marché : tab[i] = tab +N + M*(i+N);

Je comprend pas pourquoi on doit faire i+N à la fin

[emixam16]

Ton compilateur te donne des warnings, ce n'est pas pour rien. Essaie de les comprendre et les interpréter. Un warning c'est rarement anodin.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
warning: assignment from incompatible pointer type [-Wincompatible-pointer-types]
         tab[i] = tab + N + M*i;

Allez, je vais t'aider car ton problème est légèrement piégeux.

En gros tu initialise un int* à partir d'un int**. Et ça, ben c'est pas bon.

Donc soit tu te dis, je vais calculer les tailles manuellement

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

 tab[i] = ((void*)tab) + N*sizeof(int**) + M*i*sizeof(int);

Soit tu te force tab+N à être traité comme un int*

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

tab[i] = ((int*)(tab + N)) + M*i;

Et voilà, tu as un code qui marche avec un seul malloc!
--
Note: Tu es assez débutant et cette méthode est assez bourrine avancée. Ne t'en sers pas comme exemple général, les autres méthodes sont plus simples, plus intuitives et peu ou prou aussi rapides. Donc, sauf quand tu sais ce que tu fais, évite ce genre "d'optimisations", surtout si tu codes en groupe, tu vas rapidement te faire détester!

[Adiren]

J'ai réussi en faisant cela :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int** initMatrix(int N, int M){
 
    int** tab = (int**) malloc(N*sizeof(int*) + N*M*sizeof(int));
 
    for(int i=0;i<N ;i++){
        tab[i] = (tab +N) +M*(i+N);
        for(int j=0; j<M; j++){
            tab[i][j] = i+j;
        }
    }
   return tab; 
}

C'était un peu en bidouillant en fonction des erreurs retournées mais je ne comprend vraiment pas cette solution. Tu peux m'expliquer s'il te plait ? C'est le M*(i+N).

[Sve@r]

Tu peux m'expliquer s'il te plait ? C'est le M*(i+N).

Je pense que c'est pour placer les différents pointeurs de ligne tab[i] après la zone de datas. Tu peux t'en rendre compte si tu isoles le calcul dans une variable que tu affiches

Accessoirement je te conseillerais de mettre des variables plus explicites que ce "N" et "M". Par exemple "nLig" et "nCol" comme j'ai fait chez-moi ce qui donne

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int** initMatrix(int nLig, int nCol) {
	int** tab=malloc(nLig * sizeof(*tab) + nLig * nCol * sizeof(**tab));
	printf("tab=%p\n", tab);
	size_t off;
 
	for(int i=0; i<nLig; i++) {
		off=nLig + nCol * (i + nLig);
		tab[i]=(int*)(tab + off);
		printf("off=%lu, tab[%d]=%p\n", off, i, tab[i]);
		for(int j=0; j<nCol; j++)
			tab[i][j]=i + j;
	}
	return tab; 
}

[Invité]

Bonsoir,

Tu peux m'expliquer s'il te plait ? C'est le M*(i+N).

Je pense que c'est pour placer les différents pointeurs de ligne tab[i] après la zone de datas. Tu peux t'en rendre compte si tu isoles le calcul dans une variable que tu affiches

C'est le but disons… mais ce n'est pas correct. Ça ne fait que tomber en marche.
Rien que la première adresse pour i=0 : (tab + nLig) + nCol * (0 + nLig) = (tab + nLig) + nCol * nLig va déjà taper au dela de la zone allouée (en 64 bits où généralement sizeof(int*) = 2 * sizeof(int) = 8. En 32 bits où on aura généralement sizeof(int*) = sizeof(int) = 4, elle arrive pile à la toute fin).

tab étant de type int**, avec tab + off on va se déplacer par unités de sizeof(*tab) = sizeof(int*) = 8 (64 bits) / 4 (32 bits).

La première partie nLig qui constitue le calcul de off est correcte : on passe la première zone de taille nLig * sizeof(*tab). Mais ensuite il faut se déplacer par unités de sizeof(int). Et pour cela il faut revenir à un int * :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int *debut_tableau = (int*)(tab + nLig);

Puis chaque ligne contenant nCol valeurs, aller sur la i^e ligne revient à se déplacer de i * nCol cases :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

tab[i] = debut_tableau + i * nCol;

Le but final étant de faire pointer chaque pointeur tab[i] (cases bleus à gauche) vers l'adresse de la première case de chaque ligne correspondante (cases rouges tab[i][0]).

[Sve@r]

tab étant de type int**, avec tab + off on va se déplacer par unités de sizeof(*tab) = sizeof(int*) = 8 (64 bits) / 4 (32 bits).

Exact, effectivement j'ai raté ce détail. Mais (à ma décharge ) j'ai juste repris le code initial en isolant le calcul dans "off". Le code initial ajoute ce calcul à tab, j'ajoute off à tab.

Le but final étant de faire pointer chaque pointeur tab[i] (cases bleus à gauche) vers l'adresse de la première case de chaque ligne correspondante (cases rouges tab[i][0]).

Oui mais pour moi c'est dans l'autre sens. Les pointeurs sont à la fin de la zone des ints, qui, elle, commence au début de tab. Ceci pour permettre par exemple à un itérateur qui partirait de tab de pouvoir lui-aussi accéder aux ints par simple incrément sans avoir à le faire partir d'un offset à la c..
Et ces pointeurs continuent évidemment à pointer vers les différents "tab[x]" qui identifient chaque début de ligne.
Sinon très belle image. Tu l'as faite avec quoi ?

[edit] Ok, j'ai affiché les adresse

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <stdlib.h>
 
int** initMatrix(int nLig, int nCol) {
	printf("sizeof(int)=%lu\n", sizeof(int));
	printf("sizeof(int*)=%lu\n", sizeof(int*));
	printf("sizeof(int**)=%lu\n", sizeof(int**));
	printf("lig=%d, col=%d\n", nLig, nCol);
	int** tab;
	size_t t=nLig * sizeof(*tab) + nLig * nCol * sizeof(**tab);
	printf("alloc=%lu\n", t);
	tab=malloc(t);
	printf("tab=%lu\n", tab);
	size_t off;
 
	for(int i=0; i<nLig; i++) {
		off=nLig + nCol * (i + nLig);
		tab[i]=(int*)(tab + off);
		printf("off=%lu, tab[%d]=%lu\n", off, i, tab[i]);
		for(int j=0; j<nCol; j++)
			tab[i][j]=i + j;
	}
	return tab; 
}
 
int main() {
	int l=3, c=5;
	int **tab=initMatrix(l, c);
	for (int i=0; i < l; i++) {
		for (int j=0; j < c; j++)
			printf("%lu tab[%d][%d]=%d\n", &tab[i][j], i, j, tab[i][j]);
	}
}

Et voici ce que ça donne (je supprime les grands chiffres des millions)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
sizeof(int)=4
sizeof(int*)=8
sizeof(int**)=8
lig=3, col=5
alloc=84
tab=616880
off=18, tab[0]=617024
off=23, tab[1]=617064
off=28, tab[2]=617104
617024 tab[0][0]=0
617028 tab[0][1]=1
617032 tab[0][2]=2
617036 tab[0][3]=3
617040 tab[0][4]=4
617064 tab[1][0]=1
617068 tab[1][1]=2
617072 tab[1][2]=3
617076 tab[1][3]=4
617080 tab[1][4]=5
617104 tab[2][0]=2
617108 tab[2][1]=3
617112 tab[2][2]=4
617116 tab[2][3]=5
617120 tab[2][4]=6

Effectivement, avec tab qui commence à 616880 et qui alloue 84 octets, les adresses ne peuvent aller que de 616880 à 616964 et ne peuvent pas atteindre ces 617xxx. Pourtant les 84 octets c'est bon (15 int de 4 + 3 int* de 8). C'est donc le calcul qu'il faut revoir. Et déjà une chose est sûre, avec un off qui compte en octets, il faut se déplacer dans tab en octets donc le caster en char* chaque fois qu'on y fait des opérations dessus.

Mais si on rectifie le calcul (ie tab[i]=(int*)((char*)tab + off), alors au résultat

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
sizeof(int)=4
sizeof(int*)=8
sizeof(int**)=8
lig=3, col=5
alloc=84
tab=25808
off=18, tab[0]=25826
off=23, tab[1]=25831
off=28, tab[2]=25836
25826 tab[0][0]=1436508729
25830 tab[0][1]=0
25834 tab[0][2]=131584
25838 tab[0][3]=196608
25842 tab[0][4]=262144
25831 tab[1][0]=0
25835 tab[1][1]=514
25839 tab[1][2]=768
25843 tab[1][3]=1024
25847 tab[1][4]=1280
25836 tab[2][0]=2
25840 tab[2][1]=3
25844 tab[2][2]=4
25848 tab[2][3]=5
25852 tab[2][4]=6

Donc là les différents "tab[x]" ont les bonnes valeurs d'adresse, mais ça cafouille aux valeurs...