ít hoặc less_equal bằng cách sử dụng thiết lập

Question

Chúng ta có thể vượt qua một chức năng như < (ít hơn) điều hành cho các cấu trúc dữ liệu STL như set, multiset, map, priority_queue ...

Có một vấn đề nếu chức năng của chúng tôi hoạt động như <= (less_equal)?

Answer 1

Từ hiệu suất STL -> Mục 21. Luôn có hàm so sánh trả về false cho giá trị bằng nhau.

Tạo một bộ nơi less_equal là kiểu so sánh, sau đó chèn 10 vào tập:

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

Bây giờ thử chèn 10 một lần nữa:

s.insert(10); 

Đối với cuộc gọi này để chèn, tập có để tìm hiểu xem liệu 10 đã có mặt chưa. Chúng tôi biết . nhưng bộ đồ ngốc nghếch như bánh mì nướng, nên nó phải kiểm tra. Để làm cho nó dễ dàng hơn để hiểu điều gì sẽ xảy ra khi thiết lập thực hiện điều này, chúng tôi sẽ gọi số 10 ban đầu là được chèn 10A và 10 mà chúng tôi đang cố gắng chèn 10B.Thiết lập thông qua các cấu trúc dữ liệu nội bộ của nó tìm kiếm nơi để chèn 10B. Cuối cùng nó phải kiểm tra 10B để xem nó có giống với 10A hay không. Định nghĩa của "giống nhau" đối với các thùng chứa liên kết là tương đương, do đó, các thiết lập kiểm tra để xem liệu 10B có tương đương với 10A hay không. Khi thực hiện phép thử này, nó sẽ tự nhiên sử dụng hàm so sánh của tập hợp. Trong ví dụ này, đó là toán tử < =, vì chúng tôi đã chỉ định less_equal làm hàm so sánh của tập hợp và các toán tử less_equal có nghĩa là. Tập do đó kiểm tra xem biểu thức này là đúng:

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

Vâng, 10A và 10B đều 10, do đó, nó rõ ràng đúng là 10A < = 10B. Tương tự rõ ràng, 10B < = 10A. Biểu thức trên như vậy, đơn giản hoá để

!!(true)&&!(true) 

và đơn giản hóa để

false && false 

mà chỉ đơn giản là sai. Tức là, tập hợp kết luận rằng 10A và 10B không tương đương, do đó không giống nhau, và do đó nó đi về việc chèn 10B vào thùng chứa cùng với 10A. Về mặt kỹ thuật, hành động này mang lại hành vi không xác định, nhưng kết quả gần như phổ quát là tập hợp kết thúc với hai bản sao của giá trị 10 và điều đó có nghĩa là không còn một bộ nữa. Bằng cách sử dụng less_equal làm loại so sánh của chúng tôi, chúng tôi đã làm hỏng vùng chứa ! Hơn nữa, bất kỳ hàm so sánh nào mà các giá trị bằng nhau trả về true sẽ làm điều tương tự. Giá trị bằng nhau, theo định nghĩa, không tương đương!

Answer 2

Có thực sự là một vấn đề.

Chức năng so sánh phải đáp ứng strict weak ordering mà <= thì không.

Answer 3

Có, có sự cố.

Chính thức, hàm so sánh phải xác định đặt hàng yếu kém nghiêm ngặt và <= không làm điều đó.

cụ thể hơn, < cũng được sử dụng để xác định sự tương đương (x và y tương đương iff !(x < y) && !(y < x)). Điều này không đúng với <= (sử dụng toán tử đó sẽ khiến bộ của bạn tin rằng các đối tượng là không bao giờ là tương đương)