Choix de conteneur pour un algo

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

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

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

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

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

Citation:

---

Envoyé par loufoque

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

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

@tnarol :

Sache que ce qui est dans la STL , et toujours le plus efficace , sur et pratique.
En programmation on c'est vite rendu compte qu'on fesait toujours les mêmes choses. ( tableaux , liste chainées ). Alors la STL est apparue pour nous donner tout cela déjà implementer , bug free ( donc pas de perte de temps sur du débuggage d'une structure bizarre ) , rapide/optimiser , multi plate forme .

Je n'ai rien contre ta structure , mais autant prendre ce que l'on te propose ... sachant que lorsque tu aura codé la structure , il se peut que tu ai fait une erreur ( même de frappe ) super idiote , et que tu passe 2heure à debugger.
Avec la STL t'aura moins de chance.

C'est optimiser c'est sure , recemment j'ai vu un gars qui disé que sa list était plus rapide que celle de la STL , finalement non :) ( en plus il était dans un cas très précis ).

La STL , te permettra aussi d'avoir des conteneurs des types que tu veux ( grace aux templates ).

Citation:

---

Envoyé par tnarol

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

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