Discussion :

[NoIdea]

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 :

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

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 ?

[Jean-Marc.Bourguet]

Code :

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

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 :

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

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

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 :

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

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

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

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

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

[Jean-Marc.Bourguet]

Code :

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

order.sort(Compare(variable_de_type_menu));

[bruno_pages]

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

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

Code :

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

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

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

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

[NoIdea]

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

Code :

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

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.

[bruno_pages]

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

j'ai répondu à cela, regardez mieux ...

[Jean-Marc.Bourguet]

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.

[Arzar]

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 ?

[Jean-Marc.Bourguet]

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.

[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

[NoIdea]

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

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

[NoIdea]

Avec ce code j'obtiens que 2 millisecondes :

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