list::sort parametres et fonctions membre

Version imprimable

18/04/2010, 13h30
NoIdea

list::sort parametres et fonctions membre
Bonjour, dans une classe Menu, j'ai un type list nommé order et un vecteur de Menu_Object* nommé MyMenu.

Menu_Object possède une fonction nommée int get_ordre().

J'aimerais trier order comme ceci :
Code:

1 2 3 4 5 6 bool Menu::compare(int one, int two) { if(MyMenu[one]->get_ordre()<MyMenu[two]->get_ordre()) return true; return false; }
Malheureusement, le compilateur m'affiche l'erreur

In constructor 'Menu::Menu(std::vector<Menu_Object*, std::allocator<Menu_Object*>>, void(*)(...
no matching function for call to 'std::list<int, std::allocator<int>>::sort(<unknown type>)'

il me propose 2 candidats que je peux vous afficher si nécessaire.

Après quelques test je me suis aperçu que le problème venait du fait que compare est une fonction membre de menu. Comment éviter ce problème ?

Code:

1 2 3 4 5 6 bool Menu::compare(int one, int two) { if(MyMenu[one]->get_ordre()<MyMenu[two]->get_ordre()) return true; return false; }
Pourquoi pas
Code:

1 2 3 4 bool Menu::compare(int one, int two) { return MyMenu[one]->get_ordre()<MyMenu[two]->get_ordre(); }
(Ma question est sérieuse, j'ai jamais compris le cheminement qui amenait à écrire qqch comme ta fonction).

Citation:

Après quelques test je me suis aperçu que le problème venait du fait que compare est une fonction membre de menu. Comment éviter ce problème ?

Une fonction membre a besoin de this, donc passe un foncteur contenant ce que tu veux, genre
Code:

1 2 3 4 5 6 7 8 9 10 11 struct Compare { Compare(Menu const& menu) : myMenu(menu) {} Compare(Compare const& other) : myMenu(other.myMenu) {} bool operator()(int one, int two) const { return myMenu[one]->get_ordre()<myMenu[two]->get_ordre(); } private: Menu& operator=(Compare const&); Menu const& myMenu; }

18/04/2010, 13h55
NoIdea

Je suis assez nouveau en c++ (mais j'ai fait pas mal de c), et je ne maitrise pas encore les foncteurs (j'utilise plutôt des pointeurs de fonctions).

La raison pour laquelle j'ai écrit ma fonction telle qu'elle est écrite est :
http://www.cplusplus.com/reference/stl/list/sort/

Je vais la changer pour ta fonction (bien que ca ne change pas grand chose).
Je pars me renseigner sur les foncteurs, cependant, comment passes tu en argument ton foncteur dans

Code:

order.sort(/*fonction*/)

?
Derniere question, l'utilisation de sort dans une liste chainée est plus rapide que sort pour un vecteur (du moins je l'espère) ?
18/04/2010, 13h59
Jean-Marc.Bourguet

Code:

order.sort(Compare(variable_de_type_menu));
18/04/2010, 14h15
bruno_pages
Citation:

Envoyé par Jean-Marc.Bourguet

(Ma question est sérieuse, j'ai jamais compris le cheminement qui amenait à écrire qqch comme ta fonction).

:lol: pas de panique, vous n'êtes pas le seul dans ce cas, dans le même genre il y a aussi
Code:

1 2 3 4 5 int i; ... if (i != 123) i = 123;
Citation:

Envoyé par NoIdea

l'utilisation de sort dans une liste chainée est plus rapide que sort pour un vecteur (du moins je l'espère) ?

8O l'accès a un élément quelconque d'une liste est en O(n) par contre l'accès a un élément quelconque d'un vecteur est en O(1), le tri d'un vecteur sera donc plus rapide dés qu'il y plus d'un élément

Merci beaucoup. J'ai réussi à l'aide de ceci :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 struct compare { private : Menu& menu; public : compare(Menu& pt):menu(pt){}; bool operator()(int one, int two) const { return menu.get_menu_object(one)->get_ordre()<menu.get_menu_object(two)->get_ordre(); } };
Me manque juste la réponse à ma question sur la rapidité de sort sur liste.

18/04/2010, 14h33
bruno_pages

Citation:

Envoyé par NoIdea

Me manque juste la réponse à ma question sur la rapidité de sort sur liste.

j'ai répondu à cela, regardez mieux ...
18/04/2010, 14h41
Jean-Marc.Bourguet

Citation:

Envoyé par bruno_pages

8O l'accès a un élément quelconque d'une liste est en O(n) par contre l'accès a un élément quelconque d'un vecteur est en O(1), le tri d'un vecteur sera donc plus rapide dés qu'il y plus d'un élément

Une liste peu être triée par un merge sort et de mémoire ceux-ci sont non seulement en N log N dans le pire cas (comme un heap sort), mais ont une meilleure constante qu'un quick sort et permettent de tirer avantage de données partiellement triées.

En prime, réordonner des noeuds d'une liste permet d'éviter les copies d'un tri en place sur un vecteur.

Donc ça ne me semble pas évident du tout que pour trier une liste soi un plus mauvais choix qu'un vecteur. Comme il y a d'autres effets qui peuvent favoriser le vecteur (meilleure localité), la seule réponse à la question est qu'il faut mesurer.
18/04/2010, 14h53
Arzar

Citation:

Envoyé par Jean-Marc.Bourguet

Une liste peu être triée par un merge sort et de mémoire ceux-ci sont non seulement en N log N dans le pire cas (comme un heap sort), mais ont une meilleure constante qu'un quick sort et permettent de tirer avantage de données partiellement triées.

En prime, réordonner des noeuds d'une liste permet d'éviter les copies d'un tri en place sur un vecteur.

Donc ça ne me semble pas évident du tout que pour trier une liste soi un plus mauvais choix qu'un vecteur. Comme il y a d'autres effets qui peuvent favoriser le vecteur (meilleure localité), la seule réponse à la question est qu'il faut mesurer.

Oui, mais dans le cas de NoIdea, c'est une liste d'int qui est triée. Un vecteur sera toujours plus rapide pour trier des entiers qu'une liste, non ?
18/04/2010, 15h03
Jean-Marc.Bourguet

Citation:

Envoyé par Arzar

Oui, mais dans le cas de NoIdea, c'est une liste d'int qui est triée. Un vecteur sera toujours plus rapide pour trier des entiers qu'une liste, non ?

C'est effectivement le genre de cas ou un vecteur a des avantages, mais de là à répondre toujours... toujours, c'est une contrainte forte. Si tu tries ton vecteur avec un quick sort et que tu tombes dans le cas où il est en N², ça risque d'être quand même être plus lent.
18/04/2010, 15h24
NoIdea

Ok merci pour toutes ces réponses. Dans mon cas l'utilisation d'une liste ou d'un vecteur ne change rien (je me contente de trier et de lire) sauf la rapidité.
Je vais faire des test. Je vous tiens informés

Avec ce code : (je sais c'est du C mais bon...)

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
34
#include <stdlib.h>
#include <stdio.h>
#include <list>
#include <time.h>
 
using namespace std;
 
int main()
{
	srand(time(NULL));
	int i,j, nb=1000;
	double start, end;
	list<int> L[nb];
	if(L==NULL)
		printf("probleme");
	list<int>::iterator it;
	for(j=0;j<nb;j++)
	{
		it=L[j].begin();
		for(i=0;i<10000;i++)
		{
			L[j].insert(it,rand());
		}
	}
	start=time(NULL);
	for(j=0;j<nb;j++)
	{
		L[j].sort();
	}
	end=time(NULL);
	double dif=end-start;
	printf("%G",dif/CLOCKS_PER_SEC);
	system("pause");
}

Je trouve 5 millisecondes. Je vais maintenant tester avec vector.

Avec ce code j'obtiens que 2 millisecondes :

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
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <time.h>
#include <algorithm>
 
using namespace std;
 
int main()
{
	srand(time(NULL));
	int i,j, nb=1000;
	double start, end;
	vector<int> V[nb];
 
	for(j=0;j<nb;j++)
	{
		for(i=0;i<10000;i++)
		{
			V[j].push_back(rand());
		}
	}
	start=time(NULL);
	for(j=0;j<nb;j++)
	{
		sort(V[j].begin(), V[j].end());
	}
	end=time(NULL);
	double dif=end-start;
	printf("%G",dif/CLOCKS_PER_SEC);
	system("pause");
}

Je conclus donc que pour un conteneur pas du tout trié et qui contient des ints, vector est mieux que liste ?