Tableaux à deux dimensions

Tableaux à deux dimensions

Lignes et colonnes

Un tableau à deux dimensions de $m$ lignes et $n$ colonnes est une collection de $m \cdot n$ données du même type, chacune désignée par deux indices : celui de sa ligne, $i$, avec $0 \leq i < m$, et celui de sa colonne, $j$, avec $0 \leq j < n$. Les mathématiques l’appellent matrice et écrivent $a_{ij}$ ; le cours Algèbre et géométrie II étudie les matrices et leurs opérations, et cette leçon en écrit quelques-unes sous forme de programmes. L’ordre des indices ne souffre aucune exception : d’abord la ligne, ensuite la colonne. Les confondre est l’erreur la plus fréquente avec ces tableaux, et le compilateur ne peut pas la signaler, car les deux indices sont du même type.

La leçon Vecteurs a présenté la séquence de taille variable. S’il en est ainsi, un tableau à deux dimensions est une séquence de lignes, et chaque ligne est à son tour une séquence : un vecteur dont les éléments sont des vecteurs, std::vector<std::vector<int>>.

#include <print>#include <vector>​int main(){    std::vector<std::vector<int>> table{{1, 2, 3}, {4, 5, 6}};    std::println("{}", table);    std::println("Lignes {}, colonnes {}", table.size(), table[0].size());    std::println("Ligne 1 : {} ; ligne 1, colonne 2 : {}", table[1], table[1][2]);    table[0][1] = 20;    for (const std::vector<int>& row : table) {        for (const int value : row) {            std::print("{:>4}", value);        }        std::println("");    }    const std::vector<std::vector<int>> zeros(3, std::vector<int>(4));    std::println("{}", zeros);}

[[1, 2, 3], [4, 5, 6]]Lignes 2, colonnes 3Ligne 1 : [4, 5, 6] ; ligne 1, colonne 2 : 6   1  20   3   4   5   6[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

La ligne 6 écrit le tableau comme une liste de lignes, chacune entre ses accolades, et le formatage des ranges l’affiche de la même façon, avec des crochets. table.size() est le nombre de lignes, et table[0].size(), la longueur de la première, qui dans un tableau bien formé est le nombre de colonnes. table[1] est la ligne 1 entière, un std::vector<int>, et table[1][2], l’élément 2 de cette ligne : le double indice n’est pas une opération nouvelle, mais deux accès successifs ; le premier choisit la ligne et le second, à l’intérieur de celle-ci, la colonne. Les lignes 11 à 16 écrivent le tableau sous forme de grille avec deux for basés sur un intervalle imbriqués ; la ligne du tableau est prise par référence constante pour ne pas la copier à chaque itération. La ligne 17 crée un tableau de 3 sur 4 rempli de zéros : avec des parenthèses, comme dans la leçon Vecteurs, on demande 3 copies d’une ligne de quatre zéros.

Lignes de longueurs différentes

Rien n’oblige les lignes d’un vecteur de vecteurs à avoir la même longueur : chacune est un vecteur indépendant. C’est parfois ce que l’on veut, comme dans le triangle de Pascal ; mais dans un tableau à deux dimensions, rectangulaire par définition, une ligne plus courte est une erreur des données, et le programme qui utilise table[0].size() comme nombre de colonnes lit hors de celle-ci. Un tableau qui vient de l’extérieur doit donc être vérifié.

#include <print>#include <vector>​// Précondition : aucune.// Postcondition : renvoie true si table a au moins une ligne et si toutes// ses lignes ont la longueur de la première.bool isRectangular(const std::vector<std::vector<int>>& table){    if (table.empty()) {        return false;    }    for (const std::vector<int>& row : table) {        if (row.size() != table[0].size()) {            return false;        }    }    return true;}​int main(){    const std::vector<std::vector<int>> pascal{{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}};    const std::vector<std::vector<int>> grid{{1, 2, 3}, {4, 5, 6}};    std::println("{} {}", pascal, isRectangular(pascal));    std::println("{} {}", grid, isRectangular(grid));}

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]] false[[1, 2, 3], [4, 5, 6]] true

La fonction exclut le tableau sans lignes, dans lequel table[0] n’existe pas. Les fonctions de cette leçon qui lisent table[0].size() exigent dans leur précondition un tableau rectangulaire et non vide, et isRectangular permet de le garantir.

Le tableau de tableaux de taille fixe

Quand les dimensions sont connues à la compilation (un échiquier, un carré magique), le tableau à deux dimensions peut être un std::array de std::array : std::array<std::array<int, 3>, 3> se lit de l’intérieur vers l’extérieur, « 3 lignes de 3 entiers ». Le carré magique d’ordre 3, dont les lignes, les colonnes et les diagonales ont pour somme 15, sert d’exemple.

#include <array>#include <print>​int main(){    constexpr std::array<std::array<int, 3>, 3> magic{{        {2, 7, 6},        {9, 5, 1},        {4, 3, 8},    }};    std::println("{}", magic);    std::println("Centre {}, {} octets", magic[1][1], sizeof(magic));}

[[2, 7, 6], [9, 5, 1], [4, 3, 8]]Centre 5, 36 octets

Les accolades sont au nombre de trois à chaque extrémité. std::array a un seul membre, un tableau C, de sorte que l’accolade extérieure est celle de std::array, la deuxième celle de ce tableau C intérieur, et seule la troisième celle de chaque ligne. Avec deux accolades, la première ligne est prise comme initialiseur du tableau C intérieur, et la seconde n’a plus rien à initialiser.

#include <array>#include <print>​int main(){    const std::array<std::array<int, 3>, 2> table{{1, 2, 3}, {4, 5, 6}};    std::println("{}", table);}

main.cpp: In function ‘int main()’:main.cpp:6:71: error: too many initializers for ‘const std::array<std::array<int, 3>, 2>’    6 |     const std::array<std::array<int, 3>, 2> table{{1, 2, 3}, {4, 5, 6}};      |                                                                       ^

Too many initializers : la liste {4, 5, 6} est de trop. La liste plate, {1, 2, 3, 4, 5, 6}, compile aussi et remplit les lignes dans l’ordre, mais elle cache la forme du tableau ; le cours écrit les trois accolades.

Les 36 octets du sizeof sont ceux de neuf int de 4 octets (la taille habituelle, que la norme ne garantit pas), sans rien d’autre : le tableau de tableaux range les lignes l’une après l’autre dans un seul bloc. Le vecteur de vecteurs, en revanche, demande un bloc par ligne, en plus de celui des lignes, et ces blocs n’ont aucune raison d’être contigus. Le choix suit donc la règle des leçons Tableaux de taille fixe et Vecteurs.

• Si les deux dimensions sont connues à la compilation, le tableau de tableaux de taille fixe : un seul bloc, la forme rectangulaire garantie par le type et la possibilité de constexpr.
• Si l’une d’elles n’est connue qu’à l’exécution, le vecteur de vecteurs, avec l’obligation de vérifier que les lignes ont la même longueur, ou le vecteur plat de la dernière section.