Re: [問題] 有關運算子多載

[littleshan (我要加入劍道社!)]

※ 引述《tropical72 (藍影)》之銘言：
: xMaxtrix& xMatrix:: scopy( const xMatrix& m) const; /* shallow  */
: xMatrix   xMatrix:: dcopy( const xMatrix& m) const; /* deep */
: xMatrix   xMatrix:: operator = () const; /* 裡面做 shallow copy  */
: 不過完全不能以 shall copy 進行， (所以上面 code 也是白寫的 Orz)
: 因為做 shall copy , 最後物件解構時，
: 便如 littleshan 所言會有 double delete 情形發生，
: 不知是否有解決方案？
時間有限，我先回答前面這個問題。

如果你要使用 shallow copy 減少複製的時間成本，
那就必需為每個物件加上 reference counting

    class Matrix {
        size_t row, col;
        double **data;
        size_t *ref_count; // reference count
        ...
    };

    然後在進行 shallow copy 的時候增加 reference count

    Matrix& Matrix::operator=(const Matrix& m)
    {
        // copy members
        ....
        // increase reference count
        (*ref_count)++;
    }

    解構的時候檢查 reference count 來判斷是否需要歸還記憶體

    Matrix::~Matrix()
    {
        (*ref_count)--;
        if(*ref_count == 0)
            release();
    }

不過在做之前，有一些重要的考量點：

 1. 一般而言，「複製」一個物件不會對原物件產生變化，因此在 multi-
    threading 的環境下，多支 thread 複製同一個物件時，因為並不會對
    來源做寫入，因此也不至於產生 race condition。但在 reference
    counting 的情況，「複製」的同時會對 reference count 進行寫入，
    從而造成 race condition。因此在上面對 ref_count 遞增及遞減時，
    必需使用 atomic operation。

 2. 此時的 Matrix 物件具有 reference semantic。簡單講就是不同物件
    會指涉到同一塊記憶體，從而造成副作用 (side effect)。

        Matrix a = ...;
        Matrix b = a;
        b.set(10, 10, 200); // set b.data[10][10] to 200

    這時候 a 的內容也會被改變，這個行為和一般的 C++ 物件很不一樣。
    因為 C++ 提供指標和參照來達成 reference semantic，所普遍來說
    大部份的 class 都具有 value semantic。

    這邊舉個例子：假設有人寫了一個 function template 來計算加乘法：

        template <typename T>
        T mul_and_add(const T& a, const T& b, const T& c)
        {
            // returns a*b+c, which is common in matrix operation
            T r = a;
            r *= b;
            r += c;
            return r;
        }

    這樣寫「看起來」是沒問題的，然而他假設 T 具有 value semantic，
    亦即第一行的 r = a 是 deep copy，其後的 r *= b 只會影響 r
    而不會影響 a，這個假設套用到前面的 Matrix 時卻大錯特錯。

    更有甚者，C++ 的 const 在這邊暴露了他的缺點。儘管我們使用 const T&
    來修飾 a，但這保護不了 a 的指標成員所指向的資料。下面是個簡單說明

        class Obj {
        public:
            int *ptr;
            Obj() { ptr = new int; }
            ~Obj() { delete ptr; }
        };

        const Obj foo;
        foo.ptr = new int; // error
        *(foo.ptr) = 10;   // OK

    這造成 C++ 中，具有 reference semantic 的物件無法被 const 保護，
    我們只要對他做一個 shallow copy 即可隨意寫入：

        void foo(const Matrix& m){
            m.set(10, 10, 100); // error
            Matrix x = m;
            x.set(10, 10, 100); // OK, m is also modified
        }

    如果我們使用指標或參照，compiler 是可以幫我們擋下這種行為，
    因為 const 指標不能被指派到 non-const 指標上：

        void foo(const Matrix* m){
            Matrix* x = m;      // error: x is non-const pointer to Matrix
            x->set(10, 10, 100);
        }

綜合以上說明，我不建議你在 C++ 中創造這種使用 shallow copy、具有
reference semantic 的物件，會造成許多潛在的問題。

        *       *       *       *       *       *

為了避免上述的問題，我們必須使用 deep copy 讓物件具有 value semantic。
然而這又形成多餘的複製成本。想像以下的程式碼：

    Matrix a, b, c;
    ...
    a = b * c;

b*c 會產生一份暫時物件。若我們使用 shallow copy，等號的賦值只會複製
指標，但在 deep copy 的情況下必須複製整個暫時物件，然後再把暫時物件
解構，這過程看起來實在有夠蠢。而且在這個例子中 a 已經是建構完成的物
件，因此 RVO 幫不上忙。

解決的方法當然還是有的，一個是 expression template，另一個是 rvalue
reference。

篇幅關係我簡單講原理，expression template 的做法是改寫operator*()，
讓 b*c 的結果回傳一個 proxy object，而非馬上計算出結果。而在
operator=() 中，讓 Matrix 接到 proxy object 的時候再計算結果。
此時因為我們可以直接把結果存在 a 裡面，從而避免產生暫時物件的成本。

rvalue reference 則是 C++11 新標準的功能，意為指向暫時物件的參照。
由於我們可以直接操作暫時物件，而非操作暫時物件的副本，因此可以做到
「只對暫時物件進行 shallow copy」的目標。

        *       *       *       *

以下是自嗨時間...

作為 C++ 的繼承者，D 語言對這個問題提供了完全不同的解法。D 的 struct
是 value semantic，然而 D compiler 對 struct 的內容有特別的要求：

    struct 內部不能儲存指向 struct 內部成員的指標。

這個要求讓 struct 可以任意地「搬移」，也就是即使把任意 struct 的內容
原封不動地搬到記憶體的另一個地方，它也能保持資料的一致性。因此上述的
程式碼：

    a = b * c;

計算出暫時物件後，a 的內容會被解構 (因為即將被覆寫)，然後暫時物件會被
直接「搬移」到 a 的位址上。由於「搬移」只是複製 struct 的內容，亦即
僅複製指向二維陣列的指標，因此這個操作非常快。這些過程全部由 compiler
在最佳化的時候完成，除了 copy ctor 外 (在 D struct 中稱為 postblit)
完全不需要其它程式碼來輔助 compiler，so cool~

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.3.139
→ hilorrk:比起expression template 還是rvalue的move語義更直觀簡便
推 tropical72:可 m 起來嗎 ? 實在寫得太精彩了 , 推推
→ diabloevagto:太深奧了...
※ 編輯: littleshan      來自: 220.135.3.139        (11/04 17:26)
→ diabloevagto:指標指向的是一個變數用const可以保護
→ diabloevagto:http://codepad.org/nxb0IO0X
→ diabloevagto:但如果是class就保護不到，請問有辦法嗎？
→ diabloevagto:http://codepad.org/ScztZEbM
→ littleshan:const test* ptr=&i;
→ littleshan:const 放前放後意思差很多
→ diabloevagto:我記得說const放前面是ptr的值不能修改，後面是指向
→ diabloevagto:的那個值不能修改
→ diabloevagto:但是ptr如果指向一個class，在用->指向class內部的
→ littleshan:你記反了
→ diabloevagto:變數，這樣子放在後面一樣能夠修改到，不知道友沒有
→ diabloevagto:辦法可以不要被修改到？
→ diabloevagto:我自己測試完之後也記錯了...
→ littleshan:後面的那個情況只能用private+getter/setter去限制
→ diabloevagto:感謝！