container pour scheduler

:salut:
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. :D

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.

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

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

Merci pour vos réponses.

Citation:

---

Envoyé par JolyLoic

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 :cry: (Me demander pas pourquoi je maitrise pas tout l'environnement qui m'entoure :cry:)

Citation:

---

Envoyé par koala01

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

---

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

Une map ou une multimap sont triées.

Citation:

---

Envoyé par JolyLoic

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 ?

Quand tu parcours de begin() à end() en incrémentant l'itérateur tout bêtement, tu as la garantie d'itérer selon l'ordre défini pour la clef.

Exact, un petit oubli de ma part :oops:

Disons que ma structure peut se résumer à une simple

Code:

---

std::map<int float> my_map

---

Seulement ici mes éléments seront trié par la valeur de l'identifiant (l'int) alors que je souhaite les trier suivant leur valeur (le float).
je pourrais alors me tourner vers une

Code:

---

std::multimap<float,int> my_multimap

---

(multi pour autoriser les doublons de mes valeurs)
Mais ici je vais avoir du mal à accéder rapidement à la valeur d'un identifiant passé en paramètre (parcourir toute la multimap à la recherche de la bonne valeur ie l'identifiant ?) .
Que faire alors ? Un mix :

Code:

---

1 2 3

std::map<int float> value_access std::multimap<float,int> sorted_value

---

Trié une map par valeur ? (je ne pense pas que cela soit possible)
Où une autre solution ?

:question:

Citation:

---

Envoyé par befalimpertinent

Où une autre solution ?

---

Il tu suffit d'utiliser boost::multi_index et de... Oups, pardon....

Pour bricoler un truc à la main, je partirais probablement vers une solution assez proche de celle décrite initialement.

Ok merci !
Je devrais pouvoir me débrouiller avec ça.
Et je vais aussi en profiter pour zieuter du côté du fameux boost::multi_index.

Bonjour,

Ce qui est certain, c'est que si tu utilises un double conteneur hfait à la main, tu devrais le contenir dans une classe dédiée (un template?) afin de localiser le code qui assume la responsabilité de la cohésion des conteneurs près d'iceux.

quelque chose comme :

Code:

---

1 2 3 4 5 6 7 8 9 10

template<typename T, typename V> class my_own_priority_queue { ... void insert_element_with_value(T,V); void insert_element_with_value(T,V); T pop(); V getValue(T); void setValue(T,V); }

---