Statique ou dynamique ?

Bonjour,

Je suis en train de réaliser un petit Morpion à titre d'exercice. Je représente la grille par un tableau de char et une question me taraude. Dans la mesure où la grille est de taille fixe, est-ce qu'il vaut mieux que j'utilise un char[9] ou un vector<char> ?

Je connaissais pas array, c'est vrai que ça colle plutôt bien à ce que je cherche.

J'ai une classe Player, est-ce ça peut être judicieux de faire un array<Player*, 9> ?

Je ne suis pas sur que "player" soit le bon terme. Tes joueurs ne sont pas sur le plateau de jeu a priori.

A priori, pas besoin de pointeur (et surtout pas de pointeur nu)

Ce que je pensais, c'était faire pointer la case vers le joueur qui a joué sur cette case, parce que Player à un attribut token, le caractère pour afficher ses coups dans la grille.

En soi, ce n'est pas "mauvais" comme choix, mais quel intérêt d'avoir un pointeur vers player pour aller chercher le caractère a afficher plutôt que de mettre directement le caractère dans la grille ?

J'y avais pensé, mais je perds le lien entre l'information et sa soure à ce moment-là, non ?

Que veux tu faire de ce lien ?

Si tu veux t'autoriser des grilles dont la taille serait un paramètre d'exécution, tu peux tout à fait prendre une structure dynamique. Elle serait même conseillée. Ceci dit, même pour du statique, j'avoue avoir pris un vecteur.

Sinon, en effet, nul besoin de pointeur à ce niveau pour ce type de jeu.

A titre d'information, il peut être intéressant ici d'utiliser un std::array<3, std::array<3, Whatever>>. Cela permet de manipuler effectivement une grille grid[y][x].

A ne surtout pas faire dans le cas d'un std::vector (!).

La raison m'intéresse. Un problème de performance ? Je sais qu'on conseille un seul std::vector de taille N * M qu'un std::vector contenant N std::vector de taille M dans le cas où on représente une matrice par exemple.

La raison m'intéresse. Un problème de performance ?

Exactement ! Aussi bien au niveau mémoire qu'en temps d'accès.

Un vecteur de taille n*m requière n + 1 allocation, donc hoverhead et dispersion de la mémoire plus importante. De plus, les données ne sont pas alignées et il faut 2 déréférencements pour accéder à un élément.

Si on veut utiliser une matrice alignée comme un tableau 2d, il est préférable de retourner une vue (voir std::array_view).

Réfléchis à la manière dont est structurée un vecteur en mémoire et ce qui se passe quand on change la taille et qu'elle dépasse alors la capacité du vecteur.

Plusieurs problématiques en réalité.

La première c'est la place que ça prend en mémoire : un vector de vector de T de taille N*M, c'est tout d'abord sizeof(vector) + N*sizeof(vector) + N*M*sizeof(T) octets, tandis qu'un vector de T de taille N*M, c'est seulement sizeof(vector) + N*M*sizeof(T).

La deuxième c'est la discontinuité du stockage des données : en effet, autant un vector simple s'assure que ses données sont stockées de façon contigüe en mémoire, ce qui assure les meilleures vitesses d'accès puisque si j'accède à une case X, la case X+L est dans une grande majorité des cas dans le cache ; tandis que dans le cas d'un vector de vector, on se prend de façon presque inévitable un cache miss à chaque fin de ligne.

La troisième, eh bien le nombre d'allocations nécessaires sur le tas (heap), ce qui est habituellement une opération lente (sauf si on s'amuse à gérer un pool de mémoire et des allocateurs personnalisés sur les vector), à savoir N+1 allocations pour un vector de vector, contre seulement 1 allocation pour un vector simple.

La quatrième, et cette fois-ci elle est en défaveur du vector simple, c'est la simplicité d'utilisation. Il est mille fois plus agréable de travailler avec des vector de vector, puisqu'on manipule effectivement un grid[y][x], tandis qu'il faut mettre des formules de partout avec un vector simple : grid[y*grid[0].size() + x], ce qui est un facteur d'erreurs important. Une solution peut être une classe pour encapsuler cela, et comme le dit jo_link_noir std::array_view semble être la solution standard qui se profile à l'horizon. Il faudra toutefois attendre la prochaine version du standard (C++17 si tout va bien) pour en disposer.