Trier un tableau d'objets

Version imprimable

Bonjour je veux une fonction qui trie et renvoie un tableau d'objets trié selon un de ses attributs..
Voici mon code........

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
#ifndef PROCESSUS_H
#define PROCESSUS_H
 
#include <iostream>
#include <stdlib.h>
#include <vector>
 
using namespace std;
 
class Processus{
	private:
		int num;
		int dureeEstime;
		int dateArrive;
  		int dureeSej;
		int dureeAtt;
		int priorite;
	public:
		Processus(int a,int b,int c);
		Processus();
		void affiche();
		void attribuerPriorite();
		Processus * triProcessus(Processus procs[], int nbr);
 
};
#endif

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Processus * Processus::triProcessus(Processus proc[], int nb){
	Processus * process[nb] ;
	int minarr , i, j;
	for(i=0; i<nb; i++){
		minarr = i;
		for(j=i+1; j<nb ; j++){		
			if(proc[j].dateArrive < proc[minarr].dateArrive){
				minarr = j;
			}
		}
		process[i] = new          Processus(proc[minarr].num,proc[minarr].dureeEstime,proc[minarr].dateArrive);
	}
 
	return *process;
}

03/10/2013, 22h48
imperio

Au lieu d'envoyer un tableau d'objet, pourquoi ne pas envoyer un vector ?

Pourquoi ne pas faire un petit tour sur cette page ?
03/10/2013, 23h24
koala01

Salut,

De toutes façons:

1- Un processus est, typiquement, quelque chose qui a sémantique d'entité, ce qui implique parce que tu ne peux jamais avoir deux processus qui peuvent avoir des valeurs strictement identique en mémoire au même instant (autrement, comment être sûr que tu modifies bel et bien le processus que tu crois modifier :question:)

Ce qui implique que tu peux envisager de trier tes processus selon différnts critères, mais qu'il n'y a strictement aucune raison d'implémenter un opérateur < "global" (les classes ayant sémantique d'entité ne sont pas comparables).

2- Tu ne dois jamais donner la responsabilité du tri d'objets aux objets qui doivent être triés : c'est, systématiquement "autre chose" qui s'occupe de trier les objets, éventuellement, sur base de critères bien déterminés.

3- Comme l'a si bien dit impero, tu devrais utiliser la classe std::vector pour maintenir tes (pointeurs vers les) différents objets.
04/10/2013, 15h38
oodini

Citation:

Envoyé par koala01

Ce qui implique que tu peux envisager de trier tes processus selon différnts critères, mais qu'il n'y a strictement aucune raison d'implémenter un opérateur < "global" (les classes ayant sémantique d'entité ne sont pas comparables).

Même si on veut donner une priorité aux processus ?
04/10/2013, 15h59
Médinoc

Rien ne t'empêche de les trier par priorité, mais ce n'est pas aux processus qu'il revient de faire ça, c'est au conteneur. Les processus doivent seulement soit exposer directement en lecture leur priorité, soit exposer une fonction comparePriority() (mais jamais compare() tout court).
04/10/2013, 16h02
koala01

Citation:

Envoyé par oodini

Même si on veut donner une priorité aux processus ?

A ce moment là, ton processus (ou "autre chose", qui peut être externe à ton processus) dispose de l'information ad-hoc.

Mais, si tu veux trier tes processus selon leur priorité, ce sera plus une fonction du genre lessByPriority ou toute autre que tu utiliseras ;)

Le propre de quelque chose qui est identifié de manière unique est de ne permettre que la comparaison des éléments qui le composent, quel que soit l'élément envisagé pour la comparaison.

Le fait d'avoir un opérateur "<" (ou tout autre opérateur de comparaison possible) prend la sémantique de

Code:

Tel (processus, dans le cas présent) est plus petit que tel autre.

C'est très bien, mais plus petit selon quel critère :question:

Selon son identifiant unique :question:

Selon sa priorité :question:

Selon la durée depuis laquelle il s'exécute :question:

Il est impossible de le déterminer.

Du coup, tu te trouves avec un opérateur qui risque d'être utilisé à mauvais escient parce que chacun "verra midi à sa porte" et qu'un développeur envisagera une solution et un autre envisagera une autre solution, quand il n'y en aura pas un qui considérera que c'est d'abord la priorité, puis la durée depuis laquelle le processus s'effectue ;)

Si tu ne peux pas assurer la sémantique d'un opérateur, le mieux est encore de ne pas définir cet opérateur, quitte à définir une fonction équivalente qui précise exactement ce qu'elle fait et dans quel ordre.

Il faut bien comprendre qu'un opérateur n'est jamais qu'un "sucre syntaxique": une manière de laisser le développeur aller vers sa fainéantise naturelle ;)
04/10/2013, 16h07
oodini

Citation:

Envoyé par koala01

Le fait d'avoir un opérateur "<" (ou tout autre opérateur de comparaison possible) prend la sémantique de

Code:

Tel (processus, dans le cas présent) est plus petit que tel autre.

C'est très bien, mais plus petit selon quel critère :question:

La question reste valable avec les sémantiques de valeur, à partir du moment où les données sont composées de plusieurs valeurs.
04/10/2013, 16h18
koala01

Citation:

Envoyé par oodini

La question reste valable avec les sémantiques de valeur, à partir du moment où les données sont composées de plusieurs valeurs.

C'est moins certain ;)

Une classe "complex" qui a sémantique de valeur permet très facilement de déterminer si une valeur est effectivement plus petite qu'une autre.

Rien ne t'empêche de fournir des comportements qui ne comparent que la partie réelle ou que la partie imaginaire de ta classe complexe, mais cela prend malgré tout sens de comparer toute ta classe complexe.

Pour une classe "string", les opérateurs de comparaison ont également une sémantique clairement définie ;)

Pour une classe point, l'opérateur == a une sémantique clairement définie, mais ce n'est pas le cas de l'opérateur <.

<modeDigressionSévere = ON>Notes que je parle ici uniquement des opérateurs de comparaison, mais on pourrait faire pareil avec tous les opérateurs mathématiques ;)
<modeDigressionSévere = OFF>
Donc, si tu ne peux garantir une sémantique claire pour ton opérateur, tu ne dois surtout pas le fournir à l'utilisateur qui risque de mal le comprendre (en plus quel devrait être le résultat de compteBanquaire++ ou de processus-- en considérant bien sur que ce ne sont pas des itérateurs ;) :question:)
04/10/2013, 16h58
oodini

Si tu compares des coûts, ça a clairement une sémantique de valeur.

Mais un coût peut se décomposer en coût initial, en coût amorti, etc... Il peut aussi varier selon un taux de change courant.

Donc, l'ordonnancement n'est pas par nature plus évident pour les sémantiques de valeur.
04/10/2013, 17h18
koala01

Citation:

Envoyé par oodini

Si tu compares des coûts, ça a clairement une sémantique de valeur.

Mais un coût peut se décomposer en coût initial, en coût amorti, etc... Il peut aussi varier selon un taux de change courant.

Donc, l'ordonnancement n'est pas par nature plus évident pour les sémantiques de valeur.

Ah, ben, si tu es assez bête pour mélanger des couts initiaux, des couts amortis et des couts auxquels il faut appliquer un taux de change, tant pis pour toi :D

Un cout, c'est une valeur : 45€ 35 centimes. On se fout pas mal de la manière dont ce cout est calculé : Ce qui importe, c'est que 35€ 45 centimes est plus petit que 45€35 centimes et que ce dernier est plus grand que 45€ 34 centimes ;)

Si tu n'as besoin que des couts initiaux ou que des couts soumis à un taux de change, c'est à toi à faire en sorte de ne placer que ces couts dans la liste des valeurs que tu voudras trier!

Mais, à partir du moment où tu as ta liste de couts, tu vas les considérer comme des couts sans distinction aucune ;)

Pire encore, tu devrais les considérer comme des valeurs numériques sans distinction: qu'elle apparaissent à l'actif ou au passif dans un bilan ne change rien à leur nature réelle ;)
04/10/2013, 17h37
oodini

Un coût n'est pas forcément financier. Les nouvelles politiques RSE jugent de l'éligibilité d'un placement en fonction de son coût environnemental, par exemple. Cela ne s'exprime pas aussi simplement qu'un scalaire.

Les fonds de placement choisissent des placements selon une politique qu'ils déterminent, et qui définira le coût final. Ils peuvent pour cela ajouter des curseurs. Et au final, ils veulent un classement, donc un ordonnancement.

PS : je rappelle que je ne suis pas forcément à l'aide avec ces notions de sémantique d'entité ou de valeur
04/10/2013, 18h08
koala01

Pour faire simple : un type ayant sémantique de valeur est un type pour lequel il est tout à fait possible d'avoir deux variables totalement différentes mais présentant des valeurs identique, à un instant T de ton programme.

Ainsi, la notion de cout, quelle qu'elle soit, a sémantique de valeur parce que tu peux très bien te retrouver, à un instant T de ton application, avec deux investissements qui présentent la même valeur en terme de cout.

La manière dont ce cout est calculé n'a aucune importance! Cela pourrait parfaitement être le quotient du gain espéré à terme par le facteur risque de la société, ca reste très proche d'une valeur numérique : plus il est positif, plus le cout est intéressant, nul, il risque de se réduire à une opération blanche, négatif, ca casse (car cela signifie des pertes).

Je simplifies, c'est peut etre l'inverse, mais je me suis jamais intéressé de plus près que ca à la manière dont les investissements sont envisagés par les banques... Je peux donc me permettre de dire "une bêtise" à ce sujet là :D

A partir du moment où tu peux avoir deux variables qui peuvent, d'une manière ou d'une autre, être réduites à une "valeur numérique" (un entier, un pourcentage, un réel ou n'importe quoi d'autre) qui représentent exactement la même valeur à un instant T, ta classe a sémantique de valeur.

A partir de là, il est ad minima normal de pouvoir les comparer ne serait-ce que par égalité: tu réduis (si besoin) tes variables à une valeur numérique -- le cas échéant en suivant un algorithme déterminé -- et tu compares les deux valeurs pour savoir si elles sont égales.

De même, il peut etre normal de permettre les autres comparaisons ("plus petit que", "plus grand que" "plus petit ou égal", etc) afin de déterminer, par exemple, si l'investissement A est plus ou moins intéressant que l'investissement B (A.cout() < B.cout()... et si c'est A.cout() > B.cout, cela ne change pas grand chose :D )

[EDIT]Ce n'est pas forcément le cas, mais il n'y a que le contexte qui te permettra de déterminer s'il est ou non intéressant de permettre ces comparaisons ;)
[/EDIT]
Partant de là, il devient donc possible de trier tes investissements sur base de leur cout.

Mais il est tout aussi possible de trier tes investissements sur base d'autres critères, comme le nom de la société ou du fond de capitalisation, l'évolution suivie par le taux ces dernières 24heures / minutes /secondes ou que sais-je.

Et c'est là que l'on atteint la notion de type ayant sémantique d'entité car, même si tu fais deux investissements sur les mêmes actions, au même taux et au même moment, il y aura "quelque chose" (un identifiant unique) qui permettra de ne jamais confondre le premier et le deuxième investissement:

Tu ne pourras jamais avoir, à un instant T, une variable pour laquelle l'ensemble des valeurs est strictement identique à l'ensemble des valeurs d'une autre variable : tu as une contrainte d'unicité pour chaque variable qui sera identifiable de manière unique et non ambigüe, et ce, quel que soit la manière dont tu t'y prends pour assurer cette unicité ;)

Merci à vous,
J'ai pu trier grâce à cette méthode là:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Sjfp::triOrdrePasssage(Processus *p[],int nb){
	Processus *process;
 
	int i,j,min;
 
	for(i=0 ; i< nb; i++){
		min = i;
		for(j=i+1;j<nb;j++){
			if((*p[j]).getDureeRest()<(*p[min]).getDureeRest())
			 min=j;
		}
		process = p[i];
		p[i] = p[min];
		p[min] = process;
	}
 
}

Très bien, il ne te reste plus qu'à prendre la remarque d'impero en compte : les tableaux de taille dynamique, ca se gère à coup de std::vector :D

Le remplissage du tableau se fait sous la forme de
Code:

1 2 3 vector<Processus *> tab; // le tableau à remplire Processus *p = new Processus(/*...*/); tab.push_back(p);
et l'on transmet le tableau par référence (non constante vu qu'on veut le modifier), sous une forme proche de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 /** je garde ta propre logique dans un premier temps ;) */ void Sjfp::triOrdrePasssage(std::vector<Processus *> & tab){ Processus *process; int i,j,min; for(i=0 ; i< tab.size(); i++){ min = i; for(j=i+1;j<tab.size();j++){ if((*p[j]).getDureeRest()<(*p[min]).getDureeRest()) min=j; } process = p[i]; p[i] = p[min]; p[min] = process; } }
voir, le "fin du fin", on utilise les algorithmes fournis par le standard.

Si tu ne disposes pas des possibilités de C++11, tu peux créer ce que l'on appelle un foncteur (un objet fonction :D) sous la forme de
Code:

1 2 3 4 5 struct lessByPassageOrder{ bool operator()(Processus * lhs, Processus * rhs) const{ return lhs->getDureeRest() < rhs->getDureeRest(); } };
que tu pourras utiliser avec l'algorithme std::sort, sous une forme proche de

Code:

std::sort(tab.begin(),tab.end(), lessByPassageOrder());

Et si tu disposes des fonctionnalités de C++11, il est possible d'utiliser ce que l'on appelle les expressions lambda, mais je vais te laisser digérer ceci avant d'en parler ;)