Discussion :

[dalfab]

Bonjour,

L'implémentation 2D contigüe n'est effectivement pas garantie dans la doc mais en pratique c'est très souvent le cas (voir la discussion : http://stackoverflow.com/questions/7...guous-1d-array).

Donc, pour le cas du tableau 2D statique, je ne vois pas pourquoi choisir un tableau 1D "géré à la main", qui est plus compliqué, moins robuste et dont le gain de performances n'est pas démontré (mais si quelqu'un a des benchmarks sérieux à ce sujet, je suis très intéressé...).

L'implémentation d'un tableau est garantie contiguë, donc l’implémentation d'un tableau de tableau qui reste un tableau l'est.

• La norme indique que T tab[x] <=> *(&tab[0] + x) <=> &tab[x] == (char*)tab + sizeof(T) * x
• Si T est un lui-même un tableau : &tab[y][x] == (char*)tab + sizeof(T) * y + sizeof(T') * x
• sizeof(T) est-il égal à sizeof(T')*NbColonnesDeTab ?

C'est là que le compilateur peut décider d'avoir un T plus grand pour des raisons d'alignement, afin d'optimiser.
Cela veut dire que les seuls cas où les deux formes ne sont pas synchrones correspondent à des tableaux à 2 dimensions optimisés. C'est le tableau à deux dimensions qui peut parfois être optimal!

Exemple : int tab[10][255], le compilateur pourra en réalité créer un int tab[10][256] afin d’accélérer la conversion de coordonnées.

D'où toujours préférer les tableaux à deux dimensions. Qui comme tu le dis groharpon est en plus plus robuste et plus lisible.

Dalfab

[dragonjoker59]

Effectivement dans le cas de tableaux statiques, ça devrait être sensiblement la même chose.

[bacelar]

Tout ça pour des vieux tableaux C tout pourri quand std::array existe.

Et les petits-chevaux, c'est pas un jeu de plateau ???
C'est super-pratique avec tableau à 2 dimensions, lol.
Et des jeux de plateaux qui non pas de grille carrées, je peux en trouver des dizaines.

[Iradrille]

Si les tailles sont statiques, c'est effectivement plus pratique d'utiliser un vrai tableau 2D et ce n'est pas moins performant car le compilateur va l'implémenter automatiquement sous forme de tableau 1D.

C'est là qu'est toute la différence.

Des tableaux de taille statique ? Osef, les deux sont équivalents, j'aurais (comme toi) une préférence pour les tableaux 2D puisse qu'il n'y a pas besoin de réimplémenter ça.
Des tableaux de taille inconnue ou tableau de taille statique sur lequel on accède de manière non traditionnelle aux éléments : tableaux 1D.

Le cas où le tableau 2D est supérieur n'est qu'un cas particulier.

[Invité]

[troll]

Tout ça pour des vieux tableaux C tout pourri quand std::array existe.

Surtout que std::array<std::array<int,3>,3> tab; c'est quand même vachement plus simple que int tab[3][3];.

Et les petits-chevaux, c'est pas un jeu de plateau ???
C'est super-pratique avec tableau à 2 dimensions, lol.
Et des jeux de plateaux qui non pas de grille carrées, je peux en trouver des dizaines.

J'avais compris qu'il voulait implémenter un jeu en particulier, pas tous les jeux du monde. Dans ce cas, un void* avec un malloc/free serait effectivement plus indiqué.

[/troll]

[bacelar]

Surtout que std::array<std::array<int,3>,3> tab; c'est quand même vachement plus simple que int tab[3][3];.

C'est tellement sympa les tableau à la C, ouais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
using grid = std::array<std::array<int,3>,3>;
 
...
 
grid tab;
...

C'est plus court, plus clair, ça a bien plus de fonctionnalité, les erreurs de manipulation sont détectés à la compilation, etc..., bin c'est "grid" et pas le pitoyable "int tab[3][3]".

Dans ce cas, un void* avec un malloc/free serait effectivement plus indiqué.

Utilisation de malloc/free en C++, tu viens de perdre toute crédibilité.

[Invité]

Utilisation de malloc/free en C++, tu viens de perdre toute crédibilité.

J'ignorais que j'en avais...

[koala01]

Salut,

je ne vois pas pourquoi choisir un tableau 1D "géré à la main", qui est plus compliqué, moins robuste et dont le gain de performances n'est pas démontré.

Et, heuu... Pourrais tu m'indiquer en quoi un tableau linéarisé (car c'est le terme officiel) serait plus compliqué et moins robuste qu'un vrai tableau 2D (ou nD)

Il n'y a qu'une et une seule formule (pas si) "magique" (que cela) à appliquer : indexRecherché = ligneVoulue * nombreColonnes + colonneVoulue (ou indexRecherché = colonneVoulue * nombreLignes + ligneVoulue, si tu veux du row major) et, comme on aimera de toutes façons encapsuler l'utilisation du tableau en lui même (et donc la "formule magique" qui nous permet d'accéder à l'élément recherché), que l'on appréciera toujours d'être en mesure de s'assurer que l'utilisateur de notre tableau ne fait pas de connerie en essayant d'avoir accès à un élément hors limites (ligneVoulue >= nombreLignes et / ou colonneVoulue >= nombreColonnes), on a au contraire tout intérêt à linéariser le tableau:

Même si le gain de performances reste hypothétique (ce qui reste à démontrer), on gagne en facilité pour faire la vérification des préconditions (assert(ligne < nombreLignes) et assert(colonne < nombreColonnes) au lieu de assert(ligne < tab.size() ) et assert(colonne < tab[ligne].size()), du moins, dés que chaque linge contient le même nombre de colonnes.

De plus, std::array peut éviter des problèmes si l'on connait les dimensions du tableau à la compilation, mais, si cette taille n'est connue qu'à l'exécution(et ce sera souvent le cas), nous devons -- de toutes façons -- passer par des tableaux dont la taille est gérée dynamiquement. Dans le meilleurs des cas, on utilisera un std::vector<std::vector<Data>>, dans le pire des cas, on utilisera un data ** et le jeu des allocations dynamiques de la mémoire (avec les risques inhérents à cette pratique).

Mais, dans tous les cas, si la taille n'est pas connue à la compilation, on n'a absolument aucune raison sensée de penser que les cases des différents "sous tableaux" seront effectivement contigües, alors que nous pouvons effectivement avoir cette garantie avec un tableau linéarisé, même si le nombre de lignes et le nombre de colonnes doit être précisé lors de l'exécution

[Invité]

Et, heuu... Pourrais tu m'indiquer en quoi un tableau linéarisé (car c'est le terme officiel) serait plus compliqué et moins robuste qu'un vrai tableau 2D (ou nD)

Tu trouves que T[x + W*(y + H*z)] = 42; c'est plus simple que T[x][y][z] = 42; ?

Il n'y a qu'une et une seule formule (pas si) "magique" (que cela) à appliquer : indexRecherché = ligneVoulue * nombreColonnes + colonneVoulue (ou indexRecherché = colonneVoulue * nombreLignes + ligneVoulue, si tu veux du row major)

Ça alors, je ne m'en serais jamais douté; merci pour cette leçon...

et, comme on aimera de toutes façons encapsuler l'utilisation du tableau en lui même (et donc la "formule magique" qui nous permet d'accéder à l'élément recherché), que l'on appréciera toujours d'être en mesure de s'assurer que l'utilisateur de notre tableau ne fait pas de connerie en essayant d'avoir accès à un élément hors limites (ligneVoulue >= nombreLignes et / ou colonneVoulue >= nombreColonnes), on a au contraire tout intérêt à linéariser le tableau:

Pas forcément : on peut vouloir l'encapsuler à plus haut niveau. Par exemple, dans le cas de la carte 2D qui nous intéresse ici on pourrait avoir une méthode "Carte::getCellule(int, int)" qui s'occupe du calcul d'indice sans avoir à implémenter une abstraction de tableau 2D supplémentaire.

Même si le gain de performances reste hypothétique (ce qui reste à démontrer), on gagne en facilité pour faire la vérification des préconditions (assert(ligne < nombreLignes) et assert(colonne < nombreColonnes) au lieu de assert(ligne < tab.size() ) et assert(colonne < tab[ligne].size()), du moins, dés que chaque linge contient le même nombre de colonnes.

Là ce n'est plus de la mauvaise foi, c'est carrément de la cirrhose... À partir du moment où on utilise des tableaux statiques (puisque c'est le cas de la question posée initialement), on connait les tailles et on a quelques constantes dans un coin.

De plus, std::array peut éviter des problèmes si l'on connait les dimensions du tableau à la compilation, mais, si cette taille n'est connue qu'à l'exécution(et ce sera souvent le cas), nous devons -- de toutes façons -- passer par des tableaux dont la taille est gérée dynamiquement. Dans le meilleurs des cas, on utilisera un std::vector<std::vector<Data>>, dans le pire des cas, on utilisera un data ** et le jeu des allocations dynamiques de la mémoire (avec les risques inhérents à cette pratique).

Mais, dans tous les cas, si la taille n'est pas connue à la compilation, on n'a absolument aucune raison sensée de penser que les cases des différents "sous tableaux" seront effectivement contigües, alors que nous pouvons effectivement avoir cette garantie avec un tableau linéarisé, même si le nombre de lignes et le nombre de colonnes doit être précisé lors de l'exécution

Tout à fait d'accord, mais il me semble que le problème traité ici est d'implémenter un jeu particulier avec un tableau statique tout simple et non d'implémenter tous les jeux existants ou de pouvoir jouer aux échecs sur un plateau 42x42...

[koala01]

Tu trouves que T[x + W*(y + H*z)] = 42; c'est plus simple que T[x][y][z] = 42; ?

Comme il s'agit de mettre la formule dans une seule et unique fonction (allez, dans deux pour avoir la version constante et non constante) et que l'on peut tester cette fonction "sous toutes ses coutures", oui, c'est beaucoup plus sécurisant

Ça alors, je ne m'en serais jamais douté; merci pour cette leçon...

Merci pour la note d'ironie

Pas forcément : on peut vouloir l'encapsuler à plus haut niveau. Par exemple, dans le cas de la carte 2D qui nous intéresse ici on pourrait avoir une méthode "Carte::getCellule(int, int)" qui s'occupe du calcul d'indice sans avoir à implémenter une abstraction de tableau 2D supplémentaire.

Mais là, ton tableau (qu'il soit linéarisé ou non) se transforme en détail d'implémentation... hors sujet

Là ce n'est plus de la mauvaise foi, c'est carrément de la cirrhose... À partir du moment où on utilise des tableaux statiques (puisque c'est le cas de la question posée initialement), on connait les tailles et on a quelques constantes dans un coin.

Où est la mauvaise foie lorsque tu coupe volontairement les paragraphes qui suivent alors que c'est ceux qui expliquent mon point de vue (et avec lesquels tu indiques être d'accord, entre parenthèses )