[STL] Extraire les éléments communs entre 2 Listes

Version imprimable

25/04/2007, 14h47
mambo

[STL] Extraire les éléments communs entre 2 Listes

Salut tlm,

Est ce qu'il y aurait une fonction permettant d'extraire les éléments communs entre 2 listes stl?

Merci d'avance.
25/04/2007, 15h11
IrmatDen

Salut,

A tout hasard, ce serait pas le rôle de std::set_intersection()? (A noter qu'il faut que tes conteneurs soient triés par contre.)
25/04/2007, 16h04
pyrrhon_

Citation:

Envoyé par mambo

Salut tlm,

Est ce qu'il y aurait une fonction permettant d'extraire les éléments communs entre 2 listes stl?

Merci d'avance.

De quel type de conteneur s'agit-t-il exactement? std::list, std::vector?
Que veux-tu dire exactement par "élément commun"?
25/04/2007, 16h15
mambo

ce sont des std::list. Par élément commun, je veux dire les éléments qui ont la même valeur. En fait, ce sont des listes d'entiers.

J'ai déjà implémenté ma propre méthode. Je voulais savoir s'il y a une méthode déjà pour gagner en performance.

Merci.
25/04/2007, 16h16
IrmatDen

set_intersection?? Pourquoi ne convient-elle pas?
25/04/2007, 16h38
mambo

Je la connais pas, tu peux m'en dire un peu plus.
25/04/2007, 16h41
pyrrhon_

Meilleure est l'info à sa source:
http://www.sgi.com/tech/stl/set_intersection.html

;)
25/04/2007, 17h16
pyrrhon_

Aprés réflexion, je ne pense pas que set_intersection soit utilisable avec des std::list, car ce conteneur ne garanti pas la contiguïté des éléments en mémoire. Or l'algorithme d'itération utilisé dans set_intersection utilise, il me semble, un opérateur de type '++' pour parcourir la mémoire.
25/04/2007, 17h18
IrmatDen

Huh? Il se sert des itérateurs pour parcourir les conteneurs, donc je vois pas où se situe le souci? :?
25/04/2007, 17h27
pyrrhon_

Bah je ne sais pas, mais je ne parviens pas à implémenter un exemple qui fonctionne avec des list :aie:

Est que set_intersection est plus performante que

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
list<int> ExtractCommonElements(list<int> FirstList, list<int> SecondList)
{
	list<int> ReturnedList;
	list<int>::iterator fintegit;
	list<int>::iterator sintegit;
	bool bFound = false;
	for(fintegit = FirstList.begin(); fintegit != FirstList.end(); fintegit++)
	{
		bFound = false;
		sintegit = SecondList.begin();
		while((sintegit != SecondList.end())&&(bFound==false))
		{
			if((*fintegit) == (*sintegit))
			{
				bFound = true;
				ReturnedList.insert(ReturnedList.end(),(*sintegit));
			}
			sintegit++;
		}
	}
	return ReturnedList;
}

ou bien c'est la même chose?

25/04/2007, 17h52
koopajah

Bonjour,

J'aurai tendance a dire qu'elle est plus performante puisqu'elle agit sur des listes triées.
A première vue il me semble que pour chaque élément de la liste 1 tu cherches s'il est dans la liste 2 et si oui tu le sauvegardes et tu passes au suivant dans la liste 1, jusqu'a la fin de la liste 1.

Or si tes deux listes sont triées, tu n'as besoin de les parcourir qu'une fois chacune en parallèle.
Si élément de liste1 == element de liste 2 alors je sauvegarde
sinon si element de liste 1 > element de liste 2 alors je passe au suivant dans liste 2
sinon je passe au suivant dans liste 1

et t'arretes quand t'as atteint la fin d'une des deux listes.

Citation:

Envoyé par pyrrhon_

Bah je ne sais pas, mais je ne parviens pas à implémenter un exemple qui fonctionne avec des list :aie:

Voilou, je sais pas si c'est le back_inserter que tu as raté, mais voilà un exemple qui fonctionne ;)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>
 
using namespace std;
 
int main(int argc, char **argv)
{
	list<int> listOne, listTwo, listDest;
 
	listOne.push_back(1);
	listOne.push_back(4);
	listOne.push_back(8);
	listOne.push_back(42);
 
	listTwo.push_back(3);
	listTwo.push_back(8);
	listTwo.push_back(42);
 
	set_intersection(listOne.begin(), listOne.end(), listTwo.begin(), listTwo.end(), back_inserter(listDest));
 
	cout << "ListOne:" << endl;
	copy(listOne.begin(), listOne.end(), ostream_iterator<int>(cout, "\n"));
	cout << "listTwo:" << endl;
	copy(listTwo.begin(), listTwo.end(), ostream_iterator<int>(cout, "\n"));
	cout << "listDest:" << endl;
	copy(listDest.begin(), listDest.end(), ostream_iterator<int>(cout, "\n"));
 
	cin.get();
 
	return 0;
}

25/04/2007, 18h08
pyrrhon_

En effet, c'était bien le back_inserter qui me manquait :(
Je retourne réviser mes classiques... :aie:
25/04/2007, 22h18
alskaar

Salut,

y a un petit defaut au set_intersection ou set_difference, lorsque la liste contient des doublons ;)

sinon ca marche tres bien si tu peux faire un sort avant ;)
26/04/2007, 11h12
mambo

Merci à tous pour votre aide.