[C++]二維數組還是一維數組？
記得剛學習C++那會這個問題曾困擾過我，後來慢慢形成了不管什麼時候都用一維數組的習慣，再後來知道了在一維數組中提出首列元素地址進行二維調用的辦法。可從來沒有細想過這個問題，最近自己寫了點代碼測試下，雖然還是有些不明就裡，不過結果挺有意思。
為了避免編譯器優化過度，用的是寫操作，int，測試分為不同大小的空間，同樣大小空間不同的行和列數。分別記錄逐行寫入，逐列寫入，按間隔寫入，空間申請和釋放的時間。
測試代碼
一維數組的申請和釋放
1 // Create
2 int *m = new int[n_row * n_col];
3
4 // Free
5 delete [] m;
二維數組的申請和釋放
復制代碼
1 // Create
2 int **m = new int*[n_row];
3 for ( int i = 0; i < n_row; ++i )
4 m[i] = new int[n_col];
5
6 // Free
7 for ( int i = 0; i < n_row; ++i )
8 delete [] m[i];
9 delete [] m;
復制代碼
逐行寫入
復制代碼
1 for ( int i = 0; i < n_row; ++i )
2 {
3 for ( int j = 0; j < n_col; ++j )
4 {
5 matrix[i * n_col + j] = answer;
6 // matrix[i][j] = answer;
7 }
8 }
復制代碼
逐列寫入
復制代碼
1 for ( int j = 0; j < n_col; ++j )
2 {
3 for ( int i = 0; i < n_row; ++i )
4 {
5 matrix[i * n_col + j] = answer;
6 // matrix[i][j] = answer;
7 }
8 }
復制代碼
按間隔寫入
復制代碼
1 for ( int i = 0; i < n_row; ++i )
2 {
3 for ( int j = 0; j < n_col; ++j )
4 {
5 int row = i * 7 % n_row;
6 int col = j * 11 % n_col;
7 matrix[i * n_col + j] = answer;
8 // matrix[i][j] = answer;
9 }
10 }
復制代碼
不是很確定這種測試是否很合理，不過大體上能體現我要測的東西了。需要注意的是逐行寫入中為了簡便我用的是寫入一個叫answer的變量，其實情況應該更泛化，否則用memset或者std::fill也許會更快？逐列寫入的代碼本科課程級別的典型反面代碼例子，這裡也僅僅是為了測試。
僅僅從編譯的角度來看主要的差別在下面兩句：
1 matrix[i * n_col + j] = answer;
2 matrix[i][j] = answer;
來看一下對應的匯編代碼：
復制代碼
1 ; matrix[i * n_col + j] = answer;
2 mov edx, DWORD PTR _i$3[ebp]
3 imul edx, DWORD PTR _n_col$[ebp]
4 add edx, DWORD PTR _j$2[ebp]
5 mov eax, DWORD PTR _matrix$[ebp]
6 mov ecx, DWORD PTR _answer$[ebp]
7 mov DWORD PTR [eax+edx*4], ecx
復制代碼
復制代碼
1 ; matrix[i][j] = answer;
2 mov ecx, DWORD PTR _i$4[ebp]
3 mov edx, DWORD PTR _matrix$[ebp]
4 mov eax, DWORD PTR [edx+ecx*4]
5 mov ecx, DWORD PTR _j$3[ebp]
6 mov edx, DWORD PTR _answer$[ebp]
7 mov DWORD PTR [eax+ecx*4], edx
復制代碼
都是6條指令，體系學得不好，所以也看不出哪個更快。這裡用的是Visual Studio編譯，因為本人gcc用得不熟，不知道怎麼生成這麼直觀的匯編和C++對應，效率上而言Linux下還是比Windows高一些，不過為了統一，之後的測試也基於Windows。當然上面的是沒有優化的編譯，如果開了優化(VS /O2)，匯編指令大概也都是4、5條的樣子，因為/O2優化後的匯編代碼結構不是很直觀，這裡就不貼了。（另一方面也是由於我的匯編水平很弱，看不出什麼）
除了直接使用一維和二維數組，也可以對一維數組進行二維索引，方法是把一維數組中所有對應第一列的元素的地址單獨作為一個指針數組，這樣本質上還是一維數組，但是實現了形式上的二維數組調用，這種辦法空間申請的代碼如下：
1 // Create
2 int **m = new int*[n_row];
3 int *block = new int[n_row * n_col];
4 for ( int i = 0; i < n_row; ++i )
5 m[i] = &block[i * n_col];
6 return m;
釋放的代碼和二維數組相同。
用一維數組模擬二維調用的優點是既保證了內存空間的連續性，又保持了二維調用的代碼易維護的優點。不過需要注意的是，由於是二維索引，匯編代碼和二維數組還是一樣的。
