Recherche dans un set échoue

Version imprimable

Bonjour,

Je rencontre un problème à l'utilisation de std::set. Mon objectif est d'effacer un élément donné au moyen de set::erase. Cependant cette fonction est sans effet, j'ai déterminé que le problème se situe plutôt dans la recherche de l'élément, en effet ce code:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 set<Entity*,drawPriorityComparison>& layer = m_draw_layers[ent->getDrawLayer()]; cout << "Searching for: " << ent << endl; for (set<Entity*,drawPriorityComparison>::iterator it = layer.begin(); it != layer.end(); ++it) { cout << *it << endl; } set<Entity*,drawPriorityComparison>::iterator it = layer.find(ent); if (it == layer.end()) { cout << "it is set::end" << endl; }
Donne une fois exécuté dans son contexte:
Code:

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 Searching for: 0x8d9da80 0x8d9e080 0x8d9e000 0x8d9df80 0x8d9df00 0x8d9de80 0x8d9de00 0x8d9dd80 0x8d9dd00 0x8d9dc80 0x8d9dc00 0x8d9db80 0x8d9db00 0x8d9da80 0x8d9e100 0x8d9eb00 0x8d9ea80 0x8d9ea00 0x8d9e980 0x8d9e900 0x8d9e880 0x8d9e800 0x8d9e780 0x8d9e700 0x8d9e680 0x8d9e600 0x8d9e580 0x8d9e500 0x8d9e480 0x8d9e400 0x8d9e380 0x8d9e300 0x8d9e280 0x8d9e200 0x8d9e180 it is set::end
Comment se fait-il que set::find ne trouve pas le pointeur que je recherche alors qu'il est manifestement présent et accessible lors d'une transversale du set?

Merci d'avance.

12/08/2011, 15h13
Nogane

Bonjour,
A l'état, la seul explication qui me viens est qu'il y as un bug dans drawPriorityComparison.
12/08/2011, 17h05
3DArchi

Salut,
Pareil. find appelle drawPriorityComparison. Donc s'il y a un pb, ceci peut expliquer cela. A noter qu'en mode debug, visual génère une exception si le foncteur est erronée lorsqu'on tente une recherche. Mais, ce n'est pas le cas de gcc.
14/08/2011, 12h41
Mjonir

Merci beaucoup pour vos réponses :)

Vous aviez raison, mon opérateur de comparaison était un critère d'infériorité et non d'infériorité stricte comme précisé dans la documentation. Je n'avais pas pensé qu'il était aussi utilisé pour set::find() (même si a posteriori c'est évident ^^').

Au passage, passer d'infériorité simple à stricte a posé des soucis à l'opération d'insertion. Vu que tous mes pointeurs sont différents je pensais adapté l'utilisation du set qui n'accepte qu'un seul type de clé. Cependant apparemment avec un opérateur de comparaison particulier, la différence se fait sur base de cet opérateur. C'était donc mes draw_priority et non mes pointeurs qui devenaient les clés. J'ai résolu en utilisant un multiset à la place.

Merci encore! :)
15/08/2011, 14h15
Mjonir

Rebonjour,

Je rouvre ce sujet car je me rends compte que mon problème n'est finalement toujours pas résolu. En effet désormais avec un opérateur de comparaison strict et un multiset, tout se passe bien lors de l'insertion. Cependant c'est désormais lorsqu'il s'agit d'effacer qu'est le soucis.

Pour récapituler, j'ai donc un (multi)set de Entity*, objets qui ont une méthode getDrawPriority() retournant un entier fixe et prédéfini. Mon but est d'avoir un conteneur de mes pointeurs triés par ordre de DrawPriority afin d'en faire une transversale.

J'ai du passer au multiset car apparemment les objets que j'insère ne sont considérés comme uniques que sur base de leur DrawPriority. C'est-à-dire qu'avec un set, je ne pouvais insérer qu'un objet d'une certaine priorité, l'insertion d'un autre objet était considéré comme déjà présent. Le multiset résolvait ce problème.

Cependant maintenant lorsque je tente de supprimer un pointeur donné via set::erase(Entity*), c'est tous les objets de la même priorité qui sont supprimés et pas seulement le pointeur que je désigne.

Je ne suis pas sûr de comprendre ce qui se passe, est-ce que quelqu'un pourrait m'éclairer?

Merci d'avance! :)

Salut,

Je me demande si tu ne devrais pas changer (radicalement :question:) ton fusil d'épaule...

Je m'explique : tu es visiblement confronté à deux besoins bien particuliers qui sont:

La gestion de l'existence de tes objets d'une part
la possibilité de les utiliser, sous certaines circonstances, dans un ordre de tri précis de l'autre

Ces deux besoins font partie de deux responsabilités clairement distinctes et devraient donc être remplis par... deux types d'objets distincts, mais travaillant "de concert".

Tu aurais donc un "gestionnaire d'Entity", dont le remplissage s'effectuerait au moment de la création de celles-ci, et qui déciderait, sur ordre de les détruire lorsqu'elles ne sont plus utiles pour rejoindre le premier besoin et un "conteneur trié", rempli sur base des élément du gestionnaire, et "créé à la demande" lorsque tu as besoin de ton tri.

En allant même un peu plus loin dans la réflexion, nous pourrions d'ailleurs envisager de généraliser ce deuxième type de manière à ce qu'il puisse s'adapter à d'autres critères de tri ;)

Au final, cela pourrait ressembler à quelque chose comme:

Code:

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
class Manager
{
    public:
        /* quelques typedef, uniquement pour la facilité du code
         * je ne suis cependant pas sur que le set soit la meilleure
         * solution :-P
         */
        typedef std::set<Entity *>::const_iterator const_iterator;
        /* ajoute une Entity (créée par ailleurs) au gestionnaire
         */
        void addEntity(Entity * toadd){items_.insert(toadd);}
        /* le meilleurs moyen pour travailler par "range" */
       const_iterator begin() const{return items_.begin();}
       const_iterator end() const{return items_.end();}
       /* supprime une entieté donnée du manager */
       void erase(Entity * torem)
       {
           const_iterator it=items_.find(torem)
           if(it!=items_.end())
           {
               delete *it;
               items_.erase(it);
       } 
       /* supprime toutes les entités du manager*/
       void clear()
       {
           for(const_iterator it=items_.begin();it!=items_.end();++it)
               delete *it;
           items_.clear();
       }
};
 
/* nous pouvons prévoir de nous adapter à n'importe quel critère de tri */
template <typename Rule>
class SortedManager
{
    /* des typedef uniquement pour la facilité du code, mais à usage
     * interne uniquement
     */
    typedef std::set<Entity *, Rule> set;
    typedef typename set::const_iterator const_itertaor;
    public:
        /* évitons de nous rendre trop dépendant de manager, et
         * utilisons simplement un "range" [begin , [end pour remplir
         * la collection lors de la création
         */
        template <typename iterator >
        SortedManager(iterator b, iterator e) :items_(b, e){}
        /* on ne sait pas encore quelles manipulations seront
         * effectuées mais on sait dans quel ordre elles le seront :
         * du premier élément au dernier
         */
        template<typename visitor>
        void accept(visitor & v)
        {
            for(const_iterator it = items_.begin(); 
                               it!= items_.end();
                               ++it)
                v.visit(*it);
        }
    private:
        set items_;
};

Le tout pourrait alors être utilisé sous des formes aussi diverses que:

Code:

1
2
3
4
5
6
7
8
9
10
int main()
{
    Manager man;
    /* ajout des éléments */
    SortedManager< drawPriorityComparison >sorted(man.begin(), man.end());
    /* je ne sais pas ce que fait ce visiteur, mais il le fait :D */
    AVerrySpecialVisitor visitor;
    sorted.accept(visitor);
    return 0;
}

ou qe

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
    Manager man;
    /* ajout des éléments */
    /* sélectionnons les éléments en fonction d'un critère donné */
    std::vector<Entity *> tab;
    for(Manager::const_iterator it=man.begin(); it!= man.end(); ++it)
    {
         if ((*it)->hasSomeInterestingProperty())
             tab.push_back(*it);
    }
    /* nous pouvons choisir n'importe quel prédicat pour le tri,
     * et le remplir avec les éléments sélectionnés
     */
    SortedManager<AnotherPredicate> sorted(tab.begin(),tab.end());
    /* je ne sais pas ce que fait ce visiteur, mais il le fait :D */
    AVerrySpecialVisitor visitor;
    sorted.accept(visitor);
    return 0;
}

ou bien d'autres possibilités encore ;)

16/08/2011, 22h07
Mjonir

Merci pour cette réponse :)

En fait, le set<Entity*,drawPriorityComparison> ne sert qu'à conserver une liste triée de certains Entity*. Leur existence est déjà entièrement gérée ailleurs dans un manager.

Il s'agit de l'ordre de dessin de certains objets dans un jeu 2D. Je pourrais effectivement régénérer ces listes à chaque frame, cependant cela me semble être assez lourd comme opération (potentiellement quelques milliers d'objets à remettre dans ces sets au moins 60 fois par seconde), et je suis déjà un peu limite question performance. Je préfèrerais donc grandement conserver cette liste en mémoire pour ensuite y insérer été supprimer des éléments une fois de temps en temps.

C'est pour cela que j'avais choisi std::set... me serais-je trompé sur son utilisation? :o
17/08/2011, 11h02
koala01

Citation:

Envoyé par Mjonir

Merci pour cette réponse :)

En fait, le set<Entity*,drawPriorityComparison> ne sert qu'à conserver une liste triée de certains Entity*. Leur existence est déjà entièrement gérée ailleurs dans un manager.

Cela n'apparaissait pas comme tel dans tes premiers messages ;)

Mais cela implique qu'il ne devrait, a priori, pas avoir de lien entre ta collection triée par adresse et ta collection triée par priorité d'afichage!!!

Ou, du moins, pas de lien direct ;)

Les liens nécessaires seraient plutôt de l'ordre de gestionnaire <--> collection tri par adresse et gestionnaire <--> collection triée par priorité, en veillant à ce que la création ou la destruction d'un élément au niveau du gestionnaire provoque la mise à jour de l'un et de l'autre ;)

Citation:

Il s'agit de l'ordre de dessin de certains objets dans un jeu 2D. Je pourrais effectivement régénérer ces listes à chaque frame, cependant cela me semble être assez lourd comme opération (potentiellement quelques milliers d'objets à remettre dans ces sets au moins 60 fois par seconde), et je suis déjà un peu limite question performance. Je préfèrerais donc grandement conserver cette liste en mémoire pour ensuite y insérer été supprimer des éléments une fois de temps en temps.

J'ai dit de le remplir à la demande, pas de le remplire à chaque fois que tu en as besoin ;):

L'idée est de le remplir au début, puis de le mettre à jour au gré de la construction / destruction d'objet, et de le passer par référence aux fonctions qui en ont besoin ;)

Citation:

C'est pour cela que j'avais choisi std::set... me serais-je trompé sur son utilisation? :o

La question à se poser pour répondre à celle-ci est : la priorité d'affichage des éléments présents dans ta collection est-elle susceptible d'être modifiée :question:

Si tel est le cas, le set ne sera sans doute pas la meilleure collection à utiliser, car il faudra le recréer à chaque fois que la priorité d'un élément change (ou, au minimum, le retirer pour le rajouter après)

De plus, si elle est susceptible de changer, on peut craindre que la modification de l'une provoque la modification "en cascade" d'une série d'autre :aie:

Enfin, il faudrait savoir si nous risquons d'avoir des éléments différents ayant une priorité égale (ou équivalente)...

Dans ce cas, le set est définitivement à proscrire parce que... nous ne pourrions pas y mettre tous les éléments à afficher, vu que la clé ( qui serait la priorité d'affichage ) se doit d'être unique.

Mais, quoi qu'il en soit, il faut savoir que chaque ajout / suppression d'un élément nécessitera de retrier ta collection (ou de veiller à l'insérer directement au bon endroit)
18/08/2011, 18h21
Mjonir
Citation:

Envoyé par koala01

Cela n'apparaissait pas comme tel dans tes premiers messages ;)

Mais cela implique qu'il ne devrait, a priori, pas avoir de lien entre ta collection triée par adresse et ta collection triée par priorité d'afichage!!!

Ou, du moins, pas de lien direct ;)

Les liens nécessaires seraient plutôt de l'ordre de gestionnaire <--> collection tri par adresse et gestionnaire <--> collection triée par priorité, en veillant à ce que la création ou la destruction d'un élément au niveau du gestionnaire provoque la mise à jour de l'un et de l'autre ;)

Je ne suis pas sûr de bien comprendre?

Dans mon Object_Manager je dispose d'une map<unsigned int, Object*> et d'un vector<Player*>. Player et Object héritent tous deux de Entity. Dans l'Object_Manager, je conserve ensuite un tableau de 6 (multi)set<Entity*,drawPriorityComparison> qui me permettent de mémoriser des morceaux de collection triée en y ajoutant/retirant des éléments de temps en temps.

Citation:

Envoyé par koala01

J'ai dit de le remplir à la demande, pas de le remplire à chaque fois que tu en as besoin ;):

L'idée est de le remplir au début, puis de le mettre à jour au gré de la construction / destruction d'objet, et de le passer par référence aux fonctions qui en ont besoin ;)

C'est juste, je n'y avais pas pensé. Mais ça me semble quand même toujours dommage de devoir faire de telles reconstructions. D'autant plus que dans mon multiset je ne veux pas conserver et trier tous les éléments du Manager, mais seulement certains :o

Citation:

Envoyé par koala01

La question à se poser pour répondre à celle-ci est : la priorité d'affichage des éléments présents dans ta collection est-elle susceptible d'être modifiée :question:

Si tel est le cas, le set ne sera sans doute pas la meilleure collection à utiliser, car il faudra le recréer à chaque fois que la priorité d'un élément change (ou, au minimum, le retirer pour le rajouter après)

De plus, si elle est susceptible de changer, on peut craindre que la modification de l'une provoque la modification "en cascade" d'une série d'autre :aie:

Très exceptionnellement uniquement, la priorité sera presque toujours fixe. Pour gérer le changement de priorité, j'utilise déjà un système de supression/rajout.

Il me semble que std::set est implémenté comme un arbre binaire de recherche. La suppression d'un élément puis son rajout en feuille ne devrait engendrer que quelques rotations (ou équivalent), pas un chamboulement complet. Vu que c'est vraiment exceptionnel on peut se le permettre :)

Citation:

Envoyé par koala01

Enfin, il faudrait savoir si nous risquons d'avoir des éléments différents ayant une priorité égale (ou équivalente)...

Dans ce cas, le set est définitivement à proscrire parce que... nous ne pourrions pas y mettre tous les éléments à afficher, vu que la clé ( qui serait la priorité d'affichage ) se doit d'être unique.

Oui, très souvent même. Je ne pensais pas que la clé deviendrait ainsi la priorité d'affichage et pensais qu'elle resterait les pointeurs, mais simplement triés par ordre de priorité.

Citation:

Envoyé par koala01

Mais, quoi qu'il en soit, il faut savoir que chaque ajout / suppression d'un élément nécessitera de retrier ta collection (ou de veiller à l'insérer directement au bon endroit)

C'est pour cela que je voulais justement utiliser un std::multiset, histoire ainsi de pouvoir insérer et supprimer sans tout retrier.

Finalement, tout ce que je recherche est une structure de type arbre BST efficace dont les éléments sont triés par ordre d'affichage et où je peux faire une transversale pour l'affichage.

Là dedans, je me rends compte que tout ce qui pose problème est la recherche d'un élément particulier pour la suppression. Jusque là j'utilisais de nouveau une transversale, mais il me semble qu'il serait possible de profiter de la propriété triée de l'arbre pour retrouver rapidement mon élément?

J'avais pensé utiliser une règle de tri de type:
Code:

1 2 3 4 5 bool drawPriorityComparison::operator() (const Entity* lhs, const Entity* rhs) const { return (lhs<rhs) && (lhs->getDrawPriority() < rhs->getDrawPriority()); }
Mais sans succès. Impossible de faire ça avec un (multi)set alors? Est-ce qu'il y aurait une autre structure de la STL qui convienne mieux?
18/08/2011, 19h35
JolyLoic
Citation:
Envoyé par Mjonir

Code:

1 2 3 4 5 bool drawPriorityComparison::operator() (const Entity* lhs, const Entity* rhs) const { return (lhs<rhs) && (lhs->getDrawPriority() < rhs->getDrawPriority()); }

Mais sans succès.
Tu ne respectes pas les règles d'un bon opérateur <. Regarde la faq.

Avec cet operateur, un simple set devrait suffire. Sinon, il existe aussi une structure STL nommé priority_queue, qui pourrait t'aider.
18/08/2011, 23h26
Mjonir

Effectivement, cela marche beaucoup mieux une fois corrigé! Je ne m'en étais pas rendu compte :)

J'avais déjà considéré priority_queue, mais je souhaite pouvoir conserver cette liste. Il me semble donc plus efficace de faire la transversale d'un set plutôt que de copier la priority_queue avant chaque transversale :P

Merci beaucoup à tous pour votre aide à la résolution de ce problème, je n'y serais pas arrivé autrement :)