std :: is_sorted i ściśle mniej porównania?

Question

Nie rozumiem dobrze algorytmu std::is_sorted i jego domyślnego zachowania. Jeśli spojrzymy na cppreference, to domyślnie std::is_sorted używa operatora <. Zamiast tego stwierdzam, że używanie <= byłoby naturalne. Ale moim problemem jest to, że na poniższej liście numerów:

1 2 3 3 4 5 

powróci true, nawet jeśli 3 < 3 powinny być false. Jak to możliwe ?

EDYCJA: jego wydaje się być gorszy niż to, co myślałem, ponieważ przekazanie std::less_equal<int> zwróci false w takim przypadku ... Jaki jest stan, gdy przekazuję funkcję komparatora?

Answer 1

Per 25,4/5:

Sekwencja jest sortowana w stosunku do komparatora comp jeśli dla dowolnego iterator i wskazujący na sekwencję i dowolną nieujemną liczbę całkowitą n tak, że i + n jest poprawnym iteratorem wskazującym na element sekwencji , comp(*(i + n), *i) == false.

Więc dla

1 2 3 3 4 5 

std::less<int>()(*(i + n), *i) powróci false dla wszystkich n, natomiast std::less_equal powróci true dla przypadku 3 3.

Answer 2

Nawet jeśli masz tylko operatora <, możesz dowiedzieć się, czy dwie liczby są równoważne niekoniecznie równe.

if !(first < second) and !(second < first)
then first equivalent to second

Ponadto, jako rozwiązanie paxdiablo za faktycznie wymienione pierwsze, można wdrożyć is_sorted jak dzieje się na listę i nieustannie sprawdzając < nie być prawdziwe, jeśli to prawda, że ​​nigdy nie przestać.

Oto poprawne zachowanie funkcji z cplusplus.com

template <class ForwardIterator> 
    bool is_sorted (ForwardIterator first, ForwardIterator last) 
{ 
    if (first==last) return true; 
    ForwardIterator next = first; 
    while (++next!=last) { 
    if (*next<*first)  // or, if (comp(*next,*first)) for version (2) 
     return false; 
    ++first; 
    } 
    return true; 
} 

Answer 3

Wydaje się, że przy założeniu, że jest to sprawdzanie (dla dodatniego przypadku) jeśli pierwiastek N jest mniejsza niż elementu N + 1 dla wszystkich elementów pasek ostatni. To nie byłoby rzeczywiście działa tylko z <, choć można użyć „trik” ocenić <= z < i !: poniższe dwa są równoważne:

if (a <= b) 
if ((a < b) || (!((b < a) || (a < b)))) // no attempt at simplification. 

Jednakże, jest to o wiele bardziej prawdopodobne, że wykrywa (ujemny case), jeśli element N jest mniejszy niż element N-1 dla wszystkich, ale pierwszy, aby mógł się zatrzymać, gdy tylko znajdzie naruszenie. Że może być wykonane z niczym więcej niż <, coś jak (Pseudokod):

for i = 1 to len - 1: 
    if elem[i] < elem[i-1]: 
     return false 
return true