Ich habe die ArrayList-Funktionalität in C wie folgt implementiert:
#include <stdlib.h> #include <assert.h> #include "ArrayList.h" struct _arraylist { size_t size; void ** data; }; struct _arraylist *arraylist_create() { /* Allocate Memory */ struct _arraylist *list = malloc(sizeof(struct _arraylist)); assert(list != NULL); list->size = 0; list->data = calloc(2, sizeof(void *)); assert(list->data != NULL); list->data[0] = NULL; return list; } void arraylist_setdata(struct _arraylist *list, void ** data, int max, int clear_data) { /* Sets the internal array of the arraylist */ clear_data ? arraylist_clear(list) : NULL; list->data = data; list->size = max; } void arraylist_add(struct _arraylist *list, void *elem) { /* Adds one element of generic pointer type to the internal array */ void ** new_data = realloc(list->data, arraylist_getsizeof(list)); assert(new_data != NULL); new_data[list->size] = elem; arraylist_setdata(list, new_data, list->size + 1, 0); } void *arraylist_get(struct _arraylist *list, int index) { /* Gets an member of the array at an index */ return list->data[index]; } size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } size_t arraylist_getsize(struct _arraylist *list) { /* Returns the number of elements in the arraylist */ return list->size; } void arraylist_remove(struct _arraylist *list, int index, int freeit) { /* Removes one element at and index */ if (index > list->size - 1) return; if (list->size == 1) { arraylist_clear(list); return; } if (freeit) free(arraylist_get(list, index)); for ( int i = index; i < list->size; ++i ) { if (i == list->size - 1) list->data[i] = NULL; else list->data[i] = list->data[i + 1]; } void ** new_data = realloc(list->data, arraylist_getsizeof(list)); --list->size; assert(new_data != NULL); arraylist_setdata(list, new_data, list->size, 0); } void arraylist_clear(struct _arraylist *list) { /* Clears the internal array */ list->size = 0; free(list->data); list->data = NULL; } void arraylist_deallocate(struct _arraylist *list) { /* De-allocates the arraylist from memory No usage of the arraylist is allowed after this function call */ if (list->data != NULL) free(list->data); free(list); } int arraylist_getindex(struct _arraylist *list, void *elem) { /* Looks for elem in list and returns the index or -1 if not found */ for(int i = 0; i < list->size; ++i) if (elem == arraylist_get(list, i)) return i; return -1; } I. „Ich teste es so:
#include <stdio.h> #include "ArrayList.h" int main(int argc, char const *argv[]) { ArrayList *list = arraylist_create(); int i; for(i = 0; i < 100; ++i) arraylist_add(list, &i); for(i = 0; i < 100; ++i) printf("i: %d\n", *(int *)arraylist_get(list, i)); for(i = 0; i < 100; ++i) arraylist_remove(list, i, 0); arraylist_deallocate(list); return 0; } Es funktioniert gut, obwohl realloc manchmal das Programm zum Absturz bringt. Kann ich
Kommentare
- Was Sie implementiert haben, wird häufiger als
vectorin bezeichnet C / C ++, nicht alsArrayListaus der Java-Welt.
Antwort
Zuerst ein Wort zur Benennung von :
Der Name, für den Sie sich entschieden haben Ihr Typ _arraylist ist ein falscher Name für einen Bibliotheksschnittstellentyp. Namen, die mit _ beginnen, sind im Benutzercode nicht angenehm zu bearbeiten. Sie werden häufig in Interna von Bibliotheken verwendet. Bessere Namen wären ArrayList oder array_list.
In Ihrem Anwendungsbeispiel haben Sie tatsächlich ArrayList. Bedeutet dies, dass Sie in der Kopfzeile, die hier nicht enthalten ist, so etwas haben?
typedef _arraylist ArrayList; Wenn Sie in der Kopfzeile einen undurchsichtigen Typ definiert haben, wie oben, das wäre eine gute Praxis. Dann sollten Sie jedoch keinen Verweis auf _arraylist in Ihrem Code verwenden. Verwenden Sie immer den Namen typedef „d“, um Verwechslungen zu vermeiden.
Das Funktionspräfix sollte auch genau dem Namen des Typs folgen, daher sollten für ArrayList alle Funktionen sein Stellen Sie das ArrayList_ voran, z. B.:
ArrayList * ArrayList_create(); Außerdem würde ich vorschlagen, dass Sie Namen, wie in arraylist_getsize(). Durch Hinzufügen eines Unterstrichs zu einzelnen Wörtern sind diese viel besser lesbar. Beispiel: ArrayList_get_size() .
Probleme mit dem Speicher :
Schauen wir uns arraylist_create():
struct _arraylist *arraylist_create() { struct _arraylist *list = malloc(sizeof(struct _arraylist)); assert(list != NULL); list->size = 0; list->data = calloc(2, sizeof(void *)); assert(list->data != NULL); list->data[0] = NULL; return list; } Als erstes sind die Behauptungen ungewöhnlich. Behauptungen sind nicht die richtige Methode, um einen Speicherzuordnungsfehler zu behandeln. Plus Sie werden normalerweise bei Release-Builds deaktiviert. Wenn Sie also bei der Veröffentlichung nicht genügend Speicher haben, stürzt das Programm nur stillschweigend ab. In diesem Fall sollten Sie wahrscheinlich ein NULL zurückgeben (möglicherweise auch bei stderr) und den Anrufer diesen Fehler so behandeln lassen, wie er es sieht fit.
Das zweite Problem ist hier mit calloc(). Sie weisen 2 leere Zeiger zu, jedoch wird size auf Null gesetzt. Ich verstehe das nicht wirklich. Da Ihre Struktur eher einem Array von Arrays als einer Liste ähnelt, sollten Sie das Array von Zeigern mit einer vordefinierten Standardgröße zuweisen und dann die einzelnen Arrays nach Bedarf zuweisen das Array von Zeigern bei Bedarf. Wie arraylist_create() aussehen sollte:
ArrayList * ArrayList_create() { ArrayList *list = malloc(sizeof *list); if (list == NULL) { return NULL; } list->size = 0; list->data = calloc(INITIAL_BASE_ARRAY_SIZE, sizeof(void *)); if (list->data == NULL) { free(list); // Don"t leek memory here! return NULL; } return list; } Ein weiteres großes Speicherproblem ist die Konstante Neuzuweisungen durch arraylist_add() und arraylist_remove().
Entfernen sollte die Sequenz nicht verkleinern Das Array wächst in Zukunft wieder. Sie können eine explizite Methode hinzufügen, mit der der Benutzer den Speicher bei Bedarf verkleinern kann (a la std::vector::shrink_to_fit()).
Hinzufügen zum Das Array kann so eingestellt werden, dass es in einer amortisierten konstanten Zeit ausgeführt wird, wenn Sie Speicher mit einer größeren Größe als der angeforderten vorab zuweisen. (Wieder inspiriert von der STL vector).
sizeof Fehler :
Dies gibt nicht das zurück, was Sie erwarten:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } Die sizeof gibt immer die Größe des Typs zurück, auf den er angewendet wird. Es kann nicht auf die Größe eines Arrays schließen, auf das ein Zeiger zeigt, da es sich um eine Operation zur Kompilierungszeit handelt. arraylist_getsizeof() gibt immer den gleichen Wert zurück, die Größe eines ungültigen Zeigers, der je nach Architektur 4 oder 8 beträgt.
Verwenden Sie Zusicherungen, um nach Invarianten zu suchen. :
Sie sollten assert, dass die *list Parameter jeder Funktion ist gültig. Dies ist eine Voraussetzung für jede Funktion. Sie können nicht ohne eine gültige ArrayList -Instanz funktionieren. Sie sollten dies also bestätigen, sobald die Funktion eingegeben wurde.
Verschiedenes :
Sie müssen nicht überprüfen, ob der Zeiger null vor dem Freigeben . In arraylist_deallocate() ist die Prüfung if (list->data != NULL) nicht erforderlich.
arraylist_deallocate wäre symmetrischer mit arraylist_create, wenn der Name arraylist_destroy lautet.
Kommentare
- Wie kann ich richtig prüfen, ob ich eine gültige
ArrayList-Instanz habe?Was ich bisher habe, ist ein Makro, das nach einem bestimmten Wert eines neuen Feldes sucht, das ich zustruct _arraylisthinzugefügt habe. Da die Strukturdeklaration nicht ‚ t im Header verfügbar ist, kann der Benutzer derArrayList-Schnittstelle nicht direkt auf ein Feld zugreifen (dh er muss eines von verwenden die Wrapper-Funktionen). Und ich habe speziell ‚ keinen Hinweis auf dieses Feld gegeben. - @AmrAyman, hängt von Ihrer Definition von valid ab, aber ich würde sagen, dass die Mindestvalidierung dies tun würde Überprüfen Sie, ob der Zeiger
ArrayListnicht null ist und dassArrayList::dataebenfalls nicht null ist. Sie können auch überprüfen, ob jedes Array indatanicht null ist:assert( list->data[i] != NULL );
Antwort
Sprechen wir über Leistung
Was ist, wenn Sie Ihre Liste sehr häufig verwenden müssen?
Schauen wir uns die Funktion arraylist_add genauer an. Wenn ich eine Liste mit 1 Million Bytes benötige, was 1 MB entspricht, wird Ihre data struct member 1 Million Mal.
Es ist der unterste Teil Ihrer Liste!
Vorschläge
Ordnen Sie Speicher nach Blöcken zu Beispielsweise verwendet C ++ std::vector eine zunehmende Größe der angehängten Chunks in Abhängigkeit von der aktuellen Größe von std::vector.
Dies erhöht sich Führen Sie es einige Male aus, um neue Elemente hinzuzufügen.
Lassen Sie uns über Code sprechen, wie er ist.
Versuchen Sie, einen eleganten, aber einfachen Programmablauf zu implementieren.
Erstellen Sie den Werttyp (int) ArrayList, der stattdessen Speicher durch Chuncks zuweist von ordnen Sie das gesamte Array neu zu und fügen Sie unter der Haube ein Listenverhalten hinzu. Ich meine, Liste der Chunks, Sie müssen sie noch verwalten.
Hier ist meine Lösung mit einem Beispiel für die Verwendung von Chuncks von Daten für jeden Knoten anstelle einer Neuzuweisung Knoten. Unterschiedliche Chunck-Größen können für einen der folgenden Zwecke am besten sein: Schreiben, Lesen langer Arrays; r \ w kurze Arrays; Elemente entfernen; usw.
#include <stdio.h> #include <stdlib.h> typedef struct ArrayList ArrayList; typedef ArrayList* ArrayListPtr; struct ArrayList { size_t capacity; size_t size; int *data; ArrayListPtr parent; ArrayListPtr child; }; const size_t ARRAY_LIST_CHUNCK_SIZE = 64; ArrayListPtr array_list_create_with_parent_and_chunck_size(ArrayListPtr parent, size_t chunck_size) { ArrayListPtr result = (ArrayListPtr)calloc(sizeof(ArrayList), 1); result->parent = parent; result->capacity = chunck_size; result->data = (int*)malloc(sizeof(int) * chunck_size); return result; } ArrayListPtr array_list_create_with_parent(ArrayListPtr parent) { return array_list_create_with_parent_and_chunck_size( parent, ARRAY_LIST_CHUNCK_SIZE ); } ArrayListPtr array_list_create() { return array_list_create_with_parent_and_chunck_size( NULL, ARRAY_LIST_CHUNCK_SIZE ); } void array_list_push_back(ArrayListPtr list, int value) { if (list->size >= list->capacity) { if (!list->child) { list->child = array_list_create_with_parent(list); } array_list_push_back(list->child, value); } else { list->data[list->size++] = value; } } int* array_list_get_value_by_index(ArrayListPtr list, size_t index) { if (index >= list->capacity || index >= list->size) { if (list->child) { return array_list_get_value_by_index(list->child, index - list->size); } else { return NULL; } } return list->data + index; } int main(int argc, char *argv[]) { ArrayListPtr list = array_list_create(); for (int i = 0; i < 100*1000; ++i) { array_list_push_back(list, i); } size_t test[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,31,32,33,63,64,65,999,1000}; for (int i = 0; i < sizeof(test) / sizeof(size_t); ++i) { int* result = array_list_get_value_by_index(list, test[i]); if (result) { printf("list[%ld] = %d\n", test[i], *result); } else { printf("Can"t get value by index %ld\n", test[i]); } } } Kommentare
- Ich respektiere Ihr Interesse. Dies ist jedoch C, nicht C ++. Wenn es C ++ wäre, würde ich einfach Vektoren verwenden, um das zu tun.
- @AmrAyman, überprüfen Sie es
- Das ‚ ist beeindruckend! Aber ich möchte eine Arrayliste haben, keine verknüpfte Liste. Obwohl Ihre Implementierung der verknüpften Liste hier weiter fortgeschritten ist als die normale Strukturimplementierung, hat glampert das Problem gelöst.
- Über den Leistungsgewinn. ‚ gibt es nicht wirklich so viel: Meine Implementierung basiert auf dem Heap, normalerweise, weil sie auf einem Array basiert; Ihre verlassen sich stark auf Rekursion, und das ‚ ist natürlich, weil Sie ‚ auf Knoten angewiesen sind. Außerdem wäre das Freigeben der Liste relativ langsam viel , da Sie ‚ entweder eine Rekursion (die sehr leistungsschwach ist) oder eine ziemlich komplizierte verwenden würden while-Schleife ..
Antwort
Ein Problem, das von anderen nicht erwähnt wird, ist, dass Ihr Test nicht funktioniert. Es scheint zu funktionieren, aber in Wirklichkeit nicht. Wenn Sie der Liste Werte hinzufügen, übergeben Sie die Adresse der Variablen i:
arraylist_add(list, &i); und arraylist_add speichert nur den übergebenen Wert (wie es sollte):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Sobald Sie also i = 0 durchlaufen haben. .99 alles was Sie in der Liste haben, ist die Adresse von i 100 mal. Wenn Sie die Daten zurücklesen, verwenden Sie erneut die Schleifenvariable i und ändern ihren Wert von 0..99, und der gedruckte Wert sieht richtig aus. Aber Sie sehen wirklich nur den Wert der Schleifenvariablen, die von der Schleife geändert wird.
Wenn Sie mir nicht glauben, drucken Sie einen festen Array-Eintrag aus, z. B. 50, wie in:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); wird er gedruckt 100 (oder was auch immer der Wert von i derzeit ist).
Stattdessen sollten Sie den realen Wert speichern:
arraylist_add(list, (void*) i); und drucken Sie müssen den Wert in den Typ umwandeln, der er war, als er eingegeben wurde:
printf("i: %d\n", (int)arraylist_get(list, t)); Es gibt viele andere Probleme mit dem Code, wie andere bemerkt haben Das grundlegende Design der Verwendung Ihrer arraylist_setdata für alle Änderungen ist falsch. Die Neuzuweisung bei jeder Änderung ist nur schlecht – realloc ist teuer Die Grundidee einer Liste, in der Dinge gespeichert werden, indem vorgetäuscht wird, sie seien void*, ist für mich verwirrend und scheint eine schlechte Idee zu sein.
Kommentare
- Nun, Sie werden es vielleicht nicht bemerken, aber ‚ ist genau was ich testen wollte. Diese Zeiger werden gespeichert und abgerufen richtig durch die Funktionsumhüllungen ..
- Das Speichern von Dingen als
void *ist nicht ‚ nicht wirklich so schlecht, wie es scheint.Denken Sie darüber nach,void *speichert einfach eine Speicheradresse, die mir ‚ egal ist, um welchen Typ es sich handelt. Kurz gesagt, das Array soll nur Speicheradressen speichern, und ‚ ist praktisch die einzige Möglichkeit, wie C mit verschiedenen Typen in einem einzelnen Array umgehen würde. - Über
reallocstimme ich Ihnen zu, aber ich konnte ‚ keinen besseren Weg finden, um eine Dynamik zu erstellen Array. Wie auch immer, ich folgte dem Rat von glampert ‚, eine spezielle Funktion dafür zu verpacken, dieshrink_to_fit-Funktion. - Ich stellte mir vor, Sie wollten Skalardaten variabler Größe speichern, indem Sie sie in einem
void*speichern (verschiedene Personen haben dazu Code eingereicht). Wenn Sie wirklich Zeiger speichern möchten, besteht ein besserer Test darin, mehrere verschiedene Zeiger in einer bekannten Reihenfolge zu speichern und zu überprüfen, ob Sie sie in derselben Reihenfolge zurückerhalten – anstatt dieselbe zu speichern Zeiger 100 mal. Das Problem beim Speichern von Zeigern besteht darin, dass das Objekt, auf das verwiesen wird, für die Lebensdauer der Existenz seiner Adresse im Array persistent sein muss. Trotz der Leere * können Sie natürlich keine Typen innerhalb eines Arrays mischen. - Nur eine andere Art, dasselbe zu tun, wobei das Array unmittelbar nach dem Ende der Struktur folgt. Diese Methode hat ihre eigenen Probleme. Vergessen Sie also, dass ich sie erwähnt habe.