Discussion :

[roulious]

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.

[Eusebe]

Ok...

En fait, si je fais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 )

[roulious]

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 )

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.

[Eusebe]

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

[Laurent Gomila]

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

[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

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

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Eusebe]

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

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 ?

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

- 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

[Eusebe]

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Alors, remove ou splice ?

[roulious]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Ou plutôt

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

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

[Invité]

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

[Eusebe]

Ou plutôt

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Oui, tu avais raison, j'avais mal compris la msdn

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

[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