C tableau à croissance dynamique

Question

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

Une solution rapide et sale que j'utilise jusqu'à présent est de déclarer, dans la fonction de traitement principale (focus local) le tableau avec une taille du maximum d'entités de jeu, et un autre entier pour garder la 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 beaucoup, mais ressemble à un gaspillage, puisque je vais peut-être utiliser cette solution pour 6-7 listes pour des fonctions différentes.

Je n'ai pas trouvé de solution spécifique au C (pas au C++ ou au C#) pour y parvenir. Je peux utiliser des pointeurs, mais j'ai un peu peur de les utiliser (sauf si c'est la seule solution possible).

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

Si les pointeurs sont la seule solution, comment puis-je en assurer le suivi pour éviter les fuites ?

Answer 1

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. Mais pourquoi avoir peur ? Ils ne mordent pas (tant que vous êtes prudent, bien sûr). Il n'y a pas de tableau dynamique intégré en C, vous devrez en écrire un vous-même. En C++, vous pouvez utiliser le tableau dynamique intégré std::vector classe. Le 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 envisagez 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 certaine (petite) taille par défaut, puis chaque fois que vous manquez d'espace en ajoutant un nouvel élément, vous doublez la taille du tableau. Comme vous pouvez le voir dans l'exemple ci-dessous, ce n'est pas du tout difficile : (j'ai omis les contrôles de sécurité pour des raisons de brièveté)

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

Answer 2

Une solution simple consiste à mmap . C'est très bien si vous pouvez tolérer une solution POSIX. Il suffit de mapper une page entière et de se prémunir contre les débordements, puisque realloc échouerait de toute façon pour de telles valeurs. Les systèmes d'exploitation modernes ne s'engagent pas sur l'ensemble du lot tant que vous ne l'utilisez pas, et vous pouvez tronquer les fichiers si vous le souhaitez.

Sinon, il y a realloc . Comme pour tout ce qui semble plus effrayant au début que par la suite, la meilleure façon de surmonter la peur initiale est de s'immerger dans l'inconfort de l'inconnu ! C'est dans ces moments-là qu'on apprend le plus, après tout.

Malheureusement, il y a des limites. Pendant que vous apprenez à utiliser une fonction, vous ne devez pas assumer le rôle de professeur, par exemple. Je lis souvent les réponses de ceux qui ne savent apparemment pas comment utiliser les fonctions realloc (c'est-à-dire la réponse actuellement acceptée ! ) qui expliquent aux autres comment l'utiliser de manière incorrecte, parfois sous prétexte qu'ils ont traitement des erreurs omis même s'il s'agit d'un piège courant qu'il convient de mentionner. Voici une réponse expliquant comment utiliser realloc correctement . Notez que la réponse consiste à stocker la valeur de retour dans un fichier de type différents 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 font 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, les 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 : * y (array + x) . Il est fort probable que le * est ce qui vous perturbe. Nous pouvons encore éliminer l'addition du problème en supposant que x à être 0 donc, array[0] devient *array parce qu'en ajoutant 0 ne changera pas la valeur...

... et ainsi nous pouvons voir que *array est équivalent à array[0] . Vous pouvez utiliser l'un d'eux là où vous voulez utiliser l'autre, et vice versa. Les opérateurs de tableau sont des opérateurs de pointeur.

malloc , realloc et les amis ne le font pas inventer le concept de pointeur que vous utilisez depuis le début ; ils se contentent de utiliser ceci pour mettre en œuvre une autre fonctionnalité, qui est une forme différente de durée de stockage, plus adaptée lorsque vous souhaitez des changements radicaux et dynamiques de taille .

C'est une honte que la réponse actuellement acceptée également va à l'encontre des principes de d'autres conseils très bien fondés sur StackOverflow Mais en même temps, il rate l'occasion d'introduire une fonctionnalité peu connue qui se prête parfaitement à ce cas d'utilisation : les membres de tableau flexibles ! C'est en fait une plutôt cassé réponse... :(

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 réseau de int dans la même allocation que votre count et les faire relier comme ça peut être très pratique !

sizeof (struct int_list) agira comme si value a une taille de 0, donc il vous dira la taille de la structure avec une liste vide . Vous devez encore ajouter à la taille transmise à realloc pour spécifier la taille de votre liste.

Un autre conseil pratique est de se rappeler que realloc(NULL, x) est équivalent à 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 ** en tant que premier argument peut ne pas sembler immédiatement évident, mais si vous pensez au second argument, toute modification apportée à l'option value de l'intérieur push_back ne serait pas visible pour la fonction que 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 code d'accès. array pas seulement aquí mais éventuellement aussi dans toute autre fonction à laquelle nous le passons ...

array ne pointe sur rien ; c'est une liste vide. Initialisation de c'est la même chose que de l'ajouter. Par exemple :

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

P.S. N'oubliez pas de free(array); quand vous en aurez fini avec elle !

Answer 3

Il y a quelques options auxquelles je pense.

1. Liste de liens. Vous pouvez utiliser une liste liée pour créer un tableau à croissance dynamique. Mais vous ne serez pas en mesure de faire array[100] sans avoir à passer par 1-99 d'abord. Et il se peut que ce ne soit pas très pratique à utiliser pour vous non plus.
2. Grand tableau. Il suffit de créer un tableau avec un espace plus que suffisant pour tout.
3. Redimensionnement du tableau. Recréez le tableau une fois que vous connaissez sa 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 listes chaînées et de tableaux. Il suffit d'utiliser un tableau de taille fixe et, dès que vous manquez d'espace, de créer un nouveau tableau et de le lier (il serait judicieux de garder la 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 création d'un grand tableau est bien sûr l'une des solutions les plus simples et ne devrait pas vous poser de problèmes, sauf s'il est très grand.

Answer 4

Construire sur Matteo Furlans le design, lorsqu'il a dit " la plupart des implémentations de tableaux dynamiques fonctionnent en commençant par un tableau d'une certaine (petite) taille par défaut, puis chaque fois que vous manquez d'espace lors de l'ajout d'un nouvel élément, vous doublez la taille du tableau. ". La différence dans les " travaux 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 des raisons de simplicité... Je m'appuie aussi sur brimboriums idée, 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 fichier 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);
}

Nous attendons avec impatience le critique constructive à suivre...

Answer 5

Glib a une bonne solution pour le C avec le comptage de référence pour aider à la gestion de la mémoire, et est gratuit et multiplateforme. Si vous voulez quelque chose de plus basique, vous devriez regarder du côté de realloc. La programmation en C est vraiment, vraiment difficile à faire sans pointeurs. Autant commencer à se familiariser avec eux dès maintenant.