如何在C++中处理非常大的二维数组

Question

我需要创建一个大小为800x800的二维int数组。但是这样做会导致堆栈溢出（哈哈）。

我对C ++还不熟悉，所以我应该做一些像向量的东西吗？并且只需将2D数组封装到类中？

具体而言，这个数组是我图形程序中的zbuffer。我需要为屏幕上的每个像素存储一个z值（因此是800x800的大尺寸）。

谢谢！

- Bryan

Answer 1

你只需要大约2.5兆的空间，所以只使用堆内存就可以了。除非需要调整大小，否则不需要使用vector。请参考C++ FAQ Lite中有关使用“2D”堆数组的示例。

int *array = new int[800*800];

完成后不要忘记 delete[] 它。

- Adam Mitz

---

你不需要使用“new”来分配内存。假设zbuffer需要在多个函数之间共享，那么可以将其声明为全局变量（或者如果你已经将其抽象成某个类，可以将其放在该类中）。你可以这样做：'int zBuffer[WIDTH*HEIGHT];'，假设宽度和高度不会改变。 - Mark

当然可以，但我不建议使用全局变量，因为一般来说这并不是一个好的解决方案——它在作用域和生命周期方面灵活性不高。虽然对于提问者来说可能很有效，所以你可以留下你自己的答案。 - Adam Mitz

Answer 2

到目前为止，所有的帖子都让程序员自己来管理内存。这是可以避免的，也应该避免。ReaperUnreal 的方法已经非常接近我会做的事情了，除了我会使用向量而不是数组，并且还会将维度模板参数化并更改访问函数 - 还有，只是我的个人意见，要将代码整理得更加清晰易懂：

template <class T, size_t W, size_t H>
class Array2D
{
public:
    const int width = W;
    const int height = H;
    typedef typename T type;

    Array2D()
        : buffer(width*height)
    {
    }

    inline type& at(unsigned int x, unsigned int y)
    {
        return buffer[y*width + x];
    }

    inline const type& at(unsigned int x, unsigned int y) const
    {
        return buffer[y*width + x];
    }

private:
    std::vector<T> buffer;
};

现在你可以在堆栈上很好地分配这个二维数组：

void foo()
{
    Array2D<int, 800, 800> zbuffer;

    // Do something with zbuffer...
}

我希望这可以帮到你！

编辑：从Array2D :: buffer中删除了数组规范。感谢Andreas的指正！

- Kevin

---

我完全不同意在某些环境下进行内存管理。根据你的分配模式，缺省分配器可能会严重地破碎内存，导致难以诊断的性能问题。我也不理解将数组转换为类的必要性。在我看来这是一种混淆代码的做法。 - Mark

对于某些环境来说...好的。但是将Array2D::buffer更改为使用自定义分配器非常简单-如果您知道默认的分配器很糟糕并且有更好的选择，那么您很可能也知道如何添加自定义分配器。 - Kevin

就使用类而言……为了避免使用堆栈和手动内存管理，必须使用类。就是这样。如果你愿意使用手动内存管理，可以使用“new”来分配一个二维数组。 - Kevin

这是怎么回事？当我尝试编译时，出现了“只有静态常量整型数据成员可以在类内初始化”的错误。 - nimcap

Answer 3

Kevin的例子很好，但是：

std::vector<T> buffer[width * height];

应该是

std::vector<T> buffer;

如果需要扩展，当然可以添加运算符重载而不是使用at()函数：

const T &operator()(int x, int y) const
{
  return buffer[y * width + x];
}

并且

T &operator()(int x, int y)
{
  return buffer[y * width + x];
}

例子：

int main()
{
  Array2D<int, 800, 800> a;
  a(10, 10) = 50;
  std::cout << "A(10, 10)=" << a(10, 10) << std::endl;
  return 0;
}

- Andreas Magnusson

Answer 4

你可以使用一个向量组成的向量，但这会增加一些开销。对于z缓冲区，更典型的方法是创建一个大小为800 * 800 = 640000的数组。

const int width = 800;
const int height = 800;
unsigned int* z_buffer = new unsigned int[width*height];

然后按以下方式访问像素：

unsigned int z = z_buffer[y*width+x];

- Niall Ryan

Answer 5

我可以创建一个800*800的一维数组。使用单个分配（如此）可能比分配800个不同的向量更为高效。

int *ary=new int[800*800];

然后，可能会将其封装在一个类中，该类的行为类似于2D数组。

class _2DArray
{
  public:
  int *operator[](const size_t &idx)
  {
    return &ary[idx*800];
  }
  const int *operator[](const size_t &idx) const
  {
    return &ary[idx*800];
  }
};

这里展示的抽象概念有很多漏洞，例如，如果您访问“行”末尾之外的内容会发生什么？书籍“Effective C++”对于在C++中编写良好的多维数组有很好的讨论。

- 1800 INFORMATION

---

operator[] 返回一个 int 指针？也许这就是你的意思：int* operator[](size_t y) { return &ary[y*width]; }然后你可以这样写：my2DArray[y][x]虽然更好的做法是使用 operator()：int& operator[](int x, int y) { return ary[y*width+x]; } - Niall

好观点，但我并不完全同意重载函数调用运算符一定是更好的做法。如果你正在封装一个数组，那么应该让它看起来像一个数组。 - 1800 INFORMATION

C++ FAQ中有一些使用operator()的理由。http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.11 - Niall

单维数组与多维数组相比，几乎不会节省任何空间。 - BCS

这个常见问题（FAQ）是为了说明为什么不应该使用数组语法，还是为了说明C++标准有多糟糕？我无论如何都觉得它不太令人信服。 - 1800 INFORMATION

单维数组可能会节省空间，但重点是只需进行一次大内存分配就可以提高速度。 - 1800 INFORMATION

Answer 6

有一种类似C语言的做法：

const int xwidth = 800;
const int ywidth = 800;
int* array = (int*) new int[xwidth * ywidth];
// Check array is not NULL here and handle the allocation error if it is
// Then do stuff with the array, such as zero initialize it
for(int x = 0; x < xwidth; ++x)
{
    for(int y = 0; y < ywidth; ++y)
    {
         array[y * xwidth + x] = 0;
    }
}
// Just use array[y * xwidth + x] when you want to access your class.

// When you're done with it, free the memory you allocated with
delete[] array;

你可以将 y * xwidth + x 封装在一个类中，并使用简单的 get 和 set 方法（如果您想进一步学习 C++，可能还可以重载 [] 运算符）。不过，如果你刚开始学习 C++，建议慢慢来，不要开始创建可重用的完全类模板，以便处理 n 维数组，这只会让你在刚开始时感到困惑。

一旦你开始进行图形工作，你可能会发现额外的类调用会减慢你的代码。然而，在应用程序速度不够快且你可以分析出时间损失的情况下，不要担心这个问题，而是让它更容易使用，避免可能不必要的复杂性。

我发现 C++ lite FAQ 对此类信息非常有用。特别是你的问题可以在其中找到答案：

http://www.parashift.com/c++-faq-lite/freestore-mgmt.html#faq-16.16

- Free Wildebeest

---

如果你将新创建的数组转换为“指向包含800个整数的数组的指针”（int [800] buff; // ??），你就可以避免[xw+y]这种笨拙的写法。 - BCS

这段代码有一个bug，当宽度和高度不相等时会失败。array[xxwidth + y] 应该改为 array[yxwidth + x]。 - Niall

Answer 7

你可以做的一件事是改变堆栈大小（如果你真的想要将数组放在堆栈上），在VC中使用的标志是[/F](http://msdn.microsoft.com/en-us/library/tdkhxaks(VS.80).aspx))。

但是你可能想要的解决方案是将内存放在堆上而不是堆栈上，为此你应该使用一个vector的vectors。

下面这行代码声明了一个包含800个元素的vector，每个元素都是一个包含800个int的vector，它可以帮助你避免手动管理内存。

std::vector<std::vector<int> > arr(800, std::vector<int>(800));

请注意两个闭合角括号之间的空格（> >），这是必需的，以便将其与右移运算符区分开来（在C++0x中将不再需要）。

- Motti

Answer 8

或者你可以尝试类似这样的东西：

boost::shared_array<int> zbuffer(new int[width*height]);

你应该也能做到这一点：

++zbuffer[0];

不再担心内存管理，无需自定义类来处理，而且很容易使用。

- Ryan Fox

Answer 9

如果你只需要一个实例，你可以在静态存储（文件作用域或在函数作用域中添加 static 限定符）上分配数组。

int array[800][800];

void fn()
{
    static int array[800][800];
}

这样就不会进入堆栈，也不必处理动态内存。

- mikhaild

Answer 10

嗯，基于Niall Ryan的工作，如果性能是一个问题，你可以进一步优化这个数学问题并将其封装到一个类中。

所以我们将从一些数学开始。请注意，800可以写成2的幂次方：

800 = 512 + 256 + 32 = 2^5 + 2^8 + 2^9

因此，我们可以将我们的寻址函数写成：

int index = y << 9 + y << 8 + y << 5 + x;

如果我们将所有东西都封装到一个漂亮的类中，就会得到：

。

class ZBuffer
{
public:
    const int width = 800;
    const int height = 800;

    ZBuffer()
    {
        for(unsigned int i = 0, *pBuff = zbuff; i < width * height; i++, pBuff++)
            *pBuff = 0;
    }

    inline unsigned int getZAt(unsigned int x, unsigned int y)
    {
        return *(zbuff + y << 9 + y << 8 + y << 5 + x);
    }

    inline unsigned int setZAt(unsigned int x, unsigned int y, unsigned int z)
    {
        *(zbuff + y << 9 + y << 8 + y << 5 + x) = z;
    }
private:
    unsigned int zbuff[width * height];
};

- ReaperUnreal

---

你能说“过早优化”吗？为什么不把这些花哨的技巧留给编译器呢？ - 1800 INFORMATION

两个额外的加法和三个移位真的比仅仅做一个乘法更快吗？如果这样更快，编译器不会注意到乘以常数并自行完成吗？此外，如果您更改常数，则必须记住重写移位/加法代码。 - rjmunro

我认为创建一个缓冲行指针查找表会更快。您可以在类构造函数中根据缓冲区大小创建它。 - macbirdie