Les tableaux 2D en C++

Ce qui suit présume que la lectrice/ le lecteur connaît et comprend les tableaux à une dimension en C++, les pointeurs et l'allocation dynamique de mémoire avec new et delete. Si vous ne connaissez pas ces éléments de programmation, alors vous trouverez ceci un peu aride et je doute que vous en tiriez véritablement profit.

Les exemples ci-dessous utilisent des tableaux de int, mais on pourrait utiliser n'importe quel type, y compris des objets (dans la mesure où ces objets possèdent un constructeur par défaut, car celui-ci sera appelé par le compilateur lors de la création de chaque tableau pour en initialiser les éléments).

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 :

Déclaration automatique d'un tableau 1D Déclaration automatique d'un tableau 2D
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++.

Déclaration automatique d'un tableau 1D Allocation dynamique d'un tableau 1D
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
   }
}

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].

Dans le même ordre d'idées, on aura aussi la relation tableau1D[i] == *(tableau1D+i) pour tout i entier, positif ou non (prudence!).

En réalité, les opérations sur des tableaux à l'aide d'indices ne sont que des manières abrégées de réaliser une opération d'artihmétique de pointeurs sur le tableau, pointeur sur son premier élément, suivi d'un déréférencement du pointeur résultant.

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) :

Allocation dynamique d'un tableau 1D Allocation dynamique d'un tableau 2D
int main()
{
   int n = 10; // pour simplifier
   int *tableau1D = new int[n];
   // utiliser tableau1D...
   delete [] tableau1D;
}
int main()
{
   int m = 3,
       n = 4;
   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;
}

Remarquez, dans l'exemple de droite, que chaque tableau est détruit sur une base individuelle puis le tableau de tableaux est détruit à son tour, et ce dans l'ordre.

Un ancien étudiant (brillant) et ami, André Caron, m'a écrit un petit mot pour me signaler que ce code pourrait être resserré en initialisant les pointeurs du premier niveau (chaque tableau2D[i]) à nullptr avant de commencer à les initialiser à l'aide d'invocations aux mécanismes d'allocation dynamique de mémoire. Merci!

int main()
{
   int m = 3,
       n = 4;
   int **tableau2D = new int* [m];
   for (int i = 0; i < m; i++)
      tableau2D[i] = 0;
   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 0; 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 l'opérateur typedef 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 le type ptr_int, créé par typedef, pour simplifier l'usage d'astérisques :

Allocation dynamique d'un tableau 2D Allocation dynamique d'un tableau 2D (avec typedef)
int main()
{
   int m = 3,
       n = 4;
   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;
}
typedef int* ptr_int;
int main()
{
   int m = 3,
       n = 4;
   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 :

Allocation dynamique d'un tableau 1D Équivalent avec un vecteur standard Autre équivalent avec un vecteur standard (plus simple)
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 vecteurm, 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] << ' ';
}

Si vous avez pris(e) connaisance de la théorie des itérateurs (pour lequel une brève introduction est offerte ici), vous savez déjà qu'il est possible de faire encore beaucoup mieux.

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 :

Allocation dynamique d'un tableau 2D ÉÉquivalent avec un vecteur standard
int main()
{
   int m = 3,
       n = 4;
   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;
   int m = 3,
       n = 4;
   vector<vector<int>> v(n);
   for (int i = 0; i < m; i++)
      v[i].resize(n);
   // 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.

Le sympathique Benoît Bayol m'a écrit (merci!) pour me souligner que l'utilisation du vecteur proposée ci-dessus n'est pas optimale. Il a bien raison, d'ailleurs; pour un aperçu de plus saines pratiques avec ce conteneur, jetez un coup d'oeil sur quelques-uns des articles plus poussés du présent site, incluant entre autres ../../Sources/comparatif_vecteur_tableau.html.


Valid XHTML 1.0 Transitional

CSS Valide !