Discussion :

[befalimpertinent]

En ce moment j'ai besoin d'une structure de type priority_queue mais je dois pouvoir parcourir la file pour mettre à jour certains éléments.
Seulement vous le savez sans doute :

Priority_queue does not allow iteration through its elements

Mais je sais aussi que derrière la file ce cache un autre container standard (par défaut le vector)

Priority_queue is a container adaptor, meaning that it is implemented on top of some underlying container type. By default that underlying type is vector, but a different type may be selected explicitly.

Est il possible de parcourir ce vector ou est t il définitivement caché par l'implémentation ?
Si ce n'est pas possible, ce que je crains, une idée sur la structure qui conviendrait le mieux au problème ? Sachant que :

• les éléments sont triés par priorités
• pas de doublons
• normalement on a besoin d'acceder seulement au premier élément de la file et faire un pop() dessus
• Mais de temps en temps on doit pouvoir mettre a jour les éléments restants dans la file

Pour l'instant je suis sur une structure perso composée d'un set trié selon la priorité et j'essaye de gérer moi même ke caractère fifo. Seulement je ne suis pas sur que le set soit tip-top niveau suppression du premier élément.

[yan]

Bonjour.
Peut être qu'une map est plus adapté, ou la clef est la priorité d'un élément?

[yan]

Est tu sure que c'est basé sur vector??
si oui, la fonction top ( ) te permettrais d'avoir un pointeur sur le dernier élément du vector (du moins cela me semble logique : c'est plus rapide d'enlever le dernier élément d'un vector que le premier) puis du fait un parcours dans la mémoire?

mais, bon si ce n'est pas un vector, cela ne marchera pas.

[yan]

http://gcc.gnu.org/onlinedocs/libstd...pq_design.html

[befalimpertinent]

Peut être qu'une map est plus adapté, ou la clef est la priorité d'un élément?

Pour la map : je ne pense pas que ça soit adapter dans mon cas, au niveau du tri des éléments par priorités notamment et la structure Red Black tree du map est souvent lente si on la détourne de son utilité première.

Est tu sure que c'est basé sur vector??

Pour le vector oui d'apres http://www.sgi.com/tech/stl/priority_queue.html
c'est le fameux underlying container

Merci du lien j'ai appris pas mal de chose. Je devrais m'en sortir avec ça

[yan]

Est tu sure que c'est basé sur vector??
si oui, la fonction top ( ) te permettrais d'avoir un pointeur sur le dernier élément du vector (du moins cela me semble logique : c'est plus rapide d'enlever le dernier élément d'un vector que le premier) puis du fait un parcours dans la mémoire?
.

Ne tiens pas compte de cela... Dans la doc il explique que les éléments peuvent être rangé sous forme de heap. Il n'y as donc aucune raison que top donne le dernier élément de vector ...

[EDIT]
pour le heap regarde push_heap et pop_heap
http://www.sgi.com/tech/stl/pop_heap.html


[RE EDIT]
http://cpp.developpez.com/cours/cpp/...ge_21#LXXI-C-1
comme quoi y as toujours des chose à découvrir sur ce site

[Rupella]

à la limite, tu peux te fiche que la priority_queue utilise en interne un vecteur.
C'est la structure par défaut, mais tu peux mettre un autre conteneur (lesquels, je ne les ais pas en tête, il est trop tard)...

Par contre, l'interface de la priority_queue ne te permet pas d'itération sur les éléments, à par de les ôter au fur et à mesure...

A moins d'utiliser deux priority_queue, tu fais le pop() tu modifies, et l'insert dans l'autre...