Tri uniquement en utilisant l'opérateur moins que par rapport à une fonction de comparaison trivale

Question

En C ++ / STL, le tri est effectué en utilisant uniquement l'opérateur moins que. En plus je ne sais pas comment les algorithmes de tri sont réellement mis en œuvre, je suppose que les autres opérations sont créées implicites:

a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)

Comparé à l'utilisation d'une fonction TRIVALUe * Comparez, comme par exemple Java, est-ce bon pour les performances, ou pourquoi cette décision de conception a-t-elle été prise?

Mon hypothèse est que toute fonction TRIVALUe Compareto doit encore implémenter ces comparaisons en soi, ce qui entraîne les mêmes performances.

11

Mise à jour:Il semble un vaisseau spatial <=> L'opérateur arrive en C ++ 20, donc évidemment le comité a pensé qu'il y avait des inconvénients à utiliser uniquement operator<.

Answer 1

Dans un sens, les deux autres sont implicites, mais plus précis serait de dire qu'un type de comparaison ne fait pas réellement besoin Un comparateur tri-évalué et les types de C ++ sont implémentés d'une manière qui n'en utilise pas afin de minimiser le comportement requis du comparateur.

Il serait faux pour STD :: tri pour définir et utiliser exclusivement quelque chose comme ceci:

template <typename T, typename Cmp>
int get_tri_value(const T &a, const T &b, Cmp lessthan) {
    if (lessthan(a,b)) return -1;
    if (lessthan(b,a)) return 1;
    return 0;
}

... parce que vous vous retrouvez avec un algorithme inefficace en termes de nombre d'appels à lessthan. Si votre algorithme ne fait rien d'utile avec la différence entre un retour 1 et un retour 0, vous avez gaspillé une comparaison.

C ++ fait référence à des "ordonnances faibles strictes". Si < est un ordre faible strict, et !(a < b) && !(b < a), ce n'est pas nécessairement suivre ça a == b. Ils ne sont que "au même endroit" dans l'ordre, et !(a < b) && !(b < a) est une relation d'équivalence. Donc le comparateur requis par sort ordres Cours d'équivalence des objets, il ne fournit pas de commande totale.

La seule différence que cela fait est ce que vous dites quand !(a < b). Pour une commande totale stricte, vous déduire b <= a, lire "moins ou égal à". Pour un ordre faible strict, vous ne pouvez pas définir b <= a vouloir dire b < a || b == a et avoir cela est vrai. C ++ est pédante à ce sujet, et comme il permet à l'opérateur de la surcharger à peu près, car les gens surchargement des opérateurs ont besoin du jargon afin de dire aux utilisateurs de leur code à quoi ils peuvent s'attendre en termes de lien entre les opérateurs. Java parle du comparateur et du HashCode étant cohérent avec égaux, ce dont vous avez besoin. C ++ doit traiter avec <,>, ==, <=,> =, la condition post-condition de l'affectation, etc.

C ++ adopte une approche mathématique assez pure dans l'API, donc tout est défini en termes de relation binaire unique. Java est plus convivial à certains égards, et préfère les comparaisons à trois voies où la définition de l'unité fondamentale (la comparaison) est un peu plus complexe, mais la logique qui en découle est plus simple. Cela signifie également que l'algorithme de tri obtient plus d'informations par comparaison, ce qui est parfois utile. Pour un exemple, consultez l'optimisation rapide "drapeau néerlandais", qui est un avantage lorsqu'il y a beaucoup de doublons "au même endroit" dans les données.

Dans ce cas, un comparateur à trois valeurs est un gain de vitesse. Mais C ++ utilise une définition cohérente d'un comparateur pour le tri et aussi pour set et map, lower_bound Et ainsi de suite, qui bénéficient à peine d'un comparateur à trois valeurs (peut-être sauver une comparaison, peut-être pas). Je suppose qu'ils ont décidé de ne pas compliquer leur belle interface générale dans l'intérêt de gains d'efficacité potentiel spécifiques ou limités.

Answer 2

Je suppose que dans C ++, cela a été fait juste pour réduire la duplication du code: une fois que vous avez défini une comparement OP sur une classe / type, vous êtes non seulement en mesure de comparer ces objets en écrivant simplement un <B, mais aussi à vous faire trier des ensembles de de tels objets.

Quant au tri, nous n'avons besoin que d'un opérateur moins que, pourquoi introduire des choses supplémentaires? :)

Answer 3

Si vous faites référence à STD :: Sort (), son opérateur utilise uniquement () car il n'a pas besoin de préserver l'ordre relatif d'élément équivalent, il aura donc besoin d'un opérateur moins () et de l'opérateur implicitement plus grand ().

tandis que std :: stable_sort le préservera, mais il est plus lent. Il a besoin de l'opérateur moins () et de l'itérateur bidirectionnel en échange de l'opérateur égal () pour construire la fonction de comparer "trivalue"