mniej lub less_equal korzystając ustawić

Question

Możemy przekazać funkcję jako < (mniej) operatora do struktur danych STL, takich jak set, multiset, map, priority_queue ...

jest jakiś problem, jeśli nasza funkcja działa jak <= (less_equal)?

Answer 1

Z Efektywny STL -> Pozycja 21. Zawsze funkcje porównania zwracają wartość false dla równych wartości .

Utwórz zestaw gdzie less_equal jest rodzaj porównania, a następnie włóż 10 w zestawie:

set<int, less_equal<int> > s; // s is sorted by "<=" 
s.insert(10); //insert the value 10 

Teraz spróbuj wkładając 10 znowu:

s.insert(10); 

Do niniejszego zaproszenia do wstawienia, zestaw ma aby dowiedzieć się, czy 10 jest już obecne. Wiemy, że jest to . ale zestaw jest głupi jak toast, więc musi sprawdzić. Aby ułatwić zrozumienie tego, co stanie się, gdy zestaw zrobi to, zadzwonimy do 10, który był początkowo wstawiony 10A i 10, który próbujemy wstawić 10B. Zestaw przechodzi przez swoje wewnętrzne struktury danych szukając wstawić 10B. Ostatecznie musi sprawdzić 10B, czy jest taki sam jak 10A. Definicja "tego samego" dla pojemników asocjacyjnych jest równoważna, tak więc zestaw testów sprawdza, czy 10B jest równoważny 10A. Podczas wykonywania tego testu korzysta on naturalnie z funkcji porównania zestawu zestawu: . W tym przykładzie jest to operator < =, ponieważ określiliśmy less_equal jako funkcję porównania zestawu, a less_equal oznacza operatory. Zestaw sprawdza w ten sposób, aby zobaczyć, czy to wyrażenie jest prawdziwe:

!(10A<= 10B)&&!(10B<= 10A) //test 10Aand 10B for equivalence 

Cóż, 10A i 10B są zarówno 10, więc jest to prawda, że ​​wyraźnie 10A < = 10B. Równie wyraźnie 10B < = 10A. Powyższe wyrażenie upraszcza zatem

!!(true)&&!(true) 

i upraszcza do

false && false 

który jest po prostu fałszywe. Oznacza to, że zestaw stwierdza, że ​​10A i 10B nie są równoważne, a zatem nie są takie same, a zatem chodzi o włożenie 10B do pojemnika obok 10A. Z technicznego punktu widzenia działanie to powoduje niezdefiniowane zachowanie, ale prawie uniwersalnym wynikiem jest to, że zestaw kończy się dwoma kopiami wartości 10, co oznacza, że ​​nie jest już zestawem. Używając less_equal jako naszego typu porównania, uszkodziliśmy kontener ! Co więcej, każda funkcja porównania, w której równe wartości zwracają wartość true, spowoduje to samo. Równe wartości z definicji nie są równoważne!

Answer 2

Rzeczywiście istnieje problem.

Funkcja porównania powinna spełniać warunek strict weak ordering, który nie jest zgodny z .

Answer 3

Tak, jest problem.

Formalnie funkcja porównania musi zdefiniować ścisłe słabe zamówienie, a <= tego nie robi.

dokładniej, < jest również używany do określenia równoważności (x i y są równoważne iff !(x < y) && !(y < x)). Nie jest to prawdą w przypadku <= (używając tego operatora, aby ustawić, że obiekty są nigdy nie odpowiada)