Rapidité std::vector contre liste perso
Bonjour,
Je m'occupe actuellement en créant une liste C++ ressemblant aux listes de type vector des libs std. (utilisant des template pour le type, et en utilisant le principe des listes chaînées à double sens pour le stockage).
J'en viens à quelques tests de vitesse, et je remarque que l'insertion des valeurs est plus rapide du côté de la std (pas très surprenant..) :
Pour insérer 5 000 000 de int*, ma liste prend ~ 1.94 secondes, alors que std::vector ne prend que 1.08 secondes.
J'utilise push_back avec la std::vector, est une fonction qui insère à la fin pour ma liste.
Je ne parcours pas toute la liste pour connaître la dernière adresse, j'ai toujours un pointeur vers celle-ci histoire de gagner du temps.
J'avoue qu'aller voir comment std::vector est programmé ne me tente pas énormément (peur de ne pas comprendre du tout), alors j'en viens à vous pour savoir si quelqu'un connaîtrait le fonctionnement d'allocation de std::vector.
Sachant que pour le moment, j'alloue un espace mémoire à chaque insertion, est-ce que créer des espaces mémoires avant d'en avoir besoin, et donc par plus gros 'paquet' plutôt qu'à l'unité, serait plus rapide ? Ou est-ce que l'insertion dans std::vector utilise un procédé spécial, etc... Si quelqu'un à la moindre idée/doc là dessus, je suis preneur !
Si je ne suis pas assez clair ou qu'il manque des informations, svp excusez-moi et je tenterais de résoudre ce problème.
Merci d'avance
r'm
Répondre avec citation
Partager