如何在 C++ 中处理非常大的二维数组
题
我需要创建一个大小为 800x800 的 2D int 数组。但这样做会造成堆栈溢出(哈哈)。
我是 C++ 新手,所以我应该做一些类似于向量的向量的事情吗?然后将二维数组封装到一个类中?
具体来说,这个数组是我在图形程序中的 zbuffer。我需要为屏幕上的每个像素存储一个 z 值(因此尺寸为 800x800)。
谢谢!
解决方案
您需要大约 2.5 兆,因此仅使用堆就可以了。除非需要调整矢量大小,否则不需要矢量。看 C++ 常见问题精简版 有关使用“2D”堆数组的示例。
int *array = new int[800*800];
(别忘了 delete[]
完成后就可以了。)
其他提示
到目前为止,每一篇文章都将内存管理留给了程序员。这是可以而且应该避免的。ReaperUnreal 与我所做的非常接近,除了我使用向量而不是数组,并且还设置维度模板参数并更改访问函数 - 哦,只是 IMNSHO 清理一下:
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
. 。感谢安德烈亚斯抓住了这一点!
不过,凯文的例子很好:
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;
}
你可以做一个向量的向量,但这会产生一些开销。对于 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];
我可能会创建一个 800*800 的一维数组。使用像这样的单个分配可能比分配 800 个单独的向量更有效。
int *ary=new int[800*800];
然后,可能将其封装在一个类似于二维数组的类中。
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++ 编写良好的多维数组进行了很好的讨论。
您可以做的一件事是使用 VC 更改堆栈大小(如果您确实希望数组位于堆栈上),执行此操作的标志是 [/F](http://msdn.microsoft.com/en-us/library/tdkhxaks(VS.80).aspx).
但您可能想要的解决方案是将内存放在堆中而不是堆栈中,因为您应该使用 vector
的 vectors
.
下面一行声明了一个 vector
800 个元素,每个元素是 vector
共 800 个 int
s 并使您免于手动管理内存。
std::vector<std::vector<int> > arr(800, std::vector<int>(800));
请注意两个右尖括号之间的空格 (> >
)这是为了消除它与右移运算符的歧义(在 C++0x).
或者你可以尝试类似的方法:
boost::shared_array<int> zbuffer(new int[width*height]);
您仍然应该能够执行此操作:
++zbuffer[0];
不再需要担心管理内存,无需处理自定义类,而且很容易随意使用。
有类似 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
您可以在静态存储上分配数组(在文件范围内,或添加 static
函数范围内的限定符),如果您只需要一个实例。
int array[800][800];
void fn()
{
static int array[800][800];
}
这样它就不会进入堆栈,并且您不必处理动态内存。
好吧,在 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];
};