Personnaliser le tri.

Personnaliser le tri

functors

Voir version :

Pas de dépendances

Télécharger :

#include <queue>
#include <iostream>

using namespace std;

class test
{
private:
    int a;
    int b;
public:
    test(int i,int j) {a=i;b=j;}
    int operator<(const test& t2) const {return a < t2.a;}
    int geta() const;
    int getb() const;
};

int test::geta() const
{
    return a;
}

int test::getb() const
{
    return b;
}

class monfoncteur:public binary_function<test,test,int>
{
public:
  int operator()(const test& t1,const test& t2) const
  {
    return t1.getb()<t2.getb();
  }
};

void test1()
{
    priority_queue<int,vector<int>,less<int> > q;
    q.push(5);
    q.push(13);
    q.push(8);
    q.push(6);
    cout << "lecture de la file de priotite" << endl;
    while(!q.empty())
    {
        cout << q.top() << endl;
        q.pop();
    }
}

void test2()
{
    priority_queue<test> q;
    q.push(test(15,3));
    q.push(test(8,6));
    q.push(test(9,1));
    q.push(test(12,7));
    cout << "lecture de la file de priotite" << endl;
    while(!q.empty())
    {
        cout << "a=" << q.top().geta() << " b=" << q.top().getb() << endl;
        q.pop();
    }
}

void test3()
{
    priority_queue<test,vector<test>,monfoncteur > q;
    q.push(test(15,3));
    q.push(test(8,6));
    q.push(test(9,1));
    q.push(test(12,7));
    cout << "lecture de la file de priotite" << endl;
    while(!q.empty())
    {
        cout << "a=" << q.top().geta() << " b=" << q.top().getb() << endl;
        q.pop();
    }
}

int main()
{
    test1();
    test2();
    test3();
    return 0;
}



Commentaires


Parlons foncteurs.


TEST 1 :
********

  Pour le moment, ne regardez QUE le main, et la fonction test1()

  On l'a vu avant, priority_queue a besoin de savoir comment trier les éléments pour fonctionner.
  Par défaut, elle renvoie l'élément le plus grand de la file d'abord.

  C'est bien, mais peut etre qu'on veut changer cela.
  

  ici, nous allons voir comment personnaliser cela :

  Au lieu d'écrire 
	priority_queue<int> q;
  j'écris :
	priority_queue<int,vector<int>,less<int> > q;

PIEGE !!!!!!!!!!!!!!!!!!!!!
***************************

  Laissez un espace entre 2  >
  En effet, si vous écrivez :
	priority_queue<int,vector<int>,less<int>> q;

  Le compilateur le reconnait comme l'opérateur >>, qui est l'opérateur SHR, et également utilisé notemment par cin.
  Et pan, il vous met une erreur.
  Je me rappelle, la premiere fois que j'ai tapé une ligne pareille, j'ai mis 2 heures avant de trouver pourquoi ça ne voulait pas compiler !

FIN DE PIEGE
************

  Lancez le programme : ça fait pareil.
  Parce que par défaut, ces 2 écritures sont les memes : si vous ne mettez pas la fin, par défaut, la fin est vector<> et less<>

  On peut donc changer cela.

  Premiere chose : est ce qu'on change vector<int>
  --> On pourrait, mais c'est idiot, l'algorithme est optimisé pour les vector, donc on ne touchera pas a lui.

  Par contre, on touchera au dernier élément :

  Ce dernier élément est un FONCTEUR.

  Par défaut, c'est le foncteur less<T> qui est en place.
  T est votre type : ici, un int bien sur.
  less : ça veut dire que ce sera dans l'ordre décroissant : du plus grand au plus petit.
  En effet, quand vous lancez le programme, vous voyez que les nombres apparaissent du plus grand au plus petit.

CLASSER DU PLUS PETIT AU PLUS GRAND
***********************************

  Maintenant, imaginons que vous les voulez du plus petit au plus grand :
  --> Changez de foncteur !!

  Il existe, comme vous vous doutez bien, un foncteur qui permet d'aller du plus petit au plus grand :
  il s'agit de greater.

  Changez donc la ligne en :

	priority_queue<int,vector<int>,greater<int> > q;

  Et relancez le programme. Voila qui est fait pour cette partie


TEST 2
******

  Mettez test2() dans le main a la place de test1()

  Le test 2 montre comment classer autre chose que des int.
  Je définis ci dessus une classe "test" qui contient un couple a et b.

  Je définis uen file de priorité dans laquelle je stocke des couples (voir les q.push)
  si vous lancez le programme, vous constatez que les éléments sont triés selon la valeur a.

  Pourquoi ?
  Parce que la classe contient l'opérateur < qui dit comment comparer les classes test. Et on remarque que a l'intérieur de cet opérateur,
  le test compare les "a"

  Si vous enelevez la définition de l'opérateur : vous vous prenez un message d'erreur : en effet, il faut que < soit surchargé.

  Essayez maintenant, comme pour le test 1, de remplacer par "greater" --> ça ne marche pas, car > n'est pas surchargé.
  Pour que ça marche, vous devez définir un opérateur >.

  Voici donc comment faire une file de priorité sur des classes personnalisées : 1ere méthode : surcharger des opérateurs.

TEST 3
******

  Mettez test3() dans le main a la place de test1()

  Cette fois ci, j'ai envie que les éléments soient classés selon B.
  Si vous lancez le test, vous voyez que c'est le cas. pourquoi ?

  Ce qui est embetant, c'est qu'on ne peut plus se servir de l'opérateur < : car il trie déja les a.
  Donc on va faire appel a un opérateur externe, si j'ose dire, que l'on va appeler FONCTEUR.

  Je définis :

  priority_queue<test,vector<test>,monfoncteur > q;

  Cette fois ci, ce n'est pas less ou greater, c'est "monfoncteur" un truc personnalisé.
  Regardez comment se défini le foncteur :


class monfoncteur:public binary_function<test,test,int>
{
public:
  int operator()(const test& t1,const test& t2) const
  {
    return t1.getb()<t2.getb();
  }
};


  Le foncteur, c'est une classe que vous devez créer.
  Cette classe hérite de "binary_operator" qui est une classe STL interne connue.
  Cette classe mere prend 3 template : 2 fois votre élément, et un int
  (si vous ne comprenez pas tout, dites vous que c'est toujours pareil)

  A l'intérieur de cette classe, une seule méthode, et publique : la surcharge de ()

  et vous voyez qu'ici, on fait des tests sur b, ce qui explique le résultat.

  Un foncteur a donc été utilisé ici pour redéfinir le tri.

  C'était donc les 2 méthodes.


  Certains diront "oui, autant toujours utiliser les opérateurs <"
  --> ça a des inconvénients :

  si, d'une file a une autre, vous voulez comparer des "class test" de 2 manieres différentes, il faut des foncteurs.
  si vous passez des éléments dynamiques (des pointeurs), vous etes obligé d'utiliser des foncteurs :
  en effet, les < pour les pointeurs existe déja : il compare leurs adresses.
  donc si vous voulez comparer pointeur->truc, vous etes obligé d'utiliser des foncteurs.