C-Array dynamisch wachsenden
https://stackoverflow.com/questions/3536153
-
30-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe ein Programm, das eine „rohe“ Liste der im Spiel Entität liest, und ich beabsichtige, eine Reihe zu machen eine Indexzahl halten (int) eine unbestimmten Anzahl von Einheiten, für verschiedene Dinge zu verarbeiten. Ich möchte für die Aufbewahrung solcher Indizes mit zu viel Speicher oder CPU vermeiden ...
Eine schnelle und schmutzige Lösung, die ich bisher verwenden ist zu erklären, in dem Haupt-Verarbeitungsfunktion (lokale Fokus) das Array mit einer Größe der maximalen Spieleinheiten, und einem anderen ganzen Zahl, um zu verfolgen, wie viele haben die hinzugefügt aufführen. Dies ist nicht zufriedenstellend, da jede Liste 3000+ Arrays hält, die nicht so viel ist, aber man fühlt sich wie eine Verschwendung, da ich werde mögliche Verwendung der Lösung für 6-7 Listen für Funktionen variieren.
Ich habe gefunden, keine C (nicht C ++ oder C #) spezifische Lösungen, dies zu erreichen. Ich kann Zeiger verwenden, aber ich bin ein bisschen Angst, sie zu verwenden (es sei denn, es die einzige Möglichkeit ist).
Die Arrays lassen nicht die lokalen Funktionsumfang (sie sind an eine Funktion übergeben werden, dann verworfen), für den Fall, dass die Dinge ändert.
Wenn Zeiger die einzige Lösung sind, wie kann ich sie behalten Lecks zu vermeiden?
Lösung
Ich kann Zeiger verwenden, aber ich bin ein bisschen Angst, sie zu benutzen.
Wenn Sie ein dynamisches Array benötigen, können Sie keine Zeiger entkommen. Warum haben Sie Angst, obwohl? Sie werden nicht beißen (solange Sie vorsichtig sind, das ist). Es gibt keinen eingebauten dynamischen Array in C, werden Sie nur einen selbst schreiben müssen. In C ++ können Sie die eingebaute in std::vector Klasse. C # und so ziemlich jede andere High-Level-Sprache auch eine ähnliche Klasse, die dynamische Arrays für Dich verwaltet.
Wenn Sie planen, tun Sie Ihre eigenen, hier etwas zu schreiben, um Sie zu erhalten begonnen: dynamischsten Array-Implementierungen Arbeit mit einer Reihe von einigen (kleinen) Standardgröße Anfahren, dann, wenn Sie genügend Speicherplatz vorhanden, wenn ein neues Element hinzugefügt , die doppelte Größe des Arrays. Wie Sie im Beispiel unten sehen kann, ist es nicht sehr schwierig, überhaupt: (I Sicherheitsüberprüfungen der Kürze halber weggelassen haben)
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;
}
es zu verwenden 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);
Andere Tipps
Es gibt ein paar Optionen, die ich mir vorstellen kann.
- verlinkte Liste. Sie können eine verkettete Liste verwenden, um einen dynamisch wachsenden Array wie Sache zu machen. Aber Sie werden nicht in der Lage sein
array[100]zu tun, ohne zuerst durch1-99laufen zu müssen. Und es könnte nicht so nützlich sein für Sie entweder zu verwenden. - Large Array. Einfach ein Array erstellen mit mehr als genug Platz für alles
- Ändern der Größe von Array. Erstellen Sie das Array, wenn Sie die Größe kennen und / oder erstellen Sie ein neues Array jedes Mal, wenn Sie aus dem Raum mit einem gewissen Spielraum und kopieren Sie alle Daten auf das neue Array.
- verlinkte Liste Array Kombination. Einfach ein Array mit einer festen Größe verwenden und wenn Sie genügend Speicherplatz aus, ein neues Array und Link zu, dass schaffen (es wäre klug, den Überblick über die Anordnung zu halten und die Verbindung zum nächsten Array in einer Struktur).
Es ist schwer zu sagen, was Option am besten in Ihrer Situation wäre. Einfach eine große Auswahl der einfachstenen Lösungen ist natürlich eine Erstellung und sollen Ihnen viele Probleme nicht geben, wenn es wirklich groß ist.
Wie bei allem, was beunruhigender scheint zunächst, als es später war, ist der beste Weg, um die anfängliche Angst verwinden ist auf tauchen Sie ein in die Unbequemlichkeit des unbekannten ! Es ist manchmal wie das, was wir am meisten, schließlich lernen.
Leider gibt es Einschränkungen. Während Sie noch eine Funktion verwenden lernen, sollten Sie die Rolle eines Lehrers nicht übernehmen, zum Beispiel. Ich lese oft Antworten von denen, die scheinbar nicht wissen, wie realloc zu verwenden (dh die momentan akzeptierte Antwort! ) andere sagen, wie es zu benutzen falsch, gelegentlich unter dem Vorwand, dass sie haben weggelassen Fehlerbehandlung , auch wenn dies ein häufiger Fehler ist die Erwähnung bedarf. Hier ist eine Antwort zu erklären, wie realloc richtig verwenden . Beachten Sie, dass die Antwort speichert den Rückgabewert in eine andere Variable, um die Fehlerüberprüfung durchzuführen.
Jedes Mal, wenn Sie eine Funktion aufrufen, und jedes Mal, wenn Sie ein Array verwenden, verwenden Sie einen Zeiger. Die Umwandlungen auftreten implizit, was, wenn etwas sollte noch erschreckender sein, wie es die Dinge, die wir nicht sehen, die oft Ursache der meisten Probleme. Zum Beispiel Speicherlecks ...
Array Operatoren sind Zeiger Operatoren. array[x] ist wirklich eine Abkürzung für *(array + x), die nach unten in gebrochen werden kann: * und (array + x). Es ist sehr wahrscheinlich, dass der * ist, was Sie verwirrt. Wir können weiterhin die Zugabe von dem Problem beseitigen, indem x unter der Annahme, 0 zu sein, so wird array[0] *array weil 0 Zugabe wird den Wert nicht ändern ...
... und so können wir sehen, dass *array zu array[0] entspricht. Sie können einen verwenden, wo Sie die anderen verwenden möchten, und vice versa. Array Operatoren sind Zeiger Operatoren.
malloc, realloc und Freunde nicht erfinden das Konzept eines Zeigers, die Sie zusammen mit allen habe; sie nur Verwendung diese eine andere Funktion zu implementieren, die eine andere Form von Speicherdauer ist, am besten geeignet, wenn Sie wünschen drastisch, dynamische Veränderungen in der Größe .
Es ist eine Schande, dass die derzeit akzeptierte Antwort auch gegen den Strich geht von einige andere sehr fundierte Beratung über Stackoverflow , und zugleich, eine Chance verpasst, eine wenig bekannte Funktion, die für genau diese usecase glänzt vorstellen: flexible Array-Mitglieder! Das ist eigentlich ein ziemlich gebrochen Antwort ...: (
Wenn Sie Ihre struct definieren, erklären Sie Ihre Array am Ende der Struktur, ohne eine obere Grenze. Zum Beispiel:
struct int_list {
size_t size;
int value[];
};
Damit können Sie Ihr Array von int in die gleiche Zuordnung wie Ihr count vereinen, und sie wie diese können gebunden ist sehr handlich
sizeof (struct int_list) wird handeln, als ob value eine Größe von 0 hat, so ist es die Größe der Struktur sagen werde mit einer leeren Liste . Sie müssen noch auf die Größe zu realloc weitergegeben hinzuzufügen, um die Größe der Liste angeben.
Ein weiterer praktischer Tipp ist, mich daran zu erinnern, dass realloc(NULL, x) zu malloc(x) gleichwertig ist, und wir können dies unseren Code zu vereinfachen verwenden. Zum Beispiel:
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, warum ich wählte struct int_list ** als erstes Argument zu verwenden, möglicherweise nicht sofort offensichtlich erscheinen, aber wenn man über das zweite Argument denken, werden alle Änderungen an value aus push_back würde nicht auf die Funktion sichtbar sein, die wir aus anrufen, richtig? Das gleiche gilt für das erste Argument, und wir müssen in der Lage unsere array zu ändern, nicht nur hier aber möglicherweise auch in einer anderen Funktion / s geben wir es zu ...
array beginnt an nichts zeigt; es ist eine leere Liste. Initialisierung es ist das gleiche wie er hinzufügen. Zum Beispiel:
struct int_list *array = NULL;
if (!push_back(&array, 42)) {
// success!
}
P. S. Denken Sie daran, free(array); , wenn Sie mit ihm fertig sind!
Wenn Sie sagen,
stellen ein Array eine Indexnummer (int) einer unbestimmten Anzahl von Entitäten Halte
sind Sie im Grunde sagen Sie verwenden „Zeiger“, aber eine, die ein Array-weit ist die lokale Zeiger statt Speicherweiten Zeiger. Da Sie sind konzeptionell bereits mit „Zeiger“ (dh ID-Nummern, die in einem Array auf ein Element bezieht), warum Sie nicht nur regelmäßige Zeiger verwenden (dh ID-Nummern, die in der größten Array auf ein Element bezieht: der gesamte Speicher ).
Statt Ihre Objekte eine Ressource-ID-Nummern zu speichern, können Sie sie stattdessen einen Zeiger machen speichern. Im Grunde das gleiche, aber viel effizienter, da wir „Array + Index“ in einen „Zeiger“ zu vermeiden drehen.
Pointers sind nicht beängstigend, wenn Sie von ihnen als Array-Index für den gesamten Speicher denken (was ist das, was sie tatsächlich sind)
Aufbauend auf Matteo Furlans Design, als er „, sagte dynamischsten Array-Implementierungen arbeiten, indem sie mit einer Reihe von einiger (kleinen) Standardgröße Anfahren, dann, wenn Sie genügend Speicherplatz vorhanden, wenn ein neues Element hinzugefügt wird, die doppelte Größe des Arrays “. Der Unterschied in dem „ unfertigen “ unten ist, dass es nicht doppelt so groß macht, es zielt darauf ab, mit nur das, was erforderlich ist. Ich habe auch Sicherheitsüberprüfungen der Einfachheit halber weggelassen ... Auch baut auf brimboriums Idee, ich habe versucht, eine Löschfunktion, um den Code ...
hinzufügenDie storage.h Datei sieht wie folgt 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 storage.c Datei sieht wie folgt 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 wie folgt 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 folgen ...
Um ein Array von unbegrenzten Gegenständen aller Art von Art zu erstellen:
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 jede Art von Element halten kann und es ist völlig dynamisch in der Größe.
Nun, ich denke, wenn Sie ein Element entfernen müssen Sie eine Kopie des Arrays machen das Element verachte ausgeschlossen werden.
// 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);
//
Es sei angenommen, daß getElement2BRemove(), copy2TempVector( void* ...) und fillFromTempVector(...) sind Hilfsmethoden des temp Vektor zu handhaben.
