Allouer correctement des tableaux multidimensionnels

Le but de cette question est de fournir une référence sur la façon d’allouer correctement des tableaux multidimensionnels de manière dynamic en C. C’est un sujet souvent mal compris et mal expliqué, même dans certains livres de programmation en C. Par conséquent, même les programmeurs C expérimentés ont du mal à faire les choses.


Mon professeur de programmation / livre / tutoriel m’a appris que la méthode correcte pour allouer de manière dynamic un tableau multidimensionnel consiste à utiliser un pointeur à l’autre.

Cependant, plusieurs grands utilisateurs sur SO me disent maintenant que c’est une mauvaise et mauvaise pratique. Ils disent que les pointeurs sur pointeurs ne sont pas des tableaux, que je ne les alloue pas réellement et que mon code est inutilement lent.

Voici comment on m’a appris à allouer des tableaux multidimensionnels:

#include  #include  #include  int** arr_alloc (size_t x, size_t y) { int** pp = malloc(sizeof(*pp) * x); assert(pp != NULL); for(size_t i=0; i<x; i++) { pp[i] = malloc(sizeof(**pp) * y); assert(pp[i] != NULL); } return pp; } int** arr_fill (int** pp, size_t x, size_t y) { for(size_t i=0; i<x; i++) { for(size_t j=0; j<y; j++) { pp[i][j] = (int)j + 1; } } return pp; } void arr_print (int** pp, size_t x, size_t y) { for(size_t i=0; i<x; i++) { for(size_t j=0; j<y; j++) { printf("%d ", pp[i][j]); } printf("\n"); } } void arr_free (int** pp, size_t x, size_t y) { (void) y; for(size_t i=0; i<x; i++) { free(pp[i]); pp[i] = NULL; } free(pp); pp = NULL; } int main (void) { size_t x = 2; size_t y = 3; int** pp; pp = arr_alloc(x, y); pp = arr_fill(pp, x, y); arr_print(pp, x, y); arr_free(pp, x, y); return 0; } 

Sortie

 1 2 3 1 2 3 

Ce code fonctionne très bien! Comment pourrait-il se tromper?

Afin de répondre à la question, nous devons d’abord clarifier certains concepts. Qu’est-ce qu’un tableau et comment peut-il être utilisé? Et quel est le code dans la question, si ce n’est un tableau?


Qu’est-ce qu’un tableau?

La définition formelle d’un tableau se trouve dans la norme C, ISO 9899: 2011 6.2.5 / 20 Types .

Un type de tableau décrit un ensemble d’objects non vides, alloué de manière contiguë, avec un type d’object membre particulier, appelé type d’élément.

En clair, un tableau est une collection d’éléments du même type, alloués de manière contiguë, dans des cellules de mémoire adjacentes.

Par exemple, un tableau de 3 entiers int arr[3] = {1,2,3}; serait alloué en mémoire comme ceci:

 +-------+-------+-------+ | | | | | 1 | 2 | 3 | | | | | +-------+-------+-------+ 

Alors qu’en est-il de la définition formelle d’un tableau multidimensionnel? En fait, c’est la même définition que celle citée ci-dessus. Cela s’applique récursivement.

Si nous allions allouer un tableau 2D, int arr[2][3] = { {1,2,3}, {1,2,3} }; il serait alloué en mémoire comme ceci:

 +-------+-------+-------+-------+-------+-------+ | | | | | | | | 1 | 2 | 3 | 1 | 2 | 3 | | | | | | | | +-------+-------+-------+-------+-------+-------+ 

Ce que nous avons dans cet exemple est en réalité un tableau de tableaux. Un tableau qui a 2 éléments, chacun d’eux un tableau de 3 entiers.


Un tableau est un type comme un autre

Les tableaux en C suivent souvent le même système de types que les variables normales. Comme indiqué ci-dessus, vous pouvez avoir un tableau de tableaux, tout comme un tableau de tout autre type.

Vous pouvez également appliquer le même type d’arithmétique de pointeur à des tableaux de dimension n et à des tableaux simples à une dimension. Avec des tableaux unidimensionnels réguliers, l’application de l’arithmétique de pointeur devrait être sortingviale:

 int arr[3] = {1,2,3}; int* ptr = arr; // integer pointer to the first element for(size_t i=0; i<3; i++) { printf("%d ", *ptr); // print contents ptr++; // set pointer to point at the next element } 

Ceci a été rendu possible grâce à la "décomposition de masortingce". Lorsque arr est utilisé dans une expression, il se "décompose" en un pointeur sur le premier élément.

De même, nous pouvons utiliser le même type d’arithmétique de pointeur pour parcourir un tableau de tableaux en utilisant un pointeur de tableau :

 int arr[2][3] = { {1,2,3}, {1,2,3} }; int (*ptr)[3] = arr; // int array pointer to the first element, which is an int[3] array for(size_t i=0; i<2; i++) { printf("%d %d %d\n", (*ptr)[0], (*ptr)[1], (*ptr)[2]); // print contents ptr++; // set pointer to point at the next element } 

Encore une fois, il y avait la décomposition du tableau. La variable arr qui était de type int [2][3] s'est décomposée en un pointeur sur le premier élément. Le premier élément était un int [3] et un pointeur sur un tel élément est déclaré int(*)[3] - un pointeur de tableau.

Comprendre les pointeurs sur les tableaux et leur décomposition est nécessaire pour travailler avec des tableaux multidimensionnels.


Il y a plus de cas où les tableaux se comportent comme des variables normales. L'opérateur sizeof fonctionne de la même manière pour les tableaux (non-VLA) que pour les variables régulières. Exemples pour un système 32 bits:

int x; printf("%zu", sizeof(x)); impressions 4 .
int arr[3] = {1,2,3}; printf("%zu", sizeof(arr)); imprime 12 (3 * 4 = 12)
int arr[2][3] = { {1,2,3}, {1,2,3} }; printf("%zu", sizeof(arr)); imprime 24 (2 * 3 * 4 = 24)


Comme tout autre type, les tableaux peuvent être utilisés avec des fonctions de bibliothèque et des API génériques. Comme les tableaux remplissent l’obligation d’être alloués de manière contiguë, on peut par exemple les copier en toute sécurité avec memcpy :

 int arr_a[3] = {1,2,3}; int arr_b[3]; memcpy(arr_b, arr_a, sizeof(arr_a)); 

L'allocation contiguë explique également pourquoi d'autres fonctions de bibliothèque standard similaires, telles que memset , strcpy , bsearch et qsort fonctionnent. Ils sont conçus pour fonctionner sur des tableaux alloués de manière contiguë. Ainsi, si vous avez un tableau multidimensionnel, vous pouvez le rechercher efficacement et le sortinger avec bsearch et qsort , ce qui vous évite de mettre en place une recherche binary et un sorting rapide vous-même, réinventant ainsi la roue de chaque projet.

Toutes les consistances ci-dessus entre les tableaux et les autres types sont une très bonne chose dont nous voulons tirer parti, en particulier lors de la programmation générique.


Quel est le problème point à point, sinon un tableau?

Revenons maintenant au code de la question, qui utilisait une syntaxe différente avec un pointeur à pointeur. Il n'y a rien de mystérieux à ce sujet. C’est un pointeur à saisir, pas plus pas moins. Ce n'est pas un tableau. Ce n'est pas un tableau 2D. Ssortingctement parlant, il ne peut pas être utilisé pour pointer un tableau, ni pour pointer un tableau 2D.

Un pointeur à pointeur peut toutefois être utilisé pour pointer sur le premier élément d'un tableau de pointeurs, au lieu de pointer sur le tableau dans son ensemble. Et c’est la façon dont il est utilisé dans la question - comme moyen d’émuler un pointeur de tableau. Dans la question, il est utilisé pour pointer sur un tableau de 2 pointeurs. Et puis chacun des 2 pointeurs est utilisé pour pointer un tableau de 3 entiers.

C'est ce que l'on appelle une table de correspondance, qui est une sorte de type de données abstrait (ADT), ce qui diffère du concept de niveau inférieur des tableaux simples. La principale différence est la façon dont la table de recherche est allouée:

 +------------+ | | | 0x12340000 | | | +------------+ | | v +------------+ +-------+-------+-------+ | | | | | | | 0x22223333 |---->| 1 | 2 | 3 | | | | | | | +------------+ +-------+-------+-------+ | | | 0xAAAABBBB |--+ | | | +------------+ | | | +-------+-------+-------+ | | | | | +->| 1 | 2 | 3 | | | | | +-------+-------+-------+ 

Les adresses 32 bits de cet exemple sont composées. La zone 0x12340000 représente le pointeur à pointeur. Il contient l'adresse 0x12340000 du premier élément d'un tableau de pointeurs. Chaque pointeur de ce tableau contient à son tour une adresse pointant sur le premier élément d'un tableau d'entiers.

Et voici où les problèmes commencent.


Problèmes avec la version de la table de recherche

La table de consultation est dispersée dans toute la mémoire. La mémoire n'est pas allouée de manière contiguë dans les cellules adjacentes, car chaque appel à malloc donne une nouvelle zone mémoire, qui n'est pas nécessairement située de manière adjacente aux autres. Cela nous pose de nombreux problèmes:

  • Nous ne pouvons pas utiliser l'arithmétique de pointeur comme prévu. Nous pouvons utiliser une forme d'arithmétique de pointeur pour indexer et accéder aux éléments de la table de recherche, mais nous ne pouvons pas le faire à l'aide de pointeurs de tableau.

  • Nous ne pouvons pas utiliser l'opérateur sizeof. Utilisé sur le pointeur à pointeur, il nous donnerait la taille d'un pointeur à pointeur. Utilisé pour le premier élément pointé, cela nous donnerait la taille d’un pointeur. Ni l'un ni l'autre n'a la taille d'un tableau.

  • Nous ne pouvons pas utiliser les fonctions de bibliothèque standard qui excluent un type de tableau ( memcpy , memset , strcpy , bsearch , qsort et ainsi de suite). Toutes ces fonctions supposent que les tableaux soient entrés, avec des données allouées de manière contiguë. Les appeler avec notre table de consultation en tant que paramètre entraînerait des bogues de comportement non définis, tels que des blocages de programmes.

  • Des appels répétés de malloc pour allouer plusieurs segments entraînent une fragmentation du tas, ce qui entraîne une mauvaise utilisation de la mémoire RAM.

  • Étant donné que la mémoire est dispersée, la CPU ne peut pas utiliser la mémoire cache lors d'une itération dans la table de consultation. L'utilisation efficace du cache de données nécessite un bloc de mémoire contigu qui est itéré de haut en bas. Cela signifie que la table de consultation, de par sa conception, a un temps d'access beaucoup plus long qu'un tableau multidimensionnel réel.

  • Pour chaque appel à malloc (), le code de la bibliothèque qui gère le segment de mémoire doit calculer s’il ya de l’espace libre. De même pour chaque appel à free (), il y a un code overhead qui doit être exécuté. Par conséquent, il est souvent préférable d’appeler le moins possible ces fonctions pour des performances optimales.


Les tables de recherche sont-elles toutes mauvaises?

Comme nous pouvons le constater, les tables de correspondance basées sur des pointeurs posent de nombreux problèmes. Mais ils ne sont pas tous mauvais, c'est un outil comme un autre. Il doit juste être utilisé pour le bon but. Si vous recherchez un tableau multi-dimensionnel, qui devrait être utilisé comme tableau, les tables de recherche sont clairement le mauvais outil. Mais ils peuvent être utilisés à d'autres fins.

Une table de correspondance est le bon choix lorsque vous avez besoin que toutes les dimensions aient des tailles complètement variables, individuellement. Un tel conteneur peut être pratique pour, par exemple, créer une liste de chaînes C. Il est alors souvent justifié de prendre la perte de performance de vitesse d’exécution mentionnée ci-dessus afin d’économiser de la mémoire.

De plus, la table de correspondance présente l'avantage de pouvoir ré-allouer des parties de la table au moment de l'exécution sans avoir à réallouer un tableau multidimensionnel complet. Si cela doit être fait fréquemment, la table de correspondance peut même surperformer le tableau multidimensionnel en termes de vitesse d'exécution. Par exemple, des tables de correspondance similaires peuvent être utilisées lors de l'implémentation d'une table de hachage chaînée.


Comment allouer correctement un tableau multi-dimensionnel dynamicment alors?

La forme la plus simple en C moderne consiste à utiliser simplement un tableau de longueur variable (VLA). int array[x][y];x et y sont des variables y on atsortingbue des valeurs dans l'exécution, la déclaration de tableau précédente. Cependant, les VLA ont une scope locale et ne persistent pas pendant toute la durée du programme - ils ont une durée de stockage automatique. Ainsi, bien que les VLA puissent être pratiques et rapides à utiliser pour les tableaux temporaires, ils ne constituent pas un remplacement universel de la table de correspondance de la question.

Pour allouer réellement un tableau multidimensionnel de manière dynamic, de manière à obtenir la durée de stockage allouée , nous devons utiliser malloc / calloc / realloc. Je vais donner un exemple ci-dessous.

En C moderne, vous utiliseriez des pointeurs de tableau sur un VLA. Vous pouvez utiliser ces pointeurs même lorsqu'aucun fichier VLA n'est présent dans le programme. L'avantage de les utiliser sur un type* standard type* ou un void* est une sécurité de type accrue. L'utilisation d'un pointeur sur un VLA vous permet également de transmettre les dimensions du tableau en tant que parameters à la fonction utilisant le tableau, ce qui le rend à la fois variable et sûr.

Malheureusement, pour utiliser les avantages d'un pointeur sur VLA, nous ne pouvons pas renvoyer ce pointeur en tant que résultat de fonction. Donc, si nous devons renvoyer un pointeur sur le tableau à l'appelant, il doit être passé en tant que paramètre (pour les raisons décrites dans Accès mémoire dynamic ne fonctionne que dans la fonction ). C'est une bonne pratique en C, mais rend le code un peu difficile à lire. Cela ressemblerait à ceci:

 void arr_alloc (size_t x, size_t y, int(**aptr)[x][y]) { *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array assert(*aptr != NULL); } 

Bien que cette syntaxe avec un pointeur vers un pointeur de tableau puisse sembler un peu étrange et intimidante, elle ne devient pas plus complexe que cela même si nous ajoutons plus de dimensions:

 void arr_alloc (size_t x, size_t y, size_t z, int(**aptr)[x][y][z]) { *aptr = malloc( sizeof(int[x][y][z]) ); // allocate a true 3D array assert(*aptr != NULL); } 

Maintenant, comparez ce code avec le code permettant d'append une dimension supplémentaire à la version de la table de recherche:

 /* Bad. Don't write code like this! */ int*** arr_alloc (size_t x, size_t y, size_t z) { int*** ppp = malloc(sizeof(*ppp) * x); assert(ppp != NULL); for(size_t i=0; i 

Maintenant, c’est un gâchis illisible de "programmation à trois écanvass". Et ne considérons même pas 4 dimensions ...


Le code complet d'une version utilisant de vrais tableaux 2D

 #include  #include  #include  void arr_alloc (size_t x, size_t y, int(**aptr)[x][y]) { *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array assert(*aptr != NULL); } void arr_fill (size_t x, size_t y, int array[x][y]) { for(size_t i=0; i 

C n’ont pas de tableaux multidimensionnels. Mais vous pourriez avoir des tableaux de tableaux (ou d’autres agrégats) et des tableaux de pointeurs.

Une approche possible consiste à raisonner avec certains types de données abstraits (peut-être en utilisant des membres de tableau flexibles , ce qui est une astuce d’implémentation, et vous pourriez utiliser d’autres approches), comme dans cette réponse .

Nous ne pouvons suggérer aucun type de données abstrait, car cela dépend du texte de vos devoirs, que nous n’avons pas. Vous devez concevoir votre type de données abstrait (sur un morceau de papier), puis l’appliquer ultérieurement.

Une fois que vous avez répertorié (sur un papier ou sur un tableau) toutes les opérations nécessaires sur votre ADT, leur mise en œuvre est simple.

Ce code fonctionne très bien! Comment pourrait-il se tromper?

Cette phrase est incohérente (fausse par rapport à quelles spécifications?) …

Je recommande de comstackr avec tous les avertissements et informations de débogage (par exemple avec gcc -Wall -Wextra -g avec GCC ), d’améliorer votre code jusqu’à ce que vous n’ayez plus d’avertissements, d’utiliser le débogueur gdb (pour comprendre ce qui se passe dans votre programme) et d’autres outils comme valgrind .