Come aggirare un array 2D molto grande in C++

Question

Devo creare un array int 2D di dimensioni 800x800.Ma così facendo si crea uno stack overflow (ah ah).

Sono nuovo in C++, quindi dovrei fare qualcosa come un vettore di vettori?E semplicemente incapsulare l'array 2d in una classe?

Nello specifico, questo array è il mio zbuffer in un programma di grafica.Devo memorizzare un valore z per ogni pixel sullo schermo (da qui la grande dimensione di 800x800).

Grazie!

Answer 1

Hai bisogno di circa 2,5 mega, quindi usare solo l'heap dovrebbe andare bene.Non è necessario un vettore a meno che non sia necessario ridimensionarlo.Vedere Domande frequenti su C++ Lite per un esempio di utilizzo di un array heap "2D".

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

(Non dimenticartelo delete[] fallo quando hai finito.)

Answer 2

Ogni post finora lascia la gestione della memoria al programmatore.Questo può e deve essere evitato.ReaperUnreal è dannatamente vicino a quello che farei, tranne che utilizzerei un vettore anziché un array e creerei anche i parametri del modello di dimensioni e modificherei le funzioni di accesso - e oh, IMNSHO ripulirebbe un po' le cose:

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

Ora puoi allocare perfettamente questo array 2-D sullo stack:

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

    // Do something with zbuffer...
}

Spero che aiuti!

MODIFICARE:Rimossa la specifica dell'array da Array2D::buffer.Grazie ad Andreas per averlo catturato!

Answer 3

L'esempio di Kevin è comunque valido:

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

Dovrebbe essere

std::vector<T> buffer;

Espandendolo un po' potresti ovviamente aggiungere l'overload degli operatori invece delle funzioni 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];
}

Esempio:

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

Potresti creare un vettore di vettori, ma ciò comporterebbe un sovraccarico.Per uno z-buffer il metodo più tipico sarebbe creare un array di dimensioni 800*800=640000.

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

Quindi accedere ai pixel come segue:

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

Answer 5

Potrei creare un array a dimensione singola di 800*800.Probabilmente è più efficiente utilizzare una singola allocazione come questa, piuttosto che allocare 800 vettori separati.

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

Quindi, probabilmente incapsulalo in una classe che funziona come un 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];
  }
};

L'astrazione mostrata qui ha molti buchi, ad esempio, cosa succede se accedi oltre la fine di una "riga"?Il libro "Effective C++" contiene una discussione piuttosto approfondita sulla scrittura di buoni array multidimensionali in C++.

Answer 6

Una cosa che puoi fare è cambiare la dimensione dello stack (se vuoi veramente l'array sullo stack) con VC il flag per farlo è [/F](http://msdn.microsoft.com/en-us/library/tdkhxaks(VS.80).aspx).

Ma la soluzione che probabilmente desideri è mettere la memoria nell'heap anziché nello stack, per questo dovresti usare a vector Di vectors.

La riga seguente dichiara a vector di 800 elementi, ogni elemento è a vector di 800 ints e ti evita di gestire manualmente la memoria.

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

Notare lo spazio tra le due parentesi angolari di chiusura (> >) necessario per disambiguarlo dall'operatore Shift Right (che non sarà più necessario in C++0x).

Answer 7

Oppure potresti provare qualcosa del tipo:

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

Dovresti essere ancora in grado di farlo anche tu:

++zbuffer[0];

Niente più preoccupazioni sulla gestione della memoria, nessuna classe personalizzata di cui occuparsi ed è facile da usare.

Answer 8

C'è il modo di fare in stile 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;

Potresti incapsulare il file y * xwidth + x all'interno di una classe con un metodo get and set semplice (possibilmente sovraccaricando il file [] operatore se vuoi iniziare ad entrare nel C++ più avanzato).Ti consiglio di arrivarci lentamente se stai appena iniziando con C++ e non inizi a creare modelli riutilizzabili di classe completa per array a n dimensioni che ti confonderanno quando inizi.

Non appena inizi a lavorare sulla grafica, potresti scoprire che il sovraccarico derivante dalle chiamate in classe extra potrebbe rallentare il tuo codice.Tuttavia non preoccuparti di questo finché la tua applicazione non è abbastanza veloce e puoi profilarla per mostrare dove si perde tempo, piuttosto che renderla più difficile da usare all'inizio con possibile complessità non necessaria.

Ho scoperto che le domande frequenti su C++ lite erano ottime per informazioni come questa.In particolare alla tua domanda viene data risposta:

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

Answer 9

È possibile allocare l'array sull'archiviazione statica (nell'ambito del file o aggiungere static qualificatore nell'ambito della funzione), se è necessaria una sola istanza.

int array[800][800];

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

In questo modo non andrà nello stack e non dovrai occuparti della memoria dinamica.

Answer 10

Bene, partendo da ciò che ha iniziato Niall Ryan, se le prestazioni sono un problema, puoi fare un ulteriore passo avanti ottimizzando i calcoli e incapsulandoli in una classe.

Quindi inizieremo con un po' di matematica.Ricordiamo che 800 può essere scritto in potenze di 2 come:

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

Quindi possiamo scrivere la nostra funzione di indirizzamento come:

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

Quindi se incapsuliamo tutto in una bella classe otteniamo:

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