una - vector dinamico c++

Cómo trabajar alrededor de una matriz de 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 ++, entonces ¿debería hacer algo así como un vector de vectores? ¿Y solo encapsula la matriz 2d en una clase?

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

¡Gracias!

Answer 1

Bueno, basándonos en lo que comenzó Niall Ryan, si el rendimiento es un problema, puede dar un paso más al optimizar las matemáticas y encapsular esto en una clase.

Entonces comenzaremos con un poco de matemática. Recuerde que 800 se pueden escribir en potencias de 2 como:

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

Entonces podemos escribir nuestra función de direccionamiento como:

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

Entonces, si encapsulamos todo en una buena clase, 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 2

Podría crear una matriz de una sola 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];

Entonces, 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 que se muestra aquí tiene muchos agujeros, por ejemplo, ¿qué sucede si accede 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 3

Podrías hacer un vector de vectores, pero eso tendría un poco 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];

A continuación, acceda a los píxeles de la siguiente manera:

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

Answer 4

El ejemplo de Kevin es bueno, sin embargo:

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

Debiera ser

std::vector<T> buffer;

Al expandirlo un poco, podría agregar sobrecargas de operador en lugar de las funciones at ():

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 5

O podrías intentar algo como:

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

Deberías poder hacer esto también:

++zbuffer[0];

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

Answer 6

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

Pero la solución que probablemente desee es colocar la memoria en el montón en lugar de en la pila, para eso debe usar un vector de vectors .

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

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

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

Answer 7

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 yo 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 las cosas 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 puedes asignar esta matriz 2-D en la pila muy bien:

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

    // Do something with zbuffer...
}

¡Espero que esto ayude!

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

Answer 8

Existe la forma de hacer de 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;

Podría encapsular el y * xwidth + x dentro de una clase con un método fácil de obtención y configuración (posiblemente con la sobrecarga del operador [] si desea comenzar a utilizar C ++ más avanzado). 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 entres en el trabajo de gráficos, es posible que la sobrecarga de tener llamadas de clase extra ralentice tu 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.

Descubrí que las preguntas frecuentes sobre C ++ lite eran geniales para obtener información como esta. En particular, su pregunta es respondida por:

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

Answer 9

Necesitas unos 2.5 megas, así que solo usar el montón debería 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 olvide delete[] cuando haya terminado.)

Answer 10

Puede asignar una matriz en el almacenamiento estático (en el alcance del archivo, o agregar un 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 forma no irá a la pila, y no tendrá que lidiar con la memoria dinámica.