Comment les tableaux multidimensionnels sont-ils formatés en mémoire?

185

En C, je sais que je peux allouer dynamiquement un tableau à deux dimensions sur le tas en utilisant le code suivant:

int** someNumbers = malloc(arrayRows*sizeof(int*));

for (i = 0; i < arrayRows; i++) {
    someNumbers[i] = malloc(arrayColumns*sizeof(int));
}

Clairement, cela crée en fait un tableau unidimensionnel de pointeurs vers un groupe de tableaux unidimensionnels séparés d'entiers, et "The System" peut comprendre ce que je veux dire quand je demande:

someNumbers[4][2];

Mais quand je déclare statiquement un tableau 2D, comme dans la ligne suivante ...:

int someNumbers[ARRAY_ROWS][ARRAY_COLUMNS];

... une structure similaire est-elle créée sur la pile ou est-elle complètement d'une autre forme? (c'est-à-dire est-ce un tableau 1D de pointeurs? Sinon, qu'est-ce que c'est, et comment les références sont-elles déterminées?)

De plus, quand j'ai dit «Le système», qu'est-ce qui est réellement responsable de le découvrir? Le noyau? Ou le compilateur C le trie-t-il lors de la compilation?

Chris Cooper
la source
8
Je donnerais plus de +1 si je pouvais.
Rob Lachlan
1
Attention : il n'y a pas de tableau 2D dans ce code!
trop honnête pour ce site
@toohonestforthissite En effet. Pour développer cela: Le bouclage et l'appel malloc()ne donnent pas un tableau à N dimensions. . Il en résulte des tableaux de pointeurs [vers des tableaux de pointeurs [...] pour séparer complètement les tableaux unidimensionnels . Consultez Allocation correcte de tableaux multidimensionnels pour voir comment allouer un tableau TRUE N-dimensionnel.
Andrew Henle le

Réponses:

145

Un tableau statique à deux dimensions ressemble à un tableau de tableaux - il est simplement disposé de manière contiguë en mémoire. Les tableaux ne sont pas la même chose que les pointeurs, mais comme vous pouvez souvent les utiliser de manière interchangeable, cela peut parfois être déroutant. Le compilateur effectue le suivi correctement, cependant, ce qui fait que tout s'aligne bien. Vous devez être prudent avec les tableaux 2D statiques comme vous le mentionnez, car si vous essayez d'en transmettre un à une fonction prenant un int **paramètre, de mauvaises choses vont se produire. Voici un exemple rapide:

int array1[3][2] = {{0, 1}, {2, 3}, {4, 5}};

En mémoire ressemble à ceci:

0 1 2 3 4 5

exactement la même chose que:

int array2[6] = { 0, 1, 2, 3, 4, 5 };

Mais si vous essayez de passer array1à cette fonction:

void function1(int **a);

vous recevrez un avertissement (et l'application ne parviendra pas à accéder correctement au tableau):

warning: passing argument 1 of function1 from incompatible pointer type

Parce qu'un tableau 2D n'est pas le même que int **. La décomposition automatique d'un tableau en un pointeur ne va pour ainsi dire "qu'un niveau de profondeur". Vous devez déclarer la fonction comme:

void function2(int a[][2]);

ou

void function2(int a[3][2]);

Pour tout rendre heureux.

Ce même concept s'étend aux tableaux à n dimensions. Tirer parti de ce type d'activité amusante dans votre application ne fait généralement que le rendre plus difficile à comprendre. Alors soyez prudent là-bas.

Carl Norum
la source
Merci pour l'explication. Donc "void function2 (int a [] [2]);" acceptera les 2D déclarés statiquement et dynamiquement? Et je suppose que c'est toujours une bonne pratique / essentiel de passer également la longueur du tableau si la première dimension est laissée comme []?
Chris Cooper
1
@Chris Je ne pense pas - vous aurez du mal à faire basculer C une pile ou un tableau alloué globalement en un tas de pointeurs.
Carl Norum
6
@JasonK. - non. Les tableaux ne sont pas des pointeurs. Les tableaux «se désintègrent» en pointeurs dans certains contextes, mais ils ne sont absolument pas les mêmes.
Carl Norum
1
Pour être clair: Oui Chris "c'est toujours une bonne pratique de passer la longueur du tableau" comme paramètre séparé, sinon utilisez std :: array ou std :: vector (qui est C ++ et non l'ancien C). Je pense que nous sommes d'accord @CarlNorum à la fois conceptuellement pour les nouveaux utilisateurs et pratiquement, pour citer Anders Kaseorg sur Quora: «La première étape pour apprendre C est de comprendre que les pointeurs et les tableaux sont la même chose. La deuxième étape consiste à comprendre que les pointeurs et les tableaux sont différents. »
Jason K.
2
@JasonK. "La première étape pour apprendre C est de comprendre que les pointeurs et les tableaux sont la même chose." - Cette citation est tellement fausse et trompeuse! C'est en effet l'étape la plus importante pour comprendre qu'ils ne sont pas les mêmes, mais que les tableaux sont convertis en pointeur vers le premier élément pour la plupart des opérateurs! sizeof(int[100]) != sizeof(int *)(à moins que vous ne trouviez une plate-forme avec 100 * sizeof(int)octets / int, mais c'est une chose différente.
trop honnête pour ce site
85

La réponse est basée sur l'idée que C n'a pas vraiment avoir des tableaux 2D - il a des tableaux-de-tableaux. Lorsque vous déclarez ceci:

int someNumbers[4][2];

Vous demandez someNumbersd'être un tableau de 4 éléments, où chaque élément de ce tableau est de type int [2](qui est lui-même un tableau de 2 ints).

L'autre partie du puzzle est que les tableaux sont toujours disposés de manière contiguë en mémoire. Si vous demandez:

sometype_t array[4];

alors cela ressemblera toujours à ceci:

| sometype_t | sometype_t | sometype_t | sometype_t |

(4 sometype_tobjets disposés les uns à côté des autres, sans espace entre les deux). Donc, dans votre someNumberstableau de tableaux, cela ressemblera à ceci:

| int [2]    | int [2]    | int [2]    | int [2]    |

Et chaque int [2]élément est lui-même un tableau, qui ressemble à ceci:

| int        | int        |

Donc, dans l'ensemble, vous obtenez ceci:

| int | int  | int | int  | int | int  | int | int  |
caf
la source
1
en regardant la mise en page finale, je pense que int a [] [] est accessible en tant que int * ... non?
Narcisse Doudieu Siewe
2
@ user3238855: Les types ne sont pas compatibles, mais si vous obtenez un pointeur vers le premier intdans le tableau de tableaux (par exemple en évaluant a[0]ou &a[0][0]) alors oui, vous pouvez compenser cela pour accéder séquentiellement à tous int).
caf
29
unsigned char MultiArray[5][2]={{0,1},{2,3},{4,5},{6,7},{8,9}};

en mémoire est égal à:

unsigned char SingleArray[10]={0,1,2,3,4,5,6,7,8,9};
Kanghai
la source
5

En réponse à votre également: les deux, bien que le compilateur fasse la majeure partie du gros du travail.

Dans le cas de tableaux alloués statiquement, "The System" sera le compilateur. Il réservera la mémoire comme il le ferait pour n'importe quelle variable de pile.

Dans le cas du tableau malloc'd, "The System" sera l'implémenteur de malloc (le noyau généralement). Tout ce que le compilateur allouera est le pointeur de base.

Le compilateur va toujours gérer le type comme ce qu'il est déclaré être, sauf dans l'exemple donné par Carl où il peut trouver une utilisation interchangeable. C'est pourquoi si vous passez un [] [] à une fonction, il doit supposer qu'il s'agit d'un flat alloué statiquement, où ** est supposé être un pointeur vers un pointeur.

Jon L
la source
@Jon L. Je ne dirais pas que malloc est implémenté par le noyau, mais par la libc au-dessus des primitives du noyau (comme brk)
Manuel Selva
@ManuelSelva: où et comment mallocest implémenté n'est pas spécifié par la norme et laissé à l'implémentation, resp. environnement. Pour les environnements autonomes, il est facultatif comme toutes les parties de la bibliothèque standard nécessitant des fonctions de liaison (c'est ce que les exigences entraînent réellement, pas littéralement ce que le standard déclare). Pour certains environnements hébergés modernes, il repose en effet sur les fonctions du noyau, soit le contenu complet, soit (par exemple Linux) comme vous l'avez écrit en utilisant à la fois stdlib et kernel-primitives. Pour les systèmes à un seul processus de mémoire non virtuelle, il ne peut s'agir que de stdlib.
trop honnête pour ce site
2

Supposons que nous avons a1et a2défini et initialisées comme ci - dessous (C99):

int a1[2][2] = {{142,143}, {144,145}};
int **a2 = (int* []){ (int []){242,243}, (int []){244,245} };

a1est un tableau 2D homogène avec une disposition continue simple en mémoire et l'expression (int*)a1est évaluée à un pointeur vers son premier élément:

a1 --> 142 143 144 145

a2est initialisé à partir d'un tableau 2D hétérogène et est un pointeur vers une valeur de type int*, c'est-à-dire que l'expression de déréférencement *a2s'évalue en une valeur de type int*, la disposition de la mémoire n'a pas besoin d'être continue:

a2 --> p1 p2
       ...
p1 --> 242 243
       ...
p2 --> 244 245

Malgré une disposition de la mémoire et une sémantique d'accès totalement différentes, la grammaire du langage C pour les expressions d'accès aux tableaux est exactement la même pour les tableaux 2D homogènes et hétérogènes:

  • l'expression a1[1][0]récupérera la valeur 144du a1tableau
  • l'expression a2[1][0]récupérera la valeur 244du a2tableau

Le compilateur sait que l'expression d'accès pour a1opère sur le type int[2][2], lorsque l'expression d'accès pour a2opère sur le type int**. Le code d'assemblage généré suivra la sémantique d'accès homogène ou hétérogène.

Le code se bloque généralement au moment de l'exécution lorsque le tableau de type int[N][M]est casté puis accédé en tant que typeint** , par exemple:

((int**)a1)[1][0]   //crash on dereference of a value of type 'int'
sqr163
la source
1

Pour accéder à un tableau 2D particulier, considérez la carte mémoire pour une déclaration de tableau comme indiqué dans le code ci-dessous:

    0  1
a[0]0  1
a[1]2  3

Pour accéder à chaque élément, il suffit de passer le tableau qui vous intéresse en tant que paramètres à la fonction. Ensuite, utilisez le décalage pour la colonne pour accéder individuellement à chaque élément.

int a[2][2] ={{0,1},{2,3}};

void f1(int *ptr);

void f1(int *ptr)
{
    int a=0;
    int b=0;
    a=ptr[0];
    b=ptr[1];
    printf("%d\n",a);
    printf("%d\n",b);
}

int main()
{
   f1(a[0]);
   f1(a[1]);
    return 0;
}
AlphaGoku
la source