Fonction paramétrée par un type :

Procédons de la même façon avec le deuxième exemple, et donc essayons de voir comment écrire un code ``générique'' pour le quicksort. Les mêmes solutions sont possibles :

• héritage

  On pourrait, par exemple, définir un classe (abstraite) correspondant aux ensembles ordonnés :

  class Ens_Ord{
    public:
      //...
      virtual int operator<(Ens_Ord &)=0; // relation d'ordre
      //...
  };
  class Ens_Ord_Int : public Ens_Ord{
       int data;
    public:
       int operator<(Ens_Ord & s){       // pour la laision dynamique
                                         // il doit avoir la meme signature !
           return data<(Ens_Ord_Int)s.data;
       }
       // ...
  };

  et une fonction quicksort :

  void quicksort( Ens_Ord *tab, size_t nelem){
       //...
       if(tab[i]<tab[j]) // liaison dynamique
  }

  L'inconvénient majeur de cette façon de faire est qu'elle oblige tous les types pour lesquels on pourra utiliser quicksort à être des descendants de cette classe des ensembles ordonnés Ens_Ord.
• généricité de bas niveau

  Une autre solution consiste à utiliser la généricité existant dans les constructions de bas niveau: compatibilité entre les types pointeurs et pointeurs de fonctions essentiellement. C'est ce que fait la fonction qsort de la bibliothèque standard du C.

  La fonction quicksort aura comme arguments :

  • le tableau des objets à trier est un void *
  • la taille du tableau
  • la taille des objets contenus dans le tableau
  • la fonction de comparaison entre les éléments: int (*)(const void *,const void *)
• préprocesseur

  On pourrait aussi utiliser le préprocesseur :

  void quicksort(TYPE *tab, size_t taille){     //...
       if(tab[i]<tab[j]) // operateur < défini sur TYPE
       //...
  }

  On peut alors créer un quicksort() pour le type T en compilant avec un #define TYPE T. Notons que dans ce cas, la compilation et la vérification de la syntaxe et du typage ne pourra avoir lieu qu'avec une définition #define TYPE. Comme pour les listes, il faudra aussi un nouveau nom pour le quicksort à chaque nouvelle définition deTYPE.
• template

  On peut enfin utiliser un patron de fonction.

  template <class T>
  void quicksort(T* tab, size_t n){
       if(tab[i]<tab[j]) // operateur < défini sur T
       //...
  };
  class Ord{
     //...
    public:
       int operator<(O&);
       //...
  };
  void essai(){
    int tab[100];
    Ord t[100];
    quicksort(tab,100);
    quicksort(t,100);
    //...
  }

  Dans ce cas, pour chacun des appels de quicksort, le type des paramètres permettra d'instancier la bonne version de la fonction. La situation est assez similaire à celle de la solution précédente utilisant le préprocesseur : nous aurons deux fonctions différentes générées pour le quicksort.