Cómo trabajar en torno a una matriz 2d muy grande en C++

Question

Necesito crear una matriz int 2D de tamaño 800x800. Pero hacerlo crea un desbordamiento de pila (ja, ja).

Soy nuevo en C++, por lo que debería hacer algo como un vector de vectores? ¿Y solo encapsula la matriz 2d en una clase?

En concreto, esta matriz es mi ZBuffer en un programa de gráficos. Necesito almacenar un valor z para cada píxel en la pantalla (de ahí el gran tamaño de 800x800).

Gracias!

Answer 1

Necesita aproximadamente 2,5 megas, por lo que solo usar el montón debe estar bien. No necesita un vector a menos que necesite cambiar el tamaño. Consulte C++ FAQ Lite para ver un ejemplo del uso de una matriz de montón "2D".

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

(No se olvide de delete[] que cuando haya terminado.)

Answer 2

Usted podría hacer un vector de vectores, pero que tendría algo de sobrecarga. Para un z-buffer, el método más típico sería crear una matriz de tamaño 800 * 800 = 640000.

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

entonces tener acceso a los píxeles de la siguiente manera:

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

Answer 3

I podría crear una única matriz de dimensión de 800 * 800. Probablemente sea más eficiente usar una única asignación como esta, en lugar de asignar 800 vectores separados.

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

Luego, probablemente encapsule eso en una clase que actuó como una matriz 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]; 
    } 
}; 

La abstracción se muestra aquí tiene un montón de agujeros, por ejemplo, ¿qué ocurre si el acceso fuera más allá del final de una "fila"? El libro "Effective C++" contiene una muy buena discusión sobre cómo escribir buenas matrices multidimensionales en C++.

Answer 4

Ahí está el C como forma de hacer:

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; 

Se puede encapsular el y * xwidth + x dentro de una clase con una escapada fácil y método establecido (posiblemente con sobrecarga para el operador [] si quieres empezar a recibir en más avanzada C++). Sin embargo, te recomiendo que vayas despacio si estás comenzando con C++ y no comienzas a crear plantillas de clase totalmente reutilizables para arreglos de n dimensiones que te confundirán cuando comiences.

Tan pronto como usted consigue en trabajos gráficos puede encontrarse con que la sobrecarga de tener las llamadas clases extraordinarias podría ralentizar el código. Sin embargo, no se preocupe por esto hasta que su aplicación no sea lo suficientemente rápida y pueda crear un perfil para mostrar dónde se pierde el tiempo, en lugar de hacerlo más difícil de usar al inicio con una posible complejidad innecesaria.

He encontrado que el C++ FAQ Lite fue grande para la información de este tipo.En particular, su pregunta es contestada por:

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

Answer 5

Pues bien, a partir de lo Niall Ryan comenzó, si el rendimiento es un problema, se puede tomar un paso más allá mediante la optimización de las matemáticas y encapsular esto en una clase.

Así que comenzaremos con un poco de matemática. Recordemos que 800 se puede escribir en potencias de 2 como:

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

lo tanto, podemos escribir nuestra función de direccionamiento como:

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

lo tanto, si se encapsula todo en una clase agradable obtenemos:

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

Answer 6

Cada publicación hasta ahora deja la gestión de memoria para el programador. Esto puede y debe evitarse. ReaperUnreal está muy cerca de lo que haría, excepto que usaría un vector en lugar de una matriz y también crearía los parámetros de la plantilla de dimensiones y cambiaría las funciones de acceso, y oh, solo IMNSHO limpia un poco:

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

Ahora puede asignar esta matriz 2-D en la pila bien:

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

    // Do something with zbuffer... 
} 

espero que esto ayude!

EDITAR: Se ha eliminado la especificación de matriz de Array2D::buffer. ¡Gracias a Andreas por atrapar eso!

Answer 7

Una cosa que puede hacer es cambiar el tamaño de la pila (si realmente desea la matriz en la pila) con VC la bandera de hacerlo es [/ F] (http://msdn.microsoft.com/en-us/library/tdkhxaks(VS.80).aspx).

Pero la solución es probable que desee es poner la memoria en el montón en lugar de en la pila, para eso se debe utilizar un vector de vectors.

la siguiente línea declara una vector de 800 elementos, cada elemento es un vector de 800 int s y le ahorra de administrar la memoria manualmente.

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

Tenga en cuenta el espacio entre los dos soportes angulares de cierre (> >) que se requiere para desambiguarlo del operador de desplazamiento a la derecha (que ya no será necesario en C++0x).ejemplo

Answer 8

de Kevin es bueno, sin embargo:

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

Debe ser

std::vector<T> buffer; 

Ampliando un poco se podía, por supuesto, añadir operador-sobrecargas en lugar del al() - funciones:

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

y

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

Ejemplo:

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

Answer 9

O usted podría intentar algo como:

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

Todavía debe ser capaz de hacer esto también:

++zbuffer[0]; 

n más preocupaciones sobre la gestión de la memoria, no hay clases personalizadas de las que ocuparse, y es fácil de usar.

Answer 10

Puede asignar una matriz en el almacenamiento estático (en el alcance del archivo, o agregar el calificador static en el alcance de la función), si solo necesita una instancia.

int array[800][800]; 

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

De esta manera no va a ir a la pila, y usted no tiene que lidiar con la memoria dinámica.