C dynamisch wachsendes Array

Ich habe ein Programm, das eine "rohe" Liste von Entitäten im Spiel liest, und ich beabsichtige, ein Array zu erstellen, das eine Indexnummer (int) einer unbestimmten Anzahl von Entitäten enthält, um verschiedene Dinge zu verarbeiten. Ich möchte vermeiden, zu viel Speicher oder CPU zu verwenden, um solche Indizes zu führen ...

Eine schnelle und schmutzige Lösung, die ich bisher verwende, besteht darin, in der Hauptverarbeitungsfunktion (lokaler Fokus) das Array mit der Größe der maximalen Spielentitäten und eine weitere Ganzzahl zu deklarieren, um zu verfolgen, wie viele zur Liste hinzugefügt wurden. Dies ist nicht zufriedenstellend, da jede Liste mehr als 3000 Arrays enthält, was nicht so viel ist, sich aber wie Verschwendung anfühlt, da ich die Lösung für 6-7 Listen für verschiedene Funktionen verwenden kann.

Ich habe keine C-spezifischen (nicht C ++ oder C #) spezifischen Lösungen gefunden, um dies zu erreichen. Ich kann Zeiger verwenden, habe aber etwas Angst davor, sie zu verwenden (es sei denn, dies ist der einzig mögliche Weg).

Die Arrays verlassen nicht den lokalen Funktionsumfang (sie müssen an eine Funktion übergeben und dann verworfen werden), falls sich dadurch etwas ändert.

Wenn Zeiger die einzige Lösung sind, wie kann ich sie verfolgen, um Undichtigkeiten zu vermeiden?

Ich kann Zeiger verwenden, habe aber ein bisschen Angst davor, sie zu verwenden.

Wenn Sie ein dynamisches Array benötigen, können Sie Zeigern nicht entkommen. Warum hast du aber Angst? Sie werden nicht beißen (solange Sie vorsichtig sind). In C gibt es kein eingebautes dynamisches Array. Sie müssen nur eines selbst schreiben. In C ++ können Sie die integrierte std::vectorKlasse verwenden. C # und fast jede andere Hochsprache haben auch eine ähnliche Klasse, die dynamische Arrays für Sie verwaltet.

Wenn Sie vorhaben, Ihre eigenen zu schreiben, sollten Sie zunächst Folgendes tun: Die meisten dynamischen Array-Implementierungen beginnen mit einem Array mit einer (kleinen) Standardgröße. Wenn Sie beim Hinzufügen eines neuen Elements keinen Speicherplatz mehr haben, verdoppeln Sie den Wert Größe des Arrays. Wie Sie im folgenden Beispiel sehen können, ist es überhaupt nicht sehr schwierig: (Ich habe Sicherheitsüberprüfungen der Kürze halber weggelassen)

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

Die Verwendung ist genauso einfach:

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

Ich kann mir einige Optionen vorstellen.

1. Verknüpfte Liste. Sie können eine verknüpfte Liste verwenden, um ein dynamisch wachsendes Array zu erstellen. Aber Sie werden nicht in der Lage sein, array[100]ohne zuerst durchzugehen 1-99. Und es ist möglicherweise auch nicht so praktisch für Sie.
2. Großes Array. Erstellen Sie einfach ein Array mit mehr als genug Platz für alles
3. Ändern der Größe des Arrays. Erstellen Sie das Array neu, sobald Sie die Größe kennen, und / oder erstellen Sie jedes Mal ein neues Array, wenn Ihnen der Speicherplatz mit einem gewissen Rand ausgeht, und kopieren Sie alle Daten in das neue Array.
4. Verknüpfte Liste Array-Kombination. Verwenden Sie einfach ein Array mit einer festen Größe. Wenn Ihnen der Speicherplatz ausgeht, erstellen Sie ein neues Array und verknüpfen Sie es (es ist ratsam, das Array und den Link zum nächsten Array in einer Struktur zu verfolgen).

Es ist schwer zu sagen, welche Option in Ihrer Situation am besten wäre. Das einfache Erstellen eines großen Arrays ist natürlich eine der einfachsten Lösungen und sollte Ihnen nur dann große Probleme bereiten, wenn es wirklich groß ist.

Wie bei allem, was auf den ersten Blick beängstigender erscheint als später, ist der beste Weg, die anfängliche Angst zu überwinden, in das Unbehagen des Unbekannten einzutauchen ! Es ist manchmal so, wie wir es am meisten lernen.

Leider gibt es Einschränkungen. Während Sie noch lernen, eine Funktion zu verwenden, sollten Sie beispielsweise nicht die Rolle eines Lehrers übernehmen. Ich lese oft Antworten von denen, die anscheinend nicht wissen, wie man sie verwendet realloc(dh die derzeit akzeptierte Antwort! ) Und anderen sagt, wie sie falsch verwendet werden sollen, gelegentlich unter dem Deckmantel, dass sie die Fehlerbehandlung weggelassen haben , obwohl dies eine häufige Gefahr ist was erwähnt werden muss. Hier ist eine Antwort, die erklärt, wie man reallocrichtig verwendet . Beachten Sie, dass die Antwort den Rückgabewert in einer anderen Variablen speichert , um eine Fehlerprüfung durchzuführen.

Jedes Mal, wenn Sie eine Funktion aufrufen und wenn Sie ein Array verwenden, verwenden Sie einen Zeiger. Die Konvertierungen erfolgen implizit, was, wenn überhaupt, noch beängstigender sein sollte, da die Dinge, die wir nicht sehen, häufig die meisten Probleme verursachen. Zum Beispiel Speicherlecks ...

Array-Operatoren sind Zeigeroperatoren. array[x]ist wirklich eine Abkürzung für *(array + x), die unterteilt werden kann in: *und (array + x). Es ist sehr wahrscheinlich, dass Sie *das verwirrt. Wir können weiterhin die Zugabe von dem Problem beseitigen , indem angenommen xwerden 0somit, array[0]wird , *arrayda das Hinzufügen 0nicht den Wert ändern ...

... und so können wir sehen, dass *arraydas gleichbedeutend ist mit array[0]. Sie können eines dort verwenden, wo Sie das andere verwenden möchten, und umgekehrt. Array-Operatoren sind Zeigeroperatoren.

malloc, reallocNicht und Freunde erfinden das Konzept eines Zeigers , die Sie die ganze Zeit verwendet haben; Sie verwenden dies lediglich , um eine andere Funktion zu implementieren, bei der es sich um eine andere Form der Speicherdauer handelt, die am besten geeignet ist, wenn Sie drastische, dynamische Größenänderungen wünschen .

Es ist eine Schande, dass die derzeit akzeptierte Antwort auch gegen einige andere sehr fundierte Ratschläge zu StackOverflow verstößt und gleichzeitig die Gelegenheit verpasst, eine wenig bekannte Funktion einzuführen, die genau für diesen Anwendungsfall glänzt: flexibles Array Mitglieder! Das ist eigentlich eine ziemlich kaputte Antwort ... :(

Wenn Sie Ihre definieren struct, deklarieren Sie Ihr Array am Ende der Struktur ohne Obergrenze. Beispielsweise:

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

Auf diese Weise können Sie Ihr Array intin derselben Zuordnung wie Ihre zusammenfassen count, und es kann sehr praktisch sein , sie so zu binden !

sizeof (struct int_list)verhält sich so, als hätte valuees eine Größe von 0, sodass die Größe der Struktur mit einer leeren Liste angezeigt wird . Sie müssen noch die übergebene Größe hinzufügen, reallocum die Größe Ihrer Liste anzugeben.

Ein weiterer praktischer Tipp ist, sich daran zu erinnern, dass dies realloc(NULL, x)gleichbedeutend ist malloc(x), und wir können dies verwenden, um unseren Code zu vereinfachen. Beispielsweise:

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;

Der Grund, den ich struct int_list **als erstes Argument gewählt habe, mag nicht sofort offensichtlich erscheinen, aber wenn Sie an das zweite Argument denken, sind Änderungen, die valuevon innen vorgenommen wurden, push_backfür die Funktion, von der wir aufrufen, nicht sichtbar, oder? Das gleiche gilt für das erste Argument, und wir müssen in der Lage sein, unser arraynicht nur hier, sondern möglicherweise auch in allen anderen Funktionen, an die wir es weitergeben, zu ändern ...

arraybeginnt auf nichts zu zeigen; Es ist eine leere Liste. Das Initialisieren entspricht dem Hinzufügen. Beispielsweise:

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

PS Denkenfree(array); Sie daran, wenn Sie damit fertig sind!

Aufbauend auf dem Design von Matteo Furlans , als er sagte, "die meisten dynamischen Array-Implementierungen funktionieren, indem sie mit einem Array mit einer (kleinen) Standardgröße beginnen. Wenn Sie beim Hinzufügen eines neuen Elements keinen Platz mehr haben, verdoppeln Sie die Größe des Arrays. " Der Unterschied bei " work in progress " unten besteht darin, dass es nicht doppelt so groß ist, sondern nur das verwendet, was erforderlich ist. Der Einfachheit halber habe ich auch Sicherheitsüberprüfungen weggelassen ... Aufbauend auf der Idee von brimboriums habe ich versucht, dem Code eine Löschfunktion hinzuzufügen ...

Die Datei storage.h sieht folgendermaßen aus ...

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

Die Datei storage.c sieht folgendermaßen aus ...

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

Die main.c sieht so aus ...

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

Freuen Sie sich auf die konstruktive Kritik ...

Wenn du sagst

Erstellen Sie ein Array, das eine Indexnummer (int) einer unbestimmten Anzahl von Entitäten enthält

Sie sagen im Grunde, dass Sie "Zeiger" verwenden, aber einen, der ein Array-breiter lokaler Zeiger anstelle eines speicherweiten Zeigers ist. Da Sie konzeptionell bereits "Zeiger" verwenden (dh ID-Nummern, die sich auf ein Element in einem Array beziehen), verwenden Sie einfach reguläre Zeiger (dh ID-Nummern, die sich auf ein Element im größten Array beziehen: den gesamten Speicher) ).

Anstatt dass Ihre Objekte Ressourcen-ID-Nummern speichern, können Sie sie stattdessen dazu bringen, einen Zeiger zu speichern. Grundsätzlich das Gleiche, aber viel effizienter, da wir vermeiden, "Array + Index" in einen "Zeiger" zu verwandeln.

Zeiger sind nicht beängstigend, wenn Sie sie als Array-Index für den gesamten Speicher betrachten (was sie tatsächlich sind).

So erstellen Sie ein Array mit unbegrenzten Elementen aller Art:

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

und wie man es benutzt:

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

Dieser Vektor / Array kann jede Art von Element enthalten und ist vollständig dynamisch.

Nun, ich denke, wenn Sie ein Element entfernen müssen, werden Sie eine Kopie des Arrays erstellen, das das auszuschließende Element verachtet.

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

Angenommen getElement2BRemove(), copy2TempVector( void* ...)und fillFromTempVector(...)sind Hilfsmethoden zur Behandlung des Temperaturvektors.