C dynamicznie rosnąca tablica

Mam program, który czyta „surową” listę jednostek w grze i zamierzam stworzyć tablicę zawierającą numer indeksu (int) nieokreślonej liczby jednostek, do przetwarzania różnych rzeczy. Chciałbym uniknąć używania zbyt dużej ilości pamięci lub procesora do przechowywania takich indeksów ...

Szybkim i brudnym rozwiązaniem, którego dotychczas używam, jest zadeklarowanie w głównej funkcji przetwarzania (lokalny fokus) tablicy z rozmiarem maksymalnych jednostek gry i kolejną liczbą całkowitą, aby śledzić, ile zostało dodanych do listy. To nie jest satysfakcjonujące, ponieważ każda lista zawiera ponad 3000 tablic, co nie jest tak dużo, ale wydaje się marnotrawstwem, ponieważ będę mógł użyć rozwiązania dla 6-7 list dla różnych funkcji.

Nie znalazłem żadnych rozwiązań specyficznych dla C (nie C ++ lub C #), aby to osiągnąć. Potrafię używać wskaźników, ale trochę boję się ich używać (chyba że jest to jedyny możliwy sposób).

Tablice nie opuszczają zakresu funkcji lokalnej (mają być przekazane do funkcji, a następnie odrzucone), na wypadek, gdyby coś zmieniło.

Jeśli wskaźniki są jedynym rozwiązaniem, jak mogę je śledzić, aby uniknąć wycieków?

Potrafię używać wskaźników, ale trochę boję się ich używać.

Jeśli potrzebujesz tablicy dynamicznej, nie możesz zmienić znaczenia wskaźników. Dlaczego się boisz? Nie gryzą (o ile jesteś ostrożny). W C nie ma wbudowanej tablicy dynamicznej, po prostu musisz ją napisać samodzielnie. W C ++ możesz użyć wbudowanej std::vectorklasy. C # i prawie każdy inny język wysokiego poziomu również ma podobną klasę, która zarządza tablicami dynamicznymi.

Jeśli planujesz napisać własną, oto od czego zacząć: większość implementacji tablic dynamicznych działa od początku od tablicy o pewnym (małym) domyślnym rozmiarze, a gdy zabraknie miejsca podczas dodawania nowego elementu, podwajaj rozmiar tablicy. Jak widać na poniższym przykładzie, nie jest to wcale trudne: (pominąłem kontrole bezpieczeństwa pod kątem zwięzłości)

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

Korzystanie z niego jest równie proste:

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

Przychodzi mi do głowy kilka opcji.

1. Połączona lista. Możesz użyć połączonej listy, aby stworzyć dynamicznie rosnącą tablicę. Ale nie będziesz w stanie tego zrobić array[100]bez konieczności wcześniejszego przejścia 1-99. I może nie być dla ciebie tak przydatne.
2. Duża tablica. Po prostu utwórz tablicę z wystarczającą ilością miejsca na wszystko
3. Zmiana rozmiaru tablicy. Odtwórz tablicę, gdy znasz rozmiar i / lub utwórz nową tablicę za każdym razem, gdy zabraknie miejsca z pewnym marginesem i skopiuj wszystkie dane do nowej tablicy.
4. Połączenie tablicy połączonych list. Po prostu użyj tablicy o stałym rozmiarze, a gdy zabraknie miejsca, utwórz nową tablicę i połącz się z nią (dobrze byłoby śledzić tablicę i łącze do następnej tablicy w strukturze).

Trudno powiedzieć, która opcja byłaby najlepsza w Twojej sytuacji. Samo utworzenie dużej tablicy jest oczywiście jednym z najłatwiejszych rozwiązań i nie powinno sprawiać wielu problemów, chyba że jest naprawdę duża.

Podobnie jak w przypadku wszystkiego, co na początku wydaje się straszniejsze niż później, najlepszym sposobem na przezwyciężenie początkowego strachu jest zanurzenie się w niewygodzie nieznanego ! W końcu jest to momentami, których uczymy się najwięcej.

Niestety istnieją ograniczenia. Podczas gdy nadal uczysz się korzystać z funkcji, nie powinieneś na przykład przyjmować roli nauczyciela. Często czytam odpowiedzi od tych, którzy pozornie nie wiedzą, jak używać realloc(tj . Aktualnie akceptowana odpowiedź! ), Mówiąc innym, jak używać jej nieprawidłowo, czasami pod pozorem, że pominęli obsługę błędów , mimo że jest to częsta pułapka co wymaga wzmianki. Oto odpowiedź wyjaśniająca, jak reallocprawidłowo używać . Zwróć uwagę, że odpowiedzią jest przechowywanie zwracanej wartości w innej zmiennej w celu sprawdzenia błędów.

Za każdym razem, gdy wywołujesz funkcję i za każdym razem, gdy używasz tablicy, używasz wskaźnika. Konwersje zachodzą niejawnie, co powinno być jeszcze bardziej przerażające, ponieważ to rzeczy, których nie widzimy, często powodują najwięcej problemów. Na przykład wycieki pamięci ...

Operatory tablicowe są operatorami wskaźników. array[x]jest naprawdę skrótem do *(array + x), który można podzielić na: *i (array + x). Najprawdopodobniej *to właśnie cię dezorientuje. Możemy dodatkowo wyeliminować dodatek od problemu zakładając xsię 0, a tym samym array[0]staje się *arrayponieważ dodanie 0nie zmieni wartości ...

... i dlatego widzimy, że *arrayjest to równoważne array[0]. Możesz użyć jednego, gdzie chcesz użyć drugiego i odwrotnie. Operatory tablicowe są operatorami wskaźników.

malloc, realloca przyjaciele nie wymyślają pojęcia wskaźnika, którego używałeś przez cały czas; używają tego jedynie do zaimplementowania innej funkcji, która jest inną formą czasu przechowywania, najbardziej odpowiednią, gdy chcesz drastycznych, dynamicznych zmian rozmiaru .

Szkoda, że ​​obecnie akceptowana odpowiedź jest również sprzeczna z innymi, bardzo dobrze ugruntowanymi radami na temat StackOverflow , a jednocześnie traci okazję do wprowadzenia mało znanej funkcji, która świeci dokładnie w tym przypadku: elastyczna tablica członków! To właściwie dość zepsuta odpowiedź ... :(

Kiedy definiujesz swoją struct, zadeklaruj swoją tablicę na końcu struktury, bez górnej granicy. Na przykład:

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

Pozwoli ci to połączyć swoją tablicę intw tę samą alokację co twoja count, a powiązanie ich w ten sposób może być bardzo przydatne !

sizeof (struct int_list)będzie zachowywał się tak, jakby valuemiał rozmiar 0, więc poinformuje Cię o rozmiarze struktury z pustą listą . Nadal musisz dodać rozmiar przekazany do, reallocaby określić rozmiar listy.

Inną przydatną wskazówką jest zapamiętanie, że realloc(NULL, x)jest to odpowiednik malloc(x)i możemy użyć tego do uproszczenia naszego kodu. Na przykład:

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;

Powód, dla którego zdecydowałem się użyć struct int_list **jako pierwszego argumentu, może nie wydawać się od razu oczywisty, ale jeśli pomyślisz o drugim argumencie, wszelkie zmiany wprowadzone valueod wewnątrz push_backnie będą widoczne dla funkcji, z której wywołujemy, prawda? To samo dotyczy pierwszego argumentu i musimy być w stanie zmodyfikować nasze array, nie tylko tutaj, ale być może także w każdej innej funkcji, do której przekazujemy ...

arrayzaczyna wskazywać na nic; to jest pusta lista. Inicjowanie jest tym samym, co dodawanie do niego. Na przykład:

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

PS Pamiętaj,free(array); kiedy skończysz!

Opierając się na projekcie Matteo Furlansa , kiedy powiedział, że „ większość implementacji tablic dynamicznych działa od początku z tablicą o pewnym (małym) domyślnym rozmiarze, a gdy zabraknie miejsca podczas dodawania nowego elementu, podwaj rozmiar tablicy ”. Różnica w poniższym „ pracy w toku ” polega na tym, że rozmiar nie podwaja się, a jego celem jest wykorzystanie tylko tego, co jest wymagane. Pominąłem również kontrole bezpieczeństwa ze względu na prostotę ... Opierając się również na idei brimborów , próbowałem dodać do kodu funkcję usuwania ...

Plik storage.h wygląda następująco ...

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

Plik storage.c wygląda następująco ...

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

Plik main.c wygląda tak ...

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

Czekamy na konstruktywną krytykę do naśladowania ...

Kiedy mówisz

zrobić tablicę zawierającą numer indeksu (int) nieokreślonej liczby jednostek

w zasadzie mówisz, że używasz „wskaźników”, ale takiego, który jest wskaźnikiem lokalnym obejmującym całą tablicę zamiast wskaźnikiem obejmującym całą pamięć. Ponieważ koncepcyjnie już używasz "wskaźników" (tj. Numerów identyfikacyjnych, które odnoszą się do elementu w tablicy), dlaczego nie użyjesz zwykłych wskaźników (tj. Numerów identyfikacyjnych, które odnoszą się do elementu w największej tablicy: całej pamięci ).

Zamiast przechowywać w obiektach numery identyfikatorów zasobów, możesz zmusić je do przechowywania wskaźnika. Zasadniczo to samo, ale znacznie bardziej wydajne, ponieważ unikamy zamiany „tablicy + indeks” na „wskaźnik”.

Wskaźniki nie są przerażające, jeśli myślisz o nich jako o indeksie tablicy dla całej pamięci (a tak naprawdę są)

Aby utworzyć tablicę nieograniczonej liczby elementów dowolnego typu:

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

i jak z niego korzystać:

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

Ten wektor / tablica może pomieścić dowolny typ elementu i ma całkowicie dynamiczny rozmiar.

Cóż, myślę, że jeśli chcesz usunąć element, utworzysz kopię tablicy gardzącej elementem, który ma być wykluczony.

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

Załóżmy, że getElement2BRemove(), copy2TempVector( void* ...)i fillFromTempVector(...)sposoby pomocnicze do obsługi wektor temp.