Tri d'une liste avec template

Invité · 23/12/2007, 15h17

Bonjour,

Je voudrais créer une fonction "trierListe" qui fonctionne avec des std::list et std::vector (voir code ci-dessous)

Est-ce possible ? (si oui, comment compléter la fonction "trierListe" ci-dessous ?)

NB : je rappelle que les std::vector et std:list se trient avec des méthodes un peu différentes ( voir fonction "trierListe" )

En fait le tri est un prétexte, je voudrais juste savoir quel est le type de liste reçu dans ma fonction trierListe avec template.

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
#include <stdlib.h>
#include <iostream>
 
#include <string>
#include <vector>
#include <list>
 
using namespace std;
 
class A {
   string strNom_;
 
public:
 
   A( const char * szNom) : strNom_( szNom ) {};
 
   // Opérateur de comparaison par défaut pour std::sort
   friend bool operator < (const A & a1, const A & a2) {
      return (a1.strNom_ < a2.strNom_ );
   }// operator <
 
   // Opérateur de sortie des flots
   friend std::ostream& operator<<( std::ostream& oss ,
                                    const Animal& a ) {
      oss << a.strNom_;
      return oss;
   }// operator<<
 
};// A
 
 
template<class L>
void afficherListe( L liste ) {
   typename L::iterator it;
   for ( it = liste.begin() ; it != liste.end(); ++it )
      cout << *it << endl;
}// afficherListe
 
 
template<class L>
void trierListe ( L & liste ) {
  //if ( liste est de type vector ) {
    sort( liste.begin(), liste.end() );
  //}
  //else if ( liste est de type std::list ) {
    liste.sort();
  //}
}// trierListe
 
 
int main(int argc, char *argv[]) {
   vector<A> lstV;
   //remplirListe( lstV );
 
   list<A> lstL;
   //remplirListe( lstL );
 
   // Tris 
   trierListe( lstV );
   trierListe( lstL );
 
   cout << "Liste \"vector\" apres tri ascendant" << endl;
   afficherListe( lstV );
   cout << endl;
   cout << "Liste \"list\" apres tri ascendant" << endl;
   afficherListe( lstL );
 
   system( "pause" );
   return EXIT_SUCCESS;
}// main

**yan** · 23/12/2007, 15h24

bonjour,
en faisant des spécialisation. Il me semble que comme ca ca marche :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
template<class L>
void trierListe ( std::list<L> & liste ) {
 
    liste.sort();
}
 
template<class L>
void trierListe ( std::vector<L> & liste )
{
     sort( liste.begin(), liste.end() );
 }

**Albenejean** · 23/12/2007, 15h31

Uhmmm...
Je n'ai jamais testé, et je ne veux pas dire de bétise, mais il me semble que les méthodes make_heap() et sort_heap() pouraient t'aider.
La première crée un tas à partir de deux itérateurs et la deuxième permet de trier ce tas.

**yan** · 23/12/2007, 15h33

Envoyé par Albenejean

Uhmmm...
Je n'ai jamais testé, et je ne veux pas dire de bétise, mais il me semble que les méthodes make_heap() et sort_heap() pouraient t'aider.
La première crée un tas à partir de deux itérateurs et la deuxième permet de trier ce tas.

Le heap est une autre structure. Elle fonctionne qu'avec des random iterator. comme sort. Donc cela ne marchera pas avec les liste...

**yan** · 23/12/2007, 15h46

avec la spécialisation ça marche au poile

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
22
23
24
25
26
27
28
29
30
31
32
33
 
#include <iostream>
#include <list>
#include <vector>
using namespace std;
 
template<class L>
void trierListe ( L & liste ) {
cout<<"trierListe de base"<<endl;
}
 
template<class L>
void trierListe ( list<L> & liste ) {
cout<<"trierListe de list"<<endl;
}
 
template<class L>
void trierListe ( vector<L> & liste )
{
  cout<<"trierListe de vector"<<endl;
 }
 
int main()
{
    int * myTabC = new int[10];
    list<int> myList;
    vector<int> myVect;
 
    trierListe(myTabC);
   trierListe(myList);
   trierListe(myVect);
    return 0;
}

**Laurent Gomila** · 23/12/2007, 16h23

A noter que là ce ne sont pas des spécialisations, mais plutôt des surcharges.

Invité · 23/12/2007, 17h56

Envoyé par Mongaulois

avec la spécialisation ça marche au poile

Effectivement, ça fonctionne bien, merci.

Mais mon objectif était de n'avoir qu'une seule fonction.

Il n'y a donc par moyen de savoir, dans "trierListe", quel est le type de liste que l'on reçoit ?

**yan** · 23/12/2007, 18h41

IL y as aussi
typeid
http://www.cplusplus.com/doc/tutorial/typecasting.html
mais je ne connait pas trop

Invité · 24/12/2007, 01h09

Envoyé par Mongaulois

IL y as aussi
typeid
http://www.cplusplus.com/doc/tutorial/typecasting.html
mais je ne connait pas trop

Oui, bonne idée, c'est ce que je voulais.
Le code suivant compile, s'exécute ...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
template < class L >
void trierListe ( L & liste ) {
   // Tris ascendants (appellent "operator <" de A
   if ( typeid( L ) == typeid( vector<A> ) ) {
      cout << "tri vector" << endl;
      //sort( liste.begin(), liste.end() );
   }
   if ( typeid( L ) == typeid( list<A> ) ) {
      cout << "tri list" << endl;
      //liste.sort();
   }
}// trierListe

... mais je ne peux pas enlever les "//" de commentaire devant "sort( liste.begin(), liste.end() );" et "liste.sort();", sinon, ça produit une erreur, c'est normal...

**Laurent Gomila** · 24/12/2007, 04h20

Mauvaise solution, il faut que tu effectues ce branchement à la compilation et non à l'exécution. Donc la surcharge (ou la spécialisation) est la bonne solution.

Invité · 24/12/2007, 10h56

Envoyé par Laurent Gomila

Donc la surcharge (ou la spécialisation) est la bonne solution.

Négatif. Je rappelle que le problème est d'arriver à trier des listes std::vector et std::list avec UNE SEULE fonction (sans surcharge, donc).

Envoyé par Laurent Gomila

Mauvaise solution, il faut que tu effectues ce branchement à la compilation

Bien volontiers, que proposes-tu ?

Je voudrais bien pouvoir écrire ...

Code :

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

1
2
3
4
5
6
7
 
#if ( typeid( L ) == typeid( vector<A> ) ) 
  // tri vector
#endif
#if ( typeid( L ) == typeid( list<A> ) ) 
  // tri list
#endif

... mais ça ne fonctionne pas...

**Laurent Gomila** · 24/12/2007, 11h08

Négatif. Je rappelle que le problème est d'arriver à trier des listes std::vector et std::list avec UNE SEULE fonction (sans surcharge, donc).

Le fait est que tu ne pourras pas. std::sort ne compilera pas pour std::list, et std::list::sort ne compilera pas pour std::vector ; il faudra donc à un moment où un autre que la compilation soit branchée sur deux fonctions différentes selon le type du conteneur, à moins d'utiliser une méthode de tri complétement différente qui soit unique pour les deux types de conteneurs (les seules que je vois sont très bourrines).

Tu peux nous en dire plus sur cette contrainte de "une seule fonction" ?

**NiamorH** · 24/12/2007, 12h26

Je viens enfoncer le clou concernant surcharges et spécialisations, étant donné que ces notions sont assez floues à moins de s'y plonger.

Lorsqu'on définit un template (fonction ou classe), c'est le "primary template" qu'on définit.

A partir de ce primary template on peut :

- toujours spécialiser totalement grace à template <> placé devant.
- spécialiser partiellement pour les classes templates seulement.
- surcharger pour les fonctions templates seulement. (revient à créer d'autres primary template.)

Ex :

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// Primary Template
template <class T>
void func( T )
{
}
 
// Complete Specialisation
template <>
void func<int>( int )
{
}
 
// Overload 1
template <class T>
void func( T* )
{
}
 
// Overload 2
void func( long )
{
}
 
// Overload 3
template <class T1, class T2>
void func( T1, T2 )
{
}
 
// Primary Template
template <class T>
class C
{
};
 
// Complete Specialisation
template <>
class C<int>
{
};
 
// Partial Specialisation 1
template <class T>
class C<T*>
{
};
 
// Partial Specialisation 2
template < template <class> class T1, class T2>
class C<T1<T2> >
{
};
 
// Partial Specialisation 3
template <template <class> class T>
class C<T<int> >
{
};

**Alp** · 24/12/2007, 12h30

Envoyé par Laurent Gomila

Mauvaise solution, il faut que tu effectues ce branchement à la compilation et non à l'exécution. Donc la surcharge (ou la spécialisation) est la bonne solution.

En effet, Laurent a raison. L'utilisation de typeid ne doit se faire que dans de rares cas (et encore

) car c'est comme sortir un tank pour tuer un mouche.

Niveau performances ça n'a rien à voir, et puis c'est vraiment choisir la solution de facilité. Donc à moins que ta contrainte fasse que tu ne peux pas faire autrement, utilises deux fonctions (surcharge, donc).

Invité · 24/12/2007, 13h28

L'exemple que je proposais dans ce sujet est complètement fictif. Mon but était de progresser avec les template et les tris.

Merci NiamorH pour toutes ces informations sur les template.

Effectivement, dans un programme réel je choisirais l'exemple de code de Mongaulois avec les surchages...

Merci aussi pour les typeid, je n'avais jamais essayé, ça peut servir...

Tri d'une liste avec template

Langage C++

Discussions similaires

Partager

Partager