Discussion :

[oodini]

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.

[yan]

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

[oodini]

Ou un stack, auquel j'applique l'algorithme unique_copy ?

[yan]

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

[yan]

ou peut être une list avec le find_if.

[oodini]

stack c'est dernier entrée -> premier sortie

Je m'étais en fait trompé dans le post initial.

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}

Aïe...

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

[wiztricks]

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

[yan]

http://www.sgi.com/tech/stl/stack.html

By default that underlying type is deque, but a different type may be selected explicitly.

Utiliser une deque, un vector ou une list à la place de la stack pourrais surement le faire.

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.

[HanLee]

Au pire...

http://www.boost.org/doc/libs/1_36_0...#multiple_sort