Po co używać „b <a? a: b ”zamiast„ a <b? b: a ”aby wdrożyć szablon max?


154

Szablony C ++ - kompletny przewodnik, wydanie 2, wprowadza szablon max :

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

I wyjaśnia użycie “b < a ? a : b”zamiast “a < b ? b : a”:

Zauważ, że szablon max () zgodny z [StepanovNotes] celowo zwraca „b <a? a: b ”zamiast„ a <b? b: a ”, aby upewnić się, że funkcja zachowuje się poprawnie, nawet jeśli dwie wartości są równoważne, ale nie równe.

Jak rozumieć „ even if the two values are equivalent but not equal.”? “a < b ? b : a”wydaje się mieć ten sam wynik dla mnie.


8
Wygląda niewłaściwy do mnie ... Obie odpowiedzi są „poprawne”, ale jeśli ai brównoważne , to !(a < b) && !(b < a)jest prawda, tak a < bi b < aoba fałszywe, więc w b < a ? a : b, bjest zwracana, co nie jest to, co chcesz ... Ty chcesz a < b ? b : a.
Holt

1
Często można rozróżnić między odpowiednikiem aa bz std::addressofet. glin.
Caleth

14
Jeśli to zrobisz a = max(a, b);(wielokrotnie), możesz nie chcieć aniepotrzebnie wymieniać .
Bo Persson

2
BTW, ten szablon powinien pobierać parametry z referencji do stałych i zwracać je przez referencje do stałych, w przeciwnym razie robisz kilka bezużytecznych kopii (i zamierzasz zastąpić akopią a).
Holt

3
@Caleth: Typ kanoniczny, który ma zarówno równoważność, jak i równość, to CaseInsensitiveString. W przypadku tego typu ani a <A ani A <a. Ale std::addressofto nie ma znaczenia. Właściwie T max(T a, T b)to już wiemy addressof(a) != addressof(b).
MSalters

Odpowiedzi:


150

std::max(a, b)jest rzeczywiście określona jako zwracana, agdy te dwa są równoważne.

Uważa to za błąd Stiepanowa i innych, ponieważ łamie podaną użyteczną właściwość ai bzawsze można je posortować {min(a, b), max(a, b)}; w tym celu chciałbyś max(a, b)zwrócić, bgdy argumenty są równoważne.


48
Z tego linku „Trudno mi winić ludzi, którzy to robią: w końcu po prostu postępują zgodnie ze standardową specyfikacją max napisaną przez C ++ . Zajęło mi kilka lat, zanim się pomyliłem”. - łał!
Jack Aidley

23
nie możesz po prostu zrobić {min(a, b), max(b, a)}?
Captain Man

12
@CaptainMan: Tak, ale nadal jest to mniej oczywiste. Twierdziłbym, że logiczne jest, że max(a,b)zwróci wartość „jeśli i tylko”, jeśli min(a,b)zwraca b i na odwrót, tak że są one wzajemnie odwrotne, a (nieuporządkowany) zbiór {min(a,b), max(a,b)}jest zawsze równy {a,b}.
Jack Aidley

5
@ jpmc26: Jeśli np. sortuje się listę zdarzeń według czasu, nie trzeba się przejmować tym, czy operacja sortowania jest stabilna, aby dbać o to, aby każde zdarzenie, które pojawia się dokładnie raz na wejściu, również pojawia się dokładnie raz na wyjściu. Niektóre operacje (takie jak znajdowanie i eliminowanie zduplikowanych zdarzeń) mogą wymagać użycia pełnej kolejności, ale w wielu innych przypadkach dopuszczalne może być wyszczególnienie jednoczesnych zdarzeń w dowolnej kolejności, ale ich nie powielać ani nie pomijać.
supercat

2
@supercat Stosowanie mini maxdo wszystkiego poza datownikiem (kluczem sortowania) w tym scenariuszu nie ma sensu. Same zdarzenia (obiekty) nie powinny być nawet porównywalne, jeśli równość nie oznacza zamienności. Jedynym sposobem {min(a, b), max(a, b)}sprawia żadnego sensu, ponieważ mechanizm sortowania jest jeśli obiekty są wymienne.
jpmc26

62

Ta odpowiedź wyjaśnia, dlaczego podany kod jest nieprawidłowy ze standardowego punktu widzenia C ++, ale jest poza kontekstem.

Zobacz odpowiedź @ TC, aby uzyskać kontekstowe wyjaśnienie.


Standard definiuje std::max(a, b)następująco [alg.min.max] ( wyróżnienie moje):

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

Wymaga : Typ T jest mniejszy niż porównywalny (Tabela 18).

Zwroty : większa wartość.

Uwagi : Zwraca pierwszy argument, gdy argumenty są równoważne.

Odpowiednik tutaj oznacza, że !(a < b) && !(b < a)jest to true [alg.sorting # 7] .

W szczególności, jeśli ai bsą równoważne, oba a < bi b < afalse, więc wartość po prawej :stronie zostanie zwrócona w operatorze warunkowym, więc amusi być po prawej stronie, więc:

a < b ? b : a

... wydaje się być poprawną odpowiedzią. To jest wersja używana przez libstdc ++ i libc ++ .

Tak więc informacje w Twojej wycenie wydają się błędne zgodnie z obecnym standardem, ale kontekst, w którym są zdefiniowane, może być inny.


4
Link Godbolt, który wyjaśnia problem (dzięki @songyuanyao za definicję X).
Holt

1
@JackAidley Zredagowałem odpowiedź, aby określić, że rozumowanie jest ukierunkowane na obecny standard.
Holt

@codekaizer Właściwie odnosiłem się do „Jeśli zdefiniujemy equiv (a, b) jako! comp (a, b) &&! comp (b, a)” . Zmieniłem link na lepszy cytat (3 linie poniżej w standardzie ...).
Holt

1
Zaskoczony, nikt nie wspomniał o zmiennoprzecinkowym, gdzie a<bi b<aoba mogą być fałszywe, ponieważ są nieuporządkowane (jeden lub oba NaN, więc też ==jest fałsz). Można to postrzegać jako rodzaj równoważności. luźno powiązane: maxsd a, bimplementacje instrukcji x86 a = max(b,a) = b < a ? a : b. ( Jaka jest instrukcja, która podaje wartości minimalne i maksymalne FP bez gałęzi na x86? ). Instrukcja utrzymuje operand źródłowy (drugi) w stanie nieuporządkowanym, więc pętla nad tablicą da ci NaN, jeśli były jakieś NaN. Ale max_seen = max(max_seen, a[i])zignoruje NaNs.
Peter Cordes


21

Chodzi o to, który należy zwrócić, gdy są one równoważne; std::maxmusi zwrócić a(tj. pierwszy argument) w tym przypadku.

Jeśli są równoważne, zwraca a.

Więc a < b ? b : apowinno być używane; z drugiej strony b < a ? a : b;zwróci bnieprawidłowo.

(Jak powiedział @Holt, cytat wydaje się odwrotny.)

„te dwie wartości są równoważne, ale nie równe” oznacza, że ​​mają tę samą wartość podczas porównywania, ale w niektórych innych aspektach mogą być różnymi obiektami.

na przykład

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

1
Czy mógłbyś wyjaśnić, dlaczego std::max(a, b)musi wrócić a, jeśli ai bsą równoważne?
眠 り ネ ロ ク

4
@ ネ ロ ク - To tylko arbitralny wybór ze strony normy . Chociaż jest to trochę dyskusyjne, jeśli jest dobry.
StoryTeller - Unslander Monica

Czy to tylko ja, czy jest to sprzeczne z pytaniem? Jeśli ai bsą równoważne, to !(a < b) && !(b < a)jest prawdziwe, więc a < bi b < asą fałszywe, więc ...?
Holt

2
@ ネ ロ ク Przypuszczam, że standard chce tylko sprawić, że określi; kiedy są równoważne, który z nich należy zwrócić.
songyuanyao

1
dziękuję za odświeżenie mojej pamięci o tym, dlaczego obiekt byłby „równoważny”, ale nie „równy”.
Jeff Walker
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.