Jag implementerade ArrayList-funktionalitet i C enligt följande:
#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 ”m testar det så här:
#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; } Det fungerar bra, men realloc ibland kraschar programmet. Kan jag förbättra detta?
Kommentarer
Svar
Först ett ord om att namnge :
Namnet du har valt för din typ, _arraylist är ett dåligt namn för en typ av biblioteksgränssnitt. Namn som börjar med _ är inte trevliga att arbeta med i användarkoden. De används vanligtvis i biblioteksinterna. Bättre namn skulle vara ArrayList eller array_list.
I ditt användandexempel har du faktiskt ArrayList. Betyder detta att du i rubriken, som inte ingår här, har något liknande?
typedef _arraylist ArrayList; Om du definierade en ogenomskinlig typ i rubriken, som ovan, skulle det vara en bra praxis. Men då ska du inte använda någon hänvisning till _arraylist i din kod. Använd alltid typedef ”d-namnet för att undvika förvirring.
Funktionsnamnets prefix bör också följa exakt namnet på typen, så för ArrayList bör alla funktioner vara prefix ArrayList_, t.ex.:
ArrayList * ArrayList_create(); Jag föreslår också att du undviker tightlypacked namn, som i arraylist_getsize(). Att lägga till en understrykning för att skilja ord gör dem mycket mer läsbara. Exempel: ArrayList_get_size() .
Problem med minne :
Låt oss titta på 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; } Det första ovanliga här är påståendena. Påståenden är inte rätt sätt att hantera ett minnesallokeringsfel. Plus , de är vanligtvis inaktiverade vid release-versioner, så om du råkar ta slut på minne skulle programmet bara krascha tyst. Du bör antagligen returnera en NULL i det här fallet (kanske också logga in på stderr) och låta den som ringer hantera detta fel som han / hon ser fit.
Det andra problemet här är med calloc(). Du tilldelar två ogiltiga pekare, men size är satt till noll. Jag förstår inte riktigt poängen med detta. Eftersom din struktur är mer lik och array av matriser än en lista, vad du bör göra är att fördela arrayen med pekare med någon fördefinierad standardstorlek och sedan fördela de enskilda arraysna efter behov. utbudet av pekare på begäran. Hur arraylist_create() ska se ut:
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; } Ett annat stort minnesproblem är den konstanta omfördelningar gjorda av arraylist_add() och arraylist_remove().
Ta bort bör inte krympa sekvensen. Behåll det utrymmet runt om arrayen växer igen i framtiden. Du kan lägga till ett uttryckligt sätt för att låta användaren krympa lagringen om det behövs (a la std::vector::shrink_to_fit()).
Lägger till i array kan fås att köras på amorterad konstant tid om du fördelar lagring med en större storlek än den begärda. (återigen inspirerad av STL vector).
sizeof misstag :
Detta returnerar inte vad du förväntar dig:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } sizeof operatören returnerar alltid storleken på den typ den används på. Det kan inte härleda storleken på en matris som pekas av en pekare, eftersom det är en kompileringstidsoperation. arraylist_getsizeof() returnerar alltid samma värde, storleken på en ogiltig pekare, vilken kommer att vara 4 eller 8, beroende på arkitektur.
Använd påståenden för att söka efter invarianter :
Du bör assert att *list -parametern för varje funktion är giltig. Detta är en förutsättning för varje funktion, de kan inte fungera utan en giltig ArrayList instans, så du bör hävda att när funktionen går in.
Diverse :
Du behöver inte kontrollera om pekaren är null innan du frigör det . I arraylist_deallocate() if (list->data != NULL) -kontrollen behövs inte.
arraylist_deallocate skulle vara mer symmetrisk med arraylist_create om namnet arraylist_destroy.
Kommentarer
- Hur kan jag ordentligt kontrollera om jag har en giltig
ArrayListinstans?Vad jag har hittills är ett makro som söker efter ett specifikt värde för ett nytt fält som jag lagt tillstruct _arraylist. Eftersom struct-deklarationen inte finns ’ t tillgänglig i rubriken, kanArrayListgränssnittsanvändaren inte komma åt något fält direkt (dvs. han måste använda ett av omslagsfunktionerna). Och jag gav specifikt ’ ingen aning om detta fält .. - @AmrAyman, beror på din definition av giltig, men jag skulle säga att minsta validering skulle kontrollera att
ArrayList-pekaren inte är noll och attArrayList::datainte heller är noll. Du kan också kontrollera att varje array idatainte är null:assert( list->data[i] != NULL );
Svar
Låt oss prata om prestanda
Vad händer om du behöver använda din lista mycket ofta?
Låt oss titta närmare på funktionen arraylist_add. Om jag behöver en lista med 1 miljon byte, vilket är 1 MB, kommer det att omfördela din data struct-medlem 1 miljon gånger.
Det är den lägsta delen av din lista!
Förslag
Tilldela minne med bitar t.ex. C ++ std::vector använder ökande storlek på bifogade bitar beroende på aktuell storlek på std::vector.
Detta ökar prestera det några gånger i syfte att lägga till nya element.
Låt oss prata om koden som den är
Försök implementera ett elegant men enkelt programflöde.
Skapa värdetyp (int) ArrayList, som istället tilldelar minne med bitar omfördela hela matrisen och lägg till lite listbeteende under huven. Jag menar lista över bitar, du behöver fortfarande hantera den.
Här är min lösning med exempel på att använda bitar av data för varje nod istället för att omfördela knutpunkter. Olika chunckstorlekar kan vara bäst för ett av syften: skriva, läsa långa matriser; r \ w korta matriser; ta bort element; etc.
#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]); } } } Kommentarer
- Jag respekterar ditt intresse. Detta är dock C, inte C ++. Om det var C ++ skulle jag bara använda vektorer för att göra det …
- @AmrAyman, kolla det
- Att ’ är imponerande! Men jag vill ha en arraylista, inte en länkad lista. Även om implementeringen av din länkade lista här är mer avancerad än den normala strukturimplementeringen löste glampert problemet.
- Om prestationsvinsten. Det finns inte ’ t så mycket: Min implementering är beroende av högen, normalt för att den är beroende av en matris; Din förlitar sig starkt på rekursion och att ’ är naturligt eftersom du ’ förlitar dig på noder. Att frigöra listan skulle också vara mycket långsamt relativt, eftersom du ’ antingen använder rekursion (som är mycket låg på prestanda) eller en ganska komplicerad while loop ..
Svar
Ett problem som inte nämns av andra är att ditt test inte fungerar. Det verkar fungera men i verkligheten fungerar det inte. När du lägger till värden i listan skickar du adressen till variabeln i:
arraylist_add(list, &i); Och arraylist_add sparar bara det skickade värdet (som det borde):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Så när du har gått igenom i = 0. .99 allt du har i listan är adressen till i 100 gånger. När du läser tillbaka data använder du igen loopvariabel i och ändrar dess värde från 0..99 och det utskrivna värdet ser rätt ut. Men du ser egentligen bara värdet på loop-variabeln som ändras av loop.
Om du inte tror mig, skriv ut någon fast matrispost, t.ex. 50, som i:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); kommer den att skrivas ut 100 (eller vad värdet på i för närvarande är).
I stället borde du spara det verkliga värdet:
arraylist_add(list, (void*) i); och skriva ut det måste du kasta värdet till den typ det var när det gick in:
printf("i: %d\n", (int)arraylist_get(list, t)); Det finns många andra problem med koden, som andra har noterat . Den grundläggande utformningen av att använda din arraylist_setdata för att göra alla ändringar är fel. Omfördelning vid varje ändring är bara dålig – realloc är dyrt. Och grundidén med en lista som lagrar saker genom att låtsas att de är void* är förvirrande för mig och verkar vara en dålig idé.
Kommentarer
- Du kanske inte märker det, men att ’ är exakt vad jag ville testa. Att pekare lagras och hämtas korrekt genom funktionsomslagen ..
- Att lagra saker som
void *är inte ’ t verkligen så illa som det verkar.Tänk på det,void *lagrar helt enkelt en minnesadress som jag inte ’ bryr mig om vilken typ av värde som lagras vid. Kort sagt, matrisen ska bara lagra minnesadresser, och att ’ är praktiskt taget det enda sättet att C skulle hantera olika typer i en enda array .. - Om
realloc, jag håller med dig men jag kunde bara inte ’ inte hitta ett bättre sätt att skapa en dynamisk array. Hur som helst följde jag glampert ’ s råd att lägga in en speciell funktion för det,shrink_to_fit-funktionen .. - Jag föreställde mig att du försökte spara skalardata med variabel storlek genom att lagra den i en
void*(olika personer har skickat in kod för att göra det). Om du verkligen ville lagra pekare, skulle ett bättre test vara att lagra ett antal olika pekare i en känd ordning och att kontrollera att du får tillbaka dem i samma ordning – istället för att spara samma pekaren 100 gånger. Problemet med att lagra pekare är att objektet som pekas på måste vara bestående under hela dess existens av adressen i matrisen. Trots tomrummet * kan du naturligtvis inte blanda typer inom en array. - Bara ett annat sätt att göra samma sak, där arrayen följer omedelbart efter strukturens slut. Den metoden har sina egna problem, så glöm att jag nämnde den.
vectori C / C ++, inte som ettArrayListfrån Java-världen.