Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Conteneur ordonné avec unicité ?
Bonjour,
J'aurais besoin d'une séquence de chaînes de caractères du style "dernière entrée, première sortie", mais avec garantie de l'unicité.
Apparemment, la STL n'offre rien de cela (?).
Comment procéderiez-vous ?
Une list avec par la suite une suppression des doublons via un des algorithmes offerts par la STL ?
MErci.
Salut.
Peut être une deque
http://www.sgi.com/tech/stl/Deque.html
et l'algo std::find_if pour voir si l'objet n'existe pas.
Pour info, il existe maintenant unordered_set ,mais j'ai aucune idée si cela correspondra vraiment à ce que tu veut...
Ou un stack, auquel j'applique l'algorithme unique_copy ?
stack c'est dernier entrée -> premier sortie et l'algorithme unique fait la comparaison uniquement sur les éléments consécutif :Envoyé par oodini
{1,1,1,1,2,3,4,5,1}
donnera
{1,2,3,4,5,1}
http://r0d.developpez.com/articles/algos-stl/#LII-B-8
ou peut être une list avec le find_if.
Je m'étais en fait trompé dans le post initial.
Aïe...et l'algorithme unique fait la comparaison uniquement sur les éléments consécutif :
{1,1,1,1,2,3,4,5,1}
donnera
{1,2,3,4,5,1}
Y'a sûrement moyen de faire quelque chose avec un map.
Je fais mon stack, et ensuite, je crée un map avec comme clés les chaînes de caractères, et comme valeur le "classement" de la première occurence dans le stack. Puis je reconstruis un vecteur à partir du map.
Un peu tiré par les cheveux, mais bon...
Par construction un stack est dernier entré, premier sorti.
Un conteneur de type deque semble plus approprié pour obtenir le FIFO.
Si nous souhaitons en plus que la chaîne de caractère soit "unique", il y a deux approches:
- comparer une chaine à insérer à l'ensemble des chaines de la liste,
- créer un map qui servira à tester l'existence de la chaine.
Le résultat sera le même, les performances varient en fonction du nombre de chaines de caractères qui seront dans la liste à l'instant T.
- W
http://www.sgi.com/tech/stl/stack.html
Utiliser une deque, un vector ou une list à la place de la stack pourrais surement le faire.By default that underlying type is deque, but a different type may be selected explicitly.
Mais vue que tu doit avoir accès au élément pour tester l'unicité à chaque fois,
un vector sera surement plus optimisé par rapport à la liste (mémoire contigüe). vector vs deque, aucune idée. Je ne connais pas deque.
Aprés pour tester l'unicité, le std::find.
[edit] Ou comme le propose wiztricks, peut être utiliser un autre centenaire comme le set ou map en parallèle.
Je crois que je vais gérer l'aspect FIFO en amont pour travailler en LIFO avec un vector, puis lors de l'utilisation des éléments, utiliser une map.
Si l'élément traité du vector n'est pas dans la map, je le rajoute, et je fais mon traitement avec cet élément. Autrement, je zappe et passe à l'élément suivant dans le vector.
Il y a des conteneurs déjà adaptés pour ça.
FIFO : std::queue<>
LIFO : std::stack<>
Et ce n'est pas une map que tu dois utiliser pour l'unicité, c'est un std::set<>.
std::map<> est une table associative.
En fait, ce problème s'imbrique un autre, et je vais sans doute utiliser une liste et un map, la valeur de ce dernier mes servant à autre chose.
Faut que je résolve des problèmes de conception.
Je vous tiens au courant ! Merci à tous !
Ce sont des adapteurs de conteneurs. Apres c'est toi qui choisi quel conteneur doit etre encapsulé (avec des restrictions eveidemment). Par défaut je crois que c'est une deque pour les 2 car ca peu a la fois gérer le FIFO et le LIFO (un vector est très adapté au LIFO cependant). L'adapteur va te fournir une interface simplifiée sur le conteneur en dessous qui te permet uniquement de gérer le comportement désiré.
SPARK
Moteur de particule C++ opensource avec modules de rendu OpenGL, Irrlicht et SFML
Répondre avec citation
Partager