so sánh bất bình đẳng toàn cầu cho cặp <> trong C++ chuẩn

Question

Như theo cppreference:

Trong sự so sánh bất bình đẳng (<,>), các yếu tố đầu tiên được so sánh đầu tiên, và chỉ khi so sánh sự bất bình đẳng là không đúng sự thật đối với họ, các yếu tố thứ hai là được so sánh.

mà dịch để một cái gì đó như thế này:

return ((a.first < b.first) || (!(b.first < a.first) && (a.second < b.second))); 

quesion của tôi là, tại sao nó như vậy unintuitive? Lý do đằng sau nó là gì? Và có những ví dụ nào mà lý do này dẫn đến câu trả lời đúng không?

Tôi nghĩ việc thực hiện sẽ đơn giản là:

return a.first < b.first && a.second < b.second 

Answer 1

loại này so sánh được gọi là một lexicographical ordering và là một trong những cách tự nhiên hơn để kết hợp hai thứ tự khác nhau thành một.

Các yêu cầu được yêu cầu trong C++ được gọi là strict weak orderings. Điều này có nghĩa rằng những điều sau đây phải được sự thật:

• Irreflexivity: x < x luôn luôn là sai.
• Độ nhạy: Nếu x < y và y < z, sau đó x < z.
• Tính không đối xứng: Nếu x < y, thì y < x luôn luôn là sai.
• Độ tương đương của tương đương: Nếu x và y là không thể so sánh và y và z là không thể so sánh, thì x và z là không thể so sánh.

Thuộc tính này là những gì bạn cần để đảm bảo rằng bạn có thể lấy danh sách đối tượng và đưa chúng vào thứ tự tăng dần được sắp xếp. Điều này có nghĩa là bạn có thể sử dụng std::sort trên chúng hoặc lưu trữ chúng trong std::set.

Bạn có thể chứng minh bằng một chút toán học nếu bạn có hai thứ tự yếu khác nhau nghiêm ngặt, thì thứ tự từ vựng bạn nhận được bằng cách kết hợp chúng là std::pair cũng là thứ tự yếu. Thứ tự từ điển là một trong số ít cách mà bạn có thể kết hợp các thứ tự yếu kém để thực hiện các trật tự yếu nghiêm ngặt mới.

Tuy nhiên, thứ tự mà bạn đã đề xuất là không phải đặt hàng yếu kém nghiêm ngặt và sẽ khiến một số giả định nhất định vi phạm. Đặc biệt, hãy xem xét các cặp (0, 5), (3, 3) và (1, 6). Sau đó (0, 5) là không thể so sánh với (3, 3) và (3, 3) là không thể so sánh với (1, 6). Tuy nhiên, chúng tôi thực sự có điều đó (0, 5) < (1, 6), vi phạm quy tắc transitivity tương đương. Kết quả là, nhiều thuật toán sắp xếp giả định rằng tương đương là transitive (bao gồm hầu hết các thuật toán sắp xếp chính) sẽ không hoạt động chính xác trên phạm vi của bạn, nghĩa là std::sort có thể hoạt động không chính xác. Nó cũng có nghĩa là bạn cũng không thể lưu trữ chúng trong một std::set, bởi vì các std::set interally lưu trữ tất cả mọi thứ trong một số loại thứ tự sắp xếp (thường là một cây tìm kiếm nhị phân cân bằng) và bạn có thể nhận được kết quả hoàn toàn sai.

Hy vọng điều này sẽ hữu ích!

Answer 2

Nếu a.first là ít hơn b.first, sau đó cặp là ít rồi. Không có lý do gì để so sánh phần thứ hai. Các cặp ngầm sắp xếp đầu tiên bằng phần đầu tiên của chúng, giống như các tên sắp xếp đầu tiên bằng chữ cái đầu tiên của chúng. "Apple" xuất hiện trước "Zebra" vì "A" xuất hiện trước "Z", chúng tôi không so sánh "p" với chữ "e".

Vì vậy, nếu a.first < b.first, chúng tôi đã hoàn tất. Tuy nhiên, nếu không, chúng tôi chưa làm xong. Có một cách khác là a có thể nhỏ hơn b. Đó là nếu b.first < a.first không phải là trường hợp và a.second < b.second.

Tương tự sẽ là "Ngựa vằn" và "Zyman". "Z" không nhỏ hơn "Z", nhưng "e" nhỏ hơn "y", vì vậy, chữ cái đầu tiên nhỏ hơn chữ cái thứ hai.

đôi khi bạn sẽ thấy nó được mã hóa theo cách này:

bool operator<(const foo& a, const foo& b) { 
if (a.first < b.first) return true; 
if (a.first > b.first) return false; 
return (a.second < b.second); 
} 

Tôi tìm thấy điều này dễ hiểu bằng trực giác, nhưng logic là như nhau:

Answer 3

Intuitiveness là trong mắt của khán giả. Tôi thực sự tìm thấy nó khá trực quan bản thân mình.

Nó hoạt động giống như bạn làm khi bạn so sánh các trình tự khác. Ví dụ: bạn sẽ nói rằng chuỗi "az" xuất hiện trước "ba", phải không? Nhưng bạn không có 'a' < 'b' && 'z' < 'a'! Cùng một lý do được áp dụng cho các cặp. Nó không chỉ trực quan hơn mà nó còn duy trì tất cả các thuộc tính mong muốn của một mối quan hệ như vậy.