Façon bizarre d'allouer un tableau à deux dimensions?

110

Dans un projet, quelqu'un a poussé cette ligne:

double (*e)[n+1] = malloc((n+1) * sizeof(*e));

Ce qui crée supposément un tableau bidimensionnel de (n + 1) * (n + 1) doubles.

Soi -disant, dis-je, parce que jusqu'à présent, personne à qui j'ai demandé ne pouvait me dire ce que cela faisait exactement, ni d'où cela venait ni pourquoi cela devrait fonctionner (ce qui serait prétendument le cas, mais je ne l'achète pas encore).

Peut-être que je manque quelque chose d'évident, mais j'apprécierais que quelqu'un puisse m'expliquer ci-dessus. Parce que personnellement, je me sentirais beaucoup mieux si nous utilisions quelque chose que nous comprenons réellement.

Utilisateur1291
la source
15
Même si cela fonctionne, tirez sur le poussoir.
Martin James
22
@MartinJames Pourquoi? Comment alloueriez-vous un tableau 2D dans la mémoire adjacente autrement? Un tableau 1D mutilé? C'est la programmation des années 90, nous avons maintenant des VLA.
Lundin
43
Pour mémoire, qui est le seul et unique moyen d'allouer dynamiquement un tableau 2D réelle.
Quentin
15
@Kninnug Non, cela déclarerait un tableau de pointeurs, pas un tableau 2D. Si vous voulez un tableau 2D, il n'y a aucune raison pour que vous souhaitiez allouer un tableau de pointeurs. Il est lent en raison de la fragmentation du tas et d'une mauvaise utilisation de la mémoire cache, et il est dangereux car vous ne pouvez pas l'utiliser comme un tableau (avec memcpy, etc.). De plus, le code est gonflé. Vous auriez besoin de plusieurs appels free () et il serait facile de provoquer des fuites de mémoire. Aussi répandu qu'un tel code puisse être, il est tout simplement mauvais.
Lundin
15
Ce problème aurait été plus clair à expliquer / répondre si l'échantillon n'avait pas utilisé les mêmes dimensions valorisées n+1mais à la placedouble (*e)[rows] = malloc(columns * sizeof *e);
chux - Réintégrer Monica le

Réponses:

87

La variable eest un pointeur vers un tableau d' n + 1éléments de type double.

L'utilisation de l'opérateur de déréférence sur evous donne le type de base edont est "tableau d' n + 1éléments de type double".

L' mallocappel prend simplement le type de base de e(expliqué ci-dessus) et obtient sa taille, la multiplie par n + 1et en passant cette taille à la mallocfonction. Allouant essentiellement un tableau de n + 1tableaux d' n + 1éléments de double.

Un mec programmeur
la source
3
@MartinJames sizeof(*e)équivaut à sizeof(double [n + 1]). Multipliez cela avec n + 1et vous en avez assez.
Un mec programmeur
24
@MartinJames: Quel est le problème avec ça? Ce n'est pas si précis, cela garantit que les lignes allouées sont contiguës et vous pouvez l'indexer comme n'importe quel autre tableau 2D. J'utilise beaucoup cet idiome dans mon propre code.
John Bode
3
Cela peut sembler évident, mais cela ne fonctionne que pour les tableaux carrés (mêmes dimensions).
Jens
18
@Jens: Seulement dans le sens où si vous mettez les n+1deux dimensions, le résultat sera carré. Si vous le faites double (*e)[cols] = malloc(rows * sizeof(*e));, le résultat aura le nombre de lignes et de colonnes que vous avez spécifié.
user2357112 prend en charge Monica le
9
@ user2357112 Maintenant que je préférerais de beaucoup voir. Même si cela signifie que vous devez ajouter int rows = n+1et int cols = n+1. Dieu nous sauve du code intelligent.
candied_orange
56

C'est la manière habituelle d'allouer des tableaux 2D de manière dynamique.

  • eest un pointeur de tableau vers un tableau de type double [n+1].
  • sizeof(*e)donne donc le type du type pointé, qui est la taille d'un double [n+1]tableau.
  • Vous allouez de la place pour n+1ces tableaux.
  • Vous définissez le pointeur de tableau epour qu'il pointe sur le premier tableau de ce tableau de tableaux.
  • Cela vous permet d'utiliser eas e[i][j]pour accéder à des éléments individuels dans le tableau 2D.

Personnellement, je pense que ce style est beaucoup plus facile à lire:

double (*e)[n+1] = malloc( sizeof(double[n+1][n+1]) );
Lundin
la source
12
Bonne réponse sauf que je ne suis pas d'accord avec votre style suggéré, préférant le ptr = malloc(sizeof *ptr * count)style.
chux - Réintégrer Monica le
Bonne réponse, et j'aime votre style préféré. Une légère amélioration pourrait être de souligner que vous devez le faire de cette façon, car il peut y avoir un remplissage entre les lignes qui doit être pris en compte. (Au moins, je pense que c'est la raison pour laquelle vous devez le faire de cette façon.) (Faites-moi savoir si je me trompe.)
davidbak
2
@davidbak C'est la même chose. La syntaxe du tableau est simplement du code auto-documenté: elle dit "allouer de la place pour un tableau 2D" avec le code source lui-même.
Lundin
1
@davidbak Remarque: Un inconvénient mineur du commentaire malloc(row*col*sizeof(double)) se produit en cas de row*col*sizeof()débordement, mais ce sizeof()*row*coln'est pas le cas. (eg row, col are int)
chux - Reinstate Monica
7
@davidbak: sizeof *e * (n+1)est plus facile à maintenir; si jamais vous décidez de changer le type de base (de doubleà long double, par exemple), il vous suffit de changer la déclaration de e; vous n'avez pas besoin de modifier l' sizeofexpression dans l' mallocappel (ce qui vous fait gagner du temps et vous évite de la changer à un endroit mais pas à l'autre). sizeof *evous donnera toujours la bonne taille.
John Bode
39

Cet idiome sort naturellement de l'allocation de tableau 1D. Commençons par allouer un tableau 1D d'un type arbitraire T:

T *p = malloc( sizeof *p * N );

Simple, non? L' expression *p a un type T, donc sizeof *pdonne le même résultat que sizeof (T), donc nous Nallouons suffisamment d'espace pour un tableau -element de T. Cela est vrai pour tout typeT .

Maintenant, remplaçons Tpar un type de tableau comme R [10]. Alors notre allocation devient

R (*p)[10] = malloc( sizeof *p * N);

La sémantique ici est exactement la même que celle de la méthode d'allocation 1D; tout ce qui a changé est le type de p. Au lieu de T *, c'est maintenant R (*)[10]. L'expression *pa un type Tqui est type R [10], donc sizeof *pest équivalent à sizeof (T)qui est équivalent à sizeof (R [10]). Nous allouons donc suffisamment d'espace pour un tableau Npar 10élément de R.

Nous pouvons aller encore plus loin si nous le voulons; suppose Rest lui-même un type de tableau int [5]. Remplacez cela Ret nous obtenons

int (*p)[10][5] = malloc( sizeof *p * N);

Même accord - sizeof *pest le même que sizeof (int [10][5]), et nous finissons par allouer un morceau de mémoire contigu assez grand pour contenir un Npar 10par 5tableau de int.

Voilà donc le côté allocation; qu'en est-il du côté accès?

N'oubliez pas que l' []opération d'indice est définie en termes d'arithmétique de pointeur: a[i]est définie comme *(a + i)1 . Ainsi, l'opérateur d'indice déréférence [] implicitement un pointeur. Si pest un pointeur vers T, vous pouvez accéder à la valeur pointée soit en déréférençant explicitement avec l' *opérateur unaire :

T x = *p;

ou en utilisant l' []opérateur indice:

T x = p[0]; // identical to *p

Ainsi, si ppointe sur le premier élément d'un tableau , vous pouvez accéder à n'importe quel élément de ce tableau en utilisant un indice sur le pointeur p:

T arr[N];
T *p = arr; // expression arr "decays" from type T [N] to T *
...
T x = p[i]; // access the i'th element of arr through pointer p

Maintenant, refaisons notre opération de substitution et remplaçons Tpar le type de tableau R [10]:

R arr[N][10];
R (*p)[10] = arr; // expression arr "decays" from type R [N][10] to R (*)[10]
...
R x = (*p)[i];

Une différence immédiatement apparente; nous déréférencons explicitement pavant d'appliquer l'opérateur indice. Nous ne voulons pas souscrire p, nous voulons indiquer ce qui p pointe vers (dans ce cas, le tableau arr[0] ). Étant donné que l'unaire *a une priorité inférieure à l' []opérateur indice , nous devons utiliser des parenthèses pour regrouper explicitement pavec *. Mais rappelez-vous d'en haut que *pc'est la même chose que p[0], donc nous pouvons le remplacer par

R x = (p[0])[i];

ou juste

R x = p[0][i];

Ainsi, si ppointe vers un tableau 2D, nous pouvons indexer ce tableau pcomme suit:

R x = p[i][j]; // access the i'th element of arr through pointer p;
               // each arr[i] is a 10-element array of R

Prenant cela à la même conclusion que ci-dessus et en remplaçant Rpar int [5]:

int arr[N][10][5];
int (*p)[10][5]; // expression arr "decays" from type int [N][5][10] to int (*)[10][5]
...
int x = p[i][j][k];

Cela fonctionne exactement de la même manière s'il ppointe vers un tableau normal ou s'il pointe vers la mémoire allouée via malloc.

Cet idiome présente les avantages suivants:

  1. C'est simple - juste une ligne de code, par opposition à la méthode d'allocation fragmentaire
    T **arr = malloc( sizeof *arr * N );
    if ( arr )
    {
      for ( size_t i = 0; i < N; i++ )
      {
        arr[i] = malloc( sizeof *arr[i] * M );
      }
    }
  2. Toutes les lignes du tableau alloué sont * contiguës *, ce qui n'est pas le cas avec la méthode d'allocation fragmentaire ci-dessus;
  3. Désallouer le tableau est tout aussi simple avec un seul appel à free. Encore une fois, ce n'est pas vrai avec la méthode d'allocation au coup par coup, où vous devez désallouer chacun arr[i]avant de pouvoir désallouer arr.

Parfois, la méthode d'allocation fragmentaire est préférable, par exemple lorsque votre tas est gravement fragmenté et que vous ne pouvez pas allouer votre mémoire en tant que bloc contigu, ou que vous souhaitez allouer un tableau "en dents de scie" où chaque ligne peut avoir une longueur différente. Mais en général, c'est la meilleure façon de procéder.


1. N'oubliez pas que les tableaux ne sont pas des pointeurs - au lieu de cela, les expressions de tableau sont converties en expressions de pointeur si nécessaire.

John Bode
la source
4
+1 J'aime la façon dont vous présentez le concept: allouer une série d'éléments est possible pour n'importe quel type, même si ces éléments sont eux-mêmes des tableaux.
logo_writer
1
Votre explication est vraiment bonne, mais notez que l'allocation de mémoire contiguë n'est pas un avantage tant que vous n'en avez pas vraiment besoin. La mémoire contiguë est plus chère qu'une mémoire non contiguë. Pour les tableaux 2D simples, il n'y a pas de différence dans la disposition de la mémoire pour vous (à l'exception du nombre de lignes pour l'allocation et la désallocation), préférez donc utiliser une mémoire non contiguë.
Oleg Lokshyn