C réseau dynamique croissante

https://stackoverflow.com/questions/3536153

30-09-2019
|

Question

J'ai un programme qui lit une liste « brute » des entités dans le jeu, et je me propose de faire un tableau contenant un numéro d'index (int) d'un nombre indéterminé d'entités, pour le traitement de diverses choses. Je voudrais éviter d'utiliser trop de mémoire ou CPU pour garder ces indices ...

Une solution rapide et sale que je l'utilise à ce jour est de déclarer, dans la fonction principale de traitement (mise au point locale), le tableau avec une taille des entités de jeu maximum et un autre entier de garder une trace de combien ont été ajoutés à la liste. Ce n'est pas satisfaisante, car chaque liste contient des tableaux 3000+, ce qui est pas beaucoup, mais se sent comme une perte, puisque je vais utiliser la solution possible pour 6-7 listes pour faire varier les fonctions.

Je n'ai pas trouvé de C (non C ++ ou C #) des solutions spécifiques pour y parvenir. Je peux utiliser des pointeurs, mais je suis un peu peur de les utiliser (sauf si elle est la seule façon possible).

Les tableaux ne quittent pas le champ d'application de la fonction locale (ils doivent être transmis à une fonction, puis jetés), dans le cas qui change les choses.

Si les pointeurs sont la seule solution, comment puis-je garder une trace d'eux pour éviter les fuites?

La solution

Je peux utiliser des pointeurs, mais je suis un peu peur de les utiliser.

Si vous avez besoin d'un tableau dynamique, vous ne pouvez pas échapper à des pointeurs. Pourquoi avez-vous peur bien? Ils ne mordent pas (aussi longtemps que vous êtes prudent, qui est). Il n'y a pas intégré dans le tableau dynamique C, vous aurez juste à écrire vous-même. En C ++, vous pouvez utiliser le haut- std::vector classe. C # et à peu près toutes les autres langues de niveau élevé ont également une classe similaire qui gère pour vous des tableaux dynamiques.

Si vous avez l'intention d'écrire votre propre, quelque chose est là pour vous aider à démarrer: un tableau plus dynamique travail de mise en oeuvre en commençant avec un tableau de quelques-uns (petite) taille par défaut, chaque fois que vous manquez d'espace lors de l'ajout d'un nouvel élément , le double de la taille du tableau. Comme vous pouvez le voir dans l'exemple ci-dessous, il est pas très difficile du tout: (je l'ai omis des contrôles de sécurité par souci de brièveté)

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

void initArray(Array *a, size_t initialSize) {
  a->array = (int *)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 = (int *)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);

Autres conseils

Il y a quelques options que je peux penser.

Liste de liens. Vous pouvez utiliser une liste chaînée pour faire un tableau de plus en plus dynamique comme la chose. Mais vous ne serez pas en mesure de le faire array[100] sans avoir à marcher à travers 1-99 premier. Et il pourrait ne pas être pratique pour que vous puissiez utiliser soit.
réseau d'antennes. Il suffit de créer un tableau avec plus de suffisamment d'espace pour tout
array Redimensionnement. Recréer le tableau une fois que vous connaissez la taille et / ou de créer un nouveau tableau chaque fois que vous manquez d'espace avec une certaine marge et copier toutes les données du nouveau tableau.
Liste lié combinaison Array. Il suffit d'utiliser un tableau avec une taille fixe et une fois que vous manquez d'espace, créer un nouveau tableau et un lien vers ce (il serait sage de garder une trace du tableau et le lien vers le prochain tableau dans une struct).

Il est difficile de dire quelle option serait le mieux dans votre situation. Il suffit de créer un grand tableau est ofcourse l'une des solutions les plus faciles et ne doit pas vous donner beaucoup de problèmes à moins qu'il est vraiment grand.

Comme avec tout ce qui semble plus effrayant au premier abord que ce fut plus tard, la meilleure façon d'obtenir sur la peur initiale est de vous immerger dans l'inconfort de l'inconnu ! Il est parfois comme ce que nous apprend le plus, après tout.

Malheureusement, il y a des limites. Pendant que vous êtes encore à apprendre à utiliser une fonction, vous ne devriez pas assumer le rôle d'un enseignant, par exemple. J'ai souvent lu les réponses de ceux qui apparemment ne savent pas comment utiliser realloc (ie actuellement la réponse acceptée! ) dire aux autres comment l'utiliser de manière incorrecte, parfois sous le prétexte qu'ils ont gestion des erreurs omis , même si cela est un écueil commun qui a besoin d'une mention. est ici une réponse expliquant comment utiliser correctement realloc . Notez que la réponse stocke la valeur de retour dans une différent variable afin d'effectuer une vérification d'erreur.

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

opérateurs de tableaux sont des opérateurs de pointeur. array[x] est vraiment un raccourci pour *(array + x), qui peut être décomposé en: * et (array + x). Il est fort probable que le * est ce que vous embrouille. Nous pouvons encore éliminer l'ajout du problème en supposant x être 0, donc, array[0] devient *array parce que l'ajout 0 ne changera pas la valeur ...

... et nous pouvons donc voir que *array équivaut à array[0]. Vous pouvez utiliser un où vous voulez utiliser l'autre, et vice versa. les opérateurs de tableaux sont des opérateurs de pointeur.

malloc, realloc et les amis ne sont pas inventent le concept d'un pointeur que vous avez utilisé tout le long; ils simplement utiliser ce pour mettre en œuvre une autre caractéristique, qui est une forme différente de la durée de stockage, le plus approprié lorsque vous désirez drastiques, les changements dynamiques de taille .

Il est dommage que la réponse actuellement acceptée aussi va à l'encontre du grain de d'autres conseils très bien fondée sur StackOverflow , et en même temps, manque l'occasion d'introduire une fonctionnalité peu connue qui brille exactement ce usecase: les membres du groupe flexibles C'est en fait un assez 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 tableau de int dans la même allocation que votre count, et cela peut être les avoir lié comme très pratique

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

Une autre astuce 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 ** comme premier argument peut ne pas sembler immédiatement évident, mais si vous pensez le deuxième argument, toute modification apportée à value à l'intérieur push_back ne serait pas visible à la fonction que nous appelons de, droite? La même chose vaut pour le premier argument, et nous devons être en mesure de modifier notre array, pas seulement ici mais peut-être aussi dans toute autre fonction / s on passe à ...

array commence en montrant rien; il est une liste vide. Initialisation il est le même que celui en y ajoutant. Par exemple:

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

P.S. N'oubliez pas de free(array); lorsque vous avez terminé avec!

Quand vous dites

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

vous êtes essentiellement vous dire vous utilisez des « pointeurs », mais qui est un pointeur de tableau à l'échelle locale au lieu de pointeur de mémoire à l'échelle. Puisque vous êtes sur le plan conceptuel déjà en utilisant des « pointeurs » (numéros d'identification qui fait référence à un élément dans un tableau), pourquoi ne pas vous utilisez juste des pointeurs réguliers (numéros d'identification qui fait référence à un élément dans le plus grand tableau: toute la mémoire ).

Au lieu de vos objets stockant un des numéros d'identification des ressources, vous pouvez les faire stocker un pointeur à la place. En gros la même chose, mais beaucoup plus efficace car nous évitons de tourner « tableau + index » dans un « pointeur ».

Pointeurs ne sont pas peur si vous pensez d'eux comme indice de tableau pour toute la mémoire (qui est ce qu'ils sont en réalité)

Miser sur Matteo Furlans conception, quand il a dit « la plupart des implémentations de tableau de dynamique fonctionnent en commençant avec un tableau de quelques-uns (petite) taille par défaut, chaque fois que vous manquez d'espace quand l'ajout d'un nouvel élément, le double de la taille du tableau ». La différence dans le « les travaux en cours » ci-dessous est qu'il ne sert pas de taille, il vise à utiliser uniquement ce qui est nécessaire. J'ai également omis des contrôles de sécurité pour la simplicité ... Aussi sur la construction brimboriums idée, je l'ai essayé d'ajouter une fonction de suppression du 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;  
}

Les looks main.c comme ça ...

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

Réjouissez critiques constructives à suivre ...

Pour créer un tableau d'éléments illimités de toute sorte de 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 tout type d'élément et il est tout à fait dynamique taille.

Eh bien, je suppose que si vous avez besoin d'enlever un élément vous faire une copie du tableau dédaignant 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(...) procédés auxiliaires pour traiter le vecteur temp.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow