Discussion :

[Mjonir]

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 :

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

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 :

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

[Nogane]

Bonjour,
A l'état, la seul explication qui me viens est qu'il y as un bug dans drawPriorityComparison.

[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.

[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!

[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!

[koala01]

Salut,

Je me demande si tu ne devrais pas changer (radicalement ) 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 :

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

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

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 :

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

[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

[koala01]

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

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

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

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

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)

[Mjonir]

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.

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

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

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

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

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é.

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 :

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

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?

[JolyLoic]

Code :

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

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.

[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

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