Déplacement d'éléments d'une "list"

Version imprimable

Bonjour à tous,

J'utilise des std::list pour stocker des éléments dont l'ordre est important (chaque élément est unique).
J'ai besoin de déplacer certains éléments pour les mettre en fin de liste. La seule solution que j'aie trouvée pour l'instant, c'est de rechercher l'élément à déplacer, le supprimer, puis l'ajouter en fin de liste.

Exemple de fonction qui le fait (si l'élément à déplacer n'existe pas, on se contente de l'ajouter) :
Code:

1 2 3 4 5 6 7 8 9 10 11 void pushFront(Objet * MonObjet) { std::list<Objet *>::iterator i = find(ObjetList.begin(), ObjetList.end(), MonObjet); if (i != ObjetList.end()) { ObjetList.erase(i); } ObjetList.push_back(MonObjet); }
Existerait-il une méthode plus simple pour réaliser cette action ?
Si ça n'existe pas, est-ce qu'il est possible de créer une méthode générique avec un template (répondez-moi uniquement par oui ou non, ça me permettra de m'exercer avec les templates ;) )

Merci d'avance pour vos réponses !

Tu peux utiliser swap au lieu de faire de l'insertion/suppression :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void pushFront(Objet * MonObjet)
{
    std::list<int>::iterator const it = std::find(ObjetList.begin(), ObjetList.end(), MonObjet);
 
    if(it != list.end())
    {
        // l'objet existe, on l'echange avec le dernier element de la liste
        std::swap(*it, *(ObjetList.rbegin()) );
    }
    else
    {
        // l'objet n'existe pas, on l'insere en fin
        ObjetList.push_back(MonObjet);
    }
}

27/07/2006, 15h55
Eusebe

Non, ça ne me va pas : swap déplace le dernier élément de la liste dans ce cas. Et moi, je veux que seul l'élément à mettre à la fin soit déplacé.

Par exemple, si j'ai une liste avec 1, 2, 3, 4.
Si je demande à placer 2 en dernier, je veux obtenir 1, 3, 4, 2.

Avec swap, j'obtiens 1, 4, 3, 2.
27/07/2006, 16h09
Invité

est ce que la methode std::list::splice() fait ce que tu veux ?
http://msdn2.microsoft.com/en-us/library/72fb8wzd.aspx
27/07/2006, 16h22
roulious

Citation:

Envoyé par toxcct

est ce que la methode std::list::splice() fait ce que tu veux ?
http://msdn2.microsoft.com/en-us/library/72fb8wzd.aspx

Je ne pense pas que ça soit la bonne solution non plus : splice déplace des éléments d'une liste à une autre.

Citation:

Envoyé par Eusebe

Non, ça ne me va pas : swap déplace le dernier élément de la liste dans ce cas.

Tiens, je n'avais pas lu correctement ton problème :). Ta fonction de départ semble être la façon de faire la plus simple. Tu peux en faire une fonction générique avec un template, regarde du côté de std::remove et std::back_inserter.
27/07/2006, 16h25
Invité

Citation:

Envoyé par roulious

Je ne pense pas que ça soit la bonne solution non plus : splice déplace des éléments d'une liste à une autre.

tout comme swap()... mais ya qua lui dire que les deux listes sont en fin de compte la meme liste.
27/07/2006, 16h33
roulious

Citation:

Envoyé par toxcct

tout comme swap()... mais ya qua lui dire que les deux listes sont en fin de compte la meme liste.

On peut, mais c'est interdit par le standard:

Citation:

Envoyé par Standard C++

void splice(iterator position, list<T, Allocator>& x); requires &x != this

Et c'est pareil pour les deux autres formes. Avec un peu de chance, ca marche avec VC++ vu que la MSDN ne donne pas cette précondition, mais le code ne sera plus standard et risque fortement de casser sur d'autres plateformes.
27/07/2006, 16h34
Eusebe
Oui, avec splice, je peux m'en sortir, mais je dois pour ça créer un itérateur de plus... et je ne suis pas sûr que ce soit plus efficace que le code d'origine (puisque ça fait aussi une suppression / ajout).
Code:

1 2 3 4 std::list<Objet *>::iterator i = find(ObjetList.begin(), ObjetList.end(), MonObjet); std::list<Objet *>::iterator j = i; ++j; ObjetList.splice(ObjetList.end(), ObjetList, i, j);
Je vais essayer de faire un template, faut bien y passer un jour (ça sera mon premier :lol:)

YEEEESSS !

J'ai réussi à créer mon premier template ! :mrgreen:

Pour ceux que ça intéresse :
Code:

1 2 3 4 5 6 template<typename T> void MoveBack(std::list<T> & TList, const T & Element) { TList.remove_if(std::bind2nd(std::equal_to<T>(), Element)); TList.push_back(Element); }

27/07/2006, 17h29
Invité

bien joué...
mais du coup, ca mérite bien une explication tout ca... lol

Un peu plus générique, mais avec un peu plus de pré-conditions sur les types :
Code:

1 2 3 4 5 6 7 8 template<typename Container> void MoveBack(Container& c, typename Container::value_type const & element) { std::remove(c.begin(), c.end(), element); std::back_inserter(sequence) backInserter; *backInserter = element; }
Dans ce cas, Container doit être une Back Insertion Sequence (http://www.sgi.com/tech/stl/BackInsertionSequence.html )

27/07/2006, 17h43
Eusebe
:mouarf:

Déjà, ma liste étant composée d'éléments uniques, j'ai remplacé
Code:

1 2 3 4 5 6 std::list<Objet *>::iterator i = find(ObjetList.begin(), ObjetList.end(), MonObjet); if (i != ObjetList.end()) { ObjetList.erase(i); }
par

Code:

ObjetList.remove_if(std::bind2nd(std::equal_to<Objet *>(), MonObjet));

Qui fait la même chose : suppression de l'élément MonObjet, mais en beaucoup plus court :D (merci roulious de m'avoir dis d'aller regarder vers std::remove).

Ensuite, j'ai considéré que je travaillais uniquement sur des 'list', mais que je ne connaissais pas leur contenu.

J'ai donc créé un template qui prend en premier paramètre la liste (dont le type de données listées est inconnu, et remplacé par "T") et en deuxième paramètre l'élément à mettre en fin de liste (qui doit être du type listé, et donc "T").

Après, il n'y a plus qu'à appliquer la suppression (avec remove_if), puis l'ajout en fin de liste de mon élément...

Citation:
Envoyé par roulious
Un peu plus générique, mais avec un peu plus de pré-conditions sur les types :
Code:

1 2 3 4 5 6 7 8 template<typename Container> void MoveBack(Container& c, typename Container::value_type const & element) { std::remove(c.begin(), c.end(), element); std::back_inserter(sequence) backInserter; *backInserter = element; }
Dans ce cas, Container doit être une Back Insertion Sequence (http://www.sgi.com/tech/stl/BackInsertionSequence.html )
Ouh là...
Je vais regarder ça de près...
Merci roulious !

Après quelques modifs, ça marche... :D
Mais comme je ne suis pas très sûr des modifs que j'ai faites :oops: , vous pouvez vérifier ?
Code:

1 2 3 4 5 6 template<typename Container> void MoveBack(Container& c, typename Container::value_type const & element) { c.erase(std::remove(c.begin(), c.end(), element), c.end()); *std::back_inserter(c) = element; }

27/07/2006, 18h31
Laurent Gomila

back_inserter ne sert à rien, il ne fait qu'appeler push_back au final.

std::remove est à exclure car la norme indique bien que l'on n'a aucune garantie quant aux valeurs se trouvant après l'itérateur renvoyé, même si elles sont toujours accessibles.

Mais vu que tu utilises erase dans ton dernier post... Tu veux supprimer les éléments, ou bien les placer à la fin comme tu le disais dans ton premier post ?
27/07/2006, 19h00
roulious

Citation:

Envoyé par Laurent Gomila

back_inserter ne sert à rien, il ne fait qu'appeler push_back au final.

Vrai. C'est des bouts de copier-coller qui restent d'une solution que j'essayais de faire avec juste des itérateurs.

Citation:

Envoyé par Laurent Gomila

std::remove est à exclure car la norme indique bien que l'on n'a aucune garantie quant aux valeurs se trouvant après l'itérateur renvoyé, même si elles sont toujours accessibles.

Dans son exemple, Eusebe n'utilise pas les valeurs situées apres l'itérateur renvoyé, mais les itérateurs sur ces valeurs, ce qui marche. Cette ligne de code se trouve dans la doc STL de chez SGI (http://www.sgi.com/tech/stl/remove.html#1)

Citation:

Envoyé par Laurent Gomila

Mais vu que tu utilises erase dans ton dernier post... Tu veux supprimer les éléments, ou bien les placer à la fin comme tu le disais dans ton premier post ?

Si l'élément existe, on le supprime de sa position actuelle. Après l'éventuelle suppression, on le met en fin de conteneur.

Si l'élément n'existe pas, remove renvoie end et erase ne fait rien.
27/07/2006, 19h12
Laurent Gomila

Citation:

Dans son exemple, Eusebe n'utilise pas les valeurs situées apres l'itérateur renvoyé, mais les itérateurs sur ces valeurs, ce qui marche. Cette ligne de code se trouve dans la doc STL de chez SGI (http://www.sgi.com/tech/stl/remove.html#1)

Oui, c'est ton code qui n'était pas bon (remove suivi d'un push_back) ;)

Citation:

Si l'élément existe, on le supprime de sa position actuelle. Après l'éventuelle suppression, on le met en fin de conteneur.

Si l'élément n'existe pas, remove renvoie end et erase ne fait rien.

Ok, j'avais lu un peu trop vite.

Par contre :

- remove_if + bind2nd + equal_to c'est inutile, par défaut la fonction remove (sans if) fait exactement la même chose sur l'élément passé en paramètre

- list.erase(std::remove(...)), si valide (pas sûr), c'est ni plus ni moins list.remove(...)
27/07/2006, 19h25
roulious

Citation:

Envoyé par Laurent Gomila

Oui, c'est ton code qui n'était pas bon (remove suivi d'un push_back) ;)

J'ai toujours tendance a me mélanger les pinceaux avec remove, quie je trouve assez peu intuitif.

Citation:

Envoyé par Laurent Gomila

- remove_if + bind2nd + equal_to c'est inutile, par défaut la fonction remove (sans if) fait exactement la même chose sur l'élément passé en paramètre

C'est bien pour ça que le bind_2nd n'est pas dans mon code ;)

Citation:

Envoyé par Laurent Gomila

- list.erase(std::remove(...)), si valide (pas sûr), c'est ni plus ni moins list.remove(...)

Dans ce cas précis, oui, puisque la liste contient des éléments uniques. Dans un cas plus général, si la liste peut contenir plusieurs éléments ayant une propriété donnée, la façon la plus simple et la plus sure de les effacer est de les placer à la fin du conteneur (ce que fait remove), et d'effacer ensuite l'intervalle (remove(...), end).
27/07/2006, 19h27
Eusebe

Citation:

Envoyé par Laurent Gomila

- list.erase(std::remove(...)), si valide (pas sûr), c'est ni plus ni moins list.remove(...)

Oui, mais la première solution est plus générique, et fonctionne aussi sur d'autres conteneurs, non ?
27/07/2006, 19h36
Laurent Gomila

Citation:

J'ai toujours tendance a me mélanger les pinceaux avec remove, quie je trouve assez peu intuitif.

Je suis assez d'accord. La fonction libre remove n'efface pas les éléments, alors que les fonctions membres remove (sur les conteneurs sur lesquels elle est disponible) le font ; du coup ça se mélange aussi un peu avec erase.

Citation:

Dans ce cas précis, oui, puisque la liste contient des éléments uniques. Dans un cas plus général, si la liste peut contenir plusieurs éléments ayant une propriété donnée, la façon la plus simple et la plus sure de les effacer est de les placer à la fin du conteneur (ce que fait remove), et d'effacer ensuite l'intervalle (remove(...), end).

Sauf sur les conteneurs sur lesquels remove est implémenté en fonction membre ; chose qui signifie toujours que ce sera plus adapté que d'utiliser la version libre.

Citation:

Oui, mais la première solution est plus générique, et fonctionne aussi sur d'autres conteneurs, non ?

Pas sûr, justement pour ce que je dis juste avant. Il faut voir quel type d'itérateur est traité par la fonction libre remove, et voir avec quels conteneurs ça colle.
27/07/2006, 19h48
roulious

Citation:

Envoyé par Laurent Gomila

Sauf sur les conteneurs sur lesquels remove est implémenté en fonction membre

Seul list est concerné. Toutes les séquences ont une fonction membre erase, list a en plus remove et remove_if.
27/07/2006, 20h09
Eusebe
Ok...

En fait, si je fais :
Code:

1 2 3 4 5 6 template<typename Container> void MoveBack(Container & c, typename Container::value_type const & element) { c.remove(element); c.push_back(element); }
Ca ne fonctionne pas sur le conteneur "std::string" par exemple. Alors qu'avec erase... ça fonctionne. (je n'en ai pas besoin, mais c'est pour bien comprendre)

Est-ce que l'on pourrait spécialiser le template avec erase pour les listes, en lui faisant dans ce cas utiliser remove ? (je n'ai pas réussi à le faire :aie: )
27/07/2006, 20h16
roulious

Citation:

Envoyé par Eusebe

Est-ce que l'on pourrait spécialiser le template avec erase pour les listes, en lui faisant dans ce cas utiliser remove ? (je n'ai pas réussi à le faire :aie: )

Non, on ne peut pas : ça serait une spécialisation partielle (list<T> pour tous les T), et les spécialisations partielles de fonctions ne sont pas autorisées actuellement par le langage.
27/07/2006, 20h22
Eusebe

Citation:

Envoyé par roulious

Non, on ne peut pas : ça serait une spécialisation partielle (list<T> pour tous les T), et les spécialisations partielles de fonctions ne sont pas autorisées actuellement par le langage.

Oui, c'est bien ce que me renvoyais le compilateur :aie:
27/07/2006, 20h37
Laurent Gomila

Il suffit de passer en interne par une classe, qui elle peut être spécialisée partiellement.
27/07/2006, 20h46
roulious

On peut effectivement, mais ça commence à être un peu de l'abus pour ce que voulait faire Eusebe au debut. Maintenant, si c'est pour expérimenter sur les templates et la spécialisation, c'est un bon exercice ;)
28/07/2006, 00h25
Luc Hermitte
Pourquoi ne pas utiliser splice ?
A en lire la doc http://dinkumware.com/manuals/?manua...l#list::splice, la seconde forme me parait faire exactement ce que tu veux.
->
Code:

1 2 std::list<...>::iterator where = mylist.find(what); mylist.splice(where, mylist, mylist.end());
Je soupçonne que contrairement aux autres méthodes, ce sont les itérateurs qui sont déplacés et non pas les objets qui sont copiés. Suivant ce que tu stockes, cela peut faire la différence.

Quoi d'autre ?
- l'idiome erase-remove, c'est pour purger tous les éléments qui sont trouvés. Donc attention avec ta liste si tu ne veux déplacer que le premier élément.
- Je suis déjà tombé sur une implémentation de std::remove qui déplace à la fin ce qui avait été trouvé. Car attention, cette fonction ne purge rien, elle réordonne. (=> pas faire un push_back juste après un std::remove)

Si tu as plusieurs éléments à déplacer, je suis sûr que tu dois pouvoir utiliser le std::stable_partition ici. Mais je ne sais pas s'il copie les éléments, ou bien les itérateurs. Je ne sais pas non plus si les implémentations de stable_partition font un peu de meta-prog pour reconnaitre qu'elles travaillent sur des listes et ainsi profiter de la structure particulière des listes.
28/07/2006, 10h53
Eusebe

Citation:

Envoyé par Luc Hermitte

Pourquoi ne pas utiliser splice ?
A en lire la doc http://dinkumware.com/manuals/?manua...l#list::splice, la seconde forme me parait faire exactement ce que tu veux.

En effet... J'avais zappé cette seconde forme sur la msdn :oops:

Citation:

Envoyé par Luc Hermitte

Je soupçonne que contrairement aux autres méthodes, ce sont les itérateurs qui sont déplacés et non pas les objets qui sont copiés. Suivant ce que tu stockes, cela peut faire la différence.

Je stocke des pointeurs. Donc ça ne doit pas faire trop de différence, si ?

Citation:

Envoyé par Luc Hermitte

- l'idiome erase-remove, c'est pour purger tous les éléments qui sont trouvés. Donc attention avec ta liste si tu ne veux déplacer que le premier élément.

Oui, ça c'est bon. J'ai bien précisé dans mes premiers messages que chaque élément était unique.

Citation:

Envoyé par Luc Hermitte

- Je suis déjà tombé sur une implémentation de std::remove qui déplace à la fin ce qui avait été trouvé. Car attention, cette fonction ne purge rien, elle réordonne. (=> pas faire un push_back juste après un std::remove)

Oui, oui, ça c'est noté ;)

Mais du coup, je me pose une nouvelle question. Quand je veux déplacer l'élément s'il existe, ou l'ajouter à la fin s'il n'existe pas, qu'est ce qui est le plus efficace (ou qui vous parait le plus propre) :

- supprimer l'élément avec remove (le test de son existence étant fait dans le remove) puis l'ajouter avec push_back ?

ou

- chercher l'élément dans la liste puis :
* s'il est trouvé, le déplacer avec splice
* s'il n'est pas trouvé, l'ajouter avec push_back

Citation:

Envoyé par Laurent Gomila

Il suffit de passer en interne par une classe, qui elle peut être spécialisée partiellement.

Citation:

Envoyé par roulious

On peut effectivement, mais ça commence à être un peu de l'abus pour ce que voulait faire Eusebe au debut. Maintenant, si c'est pour expérimenter sur les templates et la spécialisation, c'est un bon exercice ;)

Intéressant comme exercice... Je m'y suis donc frotté ;)
Voilà mon résultat :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 template<typename Container> class MoveBack { public: void operator () (Container& c, typename Container::value_type const & element) const { c.erase(std::remove(c.begin(), c.end(), element), c.end()); c.push_back(element); } }; template<typename T> class MoveBack<std::list<T> > { public: void operator () (std::list<T>& c, T const & element) const { c.remove(element); c.push_back(element); } };
A priori, ça fonctionne :D

Bon, maintenant que j'ai un peu progressé sur les templates, reste à voir ce que je vais utiliser en pratique... ;)

Alors, remove ou splice ? :mrgreen:

28/07/2006, 16h17
roulious
Citation:
Envoyé par Luc Hermitte

Pourquoi ne pas utiliser splice ?
A en lire la doc http://dinkumware.com/manuals/?manua...l#list::splice, la seconde forme me parait faire exactement ce que tu veux.
->

Code:

1 2 std::list<...>::iterator where = mylist.find(what); mylist.splice(where, mylist, mylist.end());
Ou plutôt
Code:

1 2 3 std::list<...>::iterator where = mylist.find(what); mylist.splice(mylist.end(), mylist, where);
On insère devant le premier paramètre et on supprime le dernier.

Citation:

Envoyé par Luc Hermitte

Quoi d'autre ?
- l'idiome erase-remove, c'est pour purger tous les éléments qui sont trouvés. Donc attention avec ta liste si tu ne veux déplacer que le premier élément.

Une des pre-conditions est que les éléments soient uniques (cf. premier post de la discussion
28/07/2006, 16h25
Invité

finalement, j'etais pas loin du tout du compte avec mon std::splice() 8-)
28/07/2006, 16h30
Eusebe

Citation:

Envoyé par roulious

Ou plutôt

Code:

std::list<...>::iterator where = mylist.find(what); mylist.splice(mylist.end(), mylist, where);

On insère devant le premier paramètre et on supprime le dernier.

Oui, c'est ce que j'ai fait pour tester ;)

Citation:

Envoyé par toxcct

finalement, j'etais pas loin du tout du compte avec mon std::splice() 8-)

Oui, tu avais raison, j'avais mal compris la msdn :oops:
28/07/2006, 23h43
Luc Hermitte

Si tu manipules des pointeurs, je pense que std::list::remove + push_back doit être un chouilla plus efficace. A mesurer.

Et quitte à faire de la meta-prog, il doit y avoir moyen de s'amuser
-> utilisation de std::list::splice pour les types qui coutent à copier
-> utilisation de container::remove + push_back si le container dipose de la fonction membre remove (faut sortir le SFINAE et un compilo très récent -> oublier GCC 3.x, donc sous windows il ne reste que VC2005 express dans les "gratuits" pré-packagés)
-> utilisation de stable_partition sur les containers à itérateurs bidirectionnels pour les types qui coutent cher à copier, mais qui proposent une fonction de swap qui ne coute plus rien en comparaison.

(Et evidemment, mesurer les perfs des diverses solutions sur les divers cas possibles avant de partir dans une quelconque direction -- je ne fais que supposer les divers coûts et peux donc complètement me planter.)
30/07/2006, 16h03
Eusebe

Merci à tous pour vos réponses !

Pour la méta-programmation, je crois que je suis encore un peu trop "jeune" pour me frotter à ce que tu proposes, Luc, mais je le note dans un coin pour plus tard, si j'ai le courage de me lancer dans cet exercice ;)

Fuseau horaire GMT +2. Il est actuellement 00h41.