Discussion :

[Eusebe]

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 :

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

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 !

[roulious]

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

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

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

[Invité]

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

[roulious]

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.

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.

[Invité]

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.

[roulious]

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:

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.

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

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

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 )

[Eusebe]

YEEEESSS !

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

Pour ceux que ça intéresse :

Code :

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

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

[Invité]

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

[roulious]

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

Code :

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

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 )

[Eusebe]

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

Code :

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

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 :

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

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

[Eusebe]

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

Code :

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

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 !

[Eusebe]

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

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.erase(std::remove(c.begin(), c.end(), element), c.end());
    *std::back_inserter(c) = element;
}

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

[roulious]

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.

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)

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.

[Laurent Gomila]

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)

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

[roulious]

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.

- 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

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

[Eusebe]

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

[Laurent Gomila]

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.

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.

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.