std :: is_sorted và so sánh hoàn toàn ít hơn?

Question

Tôi không hiểu rõ thuật toán std::is_sorted và hành vi mặc định của nó. Nếu chúng tôi xem xét cppreference, theo mặc định, std::is_sorted sử dụng toán tử <. Thay vào đó, tôi thấy rằng việc sử dụng <= sẽ là tự nhiên. Nhưng vấn đề của tôi là đối với danh sách sau đây các con số:

1 2 3 3 4 5 

nó sẽ trở lại true, ngay cả khi 3 < 3 nên false. Làm thế nào là có thể?

CHỈNH SỬA: nó dường như tồi tệ hơn những gì tôi nghĩ, bởi vì vượt qua std::less_equal<int> sẽ trả về false trong trường hợp đó ... Điều kiện được áp dụng khi tôi vượt qua một hàm so sánh là gì?

Answer 1

mỗi 25,4/5:

Một chuỗi được sắp xếp đối với một so sánh comp nếu vì bất kỳ iterator i trỏ đến chuỗi và bất kỳ số nguyên không âm nào n sao cho i + n là trình lặp hợp lệ trỏ đến phần tử của chuỗi , comp(*(i + n), *i) == false.

Vì vậy, ví

1 2 3 3 4 5 

std::less<int>()(*(i + n), *i) sẽ trở lại false cho tất cả n, trong khi std::less_equal sẽ trở lại true đối với trường hợp 3 3.

Answer 2

Thậm chí nếu bạn chỉ có nhà điều hành <, bạn có thể tìm ra nếu hai số tương đương không nhất thiết phải bằng nhau.

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

Bên cạnh đó, như giải pháp paxdiablo của thực sự đề cập đầu tiên, bạn có thể thực hiện is_sorted như đi lên danh sách và liên tục kiểm tra các < không đến mức khó tin, nếu nó là bao giờ thành sự thật bạn dừng lại.

Đây là hành vi đúng đắn về chức năng từ 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

Bạn dường như được giả định rằng nó kiểm tra (đối với trường hợp dương tính) nếu yếu tố N là ít hơn yếu tố N + 1 cho tất cả các yếu tố thanh cuối cùng. Điều đó sẽ thực sự không làm việc với chỉ <, mặc dù bạn có thể sử dụng một 'lừa' để đánh giá <= với < và !: hai sau là tương đương:

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

Tuy nhiên, nó nhiều khả năng mà nó phát hiện (tiêu cực trường hợp) nếu phần tử N nhỏ hơn phần tử N-1 cho tất cả trừ phần tử đầu tiên để nó có thể dừng lại ngay sau khi nó phát hiện ra vi phạm. Đó thể được thực hiện với không có gì hơn <, một cái gì đó tương tự (giả):

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