Pourquoi utiliser «b <a? a: b »au lieu de« a <b? b: a ”pour implémenter le modèle max?

154

Modèles C ++ - Le guide complet, 2e édition présente le modèle max :

template<typename T>
T max (T a, T b)
{
  // if b < a then yield a else yield b
  return  b < a ? a : b;
}

Et cela explique l'utilisation “b < a ? a : b”au lieu de “a < b ? b : a”:

Notez que le modèle max () selon [StepanovNotes] renvoie intentionnellement «b <a? a: b »au lieu de« a <b? b: a ”pour s'assurer que la fonction se comporte correctement même si les deux valeurs sont équivalentes mais non égales.

Comment comprendre " even if the two values are equivalent but not equal."? “a < b ? b : a”semble avoir le même résultat pour moi.

Nan Xiao
la source
8
Cela me semble faux ... Les deux réponses sont "correctes", mais si aet bsont équivalentes , alors !(a < b) && !(b < a)est vrai, donc a < bet b < asont toutes les deux fausses, donc in b < a ? a : b, best renvoyée, ce qui n'est pas ce que vous voulez ... Vous voulez a < b ? b : a.
Holt
1
Vous pouvez souvent faire la distinction entre équivalent aet bavec std::addressofet. Al.
Caleth
14
Si vous le faites a = max(a, b);(à plusieurs reprises), vous ne voudrez peut-être pas remplacer ainutilement.
Bo Persson
2
BTW ce modèle devrait prendre des paramètres par const-references et les renvoyer par const-reference, sinon, vous faites un tas de copies inutiles (et vous allez remplacer aavec une copie de a).
Holt
3
@Caleth: Le type canonique qui a à la fois l'équivalence et l'égalité est CaseInsensitiveString. Pour ce type, ni a <A ni A <a. Mais ce std::addressofn'est pas pertinent. En fait, pour le donné, T max(T a, T b)nous savons déjà addressof(a) != addressof(b).
MSalters

Réponses:

150

std::max(a, b) est en effet spécifié pour retourner a lorsque les deux sont équivalents.

C'est considéré comme une erreur par Stepanov et d'autres parce que cela brise la propriété utile donnée aet b, vous pouvez toujours les trier {min(a, b), max(a, b)}; pour cela, vous voudrez max(a, b)revenir blorsque les arguments sont équivalents.

TC
la source
48
De ce lien "Il m'est difficile de blâmer les gens qui le font: après tout, ils suivent simplement la spécification standard C ++ de max écrite par moi. Il m'a fallu plusieurs années pour voir que je me trompais." - sensationnel!
Jack Aidley
23
tu ne peux pas juste faire {min(a, b), max(b, a)}?
Captain Man
12
@CaptainMan: Oui, mais c'est encore moins évident. Je dirais qu'il est logique de max(a,b)renvoyer un si-et-seulement-si min(a,b)renvoie b, et vice versa afin qu'ils soient inversés l'un par rapport à l'autre et que l'ensemble (non ordonné) {min(a,b), max(a,b)}soit toujours égal à {a,b}.
Jack Aidley
5
@ jpmc26: Si, par exemple, on trie une liste d'événements par heure, on n'a pas besoin de se soucier de savoir si l'opération de tri est stable pour se soucier d'avoir chaque événement qui apparaît exactement une fois dans l'entrée, de même apparaître exactement une fois dans la sortie. Certaines opérations (comme la recherche et l'élimination d'événements dupliqués) peuvent nécessiter l'utilisation d'un ordre complet, mais dans de nombreux autres cas, il peut être acceptable de répertorier les événements simultanés dans un ordre arbitraire, mais pas de les dupliquer ou de les omettre.
supercat
2
@supercat Appliquer minet maxà autre chose que l' horodatage (la clé de tri) dans ce scénario n'a aucun sens. Les événements (les objets) eux-mêmes ne devraient même pas être comparables si l'égalité n'implique pas l'interchangeabilité. La seule façon {min(a, b), max(a, b)}fait tout sens comme un mécanisme de tri est si les objets sont interchangeables.
jpmc26
62

Cette réponse explique pourquoi le code donné est erroné d'un point de vue standard C ++, mais il est hors contexte.

Voir la réponse de @ TC pour une explication contextuelle.


La norme définit std::max(a, b)comme suit [alg.min.max] ( je souligne):

template<class T> constexpr const T& max(const T& a, const T& b);

Nécessite : Le type T est LessThanComparable (Tableau 18).

Retour : la valeur la plus élevée.

Remarques : renvoie le premier argument lorsque les arguments sont équivalents.

Équivalent ici signifie que !(a < b) && !(b < a)c'esttrue [alg.sorting # 7] .

En particulier, si aet bsont équivalents, les deux a < bet b < asont false, donc la valeur à droite de :sera renvoyée dans l'opérateur conditionnel, elle adoit donc être à droite, donc:

a < b ? b : a

... semble être la bonne réponse. Il s'agit de la version utilisée par libstdc ++ et libc ++ .

Les informations contenues dans votre devis semblent donc erronées selon la norme actuelle, mais le contexte dans lequel elles sont définies peut être différent.

Holt
la source
4
Lien Godbolt qui explique le problème (merci @songyuanyao pour la définition de X).
Holt
1
@JackAidley J'ai édité la réponse pour spécifier que le raisonnement cible la norme actuelle.
Holt
@codekaizer Je faisais en fait référence à "Si nous définissons equiv (a, b) comme! comp (a, b) &&! comp (b, a)" . J'ai changé le lien pour un meilleur devis (3 lignes ci-dessous dans la norme ...).
Holt
1
Surpris, personne n'a mentionné la virgule flottante, où a<bet b<apeuvent tous les deux être faux parce qu'ils ne sont pas ordonnés (un ou les deux NaN, donc ==faux aussi). Cela pourrait être considéré comme une sorte d'équivalence. vaguement lié: les maxsd a, binstructions de x86 implémentent a = max(b,a) = b < a ? a : b. ( Quelle est l'instruction qui donne FP sans branche min et max sur x86? ). L'instruction garde l'opérande source (le deuxième) sur un ordre non ordonné, donc une boucle sur un tableau vous donnera NaN s'il y avait des NaN. Mais max_seen = max(max_seen, a[i])ignorera les NaN.
Peter Cordes
Voir aussi les notes de Stepanov sur la programmation
Shafik Yaghmour
21

Le point est celui qui doit être retourné quand ils sont équivalents; std::maxdoit retourner a(c'est-à-dire le premier argument) pour ce cas.

S'ils sont équivalents, renvoie a.

Donc a < b ? b : adevrait être utilisé; d'autre part, b < a ? a : b;retournera bincorrectement.

(Comme l'a dit @Holt, la citation semble opposée.)

«les deux valeurs sont équivalentes mais non égales» signifie qu'elles ont la même valeur lorsqu'elles sont comparées, mais qu'elles migth être des objets différents à certains autres aspects.

par exemple

struct X { int a; int b; };
bool operator< (X lhs, X rhs) { return lhs.a < rhs.a; }
X x1 {0, 1};
X x2 {0, 2};
auto x3 = std::max(x1, x2); // it's guaranteed that an X which cantains {0, 1} is returned
songyuanyao
la source
1
Pourriez-vous s'il vous plaît expliquer pourquoi std::max(a, b)doit revenir a, si aet bsont équivalents?
眠 り ネ ロ ク
4
@ ネ ロ ク - C'est juste un choix arbitraire de la part du standard . Bien que ce soit un peu discutable si c'est un bon.
StoryTeller - Unslander Monica
Est-ce juste moi ou est-ce en contradiction avec la question? Si aet bsont équivalents, alors !(a < b) && !(b < a)est vrai, donc a < bet b < asont faux, alors ...?
Holt
2
@ ネ ロ ク Je suppose que la norme veut juste la faire déterminer; quand ils sont équivalents, lequel doit être retourné.
songyuanyao
1
merci de me rafraîchir la mémoire sur la raison pour laquelle un objet serait "équivalent" mais pas "égal".
Jeff Walker