Jeg implementerede ArrayList-funktionalitet i C som følger:
#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 “Jeg tester det sådan:
#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 fungerer fint, selvom realloc nogle gange styrter programmet. Kan jeg forbedre dette?
Kommentarer
Svar
Først et ord om navngivning af :
Det navn, du har valgt til din type, _arraylist er et dårligt navn for en biblioteksinterfacetype. Navne, der starter med _, er ikke behagelige at arbejde med i brugerkoden. De bruges ofte inden i biblioteksinterne. Bedre navne ville være ArrayList eller array_list.
I dit brugseksempel har du faktisk ArrayList. Betyder dette, at du i overskriften, som ikke er inkluderet her, har noget som dette?
typedef _arraylist ArrayList; Hvis du definerede en uigennemsigtig type i overskriften, som ovenfor, ville det være en god praksis. Men så skal du ikke bruge nogen henvisning til _arraylist i din kode. Brug altid typedef “d navn for at undgå forvirring.
Funktionsnavnspræfikset skal også følge nøjagtigt navnet på typen, så for ArrayList skal alle funktioner være forud for ArrayList_, fx:
ArrayList * ArrayList_create(); Jeg vil også foreslå, at du undgår tightlypacked navne, som i arraylist_getsize(). Tilføjelse af understregning for at adskille ord gør dem meget mere læsbare. F.eks.: ArrayList_get_size() .
Problemer med hukommelse :
Lad os se 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; } Første ting usædvanligt her er påstandene. Påstande er ikke den rigtige måde at håndtere en hukommelsesallokeringsfejl på. Plus , de er almindeligvis deaktiverede ved udgivelsesbygninger, så hvis du tilfældigvis løber tør for hukommelse, vil programmet bare gå ned lydløst. Du skal sandsynligvis returnere en NULL i dette tilfælde (måske også logge på stderr) og lade den, der ringer op, håndtere denne fejl, som han / hun ser fit.
Andet problem her er med calloc(). Du tildeler to ugyldige markører, men size er sat til nul. Jeg forstår ikke rigtig pointen med dette. Da din struktur er mere som og matrix af arrays, så er en liste, hvad du skal gøre er at tildele arrayet med pegepinde med en foruddefineret standardstørrelse og derefter tildele de individuelle arrays efter behov. matrixen med markører efter behov. Hvordan arraylist_create() skal se ud:
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; } Et andet stort hukommelsesproblem er den konstante re-allokeringer udført af arraylist_add() og arraylist_remove().
Fjern bør ikke krympe sekvensen. Hold dette mellemrum rundt, hvis arrayet vokser igen i fremtiden. Du kan tilføje en eksplicit måde at lade brugeren krympe lageret om nødvendigt (a la std::vector::shrink_to_fit()).
Tilføjelse til array kan fås til at køre i amortiseret konstant tid, hvis du foruddeler lagerplads med en større størrelse end den anmodede. (igen inspireret af STL vector).
sizeof fejl :
Dette returnerer ikke, hvad du forventer:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } sizeof operatøren returnerer altid størrelsen på den type, den anvendes på. Det kan ikke udlede størrelsen på et array peget af en markør, fordi det er en kompileringstidsoperation. arraylist_getsizeof() returnerer altid den samme værdi, størrelsen på en ugyldig markør, som vil være 4 eller 8, afhængigt af arkitekturen.
Brug påstande til at kontrollere invarianter :
Du skal assert at *list parameter for hver funktion er gyldig. Dette er en forudsætning for enhver funktion, de kan ikke arbejde uden en gyldig ArrayList forekomst, så du skal hævde, at når funktionen først kommer ind.
Diverse :
Du behøver ikke kontrollere, om markøren er null inden frigørelse . I arraylist_deallocate() if (list->data != NULL) -kontrollen behøves ikke.
arraylist_deallocate ville være mere symmetrisk med arraylist_create hvis den hedder arraylist_destroy.
Kommentarer
- Hvordan kan jeg korrekt kontrollere, om jeg har en gyldig
ArrayListforekomst?Det, jeg hidtil har, er en makro, der kontrollerer for en bestemt værdi af et nyt felt, jeg tilføjede tilstruct _arraylist. Da strukturdeklarationen ikke er ‘ t tilgængelig i overskriften, kanArrayListbrugergrænsefladen ikke få adgang til noget felt direkte (dvs. han skal bruge et af indpakningsfunktionerne). Og jeg gav specifikt ‘ ingen anelse om dette felt .. - @AmrAyman, afhænger af din definition af gyldig, men jeg vil sige, at den mindste validering ville være at kontrollere, at
ArrayList-markøren ikke er nul, og atArrayList::dataheller ikke er nul. Du kan også kontrollere, at hver matrix idataikke er nul:assert( list->data[i] != NULL );
Svar
Lad os tale om performance
Hvad hvis du har brug for din liste meget ofte?
Lad os se nærmere på funktionen arraylist_add; hvis jeg har brug for en liste med 1 million bytes, hvilket er 1 MB, omfordeles din data struct-medlem 1 million gange.
Det er den nederste del af din liste!
Forslag
Tildel hukommelse med bidder F.eks. bruger C ++ std::vector stigende størrelse af tilføjede klumper afhængigt af den aktuelle størrelse på std::vector.
Dette øges gøre det par gange med det formål at tilføje nye elementer.
Lad os tale om kode som den er
Prøv at implementere noget elegant, men simpelt programflow.
Opret værditype (int) ArrayList, som i stedet tildeler hukommelse med stykker for at omfordele det fulde array og tilføje noget listeopførsel under emhætten. Jeg mener en liste over klumper, du skal stadig administrere det.
Her er min løsning med eksempel på at bruge data klumper til hver node i stedet for at omfordele noder. Forskellig chunck-størrelse kan være bedst til et af formålene: at skrive, læse lange arrays; r \ w korte arrays; fjernelse af elementer; osv.
#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
- Jeg respekterer din interesse. Dette er dog C, ikke C ++. Hvis det var C ++, ville jeg bare bruge vektorer til at gøre det ..
- @AmrAyman, tjek det
- At ‘ er imponerende! Men jeg vil have en arraylist, ikke en linket liste. Selvom implementeringen af din linkede liste her er mere avanceret end den normale strukturimplementering, løste glampert problemet.
- Om præstationsgevinsten. Der er ikke ‘ t virkelig så meget: Min implementering er afhængig af bunken, normalt fordi den er afhængig af en matrix; Med venlig hilsen stærkt på rekursion, og at ‘ er naturligt, fordi du ‘ stoler på noder. Det ville også være en masse langsomt at frigøre listen, fordi du ‘ enten bruger rekursion (som er meget lav på ydeevnen) eller en ret kompliceret mens loop ..
Svar
Et problem, som ikke andre nævner, er at din test ikke fungerer. Det ser ud til at virke, men i virkeligheden virker det ikke. Når du føjer værdier til listen, sender du adressen til variablen i:
arraylist_add(list, &i); Og arraylist_add gemmer bare den videregivne værdi (som den skal):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Så når du er gået igennem i = 0. .99 alt hvad du har på listen er i 100 gange. Når du læser dataene tilbage, bruger du igen loopvariablen i og ændrer dens værdi fra 0..99, og den udskrevne værdi ser rigtig ud. Men du ser virkelig bare værdien af løkkevariablen, der ændres af sløjfen.
Hvis du ikke tror på mig, skal du udskrive en hvilken som helst fast matrixindgang, f.eks. 50, som i:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); den udskrives 100 (eller hvad værdien for i øjeblikket er).
I stedet skal du gemme den reelle værdi:
arraylist_add(list, (void*) i); og udskrive det skal du kaste værdien til den type, den var, da den gik ind:
printf("i: %d\n", (int)arraylist_get(list, t)); Der er mange andre problemer med koden, som andre har bemærket . Det grundlæggende design af at bruge din arraylist_setdata til at foretage alle ændringer er forkert. Omallokering ved hver ændring er bare dårlig – realloc er dyrt. Og den grundlæggende idé om en liste, der gemmer ting ved at foregive, at de er void*, er forvirrende for mig og virker en dårlig idé.
Kommentarer
- Nå, du bemærker muligvis ikke det, men at ‘ er nøjagtigt hvad jeg ville teste. At markører gemmes og hentes korrekt gennem funktionsindpakningerne ..
- At gemme ting som
void *er ikke ‘ t virkelig så slemt som det ser ud til.Tænk over det,void *gemmer simpelthen en hukommelsesadresse, som jeg ikke ‘ ikke bryr mig om typen af den værdi, der er gemt på. Kort sagt skal arrayet kun gemme hukommelsesadresser, og at ‘ praktisk taget er den eneste måde, at C ville håndtere forskellige typer i en enkelt array .. - Om
realloc, jeg er enig med dig, men jeg kunne bare ikke ‘ ikke finde en bedre måde at skabe en dynamisk array. I hvert fald fulgte jeg glampert ‘ s råd om at indpakke en speciel funktion til det,shrink_to_fit-funktionen .. - Jeg forestillede mig, at du forsøgte at gemme skalardata i variabel størrelse ved at gemme dem i en
void*(forskellige mennesker har indsendt kode for at gøre det). Hvis du virkelig ville gemme markører, så ville en bedre test være at gemme et antal forskellige markører i en kendt rækkefølge og kontrollere, at du får dem tilbage i samme rækkefølge – i stedet for at gemme den samme markør 100 gange. Problemet med lagring af markører er, at det objekt, der peges på, skal være vedvarende i hele levetiden for dets adresse i arrayet. På trods af tomrummet * kan du selvfølgelig ikke blande typer inden for et array. - Bare en anden måde at gøre det samme på, hvor arrayet følger op straks efter strukturens afslutning. Denne metode har sine egne problemer, så glem at jeg nævnte den.
vectori C / C ++, ikke som enArrayListfra Java-verdenen.