多維陣列是邪惡的

評分：4.2/5（91 票）

多維陣列是邪惡的。

我看到很多菜鳥陷入了多維（以下簡稱 MD）陣列的漩渦。MD 陣列是 C/C++ 的一項“特性”，允許你在陣列中查詢事物時使用多個索引。一個典型的用法是使用一個 2D 陣列來表示一個網格或一個遊戲地圖，其中一個索引用於 X 座標，另一個用於 Y 座標。另一個常見的用法是用於“矩陣”類或類似的東西。

這些程式設計師不知道（或者沒有意識到）的是，MD 陣列很糟糕。它們是語法毒藥。它們令人困惑，難以使用，並且（取決於實現）可能實際上消耗更多的記憶體併產生更差的效能。

在論壇上看到越來越多的關於 MD 陣列的帖子後，我決定草擬這篇文章，以闡明 MD 陣列，並提供一個合理的替代方案。

-----------------------------------

MD 陣列型別 1：直接
製作 MD 陣列最明顯的方法就是直接分配

1
2
3

int evil[5][7];

evil[3][2] = 5;

看起來似乎沒有害處。在大多數情況下，確實如此。這是最友好的 MD 陣列型別。

然而，即使使用這種形式，問題也會逐漸顯現。如果你需要將這個陣列傳遞給另一個函式怎麼辦？你會這樣做：

int func(int p[][7])
{
  p[2][3] = 1;
}

//...

func(evil);

這將透過指標將 'evil' 傳遞給 'func' 函式。這並不是那麼可怕……但它的一個限制是它只接受一個 [x][7] 的陣列。如果你想用一個不同大小的 MD 陣列來呼叫該函式呢……比如 int evil[4][5];？底線是你不能。你必須完全將 MD 陣列從函式中取出，並將其轉換為 1D 陣列，並將寬度作為單獨的引數傳遞。

int func2(int p[], int width)
{
  // p[2][3] = 1;         // no good anymore, 1D array
  p[ (2*width) + 3] = 1;  // the 1D apprach to do the same thing

/*  It's worth noting here that the above (y*width)+x calculation is basically what
    MD arrays compile to anyway.  The compiler just hides it from you with MD arrays.
     Or at least it's true with Straight Flavor MD arrays.  Other flavors are more sinister.
*/
}

//...
int evil[4][5];
func2(evil[0],5);  // ugly

你可能會注意到我將最後一行標記為醜陋。因為它確實如此。它令人困惑，語法不明確，並且很容易犯錯並將錯誤的值作為寬度傳遞。

這種型別的另一個問題是它與其他 MD 型別完全不相容。你很快就會看到。

MD 陣列型別 2：巢狀 New（動態）
一旦人們從直接 MD 陣列畢業，他們就會開始想知道如何使他們的陣列大小動態化。這就是可怕的“巢狀 new”技術出現的地方

// let's say we want to dynamically make int[Y][X]:
int** superevil = new int*[Y];
for(int i = 0; i < Y; ++i)
  superevil<i> = new int[X];

// now we can do this:
superevil[2][3] = 1;

// but cleanup is just as ugly as allocation:
for(int i = 0; i < Y; ++i)
  delete[] superevil<i>;
delete[] superevil;

請注意，這實際上建立了一個指向指標的指標，而不是真正的 2D 陣列。雖然 "superevil" 和 "evil"（來自上一節）都使用 [雙][括號] 訪問，但它們在底層的功能卻大相徑庭。

巢狀 New MD 陣列效率低下。除了為普通的 2D 陣列分配所有空間之外，你還為指標分配空間。不僅如此，為了訪問陣列中的任何元素，你必須解引用兩個指標！

真的……看看所需的凌亂的分配/銷燬程式碼。

讓我們回到呼叫函式……讓我們採用上一節中的兩個函式

1
2

int func(int p[][7]);
int func2(int p[], int width);

你如何使用 'superevil' 呼叫這些函式？

猜猜怎麼著。你不能。沒錯……你完蛋了。巢狀 New 陣列並不是與直接陣列相同意義上的 2D 陣列。直接 MD 陣列只需要 1 個解引用，但巢狀 new 需要 2 個解引用。為了將它傳遞給函式，你需要建立另一個

int func3(int** p,int width);

但現在你可能會注意到 func3 不適用於直接陣列。它們只是完全不相容。

巢狀 new 方法唯一值得稱道的地方是它不需要整個 MD 陣列是連續的，這意味著如果記憶體嚴重碎片化，你更有可能獲得所需的記憶體。但這種微弱的好處很少適用，並且被其缺點所掩蓋。

MD 陣列型別 3：向量的向量
更精通 STL 的程式設計師會選擇向量的向量方法來處理 MD 陣列，而不是巢狀 New

// to make a [5][6] array:
vector< vector<int> > stillevil( 5, vector<int>(6) );

stillevil[2][3] = 1;

關於這一點沒什麼好說的。與巢狀 New 一樣，它與其他 MD 陣列型別不相容。如果你需要將這個陣列傳遞給函式，則上述任何函式都將無法工作。

此外，與巢狀 New 一樣，它效率低下，因為它需要額外的記憶體並且具有雙重間接定址。

從好的方面來說，你不需要清理程式碼，並且分配程式碼不像那麼醜陋（但仍然很醜陋！）

殺死 MD：1D 模仿
只要你知道維度，就可以在 1D 陣列中模擬 MD 陣列。例如，如果你想要一個 2x3 的陣列，它在概念上看起來像這樣

0 1 2 3 4 5
這個陣列有 6 個元素（2 * 3）。你會注意到每一行都以寬度的倍數 (2) 開頭。因此，你可以像這樣在 1D 陣列中模擬 2D 陣列

// int evil[5][6];      // desired 2D array
int mimic[5*6];         // mimicing 1D array

// evil[2][3] = 1;      // desired [2][3] index
mimic[ (2*6) + 3] = 1;  // mimiced [2][3] index

所有這些數學運算看起來有點笨拙且效率低下。但實際上，編譯器也對 MD 陣列執行所有這些數學運算，因此這並不比 MD 陣列效率低。不過，不得不承認它確實很醜陋。

所以你可能會問自己……“這樣做有什麼好處？”

好吧，與所有不同且完全不相容的 MD 陣列型別不同，各自的1D型別都是相容的！

考慮以下情況

int func2(int p[], int width);  // remember this function?
                                // it'll work with all flavors of mimicing 1D arrays!

int a[ 5 * 6 ];
func2( a, 6 );  // works
//---

int* b = new int[5*6];
func2( b, 6 );  // works
//---

vector<int> c(5*6);
func2( &c[0], 6 );  // works (but is a little ugly, granted)

看看它有多優雅？除了索引中醜陋的數學運算之外，一切都更加流暢地融合在一起。這是殺死 MD 陣列的第一步。下一步甚至更棒。

殺死 MD：抽象的陣列類
雖然 1D 陣列更容易使用，但它們確實存在一些問題

- 查詢需要你知道陣列的維度（不知道寬度就不能 y*width）。
- 查詢語法醜陋且容易出錯。當你進入更大的維度時，情況只會變得更糟。想象一個模仿的 3D 陣列：z*width*height + y*width + x。

C++ 為這個問題提供了一個極好的解決方案：類。只需建立一個 Array2D/Matrix/whatever 類來包裝所有這些行為。

（或者不要——可能有很多現成的可以在網上使用，我實際上從未費心尋找。Boost 可能有一個，我想——我總有一天要更多地研究這個問題。如果你正在閱讀本文的更深入部分，我將假設你沒有/不想使用這樣的庫並想編寫自己的庫）

雖然你不能過載 [括號] 運算子來接受兩個引數 *，但你可以過載括號運算子。所以語法有點不同

// int bad[4][5];
Array2D<int> good(4,5);

// bad[1][2] = 3;
good(1,2) = 3;

（* 是的，你可以過載括號並返回一種奇怪的型別來使雙括號工作，但它會導致各種問題並破壞使用完全包含的類的所有優雅性）

那麼你如何建立這個 Array2D 類？只要你不想要花裡胡哨的東西，它就可以非常簡單。

這是一個非常簡單的類，沒有任何花裡胡哨的東西

template <typename T>
class Array2D
{
public:
  // constructor
  Array2D(unsigned wd,unsigned ht)
    : nWd(wd), nHt(ht), pAr(0)
  {
    if(wd > 0 && ht > 0)
      pAr = new T[wd * ht];
  }

  // destructor
  ~Array2D()
  {
    delete[] pAr;
  }

  // indexing (parenthesis operator)
  //  two of them (for const correctness)

  const T& operator () (unsigned x,unsigned y) const
  {  return pAr[ y*nWd + x ];   }

  T& operator () (unsigned x,unsigned y)
  {  return pAr[ y*nWd + x ];   }

  // get dims
  unsigned GetWd() const { return nWd; }
  unsigned GetHt() const { return nHt; }


  // private data members
private:
  unsigned nWd;
  unsigned nHt;
  T*       pAr;

  // to prevent unwanted copying:
  Array2D(const Array2D<T>&);
  Array2D& operator = (const Array2D<T>&);
};

這就是全部！