IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

SL & STL C++ Discussion :

std::list, std::vector et allocation mémoire


Sujet :

SL & STL C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé
    Avatar de buzzkaido
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juillet 2004
    Messages
    821
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juillet 2004
    Messages : 821
    Par défaut std::list, std::vector et allocation mémoire
    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 !

  2. #2
    Rédacteur
    Avatar de Laurent Gomila
    Profil pro
    Développeur informatique
    Inscrit en
    Avril 2003
    Messages
    10 651
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2003
    Messages : 10 651
    Par défaut
    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)

  3. #3
    Membre émérite
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    1 064
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2005
    Messages : 1 064
    Par défaut
    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é).

  4. #4
    Membre éclairé
    Avatar de buzzkaido
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juillet 2004
    Messages
    821
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juillet 2004
    Messages : 821
    Par défaut
    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 ?

  5. #5
    Rédacteur
    Avatar de Laurent Gomila
    Profil pro
    Développeur informatique
    Inscrit en
    Avril 2003
    Messages
    10 651
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2003
    Messages : 10 651
    Par défaut
    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.

  6. #6
    Rédacteur
    Avatar de Laurent Gomila
    Profil pro
    Développeur informatique
    Inscrit en
    Avril 2003
    Messages
    10 651
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2003
    Messages : 10 651
    Par défaut
    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.

  7. #7
    Membre éclairé
    Avatar de buzzkaido
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juillet 2004
    Messages
    821
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juillet 2004
    Messages : 821
    Par défaut
    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 ?

  8. #8
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 635
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 635
    Par défaut
    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
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  9. #9
    Membre émérite
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    1 064
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2005
    Messages : 1 064
    Par défaut
    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

Discussions similaires

  1. std::list ou std::vector comme argument de template
    Par epsilon68 dans le forum C++
    Réponses: 11
    Dernier message: 01/03/2011, 23h34
  2. std::vector et espace mémoire
    Par salseropom dans le forum C++
    Réponses: 6
    Dernier message: 10/02/2011, 23h25
  3. [Tuto] Recherche de tutoriel sur std::list et std::vector
    Par pegase06 dans le forum SL & STL
    Réponses: 27
    Dernier message: 24/07/2007, 16h23
  4. Réponses: 16
    Dernier message: 30/05/2006, 18h46
  5. acceder au n iéme element d'une liste std::list
    Par sorari dans le forum SL & STL
    Réponses: 4
    Dernier message: 23/03/2005, 15h21

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo