IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

SL & STL C++ Discussion :

Inverser un prédicat de tri


Sujet :

SL & STL C++

  1. #1
    Membre éclairé
    Inscrit en
    Mai 2006
    Messages
    330
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 330
    Par défaut Inverser un prédicat de tri
    Salut,

    J'ai défini un foncteur qui me permet de faire un tri personnalisé en le donnant comme prédicat à "sort". J'aimerais savoir s'il y a moyen de faire le tri en sens inverse en utilisant le même prédicat, mais sûrement avec autre chose qui permet d'inverser son résultat booléen. J'ai essayé sans succès d'utiliser "logical_not", je m'embrouille un peu dans l'abstraction à ce niveau...

    Merci

  2. #2
    Membre émérite

    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 717
    Par défaut
    La solution la plus simple pour trier en sens inverse est d'utiliser les reverse iterator :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    std::sort(v.rbegin(), v.rend(), Pred());

  3. #3
    Membre éclairé
    Inscrit en
    Mai 2006
    Messages
    330
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 330
    Par défaut
    Citation Envoyé par Sylvain Togni Voir le message
    La solution la plus simple pour trier en sens inverse est d'utiliser les reverse iterator :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    std::sort(v.rbegin(), v.rend(), Pred());
    OK, super merci, c'est probablement le plus efficace.

    Sinon par curiosité je serais intéressé de savoir s'il y a moyen de le faire en créant un nouveau foncteur dérivé du premier.

  4. #4
    Membre émérite

    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 717
    Par défaut
    Ben oui mais il faut du code supplémentaire, ou utiliser unary_negate qui fait parti de tr1
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    std::sort(v.begin(), v.end(), std::unary_negate(Pred()));

  5. #5
    Membre émérite

    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 717
    Par défaut
    Pardon, c'est binary_negate

  6. #6
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 644
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 644
    Par défaut
    Salut,

    Il faut cependant veiller à garder la même sémantique à ton prédicat...

    En effet, un prédicat "PlusPetitQue" donne vrai si le premier opérande est effectivement plus petit que le second et faux si le premier opérande est égal ou plus grand que le second...

    Si tu inverse simplement le résultat de ton prédicat, tu risque d'avoir des problèmes avec ton tri car il s'effectue en vérifiant une équivalence:
    Soit deux valeur a et b
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    si ( a PluPetitQue b)
       a < b
    sinon si (b PlusPetitQue a)
       b < a
    sinon
        a est équivalent (égal ?? ) à b
    fin si
    Tu risque donc d'avoir une équivalence (égalité ) qui ne l'est pas (du fait de la non unicité du cas du résultat obtenu)
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  7. #7
    Membre éclairé
    Inscrit en
    Mai 2006
    Messages
    330
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 330
    Par défaut
    A propos du problème d'équivalence, je pense l'avoir assez bien compris, mais il me pose toujours problème à chaque fois que je fais des tris personnalisés. Je le traite d'une certaine manière mais je ne suis pas sûr que c'est la bonne façon.

    Au départ j'ai découvert ce problème car j'avais fait un foncteur qui ne traitait pas les cas d'égalité, de ce fait il pouvait répondre true ou false au même test "a >= b" selon l'ordre dans lequel sont présentés les arguments. Ca faisait complètement déconner l'algorithme de tri.

    Pour éviter cela j'ai pris le parti en cas d'égalité de départager les opérandes en comparant leurs adresses, ça a l'air de marcher mais quelque chose me dit que ce n'est pas bien.

  8. #8
    Rédacteur
    Avatar de 3DArchi
    Profil pro
    Inscrit en
    Juin 2008
    Messages
    7 634
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2008
    Messages : 7 634
    Par défaut
    (a<b) == false pour a==b. Ca reste vrai si tu inverses a et b. C'est bêtement mathématique
    En d'autres termes, si a==b, alors a<b doit retourner false. [EDIT] == se comprend ici au sens mathématique comme relation d'équivalence et non comme comportement de l'opérateur== applicable à a et b[/EDIT]
    F.A.Q. : Comment surcharger correctement l'opérateur < ?
    Si tu veux préserver l'ordre en cas d'équivalence, alors il y a stable_sort.
    Sur les algos de la STL : Les algorithmes de la STL, par R0d

Discussions similaires

  1. inverser l'ordre de tri
    Par Yepazix dans le forum Langage
    Réponses: 3
    Dernier message: 05/01/2013, 15h36
  2. [XL-2007] Tri inverse d'une ListBox
    Par blackstrange dans le forum Macros et VBA Excel
    Réponses: 6
    Dernier message: 02/07/2012, 10h10
  3. Tri de liste de prédicats
    Par Kerod dans le forum Prolog
    Réponses: 9
    Dernier message: 27/11/2008, 15h51
  4. [Débutante] Inverser un prédicat
    Par mun_a dans le forum Prolog
    Réponses: 5
    Dernier message: 14/12/2007, 09h54
  5. Tri d'un tableau en alphanumérique et non l'inverse
    Par Hecco dans le forum Collection et Stream
    Réponses: 3
    Dernier message: 15/01/2007, 13h52

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo