-
Choix du bon conteneur
bonsoir,
j'ai consulté la faq sur les differents conteneur de la STL mais j'ai encore un souci.
je dois posseder une structure contenant des pointeur vers des Objets.
ces objet possede un champ qui me permet de les trier de tel sorte que le plus grand element soit en premiere position.
a partir de la je consulte le premier element, l'utilise et souhaite le rendre indisponible (le supprimer du conteneur me semble le mieux).
mais la certain des autres elements sont mis a jour et doivent etre reoganiser afin de trouver le plus grand.
Donc plusieurs question se pose a moi :
- faut-il mieux utiliser une map un un conteneur sequentiel ?
- un vector ou une list pour un algo de tri ?
- est-il preferable de trier a chaque fois ou de parcourir a la recherche du plus grand ?
est-il possible de faire la chose suivante ?
retiré l'objet utilisé puis faire un truc du genre :
POUR chaque objet en liaison avec lui
-> mettre a jour cette objet
-> le reinsérer a la bonne place
sachant que le nombre d'objet a mettre a jour est assez minime au vue du nombre de données ?
et dans ce cas y a-t-il une methode permettant de faire un insert dans un LIST avec un parametre de tri ?
merci
-
:?
Je ne comprends pas.
Si tu ne fais que retirer un élément, ton ordre ne sera pas cassé !
-
en effet mais le probleme viens du fait que certain element seront alors mis a jour et donc devront etre remis au bon endroit dans l'ordre.
-
Si je résume, tu as X éléments, tu veux les conserver dans un ordre précis, accéder au plus grand, le supprimer et déplacer Y éléments de ton conteneurs qui auront été mis à jour aprés le traitement du plus grand, c'est ca?
Hum, ca demende encore des précisions, est-ce que tu va construire ton ensemble une fois pour toute, ou est-ce que tu va ajouter de nouveaux éléments souvent ? [ dans le deuxième cas, le std::set peut être intéréssant ] .
La supprersion de l'élément visité dans tout les cas [ compte tenu du fait que tu as un conteneur trié ] ne posera pas de problème, ni ne devrai ocassioner un grand temps de traitement .
En revanche, l'ajout de nouveaux élément et ( ce qui est lié ) le déplacement de certains éléments ... [ car je supose que souvent, déplace un élément revient a le supprimer puis le réinsérer ] va être a mon avis ton principal critère de choix .
[ je ne suis pas un expert en la matière, donc je te laisse te faire une idée plus précise par toi même plutot que de te dire des conneries ] .
-
Une mise à jour va impliquer :
- un retrait et un rajout dans le cas des ensembles (std::set). Même chose pour les tables associatives si la clé devait changer.
- un retrait et un rajout si l'évaluation de l'élément demande à le déplacer. Il doit y avoir moyen diminuer les déplacements si tu peux connaitre les positions avant et après (à coup de std::container::find ou de std::equal_range)
Après, le tout est de savoir les probabilités des diverses manipulations que tu feras ansi que leur criticité.
-
