STL : retirer une liste d'une liste

Bonjour, j'ai croisé 2-3 questions sur le sujet mais pas dans mon contexte :

C'est presque tout dans le titre... j'ai 2 listes STL et je voudrais exclure l'une de l'autre. Existe-il une fonction toute faite ? Laquelle?
Faut-il se la faire tout seul ...Comment relativement optimiser le code?

RQ :
_void unique() ne répond pas à la question
_void remove_if(Predicate p); Je crois pas qu'on puisse faire avec un prédicat...!?
_void remove(); ... et de l'huile de coude?

Merci d'avance.

Tu peux très bien faire ça avec un prédicat oui.
Après y'a la fonction membre splice...

Tu crée un prédicat, tu lui files en variable membre une réfèrence vers ta seconde liste puis tu fais un truc du style:

Code:

---

1 2 3

if(seconde_liste.contient(element)) return true; return false;

---

Ce qui est en O(n^2) au fait.
On peut aisément réduire ça si une des listes est modifiable ou si on peut utiliser de la mémoire.

regardes les algo set_difference,set_intersection et set_union

les predicats de base sont tes 2 listes triés et uniques
dans le cas ou ta liste n'est pas unique faut réécrire l'algo

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

Citation:

---

Envoyé par loufoque

Ce qui est en O(n^2) au fait.
On peut aisément réduire ça si une des listes est modifiable ou si on peut utiliser de la mémoire.

---

En pondant un algo de a à z n'importe qui peut y arriver, mais la question spécifiait une solution simple utilisant la stl.
Sinon, quitte à tout faire soi même, c'est encore plus simple et rapide si on a deux listes triées (mais encore faut-il que la classe stockée le supporte).

Merci pour toutes vos réponses.

C'est finalement set_difference que j'utilise... sauf qu'il a fallu ruser : cette fonction nécessite des opérateurs de comparaison(<,>,=,...).

RQ : cette méthode (et celle du même genre) nécessite un ostream_... en paramêtre, existe-t-il un moyen de faire que cette sortie supplémentaire soit inactivée? (STL_NULL ou un truc du genre)

Citation:

---

RQ : cette méthode (et celle du même genre) nécessite un ostream_... en paramêtre, existe-t-il un moyen de faire que cette sortie supplémentaire soit inactivée? (STL_NULL ou un truc du genre)

---

De quel ostream_... parles-tu :question:

Citation:

---

#include <algorithm>

template <class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_difference (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_difference (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);

---

Ca c'est le header... et le OutputIterator, c'est le truc dont je voulais parler à cause de l'exemple :

Citation:

---

#include <algorithm>
#include <set>
#include <iostream.h>

int main()
{

//Initialize some sets
int a1[10] = {1,2,3,4,5,6,7,8,9,10};
int a2[6] = {2,4,6,8,10,12};

set<int, less<int> > all(a1, a1+10), even(a2, a2+6),
odd;

//Create an insert_iterator for odd
insert_iterator<set<int, less<int> > >
odd_ins(odd, odd.begin());
//Demonstrate set_difference
cout << "The result of:" << endl << "{";
copy(all.begin(),all.end(),
ostream_iterator<int>(cout," "));
cout << "} - {";
copy(even.begin(),even.end(),
ostream_iterator<int>(cout," "));
cout << "} =" << endl << "{";
set_difference(all.begin(), all.end(),
even.begin(), even.end(), odd_ins);
copy(odd.begin(),odd.end(),
ostream_iterator<int>(cout," "));
cout << "}" << endl << endl;

return 0;
}

Output :
The result of:
{1 2 3 4 5 6 7 8 9 10 } - {2 4 6 8 10 12 } =
{1 3 5 7 9 }

---

...j'ai confondu.
Mais
set_difference(all.begin(), all.end(),even.begin(), even.end(), odd_ins);
ne ressort-il pas déjà un pointeur vers la liste différentiée?

La fonction va copier les éléments à retenir à l'aide du dernier paramètre -- le OutputIterator. Dans l'exemple, ils envoient le résultat directement sur la sortie standard à l'aide d'un ostream_iterator.

Toi tu peux par exemple passer le begin() d'un conteneur correctement dimensionné (pour le remplir), ou bien un back_inserter sur un conteneur vide si tu ne connais pas à l'avance la taille (back_inserter va insérer les données à l'aide de push_back).

Oui, je passe en argument ma liste de sortie... bien qu'il le fait aussi en return.

Mais pourquoi en back et pas en front?(J'ai pas besoin de connaître l'ordre... oui j'aurais pu prendre un ensemble.)

Citation:

---

Envoyé par DEVfan

bien qu'il le fait aussi en return.

---

Non. L'itérateur renvoyé pointe vers le dernier élément copié.

Citation:

---

Envoyé par DEVfan

Mais pourquoi en back et pas en front?(J'ai pas besoin de connaître l'ordre... oui j'aurais pu prendre un ensemble.)

---

Tu as aussi front_insert. Ou inserter tout court.

c'est quoi ce iostream.h ?

tu utilises un set, inserer en back ou front n'a pas de sens pour ce type de conteneur
pour une liste ca a plus de sens par exemple.

sinon j'ai pas bien compris ce que tu veux faire avec le ostream ?
un truc comme ca ?

Code:

---

1 2	set_difference(all.begin(), all.end(),even.begin(),even.end(), ostream_iterator<int>(cout, " "));

---

enfin, set_difference ne demande que l'implementation de operator<
apres tu as toujours l' operateur de recopie par defaut et le constructeur par defaut ( a la seconde je sais plus lequel il utilise meme si il semble plus logique que ce soit le constructeur de recopie )