Wie um einen sehr großen 2D-Array in C ++ arbeiten

Question

Ich brauche ein 2D-int Array der Größe 800x800 zu erstellen. Aber dabei schafft einen Stapelüberlauf (ha ha).

Ich bin neu in C ++, so soll ich tun, so etwas wie ein Vektor von Vektoren? Und kapselt nur den 2D-Array in eine Klasse?

Insbesondere dieses Array ist mein ZBuffer in einem Grafikprogramm. Ich brauche für jedes Pixel auf dem Bildschirm einen z-Wert zu speichern (und damit die Größe von 800x800).

Danke!

Answer 1

Sie müssen etwa 2,5 MB, so dass nur die Heap verwenden, sollten in Ordnung sein. Sie brauchen nicht einen Vektor, wenn Sie es, um die Größe benötigen. Siehe C ++ FAQ Lite für ein Beispiel eines "2D" Haufen mit Array.

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

(Vergessen Sie nicht, es zu delete[], wenn Sie fertig sind.)

Answer 2

Jeder Beitrag so läßt weit die Speicherverwaltung für den Programmierer. Dies kann und sollte vermieden werden. ReaperUnreal ist verdammt nah an, was ich tun würde, es sei denn ich lieber einen Vektor verwenden würde, als ein Array und auch die Abmessungen Template-Parameter vornehmen und die Zugriffsfunktionen ändern - und oh IMNSHO nur sauber die Dinge ein bisschen:

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

Jetzt können Sie verteilen diesen 2-D-Array auf dem Stapel ganz gut:

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

    // Do something with zbuffer...
}

Ich hoffe, das hilft!

EDIT: Entfernte Array Spezifikation von Array2D::buffer. Dank Andreas für den Fang!

Answer 3

Kevins Beispiel ist gut, aber:

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

sollte

std::vector<T> buffer;

es ein wenig erweitern Sie könnte natürlich betreiber Überlastungen statt der bei () hinzufügen - Funktionen:

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

und

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

Beispiel:

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

Sie können einen Vektor von Vektoren tun, aber das wäre etwas Overhead haben. Für eine Z-Puffer der typischeren Verfahren eine Reihe von Größe 800 * 800 = 640000 zu schaffen wären.

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

Dann die Pixel zuzugreifen, wie folgt:

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

Answer 5

Ich könnte ein eindimensionales Array von 800 * 800 erstellen. Es ist wahrscheinlich effizienter, eine einzige Zuordnung so zu verwenden, anstatt 800 getrennten Vektoren zuordnet.

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

Dann wahrscheinlich kapselt, dass in einer Klasse, die wie ein 2D-Array gehandelt hat.

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

Die Abstraktion hier gezeigt hat viele Löcher, beispiel, was passiert, wenn Sie aus Zugriff über das Ende einer „Reihe“? Das Buch „Effective C ++“ hat eine ziemlich gute Diskussion über gute multidimensionalen Arrays in C ++ geschrieben werden.

Answer 6

Eine Sache, die Sie tun können, ist die Stapelgröße ändern mit VC (wenn Sie wirklich das Array auf dem Stapel wollen) das Flag, dies zu tun ist [/ F] ( http://msdn.microsoft.com/en-us/library/tdkhxaks (VS.80) .aspx) .

Aber die Lösung, die Sie wahrscheinlich wollen die Erinnerung in den Haufen zu setzen, anstatt auf dem Stapel, für das Sie eine vector von vectors verwenden sollten.

Die folgende Zeile ein vector von 800 Elementen erklärt, jedes Element ein vector von 800 ints und erspart Sie die Speicher manuell zu verwalten.

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

Beachten Sie den Abstand zwischen den beiden Schließ spitzen Klammern (> >), die um sie von der Verschiebung nach rechts Operator disambiguate erforderlich ist (was nicht mehr in benötigt werden, C ++ 0x ).

Answer 7

Oder Sie könnten so etwas wie versuchen:

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

Sie sollten noch in der Lage sein, dies zu tun, auch:

++zbuffer[0];

Keine Sorgen mehr über die Speicherverwaltung, keine benutzerdefinierten Klassen kümmern, und es ist einfach, um zu werfen.

Answer 8

Es gibt die C wie Art und Weise zu tun:

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;

Sie konnten die y * xwidth + x innerhalb einer Klasse mit einer einfach bekommen und setzen Methode (möglicherweise mit Überlastung des [] Operator, wenn Sie immer in fortgeschritteneren C starten wollen ++) einzukapseln. Ich würde empfehlen, dieses immer langsam aber wenn Sie gerade erst anfangen mit C ++ und starten nicht wiederverwendbare voll Klassenvorlagen für n-dimensionalen Arrays zu schaffen, die werden Sie nur verwirren, wenn Sie beginnen ab.

Sobald Sie Grafiken erhalten in Arbeit könnten Sie feststellen, dass der Overhead Extraklasse Anrufe, die möglicherweise Ihren Code verlangsamen. Doch keine Sorge darüber, bis Ihre Anwendung nicht schnell genug ist, und Sie können es zeigen, Profil, wo die Zeit verloren geht, anstatt was es schwieriger macht zu Beginn mit möglichst unnötiger Komplexität zu verwenden.

Ich fand, dass die C ++ lite FAQ für Informationen groß war wie dieses. Insbesondere wird Ihre Frage beantwortet von:

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

Answer 9

Sie können Array auf statischen Speicher (in der Datei des Oszilloskops oder static Qualifier in Funktionsumfang hinzufügen) zuweisen, wenn Sie nur eine Instanz benötigen.

int array[800][800];

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

Auf diese Weise wird es nicht auf den Stapel gehen, und Sie müssen nicht mit dynamischem Speicher umgehen.

Answer 10

Nun, aufbauend auf was Niall Ryan gestartet, wenn die Leistung ein Problem ist, können Sie noch einen Schritt weiter nehmen durch die Mathematik zu optimieren und diese in eine Klasse eingekapselt wird.

Wir werden also mit einem wenig Mathematik beginnen. Daran erinnert, dass 800 in Potenzen von 2 geschrieben werden als:

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

So können wir unsere Adressierung Funktion als schreiben:

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

Also, wenn wir alles in eine schöne Klasse kapseln wir bekommen:

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