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

C++ Discussion :

Petit problème de pointeur sur vector dans une structure HalfEdge


Sujet :

C++

  1. #1
    Membre régulier
    Homme Profil pro
    Développeur du dimanche
    Inscrit en
    Février 2013
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur du dimanche

    Informations forums :
    Inscription : Février 2013
    Messages : 154
    Points : 105
    Points
    105
    Par défaut Petit problème de pointeur sur vector dans une structure HalfEdge
    Hello,

    Je suis actuellement en train de coder une sorte de NavMesh : l'objectif est de réaliser la triangulation d'un espace en tenant compte d'éventuelles contraintes (des murs). Chaque triangle est stocké de la manière suivante : ses trois côtés sont représentés sous la forme d'HalfEdge, en gros, des cotés orientés. Un triangle est donc stocké sous forme de 3 vecteurs, chacun représentant un coté. Ces vecteurs sont créés de telle sorte que les points du triangle soient dans le sens des aiguilles d'une montre. Mais un schéma sera plus clair :

    http://www.google.fr/imgres?imgurl=h...ed=0CHkQrQMwCw

    Voilà. Sauf qu'ici les HalfEdge sont orientés dans le sens inverse des aiguilles d'une montre. Mais mon problème est très sommaire, en fait.

    Voici ma classe Mesh, commentée et volontairement simplifiée :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
     
    class Mesh
    {
     
    private:
     
        struct HalfEdge
        {
            // first, c'est les coordonnées du point de départ de l'HalfEdge. Il pointe sur un élément de "points".
            sf::Vector2i* first;
            HalfEdge* next;
            HalfEdge* pair;
            bool fixed; // inutile ici, c'est juste pour savoir si l'HalfEdge est un mur ou non.
        };
     
        std::vector<HalfEdge> mesh;
        std::vector<sf::Vector2i> points;
     
    public:
     
        /* IntRect est une classe de la bibli SFML : c'est un simple rectangle. left = coordonnées x du coté de tout à gauche, top = coordonnées en y du coté tout en haut, width = longueur et height = hauteur */
    /* ce superRectangle que je construit est destiné à recevoir tous les autres points que j'insèrerai par la suite et qui devront être triangulés. */
        Mesh(sf::IntRect const &superRectangle)
        {
            // Encore une classe de la SFML : sf::Vector2i c'est comme un std::pair<int,int>, sauf qu'on écrit .x et .y pour .first et .second
            sf::Vector2i A,B,C,D;
     
            A = {superRectangle.left,superRectangle.top};                                               // haut-gauche
            B = {superRectangle.left+superRectangle.width,superRectangle.top};                          // haut-droite
            C = {superRectangle.left,superRectangle.top+superRectangle.height};                         // bas-gauche
            D = {superRectangle.left+superRectangle.width,superRectangle.top+superRectangle.height};    // bas-droite
     
            points = {A,B,C,D};
     
            // ici, je suis obligé de créer en avance les 6 éléments du vector, parce que les tous éléments pointent sur les autres.
            mesh.resize(6);
     
            mesh[0] = {&points[0],&mesh[1],NULL,true};          // 0
            mesh[1] = {&points[1],&mesh[2],&mesh[3],false};     // 1
            mesh[2] = {&points[2],&mesh[0],NULL,true};          // 2
            mesh[3] = {&points[2],&mesh[4],&mesh[1],false};     // 3
            mesh[4] = {&points[1],&mesh[5],NULL,true};          // 4
            mesh[5] = {&points[3],&mesh[3],NULL,true};          // 5
     
            /* Supposons maintenant que je veuille ajouter un HalfEdge qui partirait du point {50,50}, et dont le HalfEdge suivant serait celui qui part du point {0,0}. Voici ce que ça donne : */
            points.push_back({50,50});
            mesh.push_back({&points[4],&mesh[0],NULL,false});   // 6
     
            /* on vérifie que les insertions se sont faites normalement, et là c'est le drame... */
            this->test();
        }
     
        void test()
        {
            for (auto i : mesh)
            {
                std::cout<<"edge("<<i.first->x<<","<<i.first->y<<")->("<<i.next->first->x<<","<<i.next->first->y<<") | ";
                std::cout<<std::endl;
            }
        }
    };
     
    int main()
    {
        Mesh mesh(sf::IntRect(0,0,800,600));
     
    return 0;
    }
    L'insertion du 7ème HalfEdge ne semble pas se faire correctement, et je ne comprends vraiment pas d'où pourrait venir le problème.. Pourriez vous m'aider s'il vous plait

    Cordialement,
    "There should be no boundaries to human endeavor" - Hawking
    Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei

  2. #2
    Membre expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2011
    Messages
    739
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Juin 2011
    Messages : 739
    Points : 3 627
    Points
    3 627
    Par défaut
    Salut,

    J'aurais tendance à dire que tous les points sauf le dernier sont valide. Quand un push_back est fait sur un std::vector, se dernier peut redimensionner sa taille et par conséquent invalider tous les itérateurs et pointeurs sur les éléments.
    Par conséquent, les meshs précédent possèdent des pointeurs sur des valeurs de `points` qui n'existe plus.

  3. #3
    Membre régulier
    Homme Profil pro
    Développeur du dimanche
    Inscrit en
    Février 2013
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur du dimanche

    Informations forums :
    Inscription : Février 2013
    Messages : 154
    Points : 105
    Points
    105
    Par défaut
    Salut,

    Merci de ta réponse. En effet, je n'avais pas pensé à ça.. Du coup, dans ma structure HalfEdge, j'ai remplacé sf::Vector2i* first par sf::Vector2i first, et les points sont stockés directement dedans, au lieu de passer par un pointeur sur un vector de sf::Vector2i. Mais ça m'embête, ma structure devient plus lourde. Y aurait-il une autre solution, pour que ma structure garde sa légèreté, mais que le code reste aussi rapide ? Je les aimais bien moi, mes petits pointeurs

    Cordialement,
    "There should be no boundaries to human endeavor" - Hawking
    Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei

  4. #4
    Expert éminent sénior
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    Juillet 2013
    Messages
    4 627
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 4 627
    Points : 10 551
    Points
    10 551
    Par défaut
    Cela dépend si tu connais le nombre de points et de segments pour ta class Mesh dès le début, tu peux faire directement des tableaux C, alloués avec la bonne taille

  5. #5
    Membre régulier
    Homme Profil pro
    Développeur du dimanche
    Inscrit en
    Février 2013
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur du dimanche

    Informations forums :
    Inscription : Février 2013
    Messages : 154
    Points : 105
    Points
    105
    Par défaut
    Justement, je ne le connais pas
    Bon tant pis, c'est très bien comme ça de toutes façons, au moins, ça marche maintenant

    Merci à tous les deux !
    "There should be no boundaries to human endeavor" - Hawking
    Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei

  6. #6
    Expert éminent sénior
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    Juillet 2013
    Messages
    4 627
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 4 627
    Points : 10 551
    Points
    10 551
    Par défaut
    Sinon, ensuite tu peux simuler un std::vector

    Un exemple
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    class Elt {
      sf::Vector2i points[X]:
     
      Elt* next;
    };
    Avec X à déterminer

  7. #7
    Membre régulier
    Homme Profil pro
    Développeur du dimanche
    Inscrit en
    Février 2013
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur du dimanche

    Informations forums :
    Inscription : Février 2013
    Messages : 154
    Points : 105
    Points
    105
    Par défaut
    Hum je sais pas.. Quelle est la différence avec sf::Vector2i first ? Au final il fait quand même une copie, non ?
    "There should be no boundaries to human endeavor" - Hawking
    Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei

  8. #8
    Membre expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2011
    Messages
    739
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Juin 2011
    Messages : 739
    Points : 3 627
    Points
    3 627
    Par défaut
    Se qui revient au même, X n'est pas connu.
    Puis les vla c'est mal.

    Niveau légèreté, je pense que sizeof(sf::Vector2i) == sizeof(sf::Vector2i*) car les pointeur prennent plus de place que les int. De plus les accès sont généralement plus lent sur les pointeurs (un déréférencement de plus à faire) et ici probablement des cache miss ajoutés (2 vectors donc 2 zones mémoire possiblement éloignées).

    En plus de la lisibilité tu as tous gagné en virant le pointeur

  9. #9
    Expert éminent sénior
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    Juillet 2013
    Messages
    4 627
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 4 627
    Points : 10 551
    Points
    10 551
    Par défaut
    Citation Envoyé par jo_link_noir Voir le message
    Se qui revient au même, X n'est pas connu.
    Puis les vla c'est mal.
    C'est un exemple et X est à déterminer, parce qu'il faut trouver le bon compromis entre pas trop de fragments/ mémoire utilisée presque entièrement.

    Disons 16
    On va créer son tableau de points 16 par 16.
    Après effectivement, il faut faire un truc légèrement mieux parce qu'il faut le faire pour la liste des points et celle des meshs

    Et dans chaque Elt, on va avoir un tableau sans pointeur et on pourra faire
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    Elt* chunk; // Already initialized
     
    chunk->point[5].x = 12;
    chunk->point[5].y = 50;

  10. #10
    Membre régulier
    Homme Profil pro
    Développeur du dimanche
    Inscrit en
    Février 2013
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur du dimanche

    Informations forums :
    Inscription : Février 2013
    Messages : 154
    Points : 105
    Points
    105
    Par défaut
    Mais.. moi, dans chaque HalfEdge, j'ai juste besoin de stocker les coordonnées du point de départ de l'edge, pourquoi faire un tableau ? En plus, l'accès aux éléments d'un tableau, c'est long. Un pointeur, c'est mieux
    Par contre du coup, je comprends pas pourquoi j'ai pas de problème en stockant directement first dans un HalfEdge. Normalement, insérer un nouveau mesh mélange toutes les références, en tous cas c'est ce que ça faisait dans le vector "points".
    "There should be no boundaries to human endeavor" - Hawking
    Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei

  11. #11
    Expert confirmé
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2012
    Messages
    1 711
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2012
    Messages : 1 711
    Points : 4 442
    Points
    4 442
    Par défaut
    Citation Envoyé par MrPchoun Voir le message
    En plus, l'accès aux éléments d'un tableau, c'est long. Un pointeur, c'est mieux
    C'est strictement identique. (Au final un tableau n'est rien d'autre qu'un pointeur, avec un offset pour trouver le bon élément).

    L'ajout d'éléments dans points ou mesh peut invalider tous les pointeurs / itérateurs.

    Donc soit tu sais la taille de mesh / points et tu peux les initialiser à cette taille pour qu'ils ne soient pas redimentionnés.
    Soit tu peux stocker des (smart) pointeurs dans mesh / points.

    Utiliser des list à la place de vector est peut être possible aussi, tu perd l'accès aléatoire aux éléments, mais si tu n'en à besoin que lors de la création ça peut être viable.

  12. #12
    Membre expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2011
    Messages
    739
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Juin 2011
    Messages : 739
    Points : 3 627
    Points
    3 627
    Par défaut
    @foetus: aah d'accord, je n'avais pas comprit. En ce moment je filtre la moitié des infos que je vois :/
    Mais bon, autant mettre directement le vector2i dans HalfEdge. Si j'ai bien comprit le pointeur est utilisé pour faire de l'optimisation (qui de mon point de vue est ici plus casse-gueule qu'autre chose).

    @MrPchoun: Tu voulais parler de next/pair, non ? Si c'est bien ça, coup de chance, la donné pointer est supprimée mais les données mémoire non pas changés alors le problème ne se manifeste pas tout de suite.
    En complément de se que dit Iradrille, tu peux remplacer le pointeur par un index. C'est un peu casse pied à utiliser (mesh.next => mesh[mesh[x].next]) mais tant qu'aucun élément est supprimé les indices sont stable.

  13. #13
    Expert confirmé
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2012
    Messages
    1 711
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2012
    Messages : 1 711
    Points : 4 442
    Points
    4 442
    Par défaut
    Citation Envoyé par jo_link_noir Voir le message
    En complément de se que dit Iradrille, tu peux remplacer le pointeur par un index. C'est un peu casse pied à utiliser (mesh.next => mesh[mesh[x].next]) mais tant qu'aucun élément est supprimé les indices sont stable.
    Et c'est probablement la meilleure solution tant qu'il y à peu de suppression (mettre à jour tous les indices c'est possible mais long).
    J'y avais pas pensé.

  14. #14
    Membre régulier
    Homme Profil pro
    Développeur du dimanche
    Inscrit en
    Février 2013
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur du dimanche

    Informations forums :
    Inscription : Février 2013
    Messages : 154
    Points : 105
    Points
    105
    Par défaut
    @Iradrille : pour la list je suis pas très chaud, ça devient beaucoup plus difficile par la suite d'accéder à mes élements étant donné qu'ils serait triés à l'insertion. Je vais creuser du côté des smarts pointer, pour voir ce que c'est.

    @jo_link_noir :
    Tu voulais parler de next/pair, non ? Si c'est bien ça, coup de chance, la donné pointer est supprimée mais les données mémoire non pas changés alors le problème ne se manifeste pas tout de suite.
    -> Exactement ! Mais à la limite, même si le code est pas très juste dans le fond, tant que ça me donne mes bonnes valeurs, moi ça ne me dérange pas. Après, faut voir ce que ça donne lors de la suppression d'éléments..
    tant qu'il y à peu de suppression
    et des suppressions, y en a pas mal.
    "There should be no boundaries to human endeavor" - Hawking
    Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei

  15. #15
    Expert confirmé
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2012
    Messages
    1 711
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2012
    Messages : 1 711
    Points : 4 442
    Points
    4 442
    Par défaut
    Citation Envoyé par MrPchoun Voir le message
    et des suppressions, y en a pas mal.
    Beaucoup de suppressions, besoin d'un accès aléatoire, ce genre de chose semble plus adapté :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    struct HalfEdge {
    	int first; // index dans le vector
    	int next;
    	int pair;
    	bool fixed;
    };
     
    std::vector<HalfEdge> mesh;
    std::vector<sf::Vector2i> points;
    La suppression d'un point / HalfEdge peut invalider un ou plusieurs (voir même presque tous) HalfEdge, à voir s'il est possible d'itérer sur tous les HalfEdge pour supprimer ceux qui deviennent invalide, et corriger les autres.

    Sinon, si le coût de correction des HalfEdge est trop important
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    struct HalfEdge {
    	std::weak_ptr<sf::Vector2i> first;
    	std::weak_ptr<HalfEdge> next;
    	std::weak_ptr<HalfEdge> pair;
    	bool fixed;
    };
     
    std::vector<std::shared_ptr<HalfEdge>> mesh;
    std::vector<std::shared_ptr<sf::Vector2i>> points;
    La suppression d'un point / HalfEdge peut toujours invalider un ou plusieurs HalfEdge, mais on supprime les HalfEdge invalide que lors ce qu'on les utilise et détecte qu'ils sont invalide (grâce aux weak_ptr).

  16. #16
    Membre expert
    Profil pro
    Inscrit en
    Mars 2007
    Messages
    1 415
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Mars 2007
    Messages : 1 415
    Points : 3 156
    Points
    3 156
    Par défaut
    Salut

    @jo_link_noir: le fait que les pointeurs prennent plus de place que les int n'a pas d'effet ici car les int seront alignés en mémoire de la même manière que les pointeurs. On ne gagne pas de place, à moins de pack les structures, mais dans ce cas on perd en vitesse d'accès.

    Tu dis que tu ne connais pas à l'avance la taille des données... mais ce qui est nécessaire ici, c'est de connaître une borne supérieure de la taille des données, par forcément la taille exacte. Du moment que ton problème reste assez léger en mémoire (ça je ne sais pas si c'est le cas), ce n'est pas gênant d'en consommer un peu plus. Malheureusement, la suppression de données invalidera aussi tous les itérateurs et pointeurs sur les éléments se situant après l'élément supprimé, et du coup, ça ne fonctionnera pas non plus.

    La solution 2 d'Iradrille est sémantiquement correcte, mais ca me paraît quand même super lourd d'utiliser shared_ptr et weak_ptr pour des ojets aussi petits. La thread safety des weak et shared risque de coûter plus cher que l'accès aux données ! Mais après tout, ne dit-on pas qu'il faut écrire du code qui a du sens d'abord et optimiser ensuite si les performances ne sont pas satisfaisantes. Ca vaut donc le coup d'essayer.

    Les problèmes qui combinent un besoin d'accès aléatoire et de suppression ne sont pas triviaux à adresser. Mais y a-t-il vraiment besoin de supprimer les données ? Ne peux-tu pas écrire un algortihme qui se contente de ne plus utiliser les données qui ne sont plus nécessaires et nettoie tout à la fin ? Si oui, et si tu peux calculer une borne sup, ce serait le must, tant en perfo qu'en simplicité du code.
    Find me on github

  17. #17
    Membre régulier
    Homme Profil pro
    Développeur du dimanche
    Inscrit en
    Février 2013
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur du dimanche

    Informations forums :
    Inscription : Février 2013
    Messages : 154
    Points : 105
    Points
    105
    Par défaut
    Salut,

    À vrai dire j'ai eu beaucoup de mal à implémenter la solution d'Iradrille, les pointeurs intelligents, c'est pas quelque chose que je suis habitué de manipuler.. Je n'ai même pas réussi

    Je peux éventuellement me passer de supprimer des éléments, mais à ce moment chaque HalfEdge devra contenir un booléen "actif", qu'il faudra vérifier maintes et maintes fois dans l'algo de triangulation, j'ai vraiment peur que les performances de l'algo ( et plus de la structure, cette fois ) en prennent en coup. Mais faut toujours qu'on m'explique pourquoi ce code marche

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    struct gg
        {
            gg* first;
            std::pair<int,int> second;
        };
     
        std::vector<gg> vec;
     
        vec.reserve(4);
     
        vec.push_back({&vec[3],{1,5}});     // 0
        vec.push_back({&vec[0],{4,3}});     // 1
        vec.push_back({&vec[1],{3,2}});     // 2
        vec.push_back({&vec[2],{2,6}});     // 3
     
        vec.push_back({&vec[1],{7,4}});     // 4
     
        vec.erase(vec.begin()+2, vec.begin()+4);
     
        for (auto i : vec)
            std::cout<<i.first->second.first<<","<<i.first->second.second<<std::endl;
    J'ai tout fait au vector, je lui ai supprimé des éléments, j'en ai ajouté, et pourtant les références restent toujours bonnes..

    Anyway, j'ai cherché une solution d'un autre côté, et je suis tombé sur une solce, qui a en partie répondu à mes attentes.

    En partie seulement, parce que la structure suivante :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    template< class key >
    struct rec_map_gen {
        struct i;
        typedef map< key, vector< i > > t;
        struct i : t::iterator {
        	i( typename t::iterator v )
        	: t::iterator(v) {}
        };
    };
    .. stocke des vector vers itérateur, mais je ne sais vraiment pas comment faire pour la structure stocke seulement un itérateur en "value" :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    typedef map< key,  i> t;
    Mon compliateur ne semble pas trop aimer la petite ligne du dessus.

    [edit] : un pointeur sur un vector, c'est plus rapide d'accès que l'opérateur []. J'ai testé !
    [edit2] : pour ce qui est de la borne supérieure, malheureusement il n'y en a pas vraiment :/

    Cordialement,
    "There should be no boundaries to human endeavor" - Hawking
    Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei

  18. #18
    Membre expert
    Profil pro
    Inscrit en
    Mars 2007
    Messages
    1 415
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Mars 2007
    Messages : 1 415
    Points : 3 156
    Points
    3 156
    Par défaut
    Citation Envoyé par MrPchoun Voir le message
    Mais faut toujours qu'on m'explique pourquoi ce code marche J'ai tout fait au vector, je lui ai supprimé des éléments, j'en ai ajouté, et pourtant les références restent toujours bonnes..
    Simplement par chance : tu ne déréférences que des pointeurs (stockés correctement eux) et pas des itérateurs. Ce faisant, tu accèdes à des zones mémoires qui sont en théorie libérées mais qui sont restées dans l'espace mémoire de ton processus et qui contiennent toujours la bonne donnée. Si tu passes ton exécutable dans un memory checker, comme valgrind, il signalera ces erreurs (j'ai testé avec ton code, valgrind ne s'y trompe pas !).

    Citation Envoyé par MrPchoun Voir le message
    mais je ne sais vraiment pas comment faire pour la structure stocke seulement un itérateur en "value"
    Tu ne peux pas : les map n'exposent que des itérateurs sur des paires clé/valeur. Tu peux au mieux mettre ça dans un wrapper avec des opérateurs de conversion automatique. Mais ça n'en vaut pas trop la peine, ton itérateur contient bien une référence vers la paire clé/valeur, et pas une copie, tu ne gagnerais rien avec un itérateur "par valeur".
    Find me on github

  19. #19
    Membre régulier
    Homme Profil pro
    Développeur du dimanche
    Inscrit en
    Février 2013
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur du dimanche

    Informations forums :
    Inscription : Février 2013
    Messages : 154
    Points : 105
    Points
    105
    Par défaut
    Ce faisant, tu accèdes à des zones mémoires qui sont en théorie libérées mais qui sont restées dans l'espace mémoire de ton processus et qui contiennent toujours la bonne donnée
    Ah, j'ai compris cette fois

    Tu ne peux pas : les map n'exposent que des itérateurs sur des paires clé/valeur.
    Je me suis mal exprimé. J'aurais voulu qu'au lieu que la map contiennent en clé "key" et en valeur un vecteur d'itérateurs sur la map, elle contienne toujours key en clé, mais qu'en valeur, elle contienne uniquement un itérateur sur la map, et non un vector d'itérateurs. Crois tu que cela soit possible ?

    Merci de ton aide en tous cas
    "There should be no boundaries to human endeavor" - Hawking
    Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei

  20. #20
    Expert confirmé
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2012
    Messages
    1 711
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2012
    Messages : 1 711
    Points : 4 442
    Points
    4 442
    Par défaut
    Citation Envoyé par jblecanard Voir le message
    La solution 2 d'Iradrille est sémantiquement correcte, mais ca me paraît quand même super lourd d'utiliser shared_ptr et weak_ptr pour des ojets aussi petits. La thread safety des weak et shared risque de coûter plus cher que l'accès aux données ! Mais après tout, ne dit-on pas qu'il faut écrire du code qui a du sens d'abord et optimiser ensuite si les performances ne sont pas satisfaisantes. Ca vaut donc le coup d'essayer.

    Les problèmes qui combinent un besoin d'accès aléatoire et de suppression ne sont pas triviaux à adresser. Mais y a-t-il vraiment besoin de supprimer les données ? Ne peux-tu pas écrire un algortihme qui se contente de ne plus utiliser les données qui ne sont plus nécessaires et nettoie tout à la fin ? Si oui, et si tu peux calculer une borne sup, ce serait le must, tant en perfo qu'en simplicité du code.
    Oui, shared_ptr / weak_ptr ça veut dire un surcout non negligeable. Avec un haut taux de suppression ça peut (peut être :p) représenter un surcout inférieur à la correction des données.

    Une implémentation utilisant le même principe mais sans smart ptr
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    struct HalfEdge {
    	int first; // id (clés dans la map / unordered_map)
    	int next;
    	int pair;
    	bool fixed;
    };
     
    // global à tous les Meshes
    std::/* unordered_ */map<int, HalfEdge> gEdges; // on peut avoir un "vrai" type pour les ID
    std::/* unordered_ */map<int, sf::Vector2i> gPoints;
    // on peut aussi maintenir des (unordered) multimap stockant les dépendances entre Points / HalfEdge, pour une suppression rapide des HalfEdge invalides.
     
    // dans un Mesh
    std::vector<int> mesh; // id (clés dans la map / unordered_map)
    std::vector<int> points;
    Mais il y a toujours un surcout, une autre piste serait de ne supprimer les données que de temps en temps. On modifie juste les pointeurs (ou id) sans supprimer les objets. Et on effectue réellement les suppressions de temps en temps (par exemple toutes les 1000 ou 10k suppressions). Un peu comme le fonctionnement d'un GC.

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. pointeur sur tableau dans une structure
    Par rollbich dans le forum Débuter
    Réponses: 3
    Dernier message: 02/06/2013, 23h23
  2. Réponses: 7
    Dernier message: 04/12/2012, 20h02
  3. Réponses: 6
    Dernier message: 13/11/2012, 09h17
  4. Réponses: 1
    Dernier message: 22/12/2009, 12h40
  5. Réponses: 7
    Dernier message: 04/01/2006, 16h34

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