C++ std :: vecteur std :: sort boucle infinie

Question

J'ai rencontré un problème chaque fois que j'essayais de trier un vecteur d'objets qui résultait en une boucle infinie. J'utilise une fonction de comparaison personnalisée que j'ai transmise à la fonction de tri.

J'ai été en mesure de résoudre le problème en retournant false lorsque deux objets étaient égaux au lieu de vrai, mais je ne comprends pas complètement la solution. Je pense qu'il est parce que ma fonction de comparaison enfreignait cette règle comme indiqué sur cplusplus.com:

objet fonction de comparaison qui, prenant deux valeurs du même type que celles contenues dans la gamme, renvoie true si la premier argument va avant le deuxième argument dans le spécifique strict faible l'ordre définit, et faux sinon.

Quelqu'un peut-il fournir une explication plus détaillée?

Answer 1

La bonne réponse, comme d'autres l'ont souligné, est d'apprendre ce qu'est un «ordre strict strict». En particulier, si comp(x,y) est vrai, alors comp(y,x) doit être faux. (Notez que cela implique que comp(x,x) est faux.)

C'est tout ce que vous devez savoir pour corriger votre problème. L'algorithme sort ne fait aucune promesse si votre fonction de comparaison enfreint les règles.

Si vous êtes curieux de savoir ce qui s'est réellement passé, la routine sort de votre bibliothèque utilise probablement le port de synchronisation en interne. Quicksort fonctionne en recherchant à plusieurs reprises une paire d'éléments «hors service» dans la séquence et en les échangeant.Si votre comparaison indique à l'algorithme que a, b est "hors service", et qu'elle indique également à l'algorithme que b, a est "hors service", alors l'algorithme peut finir par les échanger indéfiniment.

Answer 2

Si vous cherchez une explication détaillée de ce qui commande faible stricte »est, voici quelques bonnes lectures: Order I Say!

Si vous cherchez de l'aide de fixer votre foncteur de comparaison, vous devez effectivement le poster.

Answer 3

Strict weak ordering signifie < b == vrai et lorsque vous retournez vrai pour l'égalité, c'est un < = b == vrai. Cette exigence est nécessaire pour l'optimalité pour différents algorithmes de tri.

Answer 4

Si les éléments sont les mêmes, l'un ne va pas avant l'autre. La documentation était assez claire en indiquant que vous devriez retourner false dans ce cas.

Answer 5

Un algorithme de tri pourrait facilement faire une boucle parce que vous dites que A < B et B < A quand ils sont égaux. Ainsi, l'algorithme pourrait infiniment essayer d'échanger les éléments A et B, en essayant de les placer dans le bon ordre.

Answer 6

La règle actuelle est spécifiée dans la norme C++, dans 25.3[lib.alg.sorting]/2

Comparer est utilisé comme un objet de fonction qui renvoie true si le premier argument est inférieur au second, et false autrement.

Le cas où les arguments sont égaux relève de "sinon".