Am implementat funcționalitatea ArrayList în C după cum urmează:
#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 „Îl testez astfel:
#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; } Funcționează bine, deși realloc uneori blochează programul. Pot îmbunătățiți acest lucru?
Comentarii
Răspuns
Mai întâi, un cuvânt despre numirea :
Numele pentru care ați ales tipul dvs., _arraylist este un nume greșit pentru un tip de interfață de bibliotecă. Numele care încep cu _ nu sunt plăcute de utilizat în codul de utilizator. Sunt utilizate în mod obișnuit în interiorul bibliotecii. Numele mai bune ar fi ArrayList sau array_list.
De fapt, în exemplul dvs. de utilizare, aveți ArrayList. Asta înseamnă că în antet, care nu este inclus aici, aveți așa ceva?
typedef _arraylist ArrayList; Dacă ați definit un tip opac în antet, ca mai sus, ar fi o bună practică. Dar atunci nu ar trebui să utilizați nicio referință la _arraylist în codul dvs. Utilizați întotdeauna „d numele” pentru a evita confuzia.
Prefixul numelui funcției trebuie să urmeze exact numele tipului, deci pentru ArrayList toate funcțiile ar trebui să fie a prefixat ArrayList_, de exemplu:
ArrayList * ArrayList_create(); De asemenea, aș sugera să evitați , ca în arraylist_getsize(). Adăugarea unui subliniat pentru a separa cuvintele le face mult mai lizibile. De exemplu: ArrayList_get_size() .
Probleme cu memoria :
Să vedem 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; } Primul lucru neobișnuit aici este afirmațiile. Afirmațiile nu sunt modalitatea corectă de a gestiona o eroare de alocare a memoriei. Plus , sunt dezactivate în mod obișnuit la versiunile de lansare, deci la lansare, dacă vi s-ar întâmpla să rămâneți fără memorie, programul s-ar bloca în tăcere. Probabil ar trebui să returnați un NULL în acest caz (poate, de asemenea, să vă conectați la stderr) și să lăsați apelantul să gestioneze această eroare pe măsură ce vede el / ea fit.
A doua problemă este cu calloc(). Alocați 2 pointeri de gol, cu toate acestea, size este setat la zero. Nu îmi dau seama cu adevărat. Deoarece structura dvs. este mai asemănătoare și o serie de matrici, atunci o listă, ceea ce ar trebui să faceți este să alocați matricea de indicatori cu o anumită dimensiune implicită predefinită, apoi să alocați matricele individuale după cum este necesar. matrice de indicatori la cerere. Cum ar trebui să arate arraylist_create():
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; } O altă problemă importantă de memorie este constanta realocările făcute de arraylist_add() și arraylist_remove().
Eliminare nu ar trebui să micșoreze secvența. Păstrați spațiul în jur dacă matricea crește din nou în viitor. Puteți adăuga un mod explicit de a permite utilizatorului să micșoreze spațiul de stocare dacă este necesar (a la std::vector::shrink_to_fit()).
Adăugarea la matricea poate fi executată în timp constant-amortizat dacă alocați în prealabil spațiul de stocare cu o dimensiune mai mare decât cea solicitată. (Din nou inspirat de STL vector).
sizeof greșeală :
Acest lucru nu va returna ceea ce vă așteptați:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } sizeof operatorul returnează întotdeauna dimensiunea tipului căruia i se aplică. Nu poate deduce dimensiunea unui tablou îndreptat de un pointer, deoarece este o operație de compilare. arraylist_getsizeof() va returna întotdeauna aceeași valoare, dimensiunea unui indicator gol, care va fi 4 sau 8, în funcție de arhitectură.
Utilizați afirmațiile pentru a verifica invarianții :
Ar trebui să assert div id = „1979ffde07”>
parametrul fiecărei funcții este valid. Aceasta este o condiție prealabilă a fiecărei funcții, acestea nu pot funcționa fără oArrayListinstanță validă, deci ar trebui să afirmați că odată ce funcția intră.
Diverse :
Nu trebuie să verificați dacă indicatorul este nul înainte de eliberare . În arraylist_deallocate() verificarea if (list->data != NULL) nu este activată.
arraylist_deallocate ar fi mai simetric cu arraylist_create dacă este numit arraylist_destroy.
Comentarii
- Cum pot corect verifica dacă am o instanță validă
ArrayList?Ceea ce am până acum este o macrocomandă care verifică o anumită valoare a unui câmp nou pe care l-am adăugat lastruct _arraylist. Deoarece declarația struct nu este ‘ t disponibilă în antet, utilizatorul interfețeiArrayListnu poate accesa niciun câmp direct (adică trebuie să utilizeze unul dintre funcțiile de împachetare). Și în mod specific nu ‘ nu am dat niciun indiciu despre acest câmp .. - @AmrAyman, depinde de definiția dvs. de valid, dar aș spune că validarea minimă ar fi verificați dacă indicatorul
ArrayListnu este nul și căArrayList::datanu este, de asemenea, nul. De asemenea, puteți verifica dacă fiecare matrice dindatanu este nulă:assert( list->data[i] != NULL );
Răspunde
Permite să vorbim despre performanță
Ce se întâmplă dacă trebuie să folosești lista foarte frecvent?
Să vedem mai îndeaproape funcția arraylist_add; dacă am nevoie de o listă cu 1 milion de octeți, care este 1MB, acesta va reatribui data struct membru de 1 milion de ori.
Este partea cea mai de jos a listei dvs.!
Suggestions
Alocați memoria prin bucăți , de exemplu, C ++ std::vector folosește dimensiuni crescânde ale bucăților anexate în funcție de dimensiunea actuală a std::vector.
Acest lucru va crește perfecționați-o de câteva ori în scopul adăugării de elemente noi.
Permiteți să vorbim despre cod așa cum este
Încercați să implementați un flux de program elegant, dar simplu. „4ab446b933”>
Creați un tip de valoare (int) ArrayList, care va aloca memoria în loc de blocuri de realocare a matricei complete și adăugarea unui anumit comportament de listă sub capotă. Vreau să spun listă de bucăți, trebuie totuși să o gestionați.
Iată soluția mea cu un exemplu de utilizare a unor bucăți de date pentru fiecare nod în loc de realocare noduri. Diferite dimensiuni de chunck pot fi cele mai bune pentru unul dintre scopuri: scrierea, citirea matricilor lungi; r \ w tablouri scurte; eliminarea elementelor; 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]); } } } Comentarii
- Vă respect interesul. Cu toate acestea, acesta este C, nu C ++. Dacă ar fi C ++, aș folosi doar vectori pentru a face asta ..
- @AmrAyman, verificați-l
- Impresionantul ‘! Dar vreau să am un arraylist, nu o listă legată. Deși implementarea listei conectate aici este mai avansată decât implementarea structurilor normale, glampert a rezolvat problema.
- Despre câștigul de performanță. Nu există ‘ într-adevăr atât de mult: Implementarea mea se bazează pe heap, în mod normal, deoarece se bazează pe o matrice; Al tău se bazează în mare măsură pe recursivitate și este ‘ firesc, deoarece ‘ te bazezi pe noduri. De asemenea, eliberarea listei ar fi un lot relativ lent, deoarece ‘ fie utilizați recursivitatea (care este într-adevăr scăzută în ceea ce privește performanța), fie un proces destul de complicat while loop ..
Răspuns
O problemă nemenționată de alții este că testul dvs. nu funcționează. Se pare că funcționează, dar în realitate nu funcționează. Când adăugați valori la listă, treceți adresa variabilei i:
arraylist_add(list, &i); Și arraylist_add salvează doar valoarea trecută (așa cum ar trebui):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Deci, odată ce ați parcurs i = 0. .99 tot ce ai în listă este adresa de 100 de ori. Când citiți datele înapoi, utilizați din nou variabila buclă i și modificați valoarea acesteia de la 0..99, iar valoarea imprimată arată corect. Dar vedeți doar valoarea variabilei buclă modificată de buclă.
Dacă nu mă credeți, tipăriți orice intrare matricială fixă, de ex. 50, ca în:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); se va imprima 100 (sau oricare ar fi valoarea i în prezent).
În schimb, ar trebui să stocați valoarea reală:
arraylist_add(list, (void*) i); și să imprimați trebuie să aruncați valoarea la tipul pe care îl avea când a intrat:
printf("i: %d\n", (int)arraylist_get(list, t)); Există multe alte probleme cu codul, așa cum au observat alții . Proiectarea de bază a utilizării arraylist_setdata pentru a efectua toate modificările este greșită. Realocarea la fiecare modificare este doar rea – realloc este costisitoare. Și ideea de bază a unei liste care stochează lucruri pretinzând că sunt void* este confuză pentru mine și pare o idee proastă.
Comentarii
- Ei bine, s-ar putea să nu observați acest lucru, dar ‘ este exact ceea ce am vrut să testez. Aceste indicatoare sunt stocate și recuperate corect prin împachetările funcționale ..
- Stocarea lucrurilor ca
void *nu este ‘ într-adevăr atât de rău pe cât pare.Gândiți-vă la asta,void *stochează pur și simplu o adresă de memorie, la care ‘ nu îmi pasă de tipul valorii stocate la. Pe scurt, matricea ar trebui doar să stocheze adrese de memorie și că ‘ este practic singurul mod în care C ar putea face față diferitelor tipuri într-o singură matrice. - Despre
realloc, sunt de acord cu dvs., dar nu am putut ‘ să nu găsesc o modalitate mai bună de a crea o dinamică matrice. Oricum, am urmat sfatul glampert ‘ pentru a împacheta o funcție specială pentru aceasta, funcțiashrink_to_fit.. - Mi-am imaginat că încercați să salvați date scalare de dimensiuni variabile stocându-le într-un
void*(diverse persoane au trimis cod pentru a face acest lucru). Dacă doriți cu adevărat să stocați indicii, atunci un test mai bun ar fi să stocați un număr de diferite indicatori într-o ordine cunoscută și să verificați dacă le recuperați în aceeași ordine – în loc să salvați același lucru indicatorul de 100 de ori. Problema cu stocarea indicatorilor este că obiectul indicat trebuie să fie persistent pe toată durata existenței adresei sale în matrice. În ciuda golului *, desigur, nu puteți amesteca tipuri într-un singur tablou. - Doar un mod diferit de a face același lucru, în care tabloul urmează imediat după sfârșitul structurii. Această metodă are propriile sale probleme, așa că uitați că am menționat-o.
vectorîn C / C ++, nu caArrayListdin lumea Java.