Dynamic Arrays

Écrit le 03/07/2003 par *OgGiZ*
Dernière mise à jour : 02/02/2006

Vous connaissez probablement les tableaux et les listes chaînées ? Je développerai ici une classe permettant de créer des tableaux qui allouent automatiquement la mémoire.

Pour rappel : char ch[50]; revient au même que char *ch; ch = (char*)malloc (50*sizeof (char)); ...; free (ch); sauf que les données sont allouées dynamiquement.

Commençons simple, faisons un array de float.

class array { /* Notre classe s'appellera array */

public: /* tout ceci pourra être accédé par la variable */
    array (void) /* le constructeur */
    {
        data = NULL; /* Mettons le pointeur data sur NULL sinon il aura une valeur idiote
                        qui ne sera pas NULL et qui permettra donc l'exécution d'un free
                        sur quelque chose qui ne possède pas de données allouées (voir
                        ci-dessous). */
        reset (); /* On appelle la fonction reset qui va libérer la mémoire allouée et
                     initialiser le compteur 'num' à 0. */
    }

    ~array (void) /* le destructeur */
    {
        reset (); /* idem qu'au dessus */
    }

    int current (void) /* current retourne le nombre d'éléments dans le tableau */
    {
        return num;
    }

    void reset (void) /* C'est ici qu'on ré-initialise */
    {
        if (data) /* si data n'est pas NULL, libérons la mémoire */
            free (data);
        data = NULL; /* mettons data sur NULL pour signaler que le pointeur est bien
                        vide et qu'aucune mémoire n'est donc allouée */

        num = 0; /* mettons le nombres d'éléments présents dans le tableau à zéro. */
    }

    array& operator+= (float f) /* Ceci est la partie la plus importante. Nous rajoutons
                                   un élement dans le tableau et réalouons la mémoire grâce
                                   à l'opérateur +=. */
    {
        data = (float*)realloc (data, (num+1)*sizeof (float)); /* Il faut allouer le nombre
                d'éléments actuels plus celui que nous désirons ajouter. Attention : un float
                fait quatre bytes, il faut donc multiplier par 4 (soit sizeof (float)). */
        memcpy (data + num, &f, sizeof (float)); /* Nous copions la valeur de f dans
                data[num]. Attention : memcpy demande des pointeurs. Pour rappel :
                data[num] = *(data + num) et &data[num] = &*(data + num) qui vaut donc
                (data + num). */
        num ++; /* Incrémentons le compteur de 1. */

        return *this; /* retournons le contenu de la classe. */
    }

    float operator[](int i) /* L'opérateur [] nous permet de récupérer le float d'indice i. */
    {
        return *(data + i); /* Ceci est expliqué plus haut : data[i] = *(data + i). */
    }

    operator float*(void) /* Certaines fonctions comme glVertexArray demande tout le
                             tableau d'un seul coup. */
    {
        return data; /* retournons le pointeur vers l'endroit de la mémoire où nous
                        stockons les données */
    }

private: /* ceci ne pourra pas être accédé par la variable */
    float *data; /* les données du tableau */
    int num; /* le nombre d'éléments */
};

Pour utiliser cette classe faites juste :

array tableaudefloat; /* on crée un nouveau tableau */
tableaudefloat += 10.0f; /* on ajoute la valeur 10.0f */

for (int i=0;i<tableaudefloat.current ();i++) /* On fait une boucle pour traiter
                                                 chaque valeur du tableau */ 
    printf ("%fn", tableaudefloat[i]); /* On imprime la valeur */

Un peu plus compliqué à présent : nous allons choisir un autre type de données que le float ET nous allons laisser l'utilisateur choisir le type. Ceci grâce aux templates.

template<typename elem_type> class array { /* lorsque l'on créera une variable
      on devra faire "array<float> tableau_de_float;" pour obtenir le même résultats qu'au dessus. */

public:
    array (void)
    {
        data = NULL;
        reset ();
    }

    ~array (void)
    {
        reset ();
    }

    int current (void)
    {
        return num;
    }

    void reset (void)
    {
        if (data)
            free (data);
        data = NULL;

        num = 0;
    }

    array& operator+= (elem_type f) /* Au lieu d'utiliser le type float, utilisons le
                                       type défini par l'utilisateur. */
    {
        data = (elem_type*)realloc (data, (num+1)*sizeof (elem_type)); /* non plus
             sizeof(float) mais sizeof(elem_type) car elem_type peut être n'importe quoi,
             même une structure ! */
        memcpy (data + num, &f, sizeof (elem_type)); /* idem qu'au dessus */
        num ++;

        return *this;
    }

    elem_type operator[](int i) /* nous ne retournons plus un float mais un 'elem_type'. */
    {
        return *(data + i);
    }

    operator elem_type*(void) /* idem */
    {
        return data;
    }

private:
    elem_type *data; /* notre tableau contenant les données 'elem_type'. */
    int num;
};

« Ok, tout ça c'est bien mais moi j'aimerais bien créer des tableaux de vecteurs (par ex) » vous dites-vous ? Un vecteur (par exemple) est constitué de array de 3 float ou double dans le cas de Half-Life et autres (vec3_t pour les intimes). Il faut donc créer un tableau dynamique d'un tableau statique (ici de dimension 3). Modifions sensiblement le code.

template<typename elem_type, const int elem_size> class array { /* Nous rajoutons une
     donnée : elem_size. Ici il ne sera plus question de faire += (const) car il faudra
     retourner un pointeur vers le tableau 'statique'. Par exemple : array<vec_t,3> veclist; */

public:
    array (void)
    {
        data = NULL;
        reset ();
    }

    ~array (void)
    {
        reset ();
    }

    int current (void)
    {
        return num;
    }

    void reset (void)
    {
        if (data)
            free (data);
        data = NULL;

        num = 0;
    }

    array& operator+= (elem_type f[elem_size]) /* Il faut passer un tableau et non plus
                                                  une simple valeur. */
    {
        data = (elem_type*)realloc (data, (num+1)*sizeof (elem_type)*elem_size); /* Nous sauverons
                tout ceci de façon linéaire dans notre tableau, bref sous la forme
                v1x,v1y,v1z,v2x,v2y,v2z,... il faut donc faire des saut de 3 pour les
                vecteurs (x,y,z). Généralisons avec des sauts de taille 'elem_size' spécifiés
                dans la première ligne. */
        memcpy (data + num*elem_size, f, elem_size*sizeof (elem_type)); /* A nouveau, nous
                devons copier tout le tableau statique, pas seulement le premier élément. */
        num ++;

        return *this;
    }

    elem_type* operator[](int i) /* Nous retournons un pointeur vers le tableau statique.
                 dans le cas du vecteur il faudra faire : vec_t *v = var[index]; et
                 obtenir x, y et z par v[0], v[1] et v[2]. */
    {
        return (data + i*elem_size); /* N'oublions pas qu'il faut sauter un certains nombres d'unités */
    }

    operator elem_type*(void) /* Cette classe ci utilisée avec cette fonction est
                  très utile en opengl ! glVertexArray, glTextureArray, glNormalArray, etc ... */
    {
        return data;
    }

private:
    elem_type *data;
    int num;
};

Vous pouvez imaginer toutes sortes de code dans ce même style. Voir même une classe qui permet de rajouter différents types de données à l'intérieur. Enfin, ça c'est à vous de voir ce dont vous avez besoin :)