Trình vòng lặp của một container có thể mang lại thứ gì khác hơn là một giá trị không?

Question

Tôi có nhiều hay ít đi đến kết luận rằng không thể viết một thùng chứa phù hợp có value_type không được lưu trữ trực tiếp trong vùng chứa. Tôi nghĩ điều này thật không may, vì tôi thường muốn tôi có các thùng chứa nơi mà giá trị được tính toán hoặc lắp ráp một phần từ các phần không liên quan (ví dụ bên dưới, nhưng không liên quan trực tiếp đến câu hỏi). Tôi biết làm thế nào để viết vòng lặp mà sử dụng các đối tượng proxy, mặc dù nó khá khó chịu. Nhưng bây giờ tôi tự hỏi liệu có thực sự là không gian trong tiêu chuẩn C++ cho những con thú như vậy. Có lẽ có quá nhiều lời nói ở đây; phiên bản tl; dr rất đơn giản: Đoạn 1 và 6 của § 24.2.5 thực sự có ý nghĩa gì, và ở mức độ nào sẽ vi phạm các thuật toán tiêu chuẩn phá vỡ ý nghĩa? Hoặc, để đặt nó theo một cách khác, làm thế nào họ có thể được giải thích để cho phép lặp đi lặp lại proxy?

Như Pete Becker đã chỉ ra, thực sự không có gì buộc các thùng chứa của tôi tuân thủ các yêu cầu đặt ra cho các thùng chứa thư viện chuẩn. Nhưng để sử dụng một container với nhiều thuật toán chuẩn, nó phải có một trình vòng lặp phù hợp với ít nhất forward_iterator_tag, hoặc phải nói về điều đó nhưng vẫn quản lý để đáp ứng các yêu cầu hoạt động (nếu không chính thức). vòng lặp.

Đây là lập luận của tôi:

Bảng 96 (§ 23.2.1), yêu cầu container, bao gồm:

Expression  Return type   Assertion/note 
------------ -------------  --------------------- 
X::iterator iterator type  any iterator category 
       whose value   that meets the 
       type is T   forward iterator 
            requirements. 
            Convertible to 
            const_iterator. 

a.begin()  iterator; 
       const_iterator for 
       constant a. 

Bây giờ, phía trước iterator:

§ 24.2.5, para. 1:

Loại lớp hoặc loại con trỏ X đáp ứng các yêu cầu của trình lặp chuyển tiếp nếu & hellip;

- nếu X là trình lặp có thể thay đổi, reference là tham chiếu đến T; nếu X là một iterator const, reference là một tham chiếu đến const T

Đúng là không có yêu cầu trực tiếp cho *a trở reference (nơi a là loại X). Các yêu cầu là:

từ Bảng 107 (lặp đầu vào) *a phải "chuyển đổi thành T" nếu a là dereferencable.

từ Bảng 106 (trình lặp) *r phải có loại reference trong đó r là loại X& và không thể chấp nhận được.

Tuy nhiên, Bảng 106 cũng quy định rằng ++r lợi nhuận X&, vì vậy *++r phải reference. Ngoài ra, (theo Bảng 107), *a++ phải là reference, mặc dù (Bảng 109) a[n] chỉ cần "chuyển đổi thành tham chiếu". Tôi phải nói rằng tôi không thấy cách *a nơi a là loại X và *r nơi r thuộc loại X& có thể khác, nhưng có thể tôi thiếu một số sự tinh tế.

Có thể có một căn phòng nhỏ lung linh ở đây nhưng không nhiều; tại một thời điểm nào đó, bạn cần phải chuẩn bị để tạo ra một T, nếu bạn không thực sự có một trong vùng chứa, để bạn có thể cung cấp một tham chiếu đến nó.

Nhưng kicker là

§ 24.2.5, para. 6 (a và b là những giá trị của loại X): Nếu a và b đều dereferenceable, sau đó a == b khi và chỉ khi *a và *b đang bị ràng buộc để cùng một đối tượng.

Tôi không thể tìm thấy định nghĩa chính thức của bound to, nhưng có vẻ như chiến lược thông thường để tạo vòng lặp của đối tượng không định địa chỉ là tạo đối tượng proxy, thường được lưu trữ bên trong bản thân trình lặp. Trong trường hợp này, nó sẽ đòi hỏi một sự hiểu biết cực kỳ hào phóng về những gì "ràng buộc" có nghĩa là diễn dịch 24.2.5/6 theo bất kỳ cách nào khác hơn là cấm so sánh bình đẳng thành công giữa hai đối tượng lặp khác nhau, ngay cả khi chúng có cùng một vị trí trong thùng chứa.

Mặt khác, tôi lưu ý rằng Dietmar Kuhl, người nên biết, để đáp ứng của mình để this question nói rằng:

C++ 2011 đã yêu cầu thư giãn và lặp không nhất thiết cần thiết để mang lại một giá trị trái

Vì vậy, một trình lặp có thể trả lại proxy hay không? Nếu có thể, bản chất của một proxy như thế nào? Trường hợp nào lý do của tôi mà một iterator như vậy là không tuân thủ không?

---

Như đã hứa, một vài container mà value_types hiệu quả sẽ không được lưu trữ liên tục kế nhau trong container:

1) Một container kết hợp nhỏ gọn có trọng điểm và các loại giá trị có thể được lưu trữ hiệu quả hơn trong hai vectơ riêng biệt. (Giữ các phím trong một vec-tơ cũng có thể cải thiện tính thân thiện với bộ nhớ cache, cũng như giảm chi phí phân bổ.)

2) A vector<T> mà giả mạo là map<integer_type, T>, đơn giản hóa khả năng tương tác với các loại khác map<X, T>.

3) Vùng chứa hợp lý được hình thành bằng cách nén một số vùng chứa khác, tạo ra một giá trị logic_type là một tham chiếu tuple cho các loại giá trị của các vùng chứa đã nén. (Trong một số ứng dụng, một hoặc nhiều thùng chứa đã nén có thể được tính toàn bộ, hoặc là một hàm số của các giá trị khác, hoặc dưới dạng một số thứ tự.)

4) Chế độ xem của vùng chứa loại tổng hợp chỉ một số giá trị. (Khá có thể, cả thùng chứa cơ bản lẫn khung nhìn là các bộ dữ liệu trong đó danh sách kiểu của trình xem tuple là một tập hợp con, có thể theo một thứ tự khác, của các kiểu thùng chứa cơ bản).

Tôi chắc rằng những người khác có thể dễ dàng thêm vào danh sách này; đây chỉ là những cái tôi đã hack xung quanh trong một số cách này hay cách khác trong vài tháng qua.

Answer 1

Đừng giới hạn bản thân bằng cách suy nghĩ về "thùng chứa phù hợp": không có gì trong tiêu chuẩn phụ thuộc vào việc có.Hãy nghĩ về các yêu cầu về container như một cách viết tắt mô tả các yêu cầu đối với các thùng chứa được định nghĩa trong tiêu chuẩn. Chỉ có bấy nhiêu thôi. Miễn là các vòng lặp mà container của bạn tạo ra là hợp lệ, bạn sẽ ổn với tất cả các thuật toán tương ứng, và, có lẽ, với các thuật toán mà bạn tự viết.

Answer 2

Mô hình tốt nhất là std::vector<bool>. Nó gần như được tuân thủ nhất có thể, nhưng các trình vòng lặp của nó làm năng suất proxy.

Tiêu chuẩn thậm chí xác định rằng std::vector<bool>::reference là một lớp. Tuy nhiên, bảng yêu cầu vùng chứa chỉ định rằng X::reference sản lượng "lvalue of T." Do đó, nó hoàn toàn không tuân thủ.

Nhưng lặp không bị ràng buộc để T. Trình lặp số value_type phải là T và tham khảo các yêu cầu về trình lặp đầu vào, reference phải chuyển đổi thành value_type.

Như Pete Becker đề cập, các bảng của yêu cầu này là chăn khá rộng, và các thuật toán cá nhân xác định những gì họ cần. Chỉ có một thuật toán yêu cầu reference thực sự là một tham chiếu sẽ phá vỡ, đó là loại chỉ nói rõ ràng.