điều hành quá tải [] cho một vector thưa thớt

Question

Tôi đang cố gắng để tạo ra một "thưa thớt" class vector trong C++, như vậy:

template<typename V, V Default> 
class SparseVector { 
    ... 
} 

Bên trong, nó sẽ được đại diện bởi một std::map<int, V> (nơi V là loại giá trị được lưu trữ). Nếu phần tử không có trong bản đồ, chúng tôi sẽ giả sử rằng phần tử này bằng với giá trị Default từ đối số mẫu.

Tuy nhiên, tôi gặp sự cố khi quá tải toán tử chỉ số, []. Tôi phải quá tải các nhà điều hành [], bởi vì tôi đang đi qua các đối tượng từ lớp này vào một chức năng tăng mà mong đợi [] để hoạt động chính xác.

Phiên bản const đủ đơn giản: kiểm tra xem chỉ mục có trong bản đồ hay không, trả về giá trị của nó nếu có hoặc Default nếu không.

Tuy nhiên, phiên bản không phải const yêu cầu tôi trả lại tham chiếu và đó là nơi tôi gặp sự cố. Nếu giá trị chỉ là đọc, tôi không cần (cũng không muốn) thêm bất kỳ thứ gì vào bản đồ; nhưng nếu nó là được viết, tôi có thể cần phải đặt một mục mới vào bản đồ. Vấn đề là quá tải [] không biết liệu giá trị có đang là đọc hoặc được viết. Nó chỉ trả về một tham chiếu.

Có cách nào để giải quyết vấn đề này không? Hoặc có lẽ để làm việc xung quanh nó?

Answer 1

Có thể có một số thủ thuật rất đơn giản, nhưng nếu không tôi nghĩ operator[] chỉ phải trả lại thứ gì đó có thể được gán từ V (và chuyển thành V), không nhất thiết là V &. Vì vậy, tôi nghĩ rằng bạn cần phải trả lại một số đối tượng với một quá tải operator=(const V&), mà tạo ra các mục trong container thưa thớt của bạn.

Tuy nhiên, bạn sẽ phải kiểm tra chức năng Boost nào với tham số mẫu của nó - chuyển đổi do người dùng xác định thành V có thể ảnh hưởng đến chuỗi chuyển đổi nào, chẳng hạn như ngăn chặn chuyển đổi do người dùng xác định chuỗi.

Answer 2

Đừng để toán tử không const & triển khai trả lại tham chiếu, nhưng đối tượng proxy. Sau đó bạn có thể thực hiện toán tử gán của đối tượng proxy để phân biệt các truy cập đọc với toán tử [] từ các truy nhập ghi.

Dưới đây là một số phác thảo mã để minh họa ý tưởng. Cách tiếp cận này không đẹp, nhưng tốt - đây là C++. Lập trình viên C++ không lãng phí thời gian cạnh tranh trong các cuộc thi sắc đẹp (họ cũng sẽ không có cơ hội). ;-)

template <typename V, V Default> 
ProxyObject SparseVector::operator[](int i) { 
    // At this point, we don't know whether operator[] was called, so we return 
    // a proxy object and defer the decision until later 
    return ProxyObject<V, Default>(this, i); 
} 

template <typename V, V Default> 
class ProxyObject { 
    ProxyObject(SparseVector<V, Default> *v, int idx); 
    ProxyObject<V, Default> &operator=(const V &v) { 
     // If we get here, we know that operator[] was called to perform a write access, 
     // so we can insert an item in the vector if needed 
    } 

    operator V() { 
     // If we get here, we know that operator[] was called to perform a read access, 
     // so we can simply return the existing object 
    } 
}; 

Answer 3

Tôi tự hỏi liệu thiết kế này có âm thanh hay không.

Nếu bạn muốn trả lại tham chiếu, điều đó có nghĩa là khách hàng của lớp có thể lưu trữ kết quả gọi operator[] trong tài liệu tham khảo và đọc từ/ghi vào bất kỳ lúc nào sau đó. Nếu bạn không trả lại một tham chiếu, và/hoặc không chèn một phần tử mỗi khi một chỉ mục cụ thể được giải quyết, làm thế nào họ có thể làm điều này? (Ngoài ra, tôi có cảm giác rằng tiêu chuẩn yêu cầu một container STL thích hợp cung cấp operator[] để toán tử đó trả về một tham chiếu, nhưng tôi không chắc chắn về điều đó.)

Bạn có thể phá vỡ điều đó bằng cách cung cấp proxy của mình cũng là operator V&() (sẽ tạo mục nhập và gán giá trị mặc định), nhưng tôi không chắc chắn điều này sẽ không mở lỗ vòng khác trong một số trường hợp Tôi chưa nghĩ đến.

std::map giải quyết vấn đề này bằng cách xác định rằng phiên bản không const của toán tử đó luôn chèn phần tử (và không cung cấp phiên bản const).

Tất nhiên, bạn luôn có thể nói điều này không phải là một vùng chứa STL ngoài giá và operator[] không trả lại các tham chiếu đơn giản mà người dùng có thể lưu trữ. Và có lẽ đó là OK. Tôi tự hỏi.