Jeg implementerte ArrayList-funksjonalitet 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 slik:
#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 bra, selv om realloc noen ganger krasjer programmet. Kan jeg forbedre dette?
Kommentarer
Svar
Først et ord om å navngi :
Navnet du har valgt for typen din, _arraylist er et dårlig navn for en type biblioteksgrensesnitt. Navn som starter med _ er ikke hyggelige å jobbe med i brukerkoden. De brukes ofte i biblioteksinterne. Bedre navn ville være ArrayList eller array_list.
I brukseksemplet ditt har du ArrayList. Betyr dette at i overskriften, som ikke er inkludert her, har du noe sånt?
typedef _arraylist ArrayList; Hvis du definerte en ugjennomsiktig type i overskriften, som ovenfor, vil det være en god praksis. Men da bør du ikke bruke noen henvisning til _arraylist i koden din. Bruk alltid typedef «d navn for å unngå forvirring.
Funksjonsnavnet prefiks bør også følge nøyaktig navnet på typen, så for ArrayList bør alle funksjoner være prefikset ArrayList_, f.eks:
ArrayList * ArrayList_create(); Også vil jeg foreslå at du unngår tightlypacked navn, som i arraylist_getsize(). Å legge til en understreking for å skille ord gjør dem mye mer lesbare. F.eks: ArrayList_get_size() .
Problemer med minne :
La oss 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; } Det første som er uvanlig her er påstandene. Påstander er ikke den rette måten å håndtere en minnetildeling på. , de blir ofte deaktivert ved utgivelse, så hvis du tilfeldigvis går tom for minne, vil programmet bare krasje stille. Du bør sannsynligvis returnere en NULL i dette tilfellet (kanskje også logge på stderr) og la innringeren håndtere denne feilen slik han / hun ser passer.
Andre problem her er med calloc(). Du tildeler to ugyldige pekere, men size er satt til null. Jeg skjønner ikke poenget med dette. Siden strukturen din er mer lik og en rekke matriser, så er det en liste. Det du bør gjøre er å tildele en rekke pekere med en forhåndsdefinert standardstørrelse, og deretter tildele de individuelle matriser etter behov. rekke pekere på forespørsel. Hvordan arraylist_create() skal 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; } Et annet stort minnesak er konstant re-allokeringer utført av arraylist_add() og arraylist_remove().
Fjern bør ikke krympe sekvensen. Hold den plassen rundt hvis matrisen vokser igjen i fremtiden. Du kan legge til en eksplisitt måte å la brukeren krympe lagringen om nødvendig (a la std::vector::shrink_to_fit()).
Legger til i array kan fås til å kjøre i amortisert konstant tid hvis du forhåndsdeler lagring med større størrelse enn ønsket. (Igjen inspirert av STL vector).
sizeof feil :
Dette returnerer ikke det 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 alltid størrelsen på typen den brukes på. Det kan ikke utlede størrelsen på en matrise pekt av en peker, fordi det er en kompileringstidsoperasjon. arraylist_getsizeof() vil alltid returnere den samme verdien, størrelsen på en ugyldig peker, som vil være 4 eller 8, avhengig av arkitekturen.
Bruk påstander for å se etter invarianter :
Du bør assert at *list parameteren til hver funksjon er gyldig. Dette er en forutsetning for hver funksjon, de kan ikke fungere uten en gyldig ArrayList forekomst, så du bør hevde at når funksjonen kommer inn.
Diverse :
Du trenger ikke å sjekke om pekeren er null før du frigjør det . I arraylist_deallocate() if (list->data != NULL) sjekken blir ikke trukket.
arraylist_deallocate ville vært mer symmetrisk med arraylist_create hvis hun fikk navnet arraylist_destroy.
Kommentarer
- Hvordan kan jeg ordentlig sjekke om jeg har en gyldig
ArrayListforekomst?Det jeg har så langt er en makro som ser etter en spesifikk verdi av et nytt felt jeg la til istruct _arraylist. Siden struktordeklarasjonen ikke er ‘ t tilgjengelig i overskriften, kanArrayListgrensesnittbruker ikke få tilgang til noe felt direkte (dvs. at han må bruke et av innpakningsfunksjonene). Og jeg spesifikt ga ‘ ingen anelse om dette feltet .. - @AmrAyman, avhenger av din definisjon av gyldig, men jeg vil si at minimumsvalidering ville være å sjekke at
ArrayListpekeren ikke er null og atArrayList::dataheller ikke er null. Du kan også sjekke at hver matrise idataikke er null:assert( list->data[i] != NULL );
Svar
La oss snakke om ytelse
Hva om du trenger å bruke listen din veldig ofte?
La oss se nærmere på funksjonen arraylist_add. Hvis jeg trenger en liste med 1 million byte, som er 1 MB, vil den omfordele data struct-medlem 1 million ganger.
Det er den nederste delen av listen din!
Forslag
Tildel minne med biter C ++ std::vector bruker økende størrelse på tilføyde biter avhengig av gjeldende størrelse på std::vector.
Dette vil øke gir det noen ganger med det formål å legge til nye elementer.
La oss snakke om kode som den er
Prøv å implementere en elegant, men enkel programflyt.
Opprett verditype (int) ArrayList, som tildeler minne i stedet for deler av omfordele hele oppsettet, og legge til litt oppførsel på listen under panseret. Jeg mener en liste over biter, du må fremdeles administrere den.
Her er løsningen min med eksempel på å bruke biter av data for hver node i stedet for å omdisponere noder. Forskjellig størrelse kan være best for en av formålene: å skrive, lese lange matriser; r \ w korte matriser; fjerne 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 imidlertid C, ikke C ++. Hvis det var C ++, ville jeg bare brukt vektorer til å gjøre det ..
- @AmrAyman, sjekk det
- At ‘ er imponerende! Men jeg vil ha en arraylist, ikke en koblet liste. Selv om implementeringen av din lenkede liste her er mer avansert enn den vanlige strukturimplementeringen, løste glampert problemet.
- Om ytelsesgevinsten. Det er ikke ‘ t så mye: Implementeringen min er avhengig av dyngen, vanligvis fordi den er avhengig av en matrise; Vennligst stole tungt på rekursjon, og at ‘ er naturlig fordi du ‘ stoler på noder. Å frigjøre listen vil også være mye tregt, fordi du ‘ enten bruker rekursjon (som er veldig lav på ytelsen), eller en ganske komplisert while loop ..
Svar
Et problem som ikke andre har nevnt, er at testen din ikke fungerer. Det ser ut til å fungere, men i virkeligheten virker det ikke. Når du legger til verdier i listen, sender du adressen til variabelen i:
arraylist_add(list, &i); Og arraylist_add bare lagrer den passerte verdien (som den skal):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Så når du har gått gjennom i = 0. .99 alt du har i listen er adressen til 100 ganger. Når du leser dataene tilbake, bruker du igjen loopvariabelen i og endrer verdien fra 0..99 og verdien som skrives ut ser riktig ut. Men du ser egentlig bare verdien av løkkevariabelen som blir endret av sløyfen.
Hvis du ikke tror meg, kan du skrive ut en hvilken som helst fast oppføring, f.eks. 50, som i:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); den skrives ut 100 (eller hva verdien i for øyeblikket er).
I stedet bør du lagre den virkelige verdien:
arraylist_add(list, (void*) i); og å skrive ut det må du kaste verdien til den typen den var da den gikk inn:
printf("i: %d\n", (int)arraylist_get(list, t)); Det er mange andre problemer med koden, som andre har bemerket . Den grunnleggende utformingen av å bruke arraylist_setdata for å gjøre alle modifikasjoner er feil. Det er bare dårlig å omdisponere ved hver endring – realloc er dyrt. Og grunnideen til en liste som lagrer ting ved å late som om de er void*, er forvirrende for meg og virker en dårlig idé.
Kommentarer
- Vel, du vil kanskje ikke legge merke til det, men at ‘ er nøyaktig det jeg ønsket å teste. At pekerne blir lagret og hentet riktig gjennom funksjonsinnpakningene ..
- Lagring av ting som
void *er ikke ‘ t virkelig så ille som det virker.Tenk på det,void *lagrer ganske enkelt en minneadresse, som jeg ikke ‘ ikke bryr meg om hvilken type verdi som er lagret på. Kort sagt, matrisen skal bare lagre minneadresser, og at ‘ er praktisk talt den eneste måten C ville håndtere forskjellige typer i en enkelt matrise .. - Om
realloc, jeg er enig med deg, men jeg kunne bare ikke ‘ ikke finne en bedre måte å skape en dynamisk array. Uansett fulgte jeg glampert ‘ s råd om å pakke inn en spesiell funksjon for det,shrink_to_fit-funksjonen. - Jeg forestilte meg at du prøvde å lagre skalardata i variabel størrelse ved å lagre dem i en
void*(forskjellige personer har sendt inn kode for å gjøre det). Hvis du virkelig ønsket å lagre pekere, ville en bedre test være å lagre et antall forskjellige pekere i en kjent rekkefølge og å kontrollere at du får dem tilbake i samme rekkefølge – i stedet for å lagre den samme pekeren 100 ganger. Problemet med å lagre pekere er at objektet som det pekes på må være vedvarende hele livet for eksistensen av adressen i matrisen. Til tross for tomrommet * kan du selvsagt ikke blande typer i en matrise. - Bare en annen måte å gjøre det samme på, der matrisen følger umiddelbart etter slutten av strukturen. Den metoden har sine egne problemer, så glem at jeg nevnte den.
vectori C / C ++, ikke som etArrayListfra Java-verdenen.