std :: is_sorted e strettamente meno confronto?

Question

Non capisco bene l'algoritmo std::is_sorted e il suo comportamento predefinito. Se guardiamo a cppreference, si dice che per impostazione predefinita std::is_sorted utilizza l'operatore <. Invece di quello, trovo che usare <= sia naturale. Ma il mio problema è che per il seguente elenco di numeri:

1 2 3 3 4 5 

si tornerà true, anche se dovrebbe essere 3 < 3false. Come è possibile ?

EDIT: sembra essere peggio di quello che pensavo, perché passare std::less_equal<int> restituirà false in tal caso ... Qual è la condizione applicata quando passo una funzione comparatore?

Answer 1

Per 25,4/5:

Una sequenza è ordinato rispetto ad un comparatore comp se per qualsiasi iteratore i che punta alla sequenza e qualsiasi numero intero non negativo n tale che i + n è un iteratore valido che punta a un elemento della sequenza , comp(*(i + n), *i) == false.

Così, per

1 2 3 3 4 5 

std::less<int>()(*(i + n), *i) tornerà false per tutti n, mentre std::less_equal tornerà true per caso 3 3.

Answer 2

Anche se si ha solo l'operatore <, è possibile capire se due numeri equivalenti non sono necessariamente uguali.

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

Inoltre, come la soluzione di paxdiablo effettivamente menzionato prima, si potrebbe implementare is_sorted come andare l'elenco e continuamente controllando per < non essere vera, se è sempre vero ci si ferma.

Ecco il corretto comportamento della funzione da 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

Sembra essere ammesso che sta controllando (per il caso positivo) se l'elemento N è inferiore dell'elemento N + 1 per tutti gli elementi bar l'ultimo. Che non sarebbe davvero lavorare con solo <, anche se si può usare un 'trucco' per valutare <= con < e !: le seguenti due sono equivalenti:

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

Tuttavia, è molto più probabile che rileva (il negativo caso) se l'elemento N è inferiore all'elemento N-1 per tutti tranne il primo, in modo che possa fermarsi non appena trova una violazione. Che può essere fatto con niente di più che <, qualcosa di simile (pseudocodice):

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