Les tableaux 2D en C++

Une question technico-technique qui revient souvent de la part des étudiant(e)s (et des informaticien(ne)s relativement expérimenté(e)s) est : « Comment peut-on allouer dynamiquement un tableau 2D en C++? » La question peut être élargie à un tableau à plus de deux dimensions, évidemment, mais vous pourrez sans doute déduire une stratégie simple pour atteindre votre but si tel est le cas.

L'allocation automatique d'un tableau 2D en C++ est un problème relativement simple à résoudre si on sait déclarer et manipuler les tableaux à une seule dimension :

int main() {
   const int N = 100; // arbitraire
   int tableau1D[N];
   // utiliser tableau1D
}

int main() {
   const int M = 50,
             N = 100; // arbitraire
   int tableau2D[M][N];
   // utiliser tableau2D
}

De même, l'allocation dynamique d'un tableau 1D est relativement simple dans la mesure où l'on garde en tête qu'en C et en C++, un tableau est un pointeur vers son premier élément. Notez toutefois que l'exemple de droite n'est pas banal, au sens où il alloue M*N*sizeof(int) bytes sur la pile. Si M et N croissent, il est facile de déborder de la pile.

L'exemple ci-dessous met en relief les similitudes et les différences entre allocation automatique et dynamique d'un tableau à une seule dimension en C++.

int main() {
   const int N = 100; // arbitraire
   int tableau1D[N];
   // utiliser tableau1D
}

int main() {
   int n;
   while (cin >> n && n < 0)
      ;
   if (cin) {
      int *tableau1D = new int[n];
      // utiliser tableau1D...
      delete [] tableau1D;
      // le [] est important
   }
}

int main() {
   int n;
   while (cin >> n && n < 0)
      ;
   if (cin) {
      // le [] est important
      unique_ptr<int[]> tableau1D{ new int[n] };
      // utiliser tableau1D...
   } // delete []implicite
}

On voit ici que tableau1D est un int* (pointeur de int), et qu'il pointera au premier élément du tableau. En effet, une fois new fait, on aura tableau1D == &tableau1D[0] ce qui signifiera que tableau1D pointe à l'adresse de tableau1D[0].

La nature même de l'allocation dynamique nous dit que nous devrons, en l'absence d'une collecte automatique d'ordures en C++, libérer la mémoire obtenue lors de l'appel à l'opérateur new[] (donc de l'opérateur new applicable à un tableau) à l'aide de l'opérateur delete[].

Si, en C ou en C++, un tableau est un pointeur à son premier élément, convenons aussi qu'un tableau 2D y est un tableau de tableaux. Ainsi, pour créer dynamiquement un tableau 2D, nous aurons besoin d'un pointeur sur le premier élément du premier tableau 1D, donc d'un pointeur de pointeur (ici, un int**, où les deux astérisques après le type int signifient pointeur de pointeur de int).

On créera donc dynamiquement un tableau de M par N éléments de type int comme ceci (j'ai donné des valeurs arbitraires à M et à N pour simplifier la présentation) :

int main() {
   if (int n; cin >> n) {
      int *tableau1D = new int[n];
      // utiliser tableau1D...
      delete [] tableau1D;
   }
}

int main() {
   if (int m, n; cin >> m >> n) {
      int **tableau2D = new int*[m];
      for (int i = 0; i < m; i++)
         tableau2D[i] = new int[n];
      // utiliser tableau2D...
      for (int i = 0; i < m; i++)
         delete[] tableau2D[i];
      delete[] tableau2D;
   }
}

int main() {
   if (int m, n; cin >> m >> n) {
      int **tableau2D = new int* [m];
      for (int i = 0; i < m; i++)
         tableau2D[i] = nullptr;
      for (int i = 0; i < m; i++)
         tableau2D[i] = new int[n];
      // utiliser tableau2D...
      for (int i = 0; i < m; i++)
         delete [] tableau2D[i]; // sans danger
      delete [] tableau2D;
   }
}

Ceci aurait le grand avantage de faciliter la destruction de ces tableaux en fin de parcours : delete nullptr; est inoffensif en C++, mais delete sur un pointeur quelconque non nul est explosif. L'impact se ferait surtout sentir si nous mettions en place des mécanismes pour libérer les tableaux dans un destructeur, à l'aide de l'idiome RAII.

Notez que, pour que la manoeuvre soit utile, il faut initialiser tous les pointeurs de premier niveau à nullptr avant de commencer l'allocation dynamique de mémoire pour le deuxième niveau.

Remarquez au passage qu'il serait possible d'avoir des dimensions différentes pour chaque élément de tableau2D (chaque tableau2D[i], qui est un tableau à part entière), dans la mesure évidemment où on se souvient de ces dimensions – en C et en C++, les tableaux sont des structures de données très efficaces et très primitives, mais la taille d'un tableau n'est pas inscrite dans le tableau.

Les gens qui n'aiment pas les pointeurs de pointeurs vont parfois utiliser typedef ou using pour se créer un alias qui allégera un peu la syntaxe. Vous comprendrez sans doute son effet à l'aide de l'exemple ci-dessous, qui est identique au précédent à ceci près qu'on y utilise l'alias ptr_int pour simplifier l'usage d'astérisques :

int main() {
   if(int m, n; cin >> m >> n) {
      int **tableau2D = new int*[m];
      for (int i = 0; i < m; i++)
         tableau2D[i] = new int[n];
      // utiliser tableau2D...
      for (int i = 0; i < m; i++)
         delete[] tableau2D[i];
      delete[] tableau2D;
   }
}

int main() {
   typedef int* ptr_int;
   if(int m, n; cin >> m >> n) {
      ptr_int *tableau2D = new ptr_int[m];
      for (int i = 0; i < m; i++)
         tableau2D[i] = new int[n];
      // utiliser tableau2D...
      for (int i = 0; i < m; i++)
         delete[] tableau2D[i];
      delete[] tableau2D;
   }
}

int main() {
   using ptr_int = int*;
   if(int m, n; cin >> m >> n) {
      ptr_int *tableau2D = new ptr_int[m];
      for (int i = 0; i < m; i++)
         tableau2D[i] = new int[n];
      // utiliser tableau2D...
      for (int i = 0; i < m; i++)
         delete[] tableau2D[i];
      delete[] tableau2D;
   }
}

Et voilà. En espérant que tout cela soit éclairant pour vous.

Remarque en terminant

Le langage C++ est un langage orienté objet qu'on n'exploite pas assez souvent au maximum de ses possibilités (pourtant, il est si puissant!). Parmi les outils extrêmement puissants et rapides que nous proposent les bibliothèques standard de ce langage, on trouve le type std::vector qui permet de créer des tableaux dynamiques de taille variable et qui offre le même niveau de performance que les tableaux bruts, tout en évitant tous les écueils potentiels associés à la libération de la mémoire.

Présumant qu'on veuille strictement la même fonctionnalité que celle obtenue dans les exemples 1D ci-dessus mais en utilisant des vecteurs, on pourrait écrire ce qui suit :

int main() {
   int n = 10; // pour simplifier
   int *tableau1D = new int[n];
   // utiliser tableau1D...
   delete[] tableau1D;
}

#include <vector>
int main() {
   using std::vector;
   int n = 10; // pour simplifier
   vector<int> v;
   v.resize(n);
   // utiliser v...
}

#include <vector>
int main() {
   using std::vector;
   int n = 10; // pour simplifier
   vector<int> v(n);
   // utiliser v...
}

Notez que ceci présume qu'on connaisse le nombre d'éléments requis avant de créer le tableau ou le vecteur, même si ce nombre est, comme dans note exemple, une variable (car si la taille est une constante dont la valeur est connue à la compilation, alors l'allocation dynamique de mémoire est inutile et simplement coûteuse, sauf dans le cas où cette taille est considérable et dépasse la capacité de la pile d'exécution du programme.

Si le nombre d'éléments est découvert en cours de route, ou s'il faut ajouter des éléments dans le tableau ou le vecteur sans savoir la taille au préalable), alors le vecteur offre d'énormes avantages de vitesse et de simplicité en comparaison avec les tableaux.

Pour vous le prouver, essayez d'écrire un programme C++ qui lit des entiers jusqu'à ce que l'usager entre un entier négatif, les garde dans un tableau et les affiche en ordre inverse de celui dans lequel ils ont été entrés. C'est un problème qui demande beaucoup de manipulations, de créations de tableaux intermédiaires, de copie de tableaux et ainsi de suite. Avec un vecteur, on a simplement :

#include <vector>
#include <iostream>
int main() {
   using namespace std;
   vector<int> v;
   // lecture des entiers et insertion dans le vecteur
   for (int val; cin >> val && val >= 0; )
      // ajoute val au vecteur v et l'agrandit au besoin
      v.push_back(val);
   // affichage des éléments de v du dernier au premier inclusivement
   for (int i = static_cast<int>(v.size()); --i >= 0; )
      cout << v[i] << ' ';
}

De même, pour obtenir avec des vecteurs standards la même fonctionnalité que celle obtenue dans les exemples 2D ci-dessus, on pourrait écrire ce qui suit :

int main() {
   if(int m, n; cin >> m >> n) {
      int **tableau2D = new int* [m];
      for (int i = 0; i < m; i++)
         tableau2D[i] = new int[n];
      // utiliser tableau2D...
      for (int i = 0; i < m; i++)
         delete [] tableau2D[i];
      delete [] tableau2D;
   }
}

#include <vector>
int main() {
   using std::vector;
   if(int m, n; cin >> m >> n) {
      vector<vector<int>> v(n);
      for (int i = 0; i < m; i++)
         v[i].resize(n);
      // utiliser v...
   }
}

#include <vector>
int main() {
   using std::vector;
   if(int m, n; cin >> m >> n) {
      vector<vector<int>> v(n, vector<int>(m));
      // utiliser v...
   }
}

Ce code pourrait d'ailleurs être simplifié (et fortement amélioré) à l'aide des algorithmes standard de la bibliothèque <algorithm>, mais nous éviterons ici ce sujet.

Un avantage très net des vecteurs ici tient au fait que chaque vecteur est un objet à part entière, avec ses propres attributs et ses propres méthodes, ce qui implique qu'on peut connaître dynamiquement (à l'exécution) la taille de chaque vecteur (en appelant sa méthode size()). Ceci permettrait de gérer un vecteur de vecteurs dont la taille varie avec une grande simplicité, ce qui serait ardu avec des tableaux bruts.

En général, dans du code de production, on privilégiera les vecteurs aux tableaux dans la mesure du possible. Contrairement à ce qu'on pourrait penser, il n'y a pratiquement aucune pénalité à utiliser un vecteur standard plutôt qu'un tableau, et si le besoin se fait sentir de rédiger un tableau de taille dynamique, alors il est très peu probable que vous parveniez à battre (dans le cas général) les gens oeuvrant sur la bibliothèque standard du langage et dont le design et l'optimisation de conteneurs de d'algorithmes est une mission à plein temps.

Lectures complémentaires

Quelques liens pour enrichir le propos.

• En 2019, Paul Silisteanu propose un article sur le même sujet (ou presque) : https://solarianprogrammer.com/2019/03/27/c-programming-passing-multi-dimensional-array-to-function/