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++

  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

  10. #10
    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
    Pour preciser :

    - les ajouts/suppressions sont très rares par rapport au nombre de lectures

    - je crée les objets avec un new() mais je stocke leur reference, pas l'objet lui-même, sinon rien ne marcherait

    - je ne fais pas de parcourt aléatoire, mais séquentiel. Eventuellement en commencant au milieu.

    - la capacité des vecteurs est prévue pour "a priori" ne pas être dépassée, sinon tant pis (tres peu d'insertions, donc tres peu de realloc)

    - les algos sont déjà minimés au maximum (!!!) comme dernier levier d'optimisation, il me reste le parcourt de la liste....

  11. #11
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Par défaut
    D'après ce que j'ai compris, tu fais un truc du style
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    std::vector<Object> v;
    Object* o = new Object;
    v.push_back(*o);
    ?
    C'est-à-dire n'importe quoi ?

  12. #12
    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
    meuh non !

    Quand meme pas !

    Juste :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    std::vector<Object> v;
    Object* o = new Object;
    v.push_back(o);
    J'vais quand même pas m'amuser a stocker, dans un vecteur, un pointeur sur un pointeur sur un objet.

    Surtout si c'est dans le but d'economiser des déréferencements !!!

  13. #13
    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 même temps, on ne sait toujours pas ce que tu fais vu que le code que tu donnes n'est pas correct et n'est donc vraissemblablement pas celui que tu utilises.

    J'vais quand même pas m'amuser a stocker, dans un vecteur, un pointeur sur un pointeur sur un objet.
    Dans le code de loufoque ce n'est pas un pointeur sur un pointeur sur un objet, mais une copie d'un objet alloué sur le tas.

  14. #14
    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
    Je suis pas chez moi, j'ai pas tout mon code sous la main, mais j'ai au moins ça :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // Je declare un vecteur :
    std::vector<cObjet*> m_vecteurObjet;
     
    // J'y insere des objets (plusieurs) :
    pObjet = new cObjet(...);
    m_vecteurObjet.push_back(pObjet);
     
    // Mon traitement principal consiste à :
    std::vector<cObjet*>::iterator It;
     
    for(It=m_vecteurObjet.begin();It!=m_vecteurObjet.end();It++)
    {
        (*It)->traitement(...);
    }
    Maintenant : sachant que ma fonction traitement est extrement simple :
    - addition d'un membre de l'objet avec un parametre de la fonction
    - comparaison du resultat
    - stockage du resultat (ou non) dans u autre membre de l'objet

    Je souhaiterais rendre le parcourt de la boucle le plus rapide possible :

    1/ eviter des déréferencement ?

    2/ faire en sorte que tous les objets soient stockés dans la même zone mémoire pour être tous chargés en cache ? (les objets font entre 32 et 64 octets, il y a en une centaine environ)

    3/ d'autres pistes ?


    Désolé si je ne suis pas très clair.

  15. #15
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Par défaut
    Pourquoi tu stockes des pointeurs et pas des objets directement ?

  16. #16
    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
    Plusieurs raisons à cela :

    - ailleurs dans le code, j'ai besoin d'acceder à certains objets du vecteur. Mais cela pourrait se faire via un indice ou un itérateur

    surtout :

    - je ne veux pas que les objets soient détruits lorsqu'ils sont retiré du vecteur : j'en ai besoin ailleurs

  17. #17
    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
    Dans ce cas si ce n'est pas le vecteur qui gère la durée de vie des éléments, il faudra bien n'en stocker que des pointeurs.

  18. #18
    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
    C'est ce que je pensais.

    D'où l'idée de créer les objets dans la même zone mémoire afin d'éviter les erreurs de cache.

    Je ne vois pas trop d'autres leviers pour optimiser...

    Mais je ne sais pas trop comment faire, ni même si ça a un impact significatif, étant donné le déreferencement qui precede le chargement de l'objet.

    Pourquoi je me prend la tete sur ce bout de code vous demandez-vous peut-etre ?

    Parcque c'est un bout de code qui doit tourner à fond les manettes !

  19. #19
    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
    Oui, mais :

    Dans ce cas si ce n'est pas le vecteur qui gère la durée de vie des éléments, il faudra bien n'en stocker que des pointeurs.

  20. #20
    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
    Avec seulement une centaine d'objets, on peut pas dire que ça soit vraiment indispensable de "tourner à fond les manettes". Et puis si on commence à compter les dérèfèrencements, pourquoi pas les appels de fonctions tant qu'on y est?
    Sinon, je capte de moins en moins tes explications. Tu nous dit que tes objets sont dans un conteneur mais que ce n'est pas lui qui gère leurs cycles de vie... Ce n'est donc qu'une sorte d'index non? Dans ce cas pourquoi t'acharner uniquement la dessus, tes objets devront bien être gérés par autre chose qui sera probablement un... conteneur. Faudrait pas plutot se pencher la dessus?

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