Comment contourner un très grand tableau 2D en C ++

Question

Je dois créer un tableau 2D int de taille 800x800. Mais cela crée un débordement de pile (ha ha).

Je suis novice en C ++. Devrais-je faire quelque chose comme un vecteur de vecteurs? Et simplement encapsuler le tableau 2D dans une classe?

Plus précisément, ce tableau est mon zbuffer dans un programme graphique. J'ai besoin de stocker une valeur z pour chaque pixel à l'écran (d'où la taille importante de 800x800).

Merci!

Answer 1

Vous avez besoin d’environ 2,5 Mo, il vous suffit donc d’utiliser le tas. Vous n'avez pas besoin d'un vecteur, sauf si vous devez le redimensionner. Voir C ++ FAQ Lite pour un exemple d'utilisation de l'option "2D". tas tableau.

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

(N'oubliez pas de supprimer [] lorsque vous avez terminé.)

Answer 2

Jusqu'à présent, chaque message laisse la gestion de la mémoire au programmeur. Cela peut et doit être évité. ReaperUnreal est très proche de ce que je ferais, sauf que j'utiliserais un vecteur plutôt qu'un tableau, que je créerais également les paramètres du modèle de dimensions et que je changerais les fonctions d'accès - et, oh, IMNSHO nettoyait un peu les choses:

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

Vous pouvez maintenant allouer parfaitement ce tableau 2D sur la pile:

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

    // Do something with zbuffer...
}

J'espère que cela aide!

EDIT: spécification de tableau supprimée de Array2D :: buffer . Merci à Andreas d’avoir attrapé ça!

Answer 3

L'exemple de Kevin est bon, cependant:

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

Devrait être

std::vector<T> buffer;

En le développant un peu, vous pouvez bien sûr ajouter des surcharges d’opérateurs au lieu des fonctions at ():

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

et

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

Exemple:

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

Vous pouvez créer un vecteur de vecteurs, mais cela aurait des frais généraux. Pour un tampon z, la méthode la plus typique serait de créer un tableau de taille 800 * 800 = 640000.

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

Accédez ensuite aux pixels comme suit:

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

Answer 5

Je pourrais créer un tableau à une seule dimension de 800 * 800. Il est probablement plus efficace d’utiliser une seule allocation de ce type plutôt que d’allouer 800 vecteurs distincts.

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

Ensuite, encapsulez probablement cela dans une classe agissant comme un tableau 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'abstraction présentée ici présente de nombreux trous, par exemple, que se passe-t-il si vous accédez au-delà de la fin d'une "ligne"? Le livre "Effective C ++" a une très bonne discussion sur l'écriture de bons tableaux multi-dimensionnels en C ++.

Answer 6

Une chose que vous pouvez faire est de changer la taille de la pile (si vous voulez vraiment le tableau sur la pile) avec VC l’indicateur à faire est [/ F] ( http://msdn.microsoft.com/en-us/library/tdkhxaks (VS.80) .aspx) .

Mais la solution que vous voulez probablement est de placer la mémoire dans le tas plutôt que dans la pile, pour cela vous devez utiliser un vecteur de vecteurs .

La ligne suivante déclare un vecteur de 800 éléments, chaque élément est un vecteur de 800 int et vous évite de gérer la mémoire. manuellement.

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

Notez l'espace entre les deux crochets angulaires de fermeture ( > > ) requis pour le désambiguïser de l'opérateur de décalage droit (qui ne sera plus nécessaire dans C ++ 0x ).

Answer 7

Ou vous pouvez essayer quelque chose comme:

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

Vous devriez quand même pouvoir le faire aussi:

++zbuffer[0];

Fini les soucis liés à la gestion de la mémoire, pas de classes personnalisées à gérer, et facile à utiliser.

Answer 8

Il y a la façon de faire en 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;

Vous pouvez encapsuler le y * xwidth + x dans une classe avec une méthode get et set facile (éventuellement en surchargeant l'opérateur [] si vous souhaitez commencer à obtenir en C ++ plus avancé). Je vous conseillerais toutefois d'y aller lentement si vous commencez seulement par le C ++ et ne commencez pas à créer des modèles de classe entièrement réutilisables pour les tableaux à n dimensions, ce qui vous tracassera quand vous commencerez.

Dès que vous vous lancerez dans le travail graphique, vous constaterez peut-être que la surcharge liée aux appels de classe supplémentaires risque de ralentir votre code. Cependant, ne vous inquiétez pas de cela jusqu'à ce que votre application ne soit pas assez rapide et que vous puissiez la profiler pour montrer où le temps est perdu, plutôt que de la rendre plus difficile à utiliser au début avec une possible complexité inutile.

J'ai constaté que la FAQ de C ++ lite était excellente pour des informations telles que celle-ci. En particulier, votre question reçoit la réponse suivante:

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

Answer 9

Vous pouvez allouer un tableau sur un stockage statique (dans la portée du fichier ou ajouter un qualificatif statique dans la portée de la fonction), si vous n'avez besoin que d'une instance.

int array[800][800];

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

De cette façon, la pile ne sera pas mise dans la pile et vous n’aurez pas à gérer la mémoire dynamique.

Answer 10

Bien, s’appuyant sur ce que Niall Ryan a commencé, si la performance pose problème, vous pouvez aller encore plus loin en optimisant les calculs et en les encapsulant dans une classe.

Nous allons donc commencer par un peu de maths. Rappelons que 800 peut être écrit en puissances de 2 comme suit:

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

Nous pouvons donc écrire notre fonction d'adressage en tant que:

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

Donc, si nous encapsulons tout dans une belle classe, nous obtenons:

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