Re: [問題] Dynamic Array Index Management In C

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

※ 引述《tropical72 (藍影)》之銘言：
: 但在主函式裡面，它反而又是這麼寫
: int main()
: {
:     int i, j, cnt, **ivec = imatrix(1, 10, 1, 15); // ivec[1..10][1..15]
:     for(cnt=0, i=1; i<=10; ++i)
:        for(j=1; j<=15; ++j)
:            ivec[i][j]=++cnt;
:     free_imatrix(ivec, 1, 10, 1, 15);
:     return 0;
: }
: --------
: 以 int **a = imatrix(start_x, end_x, start_y, end_y) 而言，
: 我「推測」做法應類似如下 (跳過 catch malloc fail 情況)，
: 也想請教這裡是否有更佳之做法。
: int ** imatrix(unsigned sx, unsigned ex, unsigned sy, unsigned ey)
: {
:         int **t;
:         unsigned i, j;
:         t = (int**)malloc(sizeof(int*) * (ex+1) ); /* 0~ex */
:         /* 這行是我猜的 */
:         for(i=0; i<sx; ++i) free(t[i]);
          不能這樣寫
          整塊 malloc 的就只能整塊 free
          不能分期付款

:         for(i=sx; i<=ex; ++i) t[i] = (int*)malloc(sizeof(int) * (ey+1) );
:         /* 下面這兩行也是我猜的 */
:         for(i=sx; i<=ex; ++i)
:                 for(j=0; j!=sy; ++j) free(&t[i][j]);
:         return t;
: }
: 這麼做，無疑效率變非常差，甚至會有嚴重空洞現象，
: 想請問是否有其它想法
: 這方法我認為有一嚴重缺點，sx、sy 本身起始值很大時，
: a[100000..100002][100000..100002]
: 本來只是要 [0..2][0..2] ， malloc 可說幾乎必成功，
: 但要先配 100003 個，有可能導致失敗。
: -----------
: 以上，謝謝各位不吝指教，感激不盡 *^_^*
這個沒有你想像的那麼難
考慮一下一維的情況
        double *a;
        a[x] = ...

其中的 a[x] 意指 *(a+x)
你只需要調整 a 的值，讓 a+x 會落在配置出來的範圍即可

所以如果我們這樣寫

    double* ivec(int sx, int ex)
    {
        double* a = malloc(sizeof(double) * (ex-sx+1));
        return a - sx;
    }

    void foo(void)
    {
        double vec = ivec(100000, 100010)
        for(int i = 100000; i <= 100010; ++i)
            vec[i] = i;
    }

實際上這個一維陣列只用了 11 個元素的空間
只是他傳回來的指標，離開頭有 100000 個元素的位移
所以你用起來的時候，感覺就像是有 100011 個元素一樣
當然開頭 100000 個元素是配置以外的空間
對它進行存取是違法的

二維陣列的情況是一樣的：

    double** imatrix(int sx, int ex, int sy, int ey)
    {
        double** a = (double**) malloc( sizeof(double*) * (ex-sx+1) );
        a -= sx;

        for(int x = sx; x <= ex; ++x){
            a[x] = (double*) malloc( sizeof(double) * (ey-sy+1) )
            a[x] -= sy;
        }
        return a;
    }

不過，我個人認為這樣的設計非常槽糕、容易出錯又難以 debug
關鍵在於你取得的指標並非指向配置空間的開頭
因此當你要 free 的時候，必需要傳入原始的 sx 及 sy 才能正確釋放所有的空間
真要這樣搞的話，最好用 struct 以及相關函式做好包裝
(不過就算這樣還是很容易寫 bug 啦...畢竟它是 C...)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.15.163
推 tropical72:littleshan 好強 !! 沒看到真的沒想到, 大推一個 ^^
推 KTFGU:小弟新手問一下 為什麼C比較容易bug
推 tropical72:我想多問,一維中 return (a-sx); 是否可能造成 OV ?
→ littleshan:會啊，underflow的話就自求多福吧
→ littleshan:實際上使用2's complement的系統「應該」還是能動
推 tropical72:謝謝解答 *^_^*
→ littleshan:然後，C 做不出 smart pointer，多個函式共享資料時
→ littleshan:很容易造成 double free 或 memory leak
※ 編輯: littleshan      來自: 114.32.15.163        (08/01 14:02)
推 KTFGU:恩  thx~!
→ littleshan:稍微做點修正，C可以透過GC來避免上述的問題
→ littleshan:雖然會這樣做的人不多
推 tropical72:二維筆誤 for(int x = sx; x <= sx (ex) ; ++x)
yeah...被抓包了 XD
※ 編輯: littleshan      來自: 114.32.15.163        (08/01 18:09)
推 Favonia:其實不太能這樣寫（調整 a 位置），這樣是未定義行為...:P
→ Favonia:光指過去（沒有解參照）也不行。
→ Favonia:en.wikipedia.org/wiki/Undefined_behavior 第三個例子 xD
→ firejox:你似乎沒看到內文有說這是"違法"的...
→ Favonia:內文是說解參照才違法吧？實際上就算沒有解參照還是違法。
→ tropical72:( 我手邊數值分析的書該丟了嗎 XD )
→ firejox:他是指指標的位址位移到超出malloc的情況違法
→ firejox:話說一維foo 應該是double *vec吧...
→ firejox:我不知道你的解參照是指哪邊...
→ tropical72:Favonia指的解參照,應即為提取,dereference.
→ Favonia:喔別管解參照了，我的意思是說「return a - sx;」未定義。
→ Favonia:@tropical72: 對 xD 可能這翻譯太爛了...
→ littleshan:C 規定的是 pointer to array element 的計算結果越界
→ littleshan:不過malloc回傳的pointer是否也是pointer to element
→ littleshan:這點我不確定
→ Favonia:我認為有三種可能解讀，第一個是該物件仍然沒有有效型態，
→ Favonia:那麼未盡事項算未定義。第二個是因為指標的關係所以該物件
→ Favonia:有效型態變成int那指標運算那邊會把它當成大小為1的陣列，
→ Favonia:所以還是未定義。第三個解讀是因為指標的關係所以該物件的
→ Favonia:有效型態變成int陣列，那麼還是未定義。我個人認為第三個
→ Favonia:最合理。C99的「all other accesses」我不知道有沒有包括
→ Favonia:這種，但我想不管哪一種解讀都是未定義。
→ Favonia:C99 4/2(未盡事宜)6.5/6(有效型態) 還有DR#219的討論過程
→ littleshan:不過原po的要求，只能這樣做就是了 (攤手
→ Favonia:同意 :( 我也覺得沒有可攜寫法...
推 tropical72:嗯,我的確只是好奇這段原碼可能會長怎樣,雖已知設計不
→ tropical72:好,但還是會好奇.謝謝指教 *^_^*