C tableau à croissance dynamique

126

J'ai un programme qui lit une liste "brute" d'entités dans le jeu, et j'ai l'intention de créer un tableau contenant un numéro d'index (int) d'un nombre indéterminé d'entités, pour traiter diverses choses. Je voudrais éviter d'utiliser trop de mémoire ou de CPU pour conserver de tels index ...

Une solution rapide et sale que j'utilise jusqu'à présent consiste à déclarer, dans la fonction de traitement principale (focus local), le tableau avec une taille des entités de jeu maximales, et un autre entier pour garder une trace de combien ont été ajoutés à la liste. Ce n'est pas satisfaisant, car chaque liste contient plus de 3000 tableaux, ce qui n'est pas tant que ça, mais cela ressemble à du gaspillage, car je vais utiliser la solution pour 6-7 listes pour différentes fonctions.

Je n'ai trouvé aucune solution spécifique C (pas C ++ ou C #) pour y parvenir. Je peux utiliser des pointeurs, mais j'ai un peu peur de les utiliser (à moins que ce ne soit le seul moyen possible).

Les tableaux ne quittent pas la portée de la fonction locale (ils doivent être passés à une fonction, puis rejetés), au cas où cela changerait les choses.

Si les pointeurs sont la seule solution, comment puis-je les suivre pour éviter les fuites?

Balkanie
la source
1
C'est un (très, très petit) problème en C, mais comment avez-vous manqué toutes les solutions C ++ et C # pour cela?
Ignacio Vazquez-Abrams
11
"Si les pointeurs sont la seule solution, comment puis-je les suivre pour éviter les fuites?" Soin, attention et valgrind. C'est exactement pourquoi les gens ont si peur si C en premier lieu.
Chris Lutz
27
Vous ne pouvez pas utiliser efficacement C sans utiliser de pointeurs. N'aie pas peur.
qrdl
sans grandes bibliothèques, une seule fonction pour tous également pour les structures, par exemple: stackoverflow.com/questions/3456446
...
6
Utiliser C sans pointeurs, c'est comme utiliser une voiture sans carburant.
martinkunev

Réponses:

210

Je peux utiliser des pointeurs, mais j'ai un peu peur de les utiliser.

Si vous avez besoin d'un tableau dynamique, vous ne pouvez pas échapper aux pointeurs. Pourquoi as-tu peur? Ils ne mordront pas (tant que vous faites attention, c'est-à-dire). Il n'y a pas de tableau dynamique intégré en C, vous devrez juste en écrire un vous-même. En C ++, vous pouvez utiliser la std::vectorclasse intégrée . C # et à peu près tous les autres langages de haut niveau ont également une classe similaire qui gère les tableaux dynamiques pour vous.

Si vous prévoyez d'écrire le vôtre, voici quelque chose pour vous aider à démarrer: la plupart des implémentations de tableaux dynamiques fonctionnent en commençant par un tableau d'une (petite) taille par défaut, puis chaque fois que vous manquez d'espace lors de l'ajout d'un nouvel élément, doublez le taille du tableau. Comme vous pouvez le voir dans l'exemple ci-dessous, ce n'est pas très difficile du tout: (j'ai omis les contrôles de sécurité par souci de concision)

typedef struct {
  int *array;
  size_t used;
  size_t size;
} Array;

void initArray(Array *a, size_t initialSize) {
  a->array = malloc(initialSize * sizeof(int));
  a->used = 0;
  a->size = initialSize;
}

void insertArray(Array *a, int element) {
  // a->used is the number of used entries, because a->array[a->used++] updates a->used only *after* the array has been accessed.
  // Therefore a->used can go up to a->size 
  if (a->used == a->size) {
    a->size *= 2;
    a->array = realloc(a->array, a->size * sizeof(int));
  }
  a->array[a->used++] = element;
}

void freeArray(Array *a) {
  free(a->array);
  a->array = NULL;
  a->used = a->size = 0;
}

Son utilisation est tout aussi simple:

Array a;
int i;

initArray(&a, 5);  // initially 5 elements
for (i = 0; i < 100; i++)
  insertArray(&a, i);  // automatically resizes as necessary
printf("%d\n", a.array[9]);  // print 10th element
printf("%d\n", a.used);  // print number of elements
freeArray(&a);
casablanca
la source
1
Merci pour l'exemple de code. J'ai implémenté la fonction spécifique en utilisant un grand tableau, mais je vais implémenter d'autres choses similaires en utilisant ceci, et après l'avoir contrôlé, changez les autres :)
Balkania
2
Merci beaucoup pour le code. Une removeArrayméthode qui se débarrasse du dernier élément serait également intéressante. Si vous l'autorisez, je l'ajouterai à votre exemple de code.
brimborium
5
% d et size_t ... un peu de non-non. Si vous utilisez C99 ou version ultérieure, vous pouvez profiter de l'ajout de% z
Randy Howard
13
N'omettez jamais les contrôles de sécurité avec l'allocation et la réallocation de mémoire.
Alex Reynolds
3
C'est un compromis de performance. Si vous doublez à chaque fois, vous avez parfois une surcharge de 100% et en moyenne 50%. 3/2 vous donne 50% de pire et 25% typique. Il est également proche de la base effective de la séquence de Fibionacci dans la limite (phi) qui est souvent louée et utilisée pour ses caractéristiques "exponentielles mais beaucoup moins violentes que la base-2", mais plus facile à calculer. Le +8 signifie que les tableaux qui sont raisonnablement petits ne finissent pas par faire trop de copies. Il ajoute un terme multiplicatif permettant au tableau de croître rapidement si sa taille n'est pas pertinente. Dans les utilisations spécialisées, cela devrait être réglable.
Dan Sheppard
10

Il y a quelques options auxquelles je peux penser.

  1. Liste liée. Vous pouvez utiliser une liste liée pour créer un tableau à croissance dynamique semblable à une chose. Mais vous ne pourrez pas le faire array[100]sans avoir à vous déplacer au 1-99préalable. Et ce n'est peut-être pas si pratique que vous utilisiez non plus.
  2. Grand tableau. Créez simplement un tableau avec suffisamment d'espace pour tout
  3. Redimensionner le tableau. Recréez le tableau une fois que vous connaissez la taille et / ou créez un nouveau tableau chaque fois que vous manquez d'espace avec une certaine marge et copiez toutes les données dans le nouveau tableau.
  4. Combinaison de tableaux de listes liées. Utilisez simplement un tableau avec une taille fixe et une fois que vous manquez d'espace, créez un nouveau tableau et créez un lien vers celui-ci (il serait sage de garder une trace du tableau et du lien vers le tableau suivant dans une structure).

Il est difficile de dire quelle option serait la meilleure dans votre situation. La simple création d'un grand tableau est bien sûr l'une des solutions les plus simples et ne devrait pas vous poser beaucoup de problèmes à moins qu'elle ne soit vraiment grande.

Wolph
la source
Comment sept tableaux de 3264 entiers sonnent-ils pour un jeu 2D moderne? Si je suis juste paranoïaque, la solution serait un grand tableau.
Balkania
3
Les n ° 1 et 4 ici nécessitent de toute façon l'utilisation de pointeurs et d'allocation de mémoire dynamique. Je suggère d'utiliser reallocavec # 3 - attribuez au tableau une taille normale, puis agrandissez-le chaque fois que vous en manquez. reallocse chargera de la copie de vos données si nécessaire. Quant à la question du PO sur la gestion de la mémoire, il vous suffit de le faire mallocune fois au début, freeune fois à la fin et à reallocchaque fois que vous manquez de place. Ce n'est pas si mal.
Borealid
1
@Balkania: sept tableaux de 3264 entiers correspondent à un cheveu de moins de 100 Ko. Ce n'est pas du tout beaucoup de mémoire.
Borealid
1
@Balkania: 7 * 3264 * 32 bitsonne comme 91.39 kilobytes. Pas tant que ça de nos jours;)
Wolph
1
Cette omission particulière est dommage, car ce qui devrait se passer lors du reallocretour n'est pas tout à fait évident NULL: a->array = (int *)realloc(a->array, a->size * sizeof(int));... Peut-être qu'il aurait été préférable de l'écrire comme int *temp = realloc(a->array, a->size * sizeof *a->array); a->array = temp;suit : ... De cette façon, il serait évident que tout ce qui se passe doit se produire avant la NULLvaleur est affectée à a->array(le cas échéant).
autiste
10

Comme pour tout ce qui semble plus effrayant au début qu'il ne l'était plus tard, le meilleur moyen de surmonter la peur initiale est de se plonger dans l'inconfort de l'inconnu ! C'est parfois comme cela que nous apprenons le plus, après tout.

Malheureusement, il existe des limites. Pendant que vous apprenez encore à utiliser une fonction, vous ne devriez pas assumer le rôle d'un enseignant, par exemple. Je lis souvent les réponses de ceux qui ne savent apparemment pas comment utiliser realloc(c'est-à - dire la réponse actuellement acceptée! ) En disant aux autres comment l'utiliser de manière incorrecte, parfois sous prétexte qu'ils ont omis la gestion des erreurs , même si c'est un écueil courant qui doit être mentionné. Voici une réponse expliquant comment l'utiliser realloccorrectement . Notez que la réponse stocke la valeur de retour dans une variable différente afin d'effectuer une vérification des erreurs.

Chaque fois que vous appelez une fonction et chaque fois que vous utilisez un tableau, vous utilisez un pointeur. Les conversions se produisent implicitement, ce qui devrait être encore plus effrayant, car ce sont les choses que nous ne voyons pas qui causent souvent le plus de problèmes. Par exemple, des fuites de mémoire ...

Les opérateurs de tableau sont des opérateurs de pointeur. array[x]est en fait un raccourci pour *(array + x), qui peut être décomposé en: *et (array + x). Il est fort probable que ce *soit ce qui vous trouble. Nous pouvons en outre éliminer l'addition du problème en supposant xêtre 0, ainsi, array[0]devient *arrayparce que l'ajout 0ne changera pas la valeur ...

... et ainsi nous pouvons voir que cela *arrayéquivaut à array[0]. Vous pouvez en utiliser un là où vous souhaitez utiliser l'autre, et vice versa. Les opérateurs de tableau sont des opérateurs de pointeur.

malloc, reallocet les amis n'inventent pas le concept de pointeur que vous utilisez depuis le début; ils l' utilisent simplement pour implémenter une autre fonctionnalité, qui est une forme différente de durée de stockage, la plus appropriée lorsque vous souhaitez des changements de taille drastiques et dynamiques .

Il est dommage que la réponse actuellement acceptée va également à l'encontre de certains autres conseils très fondés sur StackOverflow , et en même temps, manque une occasion d'introduire une fonctionnalité peu connue qui brille exactement pour ce cas d'utilisation: le tableau flexible. membres! C'est en fait une réponse assez cassée ... :(

Lorsque vous définissez votre struct, déclarez votre tableau à la fin de la structure, sans aucune limite supérieure. Par exemple:

struct int_list {
    size_t size;
    int value[];
};

Cela vous permettra d'unir votre tableau intdans la même allocation que la vôtre count, et les relier comme ça peut être très pratique !

sizeof (struct int_list)agira comme s'il valueavait une taille de 0, donc il vous indiquera la taille de la structure avec une liste vide . Vous devez encore ajouter à la taille passée à reallocpour spécifier la taille de votre liste.

Un autre conseil pratique est de se souvenir que cela realloc(NULL, x)équivaut à malloc(x), et nous pouvons l'utiliser pour simplifier notre code. Par exemple:

int push_back(struct int_list **fubar, int value) {
    size_t x = *fubar ? fubar[0]->size : 0
         , y = x + 1;

    if ((x & y) == 0) {
        void *temp = realloc(*fubar, sizeof **fubar
                                   + (x + y) * sizeof fubar[0]->value[0]);
        if (!temp) { return 1; }
        *fubar = temp; // or, if you like, `fubar[0] = temp;`
    }

    fubar[0]->value[x] = value;
    fubar[0]->size = y;
    return 0;
}

struct int_list *array = NULL;

La raison pour laquelle j'ai choisi d'utiliser struct int_list **comme premier argument peut ne pas sembler immédiatement évidente, mais si vous pensez au deuxième argument, toute modification apportée valuede l'intérieur push_backne serait pas visible pour la fonction à partir de laquelle nous appelons, n'est-ce pas? Il en va de même pour le premier argument, et nous devons être en mesure de modifier notre array, non seulement ici mais peut-être aussi dans toute autre fonction à laquelle nous le passons ...

arraycommence par ne pointer du doigt rien; c'est une liste vide. L'initialiser équivaut à l'ajouter. Par exemple:

struct int_list *array = NULL;
if (!push_back(&array, 42)) {
    // success!
}

PS N'oubliez pasfree(array); quand vous en avez terminé!

autistique
la source
" array[x]est vraiment un raccourci pour *(array + x), [...]" En êtes-vous sûr ???? Voir une exposition de leurs différents comportements: eli.thegreenplace.net/2009/10/21/… .
C-Star-W-Star
1
Hélas, @ C-Star-Puppy, la seule référence que votre ressource semble ne pas mentionner du tout est la norme C. C'est la spécification par laquelle vos compilateurs doivent adhérer pour s'appeler légalement compilateurs C. Votre ressource ne semble pas du tout contredire mes informations. Néanmoins, la norme a effectivement quelques exemples tels que ce petit bijou où il est révélé que array[index]est en fait ptr[index]déguisé ... « La définition de l'opérateur d'indexation []est que E1[E2]est identique à (*((E1)+(E2)))» Vous ne pouvez pas réfuter l'std
autiste
Essayez cette démonstration, @ C-Star-Puppy: int main(void) { unsigned char lower[] = "abcdefghijklmnopqrstuvwxyz"; for (size_t x = 0; x < sizeof lower - 1; x++) { putchar(x[lower]); } }... Vous aurez probablement besoin de #include <stdio.h>et <stddef.h>... Voyez-vous comment j'ai écrit x[lower](avec xle type entier) plutôt que lower[x]? Le compilateur C ne se soucie pas, car il a *(lower + x)la même valeur que *(x + lower), et lower[x]est le premier où-comme x[lower]est le second. Toutes ces expressions sont équivalentes. Essayez-les ... voyez par vous-même, si vous ne pouvez pas me croire ...
autiste
... et puis bien sûr il y a cette partie, sur laquelle j'ai mis mon propre accent, mais vous devriez vraiment lire la citation entière sans accentuer: "Sauf quand c'est l'opérande de l'opérateur sizeof, l'opérateur _Alignof, ou le opérateur & unaire, ou est une chaîne littérale utilisée pour initialiser un tableau, une expression qui a le type '' tableau de type '' est convertie en une expression avec le type '' pointeur sur le type '' qui pointe vers l'élément initial du tableau et n’est pas une valeur l . Si l’objet tableau a une classe de stockage de registre, le comportement n’est pas défini. " La même chose est vraie pour les fonctions, btw.
autiste
Ohh et sur une note finale, @ C-Star-Puppy, Microsoft C ++ n'est pas un compilateur C et ne l'a pas été depuis près de 20 ans. Vous pouvez activer le mode C89, suuuure , mais nous avons évolué au-delà de la fin des années 1980 dans l'informatique. Pour en savoir plus sur ce sujet, je suggère de lire cet article ... puis de passer à un véritable compilateur C tel que gccou clangpour l'ensemble de votre compilation C, car vous constaterez qu'il y a tellement de packages qui ont adopté les fonctionnalités C99 ...
autiste
3

S'appuyant sur la conception de Matteo Furlans , quand il a dit que "la plupart des implémentations de tableaux dynamiques fonctionnent en commençant par un tableau d'une (petite) taille par défaut, puis chaque fois que vous manquez d'espace lors de l'ajout d'un nouvel élément, doublez la taille du tableau ". La différence dans le " travail en cours " ci-dessous est qu'il ne double pas de taille, il vise à n'utiliser que ce qui est nécessaire. J'ai également omis les contrôles de sécurité pour plus de simplicité ... En s'appuyant également sur l' idée de brimboriums , j'ai essayé d'ajouter une fonction de suppression au code ...

Le fichier storage.h ressemble à ceci ...

#ifndef STORAGE_H
#define STORAGE_H

#ifdef __cplusplus
extern "C" {
#endif

    typedef struct 
    {
        int *array;
        size_t size;
    } Array;

    void Array_Init(Array *array);
    void Array_Add(Array *array, int item);
    void Array_Delete(Array *array, int index);
    void Array_Free(Array *array);

#ifdef __cplusplus
}
#endif

#endif /* STORAGE_H */

Le fichier storage.c ressemble à ceci ...

#include <stdio.h>
#include <stdlib.h>
#include "storage.h"

/* Initialise an empty array */
void Array_Init(Array *array) 
{
    int *int_pointer;

    int_pointer = (int *)malloc(sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to allocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer; 
        array->size = 0;
    }
}

/* Dynamically add to end of an array */
void Array_Add(Array *array, int item) 
{
    int *int_pointer;

    array->size += 1;

    int_pointer = (int *)realloc(array->array, array->size * sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to reallocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer;
        array->array[array->size-1] = item;
    }
}

/* Delete from a dynamic array */
void Array_Delete(Array *array, int index) 
{
    int i;
    Array temp;
    int *int_pointer;

    Array_Init(&temp);

    for(i=index; i<array->size; i++)
    {
        array->array[i] = array->array[i + 1];
    }

    array->size -= 1;

    for (i = 0; i < array->size; i++)
    {
        Array_Add(&temp, array->array[i]);
    }

    int_pointer = (int *)realloc(temp.array, temp.size * sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to reallocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer; 
    } 
}

/* Free an array */
void Array_Free(Array *array) 
{
  free(array->array);
  array->array = NULL;
  array->size = 0;  
}

Le main.c ressemble à ceci ...

#include <stdio.h>
#include <stdlib.h>
#include "storage.h"

int main(int argc, char** argv) 
{
    Array pointers;
    int i;

    Array_Init(&pointers);

    for (i = 0; i < 60; i++)
    {
        Array_Add(&pointers, i);        
    }

    Array_Delete(&pointers, 3);

    Array_Delete(&pointers, 6);

    Array_Delete(&pointers, 30);

    for (i = 0; i < pointers.size; i++)
    {        
        printf("Value: %d Size:%d \n", pointers.array[i], pointers.size);
    }

    Array_Free(&pointers);

    return (EXIT_SUCCESS);
}

Attendez-vous à la critique constructive à suivre ...


la source
1
Si c'est une critique constructive que vous recherchez, il vaut mieux poster sur Code Review . Cela dit, quelques suggestions: il est impératif que le code vérifie le succès des appels à malloc()avant d'essayer d'utiliser l'allocation. Dans le même ordre d'idées, c'est une erreur d'attribuer directement le résultat de realloc()au pointeur à la mémoire d'origine réallouée; en cas d' realloc()échec, NULLest retourné et le code est laissé avec une fuite de mémoire. Il est beaucoup plus efficace de doubler la mémoire lors du redimensionnement que d'ajouter 1 espace à la fois: moins d'appels à realloc().
ex nihilo
1
Je savais que j'allais me faire déchirer, je plaisantais juste quand j'ai dit "critique constructive" ... Merci pour le conseil ...
2
Ne pas essayer de déchirer qui que ce soit, juste offrir des critiques constructives, qui ont peut-être été à venir même sans votre plus léger;)
ex nihilo
1
David, j'ai réfléchi à votre commentaire "Il est beaucoup plus efficace de doubler la mémoire lors du redimensionnement que d'ajouter 1 espace à la fois: moins d'appels à realloc ()". Pourriez-vous m'étendre là-dessus s'il vous plaît, pourquoi est-il préférable d'allouer le double de la quantité de mémoire et éventuellement de ne pas l'utiliser, donc de gaspiller de la mémoire, plutôt que d'attribuer uniquement la quantité requise pour la tâche? Je comprends ce que vous dites sur les appels à realloc (), mais pourquoi appeler realloc () à chaque fois est-il un problème? N'est-ce pas là pour ça, pour réallouer de la mémoire?
1
Bien que le doublement strict ne soit pas optimal, c'est certainement mieux que d'augmenter la mémoire un octet (ou un int, etc.) à la fois. Le doublement est une solution typique, mais je ne pense pas qu'il existe une solution optimale qui convienne à toutes les circonstances. Voici pourquoi le doublement est une bonne idée (un autre facteur tel que 1,5 conviendrait également): si vous commencez par une allocation raisonnable, vous n'aurez peut-être pas besoin de réallouer du tout. Lorsque plus de mémoire est nécessaire, l'allocation raisonnable est doublée, et ainsi de suite. De cette façon, vous n'avez probablement besoin que d'un ou deux appels realloc().
ex nihilo
2

Quand tu dis

créer un tableau contenant un numéro d'index (int) d'un nombre indéterminé d'entités

vous dites essentiellement que vous utilisez des "pointeurs", mais un pointeur local à l'échelle du tableau au lieu d'un pointeur à l'échelle de la mémoire. Puisque vous utilisez déjà conceptuellement des "pointeurs" (c'est-à-dire des numéros d'identification qui font référence à un élément dans un tableau), pourquoi n'utilisez-vous pas simplement des pointeurs réguliers (c'est-à-dire des numéros d'identification qui font référence à un élément du plus grand tableau: toute la mémoire ).

Au lieu que vos objets stockent un numéro d'identification de ressource, vous pouvez leur faire stocker un pointeur à la place. Fondamentalement la même chose, mais beaucoup plus efficace puisque nous évitons de transformer "tableau + index" en "pointeur".

Les pointeurs ne sont pas effrayants si vous les considérez comme un index de tableau pour toute la mémoire (ce qu'ils sont en réalité)

Mensonge Ryan
la source
2

Pour créer un tableau d’éléments illimités de tout type:

typedef struct STRUCT_SS_VECTOR {
    size_t size;
    void** items;
} ss_vector;


ss_vector* ss_init_vector(size_t item_size) {
    ss_vector* vector;
    vector = malloc(sizeof(ss_vector));
    vector->size = 0;
    vector->items = calloc(0, item_size);

    return vector;
}

void ss_vector_append(ss_vector* vec, void* item) {
    vec->size++;
    vec->items = realloc(vec->items, vec->size * sizeof(item));
    vec->items[vec->size - 1] = item;
};

void ss_vector_free(ss_vector* vec) {
    for (int i = 0; i < vec->size; i++)
        free(vec->items[i]);

    free(vec->items);
    free(vec);
}

et comment l'utiliser:

// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT {
    int id;
} apple;

apple* init_apple(int id) {
    apple* a;
    a = malloc(sizeof(apple));
    a-> id = id;
    return a;
};


int main(int argc, char* argv[]) {
    ss_vector* vector = ss_init_vector(sizeof(apple));

    // inserting some items
    for (int i = 0; i < 10; i++)
        ss_vector_append(vector, init_apple(i));


    // dont forget to free it
    ss_vector_free(vector);

    return 0;
}

Ce vecteur / tableau peut contenir n'importe quel type d'élément et sa taille est complètement dynamique.

Sebastian Karlsson
la source
0

Eh bien, je suppose que si vous devez supprimer un élément, vous ferez une copie du tableau en méprisant l'élément à exclure.

// inserting some items
void* element_2_remove = getElement2BRemove();

for (int i = 0; i < vector->size; i++){
       if(vector[i]!=element_2_remove) copy2TempVector(vector[i]);
       }

free(vector->items);
free(vector);
fillFromTempVector(vector);
//

Supposons que getElement2BRemove(), copy2TempVector( void* ...)et fillFromTempVector(...)sont des méthodes auxiliaires pour gérer le vecteur temporaire.

JOSMAR BARBOSA - M4NOV3Y
la source
On ne sait pas si c'est réellement une réponse à la question posée ou s'il s'agit d'un commentaire.
C'est une opinion pour "comment faire" et je demande confirmation (est-ce que je me trompe?) SI quelqu'un a une meilleure idée. ;)
JOSMAR BARBOSA - M4NOV3Y
Je suppose que je ne comprends pas votre dernière phrase. Puisque SO n'est pas un forum fileté, les questions ouvertes comme celle-ci dans les réponses semblent étranges.
1
J'ai arrangé votre dernière phrase sur ce que je pense que vous voulez dire.