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

La solution la plus simple pour trier en sens inverse est d'utiliser les reverse iterator :

Code:

---

std::sort(v.rbegin(), v.rend(), Pred());

---

Citation:

---

Envoyé par Sylvain Togni

La solution la plus simple pour trier en sens inverse est d'utiliser les reverse iterator :

Code:

---

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.

Ben oui mais il faut du code supplémentaire, ou utiliser unary_negate qui fait parti de tr1

Code:

---

std::sort(v.begin(), v.end(), std::unary_negate(Pred()));

---

Pardon, c'est binary_negate

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:

---

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é :question:) qui ne l'est pas (du fait de la non unicité du cas du résultat obtenu) :P

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.

(a<b) == false pour a==b. Ca reste vrai si tu inverses a et b. C'est bêtement mathématique :mrgreen:
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