Discussion :

[tnarol]

Salut,

J'ai besoin de manipuler des paires de valeurs numériques (attribut1 = un entier, attribut2 = un flottant)

Je dois parcourir les paires dans l'ordre croissant de l'attribut2...jusque là pas trop de problème. Maintenant il peut arriver qu'en cours de route des nouvelles paires dont l'identifiant unique est attribut1 arrivent ou disparaissent, dans ce cas je dois reprendre le parcours depuis le début dans l'ordre croissant de attribut2.

Voici comment je compte faire:

1- je prends une structure typedef struct { int attr1; double attr2; } paire;
2- je construis un vecteur vector<paire> vectPaires avec les paires courantes
3- je trie ce vecteur selon un prédicateur sur attribut2
4- je commence le parcours dans l'ordre des indices du vecteur
5- si des paires disparaissent je les recherche une par une dans le vecteur (avec find_if) et je les retire (avec remove), inutile de retrier le vecteur je reprends le parcours du début
6- si des paires apparaissent je les ajoute au vecteur, puis je le retrie et je reprends le parcours du début.

J'ai le sentiment que ce n'est pas très optimal mais je n'ai pas trouvé mieux...je compte sur vous pour dire s'il y a plus efficace

[Goten]

Une map ne répond pas directement à tes attentes?

en fait je crois que j'ai pas compris l'histoire du : disparaisse ou apparaisse...

[3DArchi]

Salut,

• Cette entrée de la FAQ propose un schéma de décision sur le choix des conteneurs.
• Il existe un conteneur std::pair, pas besoin de réinventer la roue!
• Effectivement, les map sont triées sur la clé (modulo ce qui est dit dans l'article, mais ne s'applique pas à ton cas...) .

[loufoque]

C'est pas plutôt une priority queue que tu veux ?

[tnarol]

C'est pas plutôt une priority queue que tu veux ?

Effectivement si je regarde le schema de décision de la FAQ j'arrive à priority_queue. Intéressant mais je pense que j'ai trouvé plus efficace bien que moins élégant :

J'ajoute à ma structure contenant attribut1 et attribut2 un troisième attribut qui dit si le couple en question est présent ou non présent (apparu/disparu) - c'est possible car mon problème contient un nombre fini de couples possibles.
Ensuite si je dois fournir le couple ayant le plus petit attribut2 je recherche dans mon vecteur classé le premier qui a l'attribut "présent".

L'avantage étant que j'évite de manipuler un conteneur dont le nombre d'élements varie. Bref avec cette solution ce n'est pas très intéressant comme problème...un peu trop spécifique. Mais ça m'aura permis de faire connaissance avec la priority_queue pour une prochaine fois.

Merci

[loufoque]

Ton besoin est exactement celui d'une priority queue, qui est un besoin extrememement courant et qui peut s'implémenter de manière très efficace.
Et toi, tu choisis d'utiliser l'implémentation la pire imaginable, i.e. l'opération principale est en O(n).

[Spout]

Effectivement si je regarde le schema de décision de la FAQ j'arrive à priority_queue. Intéressant mais je pense que j'ai trouvé plus efficace bien que moins élégant :

Tu en es sûr?

Pour la recherche dans ton container (si tu restes dans l'optique STL), tu peux utiliser la fonction find_if de la STL.