Tri générique C++

Version imprimable

12/12/2013, 12h04
CliffeCSTL

Tri générique C++
Bonjour,

Je souhaite coder un une fonction de tri qui prend en entrée un pointeur sur une liste d'objets et qui me tri cette liste en fonction d'un attribut de l'objet.
Code:

1 2 3 4 class A { private: int a, b, c; }
Code:

1 2 3 4 class B { private: double d, e; }
Ma fonction doit pouvoir triée des listes d'objets de type A et B suivant l'attribut que je veux.

Merci.
12/12/2013, 13h27
Neckara

Bonjour,

On ne codera pas la fonction à ta place.
Dis-nous ce qui te bloque/ce qui te gêne/ce que tu as déjà fait/tenté et on pourra t'aider.
12/12/2013, 13h35
CliffeCSTL

Je vois pas comment faire c'est tout :p. C'est faisable au moins ?
12/12/2013, 13h37
_zzyx_

Une bonne pratique c'est de ne pas ré-inventer la roue,
Regarde plutôt de ce coté là
http://www.cplusplus.com/reference/list/list/sort/
http://www.cplusplus.com/reference/algorithm/sort/
Surtout que pour un tri générique, il sera dur de faire mieux que la STL (où alors tu n'aurais pas besoin de poser la question sur ce forum)

Dans certains cas il se peut que tu veuilles implémenté un algo précis, mais il faudra nous en dire plus

Je pense pas que se que je demande existe déjà.

Si je reprend mon exemple de la classe A :

Code:

1
2
3
4
5
6
7
8
class A {
    private:
        int a, b, c;
    public:
        A(int inA, int inB, int inC) { 
            a = inA; b = inB; c = inC;
        }
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main() {
    A a1(1, 2, 3), a2(3, 1, 2), a3(2, 3, 1);
    QList<A> listeATrier;
 
    listeATrier.push_back(a1);
    listeATrier.push_back(a2);
    listeATrier.push_back(a3);
 
    cout << listeATrier << "\n";
 
    // Tri décroissant
    Sort(listeATrier, A::a); cout << listeATrier;
    Sort(listeATrier, A::b); cout << listeATrier;
    Sort(listeATrier, A::c); cout << listeATrier;
}

Code:

1
2
3
4
5
6
console :
a1, a2, a3
 
a2, a3, a1
a3, a1, a2
a1, a2, a3

J'écris n'importe quoi mais c'est pour comprendre :)

12/12/2013, 14h29
white_tentacle
En fait ce que tu veux faire nécessite un mécanisme d’introspection, pas présent en standard en c++.

Donc en C++, tu ne peux pas trier selon un « attribut », tu peux trier en revanche selon un « comparateur ».

Donc ce que tu veux faire serait plus proche de :
Code:

1 2 3 4 Sort(listeATrier, compareAOnA); cout << listeATrier; Sort(listeATrier, compareAOnB); cout << listeATrier; Sort(listeATrier, compareAOnC); cout << listeATrier;

Code:

1
2
std::vector<A> liste { {1, 2, 3}, {3, 1, 2}, {2, 3, 1} };
std::sort(liste.begin(), liste.end(), [](A const& lhs, A const& rhs) {return lhs.b < rhs.c; });

Tu peux aussi t'amuser à définir des foncteurs qui vont simplifier l'écriture.

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
 
struct A {
    int a;
    float b;
    std::string c;
    friend std::ostream & operator<<(std::ostream & os, const A & v)
    {
        return os << "{" << v.a << ", " << v.b << ", " << v.c << "}";
    }
};
 
template <class T, class V> struct sort_by_impl {
    sort_by_impl(V T::*p) : m_p(p) {}
    bool operator()(T const& lhs, T const& rhs) const
    { return lhs.*m_p < rhs.*m_p; }
private:
    V T::*m_p;
};
 
template <class T, class V> sort_by_impl<T,V> sort_by(V T::*p) { return sort_by_impl<T,V>(p); }
 
int main ()
{
    std::vector<A> a{
        {1, 12.5, "z"},
        {2, 2.5, "b"},
        {3, 42.5, "a"}
    };
    std::copy(a.begin(),a.end(), std::ostream_iterator<A>(std::cout, "\n"));
 
    std::cout << "a\n";
    std::sort(a.begin(),a.end(), sort_by(&A::a));
    std::copy(a.begin(),a.end(), std::ostream_iterator<A>(std::cout, "\n"));
    std::cout << "b\n";
    std::sort(a.begin(),a.end(), sort_by(&A::b));
    std::copy(a.begin(),a.end(), std::ostream_iterator<A>(std::cout, "\n"));
    std::cout << "c\n";
    std::sort(a.begin(),a.end(), sort_by(&A::c));
    std::copy(a.begin(),a.end(), std::ostream_iterator<A>(std::cout, "\n"));
}
// Vim: let $CXXFLAGS='-std=c++0x'

12/12/2013, 14h49
CliffeCSTL

Moi je veux triée par rapport aux attributs.

Citation:

Envoyé par white_tentacle

En fait ce que tu veux faire nécessite un mécanisme d’introspection, pas présent en standard en c++.

Donc en C++, tu ne peux pas trier selon un « attribut », tu peux trier en revanche selon un « comparateur ».

Je ne vois pas en quoi tu ne pourrais pas, avec le code qu'il faut:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 template<class obj, class attr> struct comparateur_attribut { attr obj::* pAttribut; bool operator() (obj const &left, obj const &right) { return left.*pAttribut < right.*pAttribut; } }; template<class obj, class attr> sort(QList<obj> &objetsATrier, attr obj::* pAttribut) { //obtenir itérateurs //... comparateur_attribut cmp; cmp.pAttribut = pAttribut; std::sort(itDebut, itFin, cmp); } Sort(listeATrier, &A::a); cout << listeATrier; Sort(listeATrier, &A::b); cout << listeATrier; Sort(listeATrier, &A::c); cout << listeATrier;

13/12/2013, 10h14
oodini

Tu pourrais m'éclairer sur cette syntaxe ?

Code:

attr obj::* pAttribut;
13/12/2013, 10h21
_zzyx_

Citation:

Envoyé par CliffeCSTL

Moi je veux triée par rapport aux attributs.

Pense en C++,

* Tu as une fonction de tri, qui te permet de trier n'importe quel types d'objets soit par rapport à l'opérateur < soit par une fonction de tri
* Tu peux définir un opérateur < qui fait ce que tu veux (Par exemple considérer que bleu < rouge)
* Tu peux définir une fonction de tri qui fait ce que tu veux et qui peut etre différente de l'opérateur <

Dans les deux cas la fonction et l'opérateur se contentent de définir ce qui est plus petit, par exemple est-ce que tu veux classer tes élèves par leurs ages, leurs tailles, leurs poids, leurs notes ?

à partir de là on a répondu à ta question...
Il te suffit d'écrire la fonction de tri ou l'opérateur qui va bien, éventuellement un méchanisme pour changer le critère de tri on-the-fly
On pourrait meme imaginer que tu trie la moitié de ta collection par l'attribut A et l'autre moitiée par l'attribut B.
13/12/2013, 10h44
Médinoc

Citation:

Envoyé par oodini

Tu pourrais m'éclairer sur cette syntaxe ?

Code:

attr obj::* pAttribut;

C'est la syntaxe "pointeur de variable membre", dont je ne me souviens jamais précisément (j'ai du chercher sur le net pour écrire mon échantillon de code).
Elle est similaire à la syntaxe "pointeur de fonction membre", mais cette dernière est encore plus compliquée.

L'exemple ici signifie "pointeurs vers attr membre de la classe obj".
Avec Sort(listeATrier, &A::a);, ça correspond à int A::* pAttribut;, donc "pointeur vers int membre de la classe A".
Pour le déréférencer, il faut un objet de type A en plus du pointeur de membre.

Sous le capot, c'est encore plus marrant. Tant qu'on n'a pas d'héritage multiple c'est assez simple (en fait de pointeur, c'est juste un offset), mais dès que l'héritage multiple s'en mêle, on a des "pointeurs" pouvant faire la taille de plusieurs, à cause d'offsets ajustables qui sont modifiés lors des casts (avec un pointeur de fonction membre, j'ai réussi à avoir un sizeof(ptr)==16... en 32 bits).
13/12/2013, 10h51
oodini

Merci pour l'info !

Je crois que j'avais lu ça 2 ou 3 fois auparavant, mais si espacées dans le temps, que ça n'a pas pu imprimer. Surtout que j'ai peu l'occasion de l'utiliser, puis qu'apparemment, cela implique des membres publics.

C'est moins vrai pour les fonctions membres, mais on a des wrappers pour ça, maintenant, non ?

PS1 : attr est terme particulièrement mal choisi si ça désigne un type

Note aux admins : si ça dévie trop, merci de créer un nouveau fil
13/12/2013, 11h01
Médinoc

Je les ai nommés obj et attr pour "type de l'objet" et "type de l'attribut". J'aurais pu leur donner un nom plus explicite, mais je suis un gros fainéant.

Citation:

Envoyé par oodini

Surtout que j'ai peu l'occasion de l'utiliser, puis qu'apparemment, cela implique des membres publics.

Ça implique des membres auxquels tu à accès lorsque tu affectes le pointeur, donc une fonction membre pourrait créer un tel pointeur sur un membre privé. Et même retourner un tel pointeur à l'utilisateur, mais ce serait une horrible violation de l'encapsulation.
13/12/2013, 11h35
Bousk

Citation:

Envoyé par oodini

puis qu'apparemment, cela implique des membres publics.

J'ai jamais utilisé pour des variables, mais pour les méthodes tu peux passer une méthode non public. (au moins sous Visual Studio 2005 et 2008)
Ce qui importe c'est qui donne le pointeur vers la méthode en question.
13/12/2013, 14h52
jouana

Penche toit sur les templates (voir variadique) et pointeur sur méthode mais c'est pas beau
15/12/2013, 13h19
CliffeCSTL
Merci sa fonctionne avec ça :

Code:

std::sort(liste.begin(), liste.end(), [](A const& lhs, A const& rhs) {return lhs.b < rhs.c; });

J'ai une autre question sur ce code :
Code:

1 2 3 unsigned int fonction() { return -5; }
Pourquoi le compilateur ne dit rien ?
16/12/2013, 10h38
koala01

Salut,

Simplement parce que les mots clés (un)signed ne sont que l'indication de la convention qui sera applicable au moment où il faudra convertir une valeur en une chaîne de caractères affichable.

Au niveau du processeur, int et unsigned int sont, fondamentalement, identiques : ce sont des ensembles de (généralement) 32bits qui se suivent.

La seule différence, c'est que le bit de poids fort servira à permettre la représentation des valeurs comprises entre 2^31 et 2^32 -1 quand la convention unsigned est utilisée et à représenter la présence (s'il vaut 1) ou l'absence (s'il vaut 0) du signe moins dans le cas de signed.

Mais, fondamentalement parlant, -1 et 255 (parce que le principe est le même pour tous les types primitifs représentant des entiers et que je n'ai pas envie de me casser la tête à compter 32 "1" d'affilée :D) sont représenté par les mêmes valeurs en binaire : 11111111 (ou, en hexadécimal, c'est plus lisible : 0xFF ).

Il ne s'inquiétera de la signification à donner au bit de poids fort que lorsqu'il devra afficher le résultat : pour une valeur signée, ce sera une valeur négative, pour une valeur non signée, cela correspondra à 2^<le rang du bit observé> ;)
16/12/2013, 11h42
white_tentacle

Citation:

Envoyé par koala01

Salut,
Simplement parce que les mots clés (un)signed ne sont que l'indication de la convention qui sera applicable au moment où il faudra convertir une valeur en une chaîne de caractères affichable.

Et aussi lors des comparaisons.

Code:

(unsigned int) -5 < 3

est faux.

Honnêtement, je trouve que le compilateur pourrait donner un warning pour ce code (au moins en Wall). Gcc en donne d’ailleurs un lors des comparaisons signed/unsigned, je pense qu’il pourrait en donner lors de l’affectation.