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

Pour créer un tableau d'un nombre illimité d'éléments de n'importe quel 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/réseau peut contenir tout type d'élément et sa taille est totalement dynamique.

Answer 2

Quand tu dis

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

vous dites en fait que vous utilisez des "pointeurs", mais un pointeur local à l'échelle du tableau plutôt qu'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 d'un tableau), pourquoi ne pas simplement utiliser des pointeurs ordinaires (c'est-à-dire des numéros d'identification qui font référence à un élément du plus grand tableau : la mémoire entière).

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

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

Answer 3

Eh bien, je suppose que si vous avez besoin de 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* ...) y fillFromTempVector(...) sont des méthodes auxiliaires pour gérer le vecteur temp.

Answer 4

Ces messages sont apparemment dans le mauvais ordre ! Il s'agit du premier d'une série de trois articles. Désolé.

En essayant d'utiliser le code de Lie Ryan, j'ai eu des problèmes pour récupérer les informations stockées. Les éléments du vecteur ne sont pas stockés de manière contiguë, comme vous pouvez le constater en "trichant" un peu et en stockant le pointeur vers l'adresse de chaque élément (ce qui va bien sûr à l'encontre du concept de tableau dynamique) et en les examinant.

Avec un peu de bricolage, via :

ss_vector* vector; // pull this out to be a global vector

// Then add the following to attempt to recover stored values.

int return_id_value(int i,apple* aa) // given ptr to component,return data item
{   printf("showing apple[%i].id = %i and  other_id=%i\n",i,aa->id,aa->other_id);
    return(aa->id);
}

int Test(void)  // Used to be "main" in the example
{   apple* aa[10]; // stored array element addresses
    vector = ss_init_vector(sizeof(apple));
    // inserting some items
    for (int i = 0; i < 10; i++)
    {   aa[i]=init_apple(i);
        printf("apple id=%i and  other_id=%i\n",aa[i]->id,aa[i]->other_id);
        ss_vector_append(vector, aa[i]);
     }   
 // report the number of components
 printf("nmbr of components in vector = %i\n",(int)vector->size);
 printf(".*.*array access.*.component[5] = %i\n",return_id_value(5,aa[5]));
 printf("components of size %i\n",(int)sizeof(apple));
 printf("\n....pointer initial access...component[0] = %i\n",return_id_value(0,(apple *)&vector[0]));
 //.............etc..., followed by
 for (int i = 0; i < 10; i++)
 {   printf("apple[%i].id = %i at address %i, delta=%i\n",i,    return_id_value(i,aa[i]) ,(int)aa[i],(int)(aa[i]-aa[i+1]));
 }   
// don't forget to free it
ss_vector_free(vector);
return 0;
}

Il est possible d'accéder à chaque élément du tableau sans problème, tant que l'on connaît son adresse, donc je suppose que je vais essayer d'ajouter un élément "suivant" et utiliser ce tableau comme une liste liée. Il y a sûrement de meilleures options, cependant. Veuillez me conseiller.

Answer 5

Ces messages sont peut-être dans le mauvais ordre ! Il s'agit du numéro 2 d'une série de 3 articles. Désolé.

J'ai "pris quelques libertés" avec le code de Lie Ryan, en implémentant une liste liée pour que les éléments individuels de son vecteur soient accessibles via une liste liée. Cela permet l'accès, mais il faut admettre que l'accès aux éléments individuels prend du temps en raison de l'overhead de recherche, c'est à dire parcourir la liste jusqu'à ce que vous trouviez le bon élément. Je vais remédier à ce problème en maintenant un vecteur d'adresses contenant les indices 0 à n'importe quel indice associé à des adresses mémoire. Ce n'est toujours pas aussi efficace qu'un simple tableau, mais au moins vous n'avez pas à "parcourir la liste" à la recherche du bon élément.

    // Based on code from https://stackoverflow.com/questions/3536153/c-dynamically-growing-array
typedef struct STRUCT_SS_VECTOR
{   size_t size; // # of vector elements
    void** items; // makes up one vector element's component contents
    int subscript; // this element's subscript nmbr, 0 thru whatever
    struct STRUCT_SS_VECTOR* this_element; // linked list via this ptr
    struct STRUCT_SS_VECTOR* next_element; // and next ptr
} ss_vector;

ss_vector* vector; // ptr to vector of components

ss_vector* ss_init_vector(size_t item_size) // item_size is size of one array member
{   vector= malloc(sizeof(ss_vector)); 
    vector->this_element = vector; 
    vector->size = 0; // initialize count of vector component elements
    vector->items = calloc(1, item_size); // allocate & zero out memory for one linked list element
    vector->subscript=0;
    vector->next_element=NULL;
    //      If there's an array of element addresses/subscripts, install it now.
    return vector->this_element;
}

ss_vector* ss_vector_append(ss_vector* vec_element,                 int i) 
//                                                                          ^--ptr to this element  ^--element nmbr
{   ss_vector* local_vec_element=0;
    // If there is already a next element, recurse to end-of-linked-list
    if(vec_element->next_element!=(size_t)0) 
    {   local_vec_element= ss_vector_append(vec_element->next_element,i); // recurse to end of list
        return local_vec_element;
    }
    // vec_element is NULL, so make a new element and add at end of list
    local_vec_element= calloc(1,sizeof(ss_vector)); // memory for one component
    local_vec_element->this_element=local_vec_element; // save the address
    local_vec_element->next_element=0;
    vec_element->next_element=local_vec_element->this_element;
    local_vec_element->subscript=i; //vec_element->size; 
    local_vec_element->size=i; // increment # of vector components
    //      If there's an array of element addresses/subscripts, update it now.
    return local_vec_element;
}

void ss_vector_free_one_element(int i,gboolean Update_subscripts) 
{   // Walk the entire linked list to the specified element, patch up 
    //      the element ptrs before/next, then free its contents, then free it.
    //      Walk the rest of the list, updating subscripts, if requested.
    //      If there's an array of element addresses/subscripts, shift it along the way.
    ss_vector* vec_element;
    struct STRUCT_SS_VECTOR* this_one;
    struct STRUCT_SS_VECTOR* next_one;
    vec_element=vector;
    while((vec_element->this_element->subscript!=i)&&(vec_element->next_element!=(size_t) 0)) // skip
    {   this_one=vec_element->this_element; // trailing ptr
        next_one=vec_element->next_element; // will become current ptr
        vec_element=next_one;
    } 
    // now at either target element or end-of-list
    if(vec_element->this_element->subscript!=i)
    {   printf("vector element not found\n");return;}
    // free this one
    this_one->next_element=next_one->next_element;// previous element points to element after current one
    printf("freeing element[%i] at %lu",next_one->subscript,(size_t)next_one);
    printf(" between %lu and %lu\n",(size_t)this_one,(size_t)next_one->next_element);
    vec_element=next_one->next_element; 
    free(next_one); // free the current element
    // renumber if requested
    if(Update_subscripts)
    {   i=0;
        vec_element=vector;
        while(vec_element!=(size_t) 0)
        {   vec_element->subscript=i;
            i++;
            vec_element=vec_element->next_element; 
        }
    }
    //      If there's an array of element addresses/subscripts, update it now.
/*  // Check: temporarily show the new list
    vec_element=vector;
    while(vec_element!=(size_t) 0)
    {   printf("   remaining element[%i] at %lu\n",vec_element->subscript,(size_t)vec_element->this_element);
        vec_element=vec_element->next_element;
    } */
    return;
} // void ss_vector_free_one_element()

void ss_vector_insert_one_element(ss_vector* vec_element,int place) 
{   // Walk the entire linked list to specified element "place", patch up 
    //      the element ptrs before/next, then calloc an element and store its contents at "place".
    //      Increment all the following subscripts.
    //      If there's an array of element addresses/subscripts, make a bigger one, 
    //      copy the old one, then shift appropriate members.
    // ***Not yet implemented***
} // void ss_vector_insert_one_element()

void ss_vector_free_all_elements(void) 
{   // Start at "vector".Walk the entire linked list, free each element's contents, 
    //      free that element, then move to the next one.
    //      If there's an array of element addresses/subscripts, free it.
    ss_vector* vec_element;
    struct STRUCT_SS_VECTOR* next_one;
    vec_element=vector;
    while(vec_element->next_element!=(size_t) 0)
    {   next_one=vec_element->next_element;
        // free(vec_element->items) // don't forget to free these
        free(vec_element->this_element);
        vec_element=next_one;
        next_one=vec_element->this_element;
    }
    // get rid of the last one.
    // free(vec_element->items)
    free(vec_element);
    vector=NULL;
    //      If there's an array of element addresses/subscripts, free it now.
printf("\nall vector elements & contents freed\n");
} // void ss_vector_free_all_elements()

// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT
{   int id; // one of the data in the component
    int other_id; // etc
    struct APPLE_STRUCT* next_element;
} apple; // description of component

apple* init_apple(int id) // make a single component
{   apple* a; // ptr to component
    a = malloc(sizeof(apple)); // memory for one component
    a->id = id; // populate with data
    a->other_id=id+10;
    a->next_element=NULL;
    // don't mess with aa->last_rec here
    return a; // return pointer to component
};

int return_id_value(int i,apple* aa) // given ptr to component, return single data item
{   printf("was inserted as apple[%i].id = %i     ",i,aa->id);
    return(aa->id);
}

ss_vector* return_address_given_subscript(ss_vector* vec_element,int i) 
// always make the first call to this subroutine with global vbl "vector"
{   ss_vector* local_vec_element=0;
    // If there is a next element, recurse toward end-of-linked-list
    if(vec_element->next_element!=(size_t)0)
    {   if((vec_element->this_element->subscript==i))
        {   return vec_element->this_element;}
        local_vec_element= return_address_given_subscript(vec_element->next_element,i); // recurse to end of list
        return local_vec_element;
    }
    else
    {   if((vec_element->this_element->subscript==i)) // last element
        {   return vec_element->this_element;}
        // otherwise, none match
        printf("reached end of list without match\n");
        return (size_t) 0;
    }
} // return_address_given_subscript()

int Test(void)  // was "main" in the original example
{   ss_vector* local_vector;
    local_vector=ss_init_vector(sizeof(apple)); // element "0"
    for (int i = 1; i < 10; i++) // inserting items "1" thru whatever
    {   local_vector=ss_vector_append(vector,i);}   
    // test search function
    printf("\n NEXT, test search for address given subscript\n");
    local_vector=return_address_given_subscript(vector,5);
    printf("finished return_address_given_subscript(5) with vector at %lu\n",(size_t)local_vector);
    local_vector=return_address_given_subscript(vector,0);
    printf("finished return_address_given_subscript(0) with vector at %lu\n",(size_t)local_vector);
    local_vector=return_address_given_subscript(vector,9);
    printf("finished return_address_given_subscript(9) with vector at %lu\n",(size_t)local_vector);
    // test single-element removal
    printf("\nNEXT, test single element removal\n");
    ss_vector_free_one_element(5,FALSE); // without renumbering subscripts
    ss_vector_free_one_element(3,TRUE);// WITH renumbering subscripts
    // ---end of program---
    // don't forget to free everything
    ss_vector_free_all_elements(); 
    return 0;
}