Re: [討論] c++二維陣列的配置

[Feis (永遠睡不著 @@)]

→ rockmanray:想請問二維陣列與int**的差別就是在那個+h的地方嗎？
→ rockmanray:int** 動態配置時會將一維指標放在前面
→ rockmanray:可是int[][] 因為有array的標示所以不需要那些一維指
→ rockmanray:標嗎？
   簡單回答的話, 你這樣說沒錯.

   但是我覺得你的想法有些特異, 所以下面我就贅述一下陣列的問題.

   原則上 C/C++ 沒有二維陣列的概念, 二維陣列語法上就是『陣列的陣列』

   而陣列在操作上有兩個主要的功能:
   1. 配置存放陣列元素的記憶體
   2. 提供 [] 運算子來存取元素

   要實現第一點的話, 我們需要知道陣列內『元素個數』還有『每個元素的型態』
   要實現第二點的話, 我們需要知道陣列內『第一個元素的位址』還有『每個元素的型態』

   所以只要編譯器知道『元素個數』、『每個元素的型態』跟『第一個元素的位址』就可以實作出陣列.

   例如在 C++ 中要定義一個陣列的語法是:

   int a[5];

   5 是『元素個數』, int 是『每個元素的型態』, 而 a 可以轉型成 &a[0] 表示『第一個元素的位址』
   依照前面所提到的, 這樣的定義可以讓編譯器實作出我們需要的陣列操作沒有問題.

   但是如果有些資訊不能在編譯前就知道怎麼辦？

   例如當元素個數是個變數, 要在執行的時候才決定可以嗎?

   int N;
   ...
   int a[N];

   不幸的是, 照 C++ 標準來說, 雖然執行時我們會知道需要的資訊, 但這樣是不合法的.
   所以一些編譯器會提供 variable length array 這類擴充功能讓我們可以這麼作.

   而標準作法是利用指標跟 new 運算子來實現:

   int *a = new int[N];

   N 是『元素個數』, int 是『每個元素的型態』, 而 a 是『第一個元素的位址』

   得到這三個資訊後, 透過 new 運算子可以配置記憶體空間,
   而 a 作為一個儲存第一個元素位址的指標就可以提供 [] 運算子來存取元素.

   此時 a[i] 相當於 *(a+i)
   因此 a 可以用起來是一個有 N 個元素的 int 陣列.

   那二維陣列呢？

   int b[5][4];

   二維陣列 b 是一個陣列的陣列

   對 b 陣列來說,  5 是『元素個數』, int [4] 是『每個元素的型態』, 而 b 是『第一個元素的位址』

   如果要動態來配置 b 呢？

   int N = 5;
   int (*b)[4] = new int[N][4];

   這寫法跟剛剛的一維陣列相同, 只是陣列中每個元素又是個陣列.

   但是這裡的 4 不能是個變數, 因為他是 b 陣列中『每個元素的型態』的一部分.

   這樣不就意味著 b[i] 都必須要是個固定大小的陣列嗎?

   我們希望 b 中每個元素的型態是可變大小的陣列, 因此又要將每一個元素改為使用指標:

   int N = 5;
   int M = 4;
   int **b = new  int *[N];

   (b 用起來是一個有 N 個元素的陣列, 每個元素型態是 int *)

   此時 b 作為一個一維陣列使用有配置好記憶體跟儲存第一個元素位址

   但是 b[i] 呢?

   所以我們也需要對每一個 b[i] 作一樣的事情去配置好記憶體跟儲存第一個元素位址

   for (int i = 0; i < N; ++i) {
     b[i] = new int[M];   // b[i] 用起來是一個有 M 個元素的陣列, 每個元素型態是 int
   }

   同理在 delete 的時候我們必須要做一樣的事情 (注意順序要相反):

   for (int i = 0; i < N; ++i) {
     delete [] b[i];
   }
   delete [] b;

   上述是標準作法.

   從結果來說我們需要配置兩種陣列.

   而這樣的動態配置會讓不同的 b[i] 指向的記憶體空間沒有在空間上連續,
   有時候為了效率可以用接近原 po 的作法:

   int **b = new int*[N];
   int *c  = new int[N*M];   // 一次配置好所有 b[i] 用的空間
   for (int i = 0; i < N; ++i) {
     b[i] = c + i * M;
   }

   釋放的時候:

   delete [] c;
   delete [] b;

   但是如果要像原 po 一樣將 b 跟 c 兩個陣列塞在連續空間的話,
   可能會有 alignment 跟如果有非簡易 (non trivial) 建構式的呼叫問題.

   alignment 會影響效率, 可能需要用 alignof (C++11) 去算出對的大小

   非簡易建構式的話可能需要用 placement new 去呼叫.

   我試著寫看看, 發現有點崩潰. 需要支援:

  class A {
   public:
     A() { a = 1; }
     ~A() {}
     int Get() const { return a; }
   private:
     int a;
  };

  int main() {
    int N = 5;
    int M = 3;
    const int SIZE     = N * M * sizeof(A);
    const int PADDING  = alignof(A *) - SIZE % alignof(A *); // 計算對齊差
    // 配置所需要的記憶體: 我們將指標擺在後面 
    char *c = new char[SIZE + PADDING + N*sizeof(A*)];

    // 設定 b 跟 b[i] 去指向對應的第一個元素位址 
    A **b = static_cast<A **>(static_cast<void *>(c + SIZE + PADDING));
    for (int i = 0; i < N; ++i) {
      b[i] = static_cast<A *>(static_cast<void *>(c + i * M * sizeof(A)));
    }

    // 建構 b[i][j]
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < M; ++j) {
        new (b[i]+j) A();  // Placement new
      }
    }

    // 配置完成可以使用 A b[N][M]
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < M; ++j) {
        std::cout << b[i][j].Get() << std::endl;
      }
    }

    // 解構 b[i][j]
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < M; ++j) {
        b[i][j].~A();
      }
    }

    // 刪除配置的空間 
    delete [] c;
    return 0;
  }

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.29.148
推 handsome616:太強了.....
推 Raymond0710:上色太猛了
※ 編輯: Feis            來自: 140.112.29.148       (01/28 17:07)
推 xvid:推上色 人肉editor
推 littleshan:其實用putty+vim+複製控制碼就可以快速上色了...
推 poop101:推~~詳細的解說
推 janice001:給個m好嗎 =////=
推 user1120:推！
推 VCLee:推!!