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

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.

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

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.

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:

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

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 ;)

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.

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:

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

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

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:

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

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 ;)