Discussion :

[befalimpertinent]

Je cherche à créer une sorte de scheduler qui consiste simplement à m'ordonner des éléments suivant un coefficient et à me donner l'élément le plus grand.
Rien de bien compliqué sauf que je n'arrive pas à trouver le ou les container(s) adéquat(s) sachant que:

• les éléments sont triés
• je dois pouvoir supprimer le premier élément (pop() sur une file)
• je dois pouvoir mettre à jour certains éléments présent dans la file (impossible avec priority_queue seule) avec modification de la position dans la file suivant la nouvelle valeur

Pour l'instant j'en était à une class comportant :
- 1 multiset my_multiset trié par ordre décroissant, gérer moi même le caractère file
- 1 map<int,my_multiset::iterator> references pour pouvoir accéder rapidement à un élément de la file

Seulement plusieurs problème se pose alors. Beaucoup de suppression de premier élément du multiset (lors d'une mise à jour je dois supprimer l'ancien élément, puis insérer un ce même élément avec sa nouvelle valeur pour que sa position dans la file soit modifiée en conséquence).

Bref c'est pas top.
Si une âme charitable à compris ne serait-ce qu'un mot de ce que je voulais faire et me prodigue un conseil je lui serait reconnaissant.

[JolyLoic]

Changer la valeur d'index d'un conteneur trié n'est pas supporté directement par la STL. Il faut enlever l'élément, puis le remettre.

Boost::multi_index propose des trucs dans ce sens si ma mémoire est bonne.

[koala01]

Salut,

Pourquoi ne pas, tout bêtement, utiliser seulement un std::map, dont la clé est l'élément de tri et la valeur l'élément en lui-même

Cela ne résous pas le problème de devoir supprimer un élément pour le rajouter par la suite en cas de modification, mais, si la seule recherche effectuée porte sur l'élément de tri, c'est déjà amplement suffisant

[befalimpertinent]

Merci pour vos réponses.

Boost::multi_index propose des trucs dans ce sens si ma mémoire est bonne.

Désolé mais je préfère ne pas utiliser Boost (Me demander pas pourquoi je maitrise pas tout l'environnement qui m'entoure )

Pourquoi ne pas, tout bêtement, utiliser seulement un std::map, dont la clé est l'élément de tri et la valeur l'élément en lui-même

A la rigueur, plus une multimap qu'une map pour autoriser les doublons. Mais même avec une multimap je ne vois pas comment obtenir le caractère "file de priorité" de ma structure à moindre frais. Une multimap n'est pas trié et je veux pouvoir accéder pour un cout minimum à l'élément dont la valeur est la plus importante, le supprimer, mettre à jour quelques éléments de ma file, puis recommencer avec le nouveau plus grand élément.
Avec une multimap (ou toute structure non trié) je risque de devoir parcourir tout ma file pour trouver le plus grand élément.

C'est pourquoi j'étais plutôt parti sur un ensemble intrinsèquement trié.

[JolyLoic]

Une map ou une multimap sont triées.

[befalimpertinent]

Une map ou une multimap sont triées.

Certes, ils le sont par leur structure Red Black Tree pour accéléré la recherche dans un map. Mais puis-je vraiment parcourir ma map par ordre décroissant des valeurs directement et facilement ?
Parce que les quelques fois où j'ai utilisé une map il me semblait que lors de son parcours je retrouvai l'ordre utiliser au moment de l'insertion. Me trompe-je ?