Como contornar um array 2D muito grande em C++
Pergunta
Preciso criar uma matriz int 2D de tamanho 800x800.Mas fazer isso cria um estouro de pilha (ha ha).
Sou novo em C++, então devo fazer algo como um vetor de vetores?E apenas encapsular o array 2D em uma classe?
Especificamente, esse array é meu zbuffer em um programa gráfico.Preciso armazenar um valor z para cada pixel na tela (daí o tamanho grande de 800x800).
Obrigado!
Solução
Você precisa de cerca de 2,5 megas, então apenas usar o heap deve servir.Você não precisa de um vetor, a menos que precise redimensioná-lo.Ver Perguntas frequentes sobre C++ Lite para obter um exemplo de uso de uma matriz heap "2D".
int *array = new int[800*800];
(Não se esqueça de delete[]
quando terminar.)
Outras dicas
Cada postagem até agora deixa o gerenciamento de memória para o programador.Isto pode e deve ser evitado.ReaperUnreal está muito perto do que eu faria, exceto que eu usaria um vetor em vez de uma matriz e também criaria os parâmetros do modelo de dimensões e alteraria as funções de acesso - e, ah, apenas IMNSHO limparia um pouco as coisas:
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;
};
Agora você pode alocar esse array 2-D na pilha perfeitamente:
void foo()
{
Array2D<int, 800, 800> zbuffer;
// Do something with zbuffer...
}
Eu espero que isso ajude!
EDITAR:Especificação de array removida de Array2D::buffer
.Obrigado a Andreas por pegar isso!
O exemplo de Kevin é bom, entretanto:
std::vector<T> buffer[width * height];
Deveria estar
std::vector<T> buffer;
Expandindo um pouco, você poderia, é claro, adicionar sobrecargas de operador em vez das funções at():
const T &operator()(int x, int y) const
{
return buffer[y * width + x];
}
e
T &operator()(int x, int y)
{
return buffer[y * width + x];
}
Exemplo:
int main()
{
Array2D<int, 800, 800> a;
a(10, 10) = 50;
std::cout << "A(10, 10)=" << a(10, 10) << std::endl;
return 0;
}
Você poderia fazer um vetor de vetores, mas isso teria alguma sobrecarga.Para um buffer z, o método mais típico seria criar uma matriz de tamanho 800*800=640000.
const int width = 800;
const int height = 800;
unsigned int* z_buffer = new unsigned int[width*height];
Em seguida, acesse os pixels da seguinte forma:
unsigned int z = z_buffer[y*width+x];
Eu poderia criar uma matriz de dimensão única de 800*800.Provavelmente é mais eficiente usar uma alocação única como esta, em vez de alocar 800 vetores separados.
int *ary=new int[800*800];
Então, provavelmente encapsule isso em uma classe que funcione como um array 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];
}
};
A abstração mostrada aqui tem muitos buracos, por exemplo, o que acontece se você acessar além do final de uma "linha"?O livro "Effective C++" tem uma boa discussão sobre como escrever bons arrays multidimensionais em C++.
Uma coisa que você pode fazer é alterar o tamanho da pilha (se você realmente deseja o array na pilha) com VC, o sinalizador para fazer isso é [/F](http://msdn.microsoft.com/en-us/library/tdkhxaks(VS.80).aspx).
Mas a solução que você provavelmente deseja é colocar a memória no heap e não na pilha, para isso você deve usar um vector
de vectors
.
A linha a seguir declara um vector
de 800 elementos, cada elemento é um vector
de 800 int
se evita que você gerencie a memória manualmente.
std::vector<std::vector<int> > arr(800, std::vector<int>(800));
Observe o espaço entre os dois colchetes angulares de fechamento (> >
) que é necessário para desambiguá-lo do operador shift right (que não será mais necessário em C++0x).
Ou você pode tentar algo como:
boost::shared_array<int> zbuffer(new int[width*height]);
Você ainda deve ser capaz de fazer isso também:
++zbuffer[0];
Não há mais preocupações com o gerenciamento da memória, não há classes personalizadas para cuidar e é fácil de usar.
Existe a maneira C de fazer:
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;
Você poderia encapsular o y * xwidth + x
dentro de uma classe com um método get e set fácil (possivelmente sobrecarregando o []
operador se você quiser começar a entrar em C++ mais avançado).Eu recomendo fazer isso lentamente se você estiver apenas começando com C++ e não começar a criar modelos de classe totalmente reutilizáveis para matrizes de n dimensões, o que apenas irá confundi-lo quando você estiver começando.
Assim que você começar a trabalhar com gráficos, poderá descobrir que a sobrecarga de ter chamadas de classe extras pode tornar seu código mais lento.No entanto, não se preocupe com isso até que seu aplicativo não seja rápido o suficiente e você possa criar um perfil dele para mostrar onde o tempo foi perdido, em vez de torná-lo mais difícil de usar no início, com possível complexidade desnecessária.
Descobri que o FAQ do C++ Lite era ótimo para informações como esta.Em particular, sua pergunta é respondida por:
http://www.parashift.com/c++-faq-lite/freestore-mgmt.html#faq-16.16
Você pode alocar array no armazenamento estático (no escopo do arquivo ou adicionar static
qualificador no escopo da função), se você precisar de apenas uma instância.
int array[800][800];
void fn()
{
static int array[800][800];
}
Dessa forma ele não irá para a pilha e você não precisará lidar com memória dinâmica.
Bem, com base no que Niall Ryan começou, se o desempenho for um problema, você pode dar um passo adiante, otimizando a matemática e encapsulando isso em uma classe.
Então, começaremos com um pouco de matemática.Lembre-se de que 800 pode ser escrito em potências de 2 como:
800 = 512 + 256 + 32 = 2^5 + 2^8 + 2^9
Portanto, podemos escrever nossa função de endereçamento como:
int index = y << 9 + y << 8 + y << 5 + x;
Então, se encapsularmos tudo em uma classe legal, obteremos:
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];
};