Discussion :

[buzzkaido]

Bonjour,

Une question que je me pose sur l'allocation de mémoire dans les listes et les vecteurs :

Est-il possible de stocker dans un pointeur l'adresse d'un objet inséré dans une liste ou dans un vecteur et d'être sûr que ce pointeur pointe toujours sur l'objet ?

En gros, faire :

Code :

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

1
2
3
4
5
std::list conteneur;  ou std::vector conteneur;
cObject objet;
cObject *pObjet = &objet;
 
conteneur.push_back(objet);

Pour les listes, il s'agit de listes chainées, donc à priori, pas de soucis...

Mais pour les vecteurs, que se passe-t-il en cas de réallocation (pour cause de dépassement, par exemple) ?

Est-ce qu'au moment de la réallocation, l'objet lui-même est déplacé ?
Ou est-ce que seulement la zone réservée pour les itérateurs est réallouée et seulement les itérateurs sont déplacés ?

Merci !

[Laurent Gomila]

Si tu prends l'adresse avant insertion, tu es coulé à tous les coups car c'est une copie qui est stockée. Si tu la prends après, elle est valide tant que tu ne fais pas d'opération invalidante sur ton conteneur :
- Suppression et ajout de n'importe quel élément dans un vector, un deque ou un string
- Suppression de l'élément en question dans tout autre conteneur (list, set, map)

[zais_ethael]

Pour les vecteurs il est certain que ça ne fonctionnera pas.
Sinon, il y a un truc formidable pour ne pas avoir à se poser la question: boost::ptr_container. Ce sont des variantes pointées des containers de la stl.
En dehors de ça, stocker des itérateurs serait peut-être préfèrable, mais d'autres sur ce forum t'en diront plus sur le sujet (je ne suis pas certain de la façon dont évoluent les itérateurs si leur conteneur est modifié).

[buzzkaido]

Laurent Gomila :

car c'est une copie qui est stockée

Tu veux dire que l'ensemble de mon objet est recopié pour l'insertion ?
L'objet existe donc 2 fois en mémoire ?

Suppression et ajout de n'importe quel élément dans un vector, un deque ou un string

Tu veux dire que si j'insere un autre élément apres celui-ci, son adresse a changée ?

Suppression de l'élément en question dans tout autre conteneur

Je suppose que c'est parceque le destructeur de l'élément est appelé lors de sa suppression d'un autre conteneur... Mais si l'objet est recopié lors de son insertion, pourquoi ça pose soucis ?

[Laurent Gomila]

En dehors de ça, stocker des itérateurs serait peut-être préfèrable

Pointeur ou itérateur c'est pareil. Par contre pour un vector on peut stocker des indices, ça peut aider dans certains cas.

[Laurent Gomila]

Tu veux dire que l'ensemble de mon objet est recopié pour l'insertion ?
L'objet existe donc 2 fois en mémoire ?

Oui. Enfin comme le premier est déclaré sur la pile il sera détruit pas longtemps après.

Tu veux dire que si j'insere un autre élément apres celui-ci, son adresse a changée ?

Potentiellement. S'il n'y a pas assez de place, il y aura réallocation de mémoire et donc déplacement des éléments en mémoire.

Je suppose que c'est parceque le destructeur de l'élément est appelé lors de sa suppression d'un autre conteneur...

Ben c'est surtout parce que l'élément n'existe plus. Donc tout pointeur qui pointerait dessus deviendrait invalide.

Mais si l'objet est recopié lors de son insertion, pourquoi ça pose soucis ?

Parce que c'est sur la copie que tu pointes. L'original ayant été détruit depuis longtemps.

[buzzkaido]

Ok, merci pour toutes ces precisions.

Je vais un peu preciser le contexte :

Je crée des objets, suite à des actions de l'utilisateur. Donc de facon dynamique.

La liste de certains de ces objets doit être parcourue très très fréquemment pour en lire le contenu.

Le parcours de cette liste est à peu de chose près, le coeur de mon programme. Je souhaite donc l'optimiser au maximum.

Dans un premier temps, j'ai fait ça :

- création de chaque objet avec un new()
- insertion dans une std::list
- parcourt de la liste

Ensuite, ça :
- création de chaque objet avec un new()
- insertion dans un std::vector
- parcourt du vecteur

Ici, j'ai gagné un déréfencement à chaque parcourt de la liste, au prix d'une réallocation de temps en temps (pas très grave)

Maintenant, j'essaie de faire en sorte que chaque objet créé puis inséré soit dans la même zone mémoire que les autres, afin d'éviter de devoir recharger le cache mémoire à chaque fois que l'on passe à l'objet suivant.

Je pensais trouver une astuce en les allouant sur la pile afin qu'ils soient proches les uns des autres... visiblement c'est rapé !

Auriez-vous des suggestions ?

[koala01]

Salut,

Si ton vecteur (ou ta liste ou ... d'une manière générale, ton conteneur) est prévu pour contenir des pointeurs, rien ne t'empeche d'écrire un code du genre de

Code :

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

1
2
3
4
 
monvecteur.push_back(new MonObjet(...));
mamap.insert(std::make_pair(key,new Monobjet(...));
//etc

Les ... dans les parentheses représentant, bien évididemment, les arguments à passer au constructeurs

[zais_ethael]

Tu te pose bien beaucoup de questions, et certains de tes raisonnements sont bizarres. Pour choisir ton conteneur, voici ce que tu dois te dire:
- si tu fais des ajouts/suppressions fréquents en mileu de liste, prends une list
- si tu fais des parcours aléatoires, prends un vector
- les deux? normalement un deque doit te fournir un compromis
Pense aussi à jouer avec la capacité des vector et des deque.
Et ça ne sert à rien d'instancier par pointeur si c'est pour copier ton objet dans un conteneur juste après, de même que c'est un peu l'inverse que de vouloir optimiser le cache mémoire (puisque tes objets peuvent être instanciés n'importe où dans la mémoire). Soit dit en passant, pense plutot à minimiser la complexité de tes algos plutot que d'optimiser le cache mémoire, en général ça paie plus