Discussion :

[strayyy]

Bonjour à tous, mon problème est assez clair... J'ai lu sur http://cpp.developpez.com/faq/cpp/?page=STL qu'on pouvait faire un sort sur un vector, ce dont j'ai enormément beosin.

En gros, j'ai un zoo à gérer, avec des animaux (mignon, hein ), et je dois trier les animaux selon leur identifiant, en utilisant la STL, et ici, j'ai choisi un vector. BON.

J'ai donc deux classes, une zoo et une animal, sachant que dans zoo, je stocke un vector d'animaux, que je dois trier selon leur id...

Voici la déclaration d'animal, avec la surcharge de l'opérator < nécessaire à std::sort:

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
class animal {
 
	private:
		int id;
		string nom;
		int age;
		race *r;
	public:
 
		//constructeurs
		animal(int id, int age, string nom, race* r);
		/*animal(int id, string nom);
		animal(int id);
		animal();
		//affichage*/
		void aff_animal();
		int getid(){ return id;}
		bool operator< ( const animal & comparer) const;
};

La surcharge de <:

Code :

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

1
2
3
4
5
6
7
8
9
 
bool animal::operator< (const animal & comparer) const{
 
        if(this->id < comparer.id) return true;
 
 
        return false;
 
}

et mon tri (ici, on est dans la classe zoo, et ani est le vector d'animaux):

Code :

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

1
2
3
4
5
6
7
 
std::sort( this->ani.begin(), this->ani.end());
        cout<<"trié"<<endl;
        if(this->ani[0]<this->ani[1]) {
            cout<<"YEEAAH";}
            else{
                cout<<"blaaah";}

Bref, je compile, aucune erreur. Je lance.

Lorsque j'affiche mon vector, après avoir utilisé ma methode de tri, il ne l'est pas. J'ai essayé de foutre un cout<< dans la surcharge de <, mais ça n'affiche rien. Ensuite, j'ai toujours un YEEAAH qui s'affiche... quelque soit l'id de l'animal.

Voila, je galère depuis 2 bonnes heures, à chercher sur le net, et ça a l'air de marcher pour tout le monde, mais pas pour moi... :'(

j'ai aussi essayé en donnant une fonction (sort peut avoir 3 arguments...), mais pareil.

merci à ceux qui auront le courage de m'aider .

[HanLee]

Si tous les ID sont uniques, et que ça t'affiche YEAHH, alors on a bien les 2 premiers éléments de ton vecteur qui sont triés comme attendu, et il y a de grandes chances que tout le reste de ton vecteur le soit.

C'est normal, car

Code :

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

this->ani[0] < this->ani[1]

et que std::sort trie dans l'ordre croissant.

Si tous les ID sont uniques encore, et que ça t'affiche blaaah, là il y aurait un problème effectivement.

[strayyy]

Ben justement, ils ne le sont pas, puisque j'affiche tout mon vector, et que tout est en désordre.

Mais jviens de penser que je stocke des POINTEURS... Le sort ne me trierais pas par hasard les adresses des pointeurs? Ce qui serait au final l'explication du problème...

Et vu que ça affiche YEAAAH, alors que le 1er est supérieur au second, c'est justement que ça plante quelquepart...

[HanLee]

Ben justement, ils ne le sont pas, puisque j'affiche tout mon vector, et que tout est en désordre.

Mais jviens de penser que je stocke des POINTEURS... Le sort ne me trierais pas par hasard les adresses des pointeurs? Ce qui serait au final l'explication du problème...

Oui !

[strayyy]

Apres, je dit ça, jsuis pas sur, mais ça m'etonnerais pas xD...

Bon, et du coup, comment trier? :'(

EDIT: on cherche pas plus loin, c'est ça... si j'inverse mon signe de comparaison dans le test, j'ai un blaaah...

Et du coup, ça ne résout pas mon ennui... comment trier? On peut faire un tri manuel? Genre tout récupérer dans un tableau, et tout refoutre dedans par recopie? mais c'est ptetre pas tres joli...

[JolyLoic]

http://cpp.developpez.com/faq/cpp/?p...TL_custom_sort

[yan]

http://cpp.developpez.com/faq/cpp/?p...TL_custom_sort

De plus comme tu stock des pointeurs, ton prédicat devra prendre deux pointeurs en entrée

[strayyy]

Merci, j'avais déjà vu le sort avec un prédicat, mais je me rappelle plus si je l'avais essayé avec des pointeurs, ou des animaux directement. Je teste et je vous dit ça, mais perso, j'ai peu d'espoir .

Merci en tout cas!!!


EDIT: HIYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

ça marche!

Pour ceux qui galèreraient autant que moi... voila le predicat à utiliser:

Code :

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

1
2
3
4
5
6
7
8
struct comparerAnimalId
{
    bool operator ()( animal * a1,  animal * a2)
    {
        return a1->getid() < a2->getid();
    }
 
};

Par contre, si quelqu'un pouvait me dire pourquoi on doit faire un struct pour le foncteur ce serait cool... Je comprend le coup de la surcharge de (), mais pas pourquoi on utilise un struct suivi d'une surcharge de () plutot qu'une fonction...

[JolyLoic]

On peut utiliser une fonction aussi, ça marchera.

Dans ce cas, ce qu'on passera est un pointeur de fonction, et l'appel de fonction sera, probablement, effectué à chaque comparaison.

Avec un tel argument, lorsque tu instancies le template std::sort, le type du comparateur est connu du compilateur. Il a donc facile à optimiser et à inliner l'appel de fonction.

Du coup, on se retrouve avec du code plus rapide. C'est principalement ce qui fait que le std::sort du C++ est significativement plus rapide que le qsort du C.

[yan]

il me semble que l'utilisation des const reference est mieux.

Code :

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

1
2
3
4
5
6
7
8
struct comparerAnimalId
{
    bool operator ()( const animal * & a1,const   animal *  & a2)
    {
        return a1->getid() < a2->getid();
    }
 
};

Avec un tel argument, lorsque tu instancies le template std::sort, le type du comparateur est connu du compilateur. Il a donc facile à optimiser et à inliner l'appel de fonction.

Du coup, on se retrouve avec du code plus rapide. C'est principalement ce qui fait que le std::sort du C++ est significativement plus rapide que le qsort du C.

ca pemet aussi de faire des fonctions beaucoup plus evolué, d'utiliser des variable en plus et plein de chose. Pour un sort c'est limité ok, mais pour for_each, generate ... ca l'est plus

exemple

Code C++ :

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
struct SommePuissance
{
explicit SommePuissance(const float& puissance) :m_resultat(0),m_puissance(puissance){};
 
void operator () (const float & val) 
   {
    resultat+= pow(val, m_puissance);
   }
float m_resultat;
float m_puissance;
};
 
 
std::vector<float> myVect;
...//on remplie  myVect;
 
int resultat = std::for_each(myVect.begin(),myVect.end(),SommePuissance(2.2)).m_resultat;
std::cout<<resultat <<std::endl;
 
resultat = std::for_each(myVect.begin(),myVect.end(),SommePuissance(4.)).m_resultat;
std::cout<<resultat <<std::endl;

[strayyy]

Okay merci, maintenant chuis calé là dessus .

Et j'ai fini mon ptit projet à la noix (1200 lignes, peuh!), j'aurais une bonne note...

[HanLee]

@JolyLoic : encore qu'il paraitrait que certains compilateurs arrivent à optimiser en inlinant les pointeurs de fonctions qu'on leur passe.

@Mongaulois : yep, mais souvent on peut faire plus concis et plus élégant avec boost.bind combiné à des fonctions libres, quand il n'y a pas de problèmes de performances.

[JolyLoic]

@JolyLoic : encore qu'il paraitrait que certains compilateurs arrivent à optimiser en inlinant les pointeurs de fonctions qu'on leur passe.

D'où mon "probablement". Par contre, je n'en ai pas encore rencontré. Tu en connais ? Ca m'intéresserait de bencher.

[HanLee]

D'où mon "probablement". Par contre, je n'en ai pas encore rencontré. Tu en connais ? Ca m'intéresserait de bencher.

J'ai juste entendu une fois Luc Hermitte en parler, mais j'en connais pas.

J'ai justement testé avec le compilateur de VC2005 avec pas mal d'optimisations et g++ (que je connais pas très bien) avec -O3, et le foncteur était toujours plus rapide .