C que cresce dinamicamente

Eu tenho um programa que lê uma lista "bruta" de entidades no jogo e pretendo criar uma matriz contendo um número de índice (int) de um número indeterminado de entidades, para processar várias coisas. Gostaria de evitar o uso de muita memória ou CPU para manter esses índices ...

Uma solução rápida e suja que utilizo até agora é declarar, na principal função de processamento (foco local), o array com o tamanho máximo de entidades do jogo e outro número inteiro para acompanhar quantas foram adicionadas à lista. Isso não é satisfatório, pois todas as listas contêm mais de 3.000 matrizes, o que não é muito, mas parece um desperdício, pois é possível usar a solução para 6-7 listas para funções variadas.

Não encontrei nenhuma solução específica em C (não em C ++ ou C #) para conseguir isso. Posso usar ponteiros, mas tenho um pouco de medo de usá-los (a menos que seja a única maneira possível).

As matrizes não deixam o escopo da função local (elas devem ser passadas para uma função e depois descartadas), caso isso mude.

Se os ponteiros são a única solução, como posso acompanhá-los para evitar vazamentos?

Posso usar ponteiros, mas tenho um pouco de medo de usá-los.

Se você precisar de uma matriz dinâmica, não poderá escapar dos ponteiros. Por que você está com medo? Eles não vão morder (contanto que você seja cuidadoso). Não há matriz dinâmica embutida em C, você apenas precisará escrever uma. No C ++, você pode usar a std::vectorclasse interna. C # e quase todas as outras linguagens de alto nível também têm uma classe semelhante que gerencia matrizes dinâmicas para você.

Se você planeja escrever o seu próprio, aqui está algo para começar: as implementações mais dinâmicas da matriz funcionam começando com uma matriz de algum tamanho padrão (pequeno) e, sempre que você ficar sem espaço ao adicionar um novo elemento, duplique o tamanho da matriz. Como você pode ver no exemplo abaixo, não é muito difícil: (omiti as verificações de segurança por questões de brevidade)

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

Usá-lo é tão simples:

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

Existem algumas opções em que posso pensar.

1. Lista vinculada. Você pode usar uma lista vinculada para criar uma matriz que cresce dinamicamente. Mas você não poderá fazer isso array[100]sem ter que percorrer 1-99primeiro. E pode não ser tão útil para você usar também.
2. Grande variedade. Basta criar uma matriz com espaço mais que suficiente para tudo
3. Redimensionando matriz. Recrie a matriz assim que souber o tamanho e / ou crie uma nova matriz toda vez que ficar sem espaço com alguma margem e copie todos os dados para a nova matriz.
4. Combinação de matriz de lista vinculada. Simplesmente use uma matriz com um tamanho fixo e, quando ficar sem espaço, crie uma nova matriz e vincule-a (seria aconselhável acompanhar a matriz e o link para a próxima matriz em uma estrutura).

É difícil dizer qual opção seria melhor na sua situação. Simplesmente criar uma grande variedade é, naturalmente, uma das soluções mais fáceis e não deve gerar muitos problemas, a menos que seja realmente grande.

Como tudo o que parece mais assustador a princípio do que era depois, a melhor maneira de superar o medo inicial é mergulhar no desconforto do desconhecido ! Afinal, é em momentos como o que mais aprendemos.

Infelizmente, existem limitações. Enquanto você ainda está aprendendo a usar uma função, não deve assumir o papel de professor, por exemplo. Frequentemente leio respostas de quem aparentemente não sabe usar realloc(ou seja, a resposta atualmente aceita! ) Dizendo aos outros como usá-la incorretamente, ocasionalmente sob o pretexto de que eles omitiram o tratamento de erros , mesmo que essa seja uma armadilha comum que precisa ser mencionado. Aqui está uma resposta explicando como usar realloccorretamente . Observe que a resposta está armazenando o valor de retorno em uma variável diferente para executar a verificação de erros.

Toda vez que você chama uma função e toda vez que usa uma matriz, você está usando um ponteiro. As conversões estão ocorrendo implicitamente, o que, se algo deve ser ainda mais assustador, pois são as coisas que não vemos que geralmente causam mais problemas. Por exemplo, vazamentos de memória ...

Operadores de matriz são operadores de ponteiro. array[x]é realmente um atalho para *(array + x), que pode ser dividido em: *e (array + x). É mais provável que isso *seja o que o confunde. Podemos eliminar ainda mais a adição do problema assumindo xque 0, assim, array[0]se torna *arrayporque a adição 0não altera o valor ...

... e assim podemos ver que *arrayé equivalente a array[0]. Você pode usar um onde deseja usar o outro e vice-versa. Operadores de matriz são operadores de ponteiro.

malloc, realloce amigos não inventam o conceito de ponteiro que você usa o tempo todo; eles simplesmente usam isso para implementar algum outro recurso, que é uma forma diferente de duração do armazenamento, mais adequada quando você deseja mudanças drásticas e dinâmicas no tamanho .

É uma pena que a resposta atualmente aceita também seja contrária a alguns outros conselhos bem fundamentados sobre o StackOverflow e, ao mesmo tempo, perca a oportunidade de introduzir um recurso pouco conhecido que brilha exatamente nesse caso de uso: matriz flexível membros! Essa é realmente uma resposta bastante quebrada ... :(

Ao definir seu struct, declare sua matriz no final da estrutura, sem nenhum limite superior. Por exemplo:

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

Isso permitirá que você unir seu array intna mesma alocação que o seu count, e tê-los vinculados dessa maneira pode ser muito útil !

sizeof (struct int_list)agirá como se valuetivesse um tamanho 0, por isso informa o tamanho da estrutura com uma lista vazia . Você ainda precisa adicionar ao tamanho passado reallocpara especificar o tamanho da sua lista.

Outra dica útil é lembrar que isso realloc(NULL, x)é equivalente a malloc(x), e podemos usá-lo para simplificar nosso código. Por exemplo:

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;

A razão pela qual escolhi usar struct int_list **como o primeiro argumento pode não parecer imediatamente óbvio, mas se você pensar no segundo argumento, quaisquer alterações feitas no valueinterior push_backnão seriam visíveis para a função da qual estamos chamando, certo? O mesmo vale para o primeiro argumento, e precisamos ser capazes de modificar o nosso array, não apenas aqui, mas possivelmente também em qualquer outra função / s que passamos para ...

arraycomeça apontando para o nada; é uma lista vazia. Inicializar é o mesmo que adicionar a ele. Por exemplo:

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

PS Lembre-se defree(array); quando terminar!

Com base no design de Matteo Furlans , quando ele disse que " as implementações mais dinâmicas da matriz funcionam começando com uma matriz com algum tamanho (pequeno) padrão, sempre que você ficar sem espaço ao adicionar um novo elemento, dobre o tamanho da matriz ". A diferença no " trabalho em andamento " abaixo é que ele não dobra de tamanho, visa usar apenas o necessário. Também omiti as verificações de segurança por simplicidade ... Também com base na idéia de brimboriums , tentei adicionar uma função de exclusão ao código ...

O arquivo storage.h se parece com isso ...

#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 */

O arquivo storage.c fica assim ...

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

O main.c fica assim ...

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

Ansiosos pelas críticas construtivas a seguir ...

Quando você está dizendo

criar uma matriz contendo um número de índice (int) de um número indeterminado de entidades

você está basicamente dizendo que está usando "ponteiros", mas um que é um ponteiro local para toda a matriz em vez de ponteiro para toda a memória. Como você já está conceitualmente usando "ponteiros" (ou seja, números de identificação que se referem a um elemento em uma matriz), por que você não usa ponteiros regulares (ou seja, números de identificação que se referem a um elemento na maior matriz: toda a memória )

Em vez de seus objetos armazenarem números de identificação de recurso, você pode fazê-los armazenar um ponteiro. Basicamente a mesma coisa, mas muito mais eficiente, pois evitamos transformar "array + index" em um "ponteiro".

Os ponteiros não são assustadores se você os considera como índice de matriz para toda a memória (que é o que realmente são)

Para criar uma matriz de itens ilimitados de qualquer tipo:

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

e como usá-lo:

// 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;
}

Esse vetor / matriz pode conter qualquer tipo de item e é totalmente dinâmico em tamanho.

Bem, acho que se você precisar remover um elemento, fará uma cópia da matriz desprezando o elemento a ser excluído.

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

Assume-se que getElement2BRemove(), copy2TempVector( void* ...)e fillFromTempVector(...)são métodos auxiliares para lidar com o vector de temperatura.