多维数组是邪恶的

评分：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>&);
};

这就是全部！