Discussion :

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

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

[pyrrhon_]

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

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

[IrmatDen]

set_intersection?? Pourquoi ne convient-elle pas?

[mambo]

Je la connais pas, tu peux m'en dire un peu plus.

[pyrrhon_]

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

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

[IrmatDen]

Huh? Il se sert des itérateurs pour parcourir les conteneurs, donc je vois pas où se situe le souci?

[pyrrhon_]

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

[mambo]

Est que set_intersection est plus performante que

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

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

[IrmatDen]

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

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

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

[pyrrhon_]

En effet, c'était bien le back_inserter qui me manquait
Je retourne réviser mes classiques...

[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

[mambo]

Merci à tous pour votre aide.