C tableau à croissance dynamique

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?

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

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.

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é!

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 ...

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

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.

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.