Tại sao các vùng chứa liên kết không có thứ tự thực hiện toán tử nhỏ hơn?

Question

Các container kết hợp có thứ tự unordered_set, unordered_map vv không có ít hơn điều hành operator<, không phải là một hàm thành viên cũng không phải là một chức năng miễn phí. Tại sao? Không có chuyên môn nào của less. Các loại hash_* của SGI STL cũng thiếu tính năng này.

Nếu chúng ta loại trừ khái niệm về loại cơ bản, tất cả các loại thùng chứa thực hiện các yêu cầu của các loại thường xuyên theo quy định ví dụ trong Stepanov & McJones' Các yếu tố của Lập trình. Ngoại lệ duy nhất là các loại liên kết không có thứ tự, thiếu operator<.

---

tôi không thể đưa ra một thực hiện hiệu quả của một nhà điều hành như vậy là phù hợp với định nghĩa được bình đẳng, vì vậy hiệu quả có thể là lý do? Mặt khác, operator== cho container kết hợp có thứ tự trong một số trường hợp cần phải rehash mọi phần tử của một container và nhìn nó lên trong khác - trung bình O (N), nhưng trường hợp tồi tệ nhất O (n ²).

Answer 1

Về mặt lý thuyết nó không làm cho rất nhiều ý nghĩa. Hãy xem xét một túi bi màu khác nhau. Và giả sử bạn có hai túi bi:

1. Chứa màu đỏ, xanh dương, xanh lục.
2. Có màu tím, đỏ, vàng.

Túi 1 < túi 2?

Thậm chí nếu bạn kết hợp một để các màu sắc, nói:

red < yellow < purple < blue < green 

Nó vẫn còn khó khăn để nói nếu một túi nhỏ hơn so với người kia bởi vì trong nội bộ công ty liên kết túi không để các viên bi. Đó là túi 1 có thể được xuất ra trong bất kỳ 6 định dạng, mà tất cả đều tương đương:

1. đỏ, xanh dương, xanh lá cây
2. đỏ, xanh lá cây, xanh dương
3. màu xanh, đỏ, xanh lá cây
4. xanh, màu xanh lá cây, đỏ
5. xanh, đỏ, xanh
6. xanh lá, xanh, đỏ

Không có ở trên sáu là ít hơn bất kỳ o f khác. Thật vậy, tất cả đều bình đẳng, bất kể màu đỏ < màu xanh dương hoặc xanh dương < màu đỏ. Túi không phải là một chuỗi ... nó là một chuỗi không theo thứ tự.

Trong lịch sử các thùng chứa không có thứ tự cũng không có các toán tử bình đẳng. Tuy nhiên nó có ý nghĩa để hỏi nếu một túi chứa các viên bi cùng màu như túi khác. Và ở đây vấn đề là một trong những hiệu quả. Cuối cùng các thuật toán và kiến ​​nghị được trình bày để ép buộc ủy ban để thêm so sánh bình đẳng cho các container có thứ tự:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf