Version imprimable
Bonjour à tous,
Alors j'aimerai savoir quelle est la solution la plus performante en matière de vitesse. J'hésite entre les deux pour une gestion des objets dans un jeux-vidéo 2D. C'est-à-dire qu'il y a beaucoup de suppression d'ajout, enfin beaucoup de manipulation.
Quel est donc votre avis sur le problème ?
Merci d'avance
En première estimation comme cela:
vector:
- insertion en fin, rapide
- insertion en debut ou au milieu, galère.
- lecture séquentielle, rapide
- lecture par position, rapide
- suppression, galere
list:
- insertion en fin, rapide
- insertion en debut ou au milieu, rapide.
- lecture par position, galère
- lecture séquentielle, rapide
- suppression, rapide
Maintenant, tu choisis suivant que tu as plus souvent des insertions/suppressions ou alors des lecture par position.
De plus cf le tableau de choix dans la faq! (quel conteneur choisir? il me semble).
Effectivement, cette entrée de la FAQ propose un schéma pour choisir son conteneur.
Ensuite, au delà du conteneur, tu peux aussi réfléchir à la gestion des données. Pourquoi pendant la phase de jeu aurais-tu besoin de beaucoup d'ajout/suppression?
C'est parce-que des tanks peuvent être créé à tout moment, et quand il y en a un qui est détruit je préfère libérer la mémoire. Merci pour la FAQ, je n'étais pas tombé dessus.
Apparemment il suffit de voir si nous avons besoin d'accès par position et c'est ce qui fera la différence entre vector et liste chainée, c'est bien ça ?
Pas seulement. Il ne faut pas oublier non plus qu'une liste chaînée demande beaucoup d'allocations mémoire, même si on peut faire des allocateurs plus optimisés.
Un truc à voir aussi, c'est si tu as besoin de conserver l'ordre. Car sinon, tu peux facilement faire une suppression dans un vecteur: Il te suffit d'écraser (ou swapper) l'élément avec le dernier, puis virer le dernier...
De même, un ajout n'est pas nécessairement une insertion, et ce sont les insertions qui sont lentes (Typiquement en O(n)), pas les ajouts... (sauf augmentation de la capacité du tableau, bien sûr)
Ok merci beaucoup à vous pour cette aide. J'ai finalement utilisé un peu des deux.
A bientôt
On peut aussi faire une liste chaînée dont les nœuds sont stockés dans un vecteur.