Como contornar um array 2D muito grande em C++

Question

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!

Answer 1

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.)

Answer 2

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!

Answer 3

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;
}

Answer 4

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];

Answer 5

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++.

Answer 6

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 intse 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).

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

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];
};