Az ArrayList funkcionalitást a C-ben a következőképpen valósítottam meg:
#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 “Ezt így tesztelem:
#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; } Remekül működik, bár realloc néha összeomlik a program. javítson ezen?
Megjegyzések
Válasz
Először egy szó a elnevezésről:
A név, amelyet kiválasztott a te típusod, _arraylist rossz név a könyvtár interfész típusának. A _ kezdetű nevek nem kellemesek a felhasználói kódban. Általában a könyvtár belsejében használják őket. A jobb nevek a következők lehetnek: ArrayList vagy array_list.
Valójában a használati példában a ArrayList. Ez azt jelenti, hogy az itt nem szereplő fejlécben van valami ilyesmi?
typedef _arraylist ArrayList; Ha átlátszatlan típust definiáltál a fejlécben, mint fent, ez jó gyakorlat lenne. De akkor ne használjon a _arraylist hivatkozást a kódban. Az összetévesztés elkerülése érdekében mindig használja a typedef “d nevet.
A függvénynév előtagnak pontosan a típus nevét is követnie kell, ezért a ArrayList esetén az összes függvényt meg kell adni. a ArrayList_ előtagot, pl .:
ArrayList * ArrayList_create(); Azt is javasoljuk, hogy kerülje az tightlypacked nevek, például a arraylist_getsize() címkéknél. Ha aláhúzást adunk a szavak elkülönítéséhez, azok sokkal olvashatóbbak. Például: ArrayList_get_size() .
A memóriával kapcsolatos problémák :
A 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; } Első dolog, ami szokatlan, ezek az állítások. Az állítások nem alkalmasak a memóriaelosztási hiba kezelésére. , általában le vannak tiltva a kiadás buildjeinél, így kiadáskor, ha esetleg elfogyna a memória, a program csak csendesen összeomlik. Ebben az esetben valószínűleg vissza kell adnia egy NULL -t (esetleg be kell jelentkeznie a stderr címre is), és hagynia kell, hogy a hívó kezelje ezt a hibát, ahogy látja fit.
A második probléma itt a calloc(). 2 érvénytelen mutatót oszt ki, azonban a size értéke nulla. Nem igazán értem ennek a lényegét. Mivel a struktúrája inkább hasonlít és tömbök tömbje, majd egy lista, akkor azt kell tennie, hogy elosztja a mutató tömböt valamilyen előre definiált alapértelmezett méretűvel, majd szükség szerint kiosztja az egyes tömböket. igény szerint mutató tömb. Hogyan kell kinéznie 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; } Egy másik nagy memóriaprobléma az állandó az újrafoglalásokat a arraylist_add() és a arraylist_remove() végezte.
Az eltávolítás nem csökkenti a sorrendet. Tartsa ezt a helyet körül, ha a tömb a jövőben újra növekszik. Felvehet egy kifejezett módszert arra, hogy a felhasználó szükség esetén csökkentse a tárhelyet (a la std::vector::shrink_to_fit()).
Hozzáadás a A tömb amortizált-állandó időben futtatható, ha előre kiosztja a tárhelyet a kért méretnél. (Ismét az STL vector ihlette).
sizeof hiba :
Ez nem adja vissza azt, amire számított:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } A sizeof operátor mindig visszaadja az alkalmazott típus méretét. Nem tud következtetni egy mutató által mutatott tömb nagyságára, mert ez fordítási idejű művelet. A arraylist_getsizeof() mindig ugyanazt az értéket adja vissza, az érvénytelen mutató méretét, amely az architektúrától függően 4 vagy 8 lesz.
Állítások használatával ellenőrizze az invariánsokat :
assert Minden funkció div id = “1979ffde07”>
paramétere érvényes. Ez minden függvény előfeltétele, érvényesArrayListpéldány nélkül nem tudnak működni, ezért állítsd be, hogy amint a függvény belép.
Vegyes :
Nem kell ellenőriznie, hogy a mutató null, mielőtt felszabadítaná . A arraylist_deallocate() mezőben a if (list->data != NULL) ellenőrzés nem szükséges.
arraylist_deallocate szimmetrikusabb lenne a arraylist_create vel, ha arraylist_destroy.
Megjegyzések
- Hogyan megfelelően ellenőrizhetem, hogy van-e érvényes
ArrayListpéldányom?Eddig egy olyan makró áll rendelkezésemre, amely egystruct _arraylistfájlhoz hozzáadott új mező konkrét értékét ellenőrzi. Mivel a struct deklaráció nem ‘ t érhető el a fejlécben, aArrayListfelület felhasználói nem férhetnek hozzá közvetlenül egyetlen mezőhöz sem (vagyis a következők egyikét kell használniuk: a burkoló funkciók). És kifejezetten nem adtam ‘ semmilyen nyomot erről a mezőről. - @AmrAyman, az érvényes definíciójától függ, de azt mondanám, hogy a minimális érvényesítés ellenőrizze, hogy a
ArrayListmutató nem null-e, és hogy aArrayList::dataszintén nem null-e. Ellenőrizheti azt is, hogy adataösszes tömbje nem null-e:assert( list->data[i] != NULL );
Válasz
Beszéljünk a teljesítményről
Mi van, ha nagyon gyakran kell használni a listáját?
Nézzük meg közelebbről a arraylist_add függvényt; ha szükségem van egy 1 millió bájtos listára, amely 1 MB, akkor átcsoportosítja a data struct tag milliószor.
Ez a lista legalsó része!
Javaslatok
Rendeljen memóriát darabokra , pl., a C ++ std::vector növekvő méretű csonkokat használ, a std::vector jelenlegi méretétől függően.
Ez megnő néhányszor előadni új elemek hozzáadása céljából.
Beszéljünk a kódról a jelenlegi állapotban
Próbáljon meg valami elegáns, de egyszerű programfolyamatot megvalósítani.
Hozzon létre értéktípust (int) ArrayList, amely helyette darabokra osztja a memóriát csoportosítsa át a tömböt, és adjon hozzá néhány viselkedést a motorháztető alatt. Úgy értem, hogy a darabok listája, akkor is kezelnie kell.
Íme a megoldásom azzal a példával, hogy adatcsomókat használok minden csomóponthoz az átcsoportosítás helyett. csomópontok. Különböző chunck méretű lehet a legjobb az egyik célra: írás, hosszú tömbök olvasása; r \ w rövid tömbök; elemek eltávolítása; stb.
#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]); } } } Megjegyzések
- Tisztelem az érdeklődését. Ez azonban C, nem C ++. Ha C ++ lenne, akkor csak vektorokat használnék erre.
- @AmrAyman, ellenőrizze
- Ez ‘ lenyűgöző! De szeretnék egy tömblistát, nem pedig linkelt listát. Bár a linkelt lista megvalósítása itt fejlettebb, mint a normál struktúrás megvalósítás, a glampert megoldotta a problémát.
- A teljesítménynövekedésről. Nincs igazán olyan sok ‘: A megvalósításom a kupacra támaszkodik, általában azért, mert tömbre támaszkodik; A tiéd nagyban függ a rekurziótól, és ez ‘ természetes, mert ‘ csomópontokra támaszkodik. Ezenkívül a lista felszabadítása sok lassú lenne viszonylag lassan, mert ‘ vagy rekurziót használ (ami tényleg alacsony a teljesítményen), vagy meglehetősen bonyolult míg a hurok ..
Válasz
A mások által nem említett probléma az, hogy a tesztje nem működik. Úgy tűnik, hogy működik, de a valóságban nem. Ha értékeket ad hozzá a listához, átadja a i változó címét:
arraylist_add(list, &i); És arraylist_add csak elmenti az átadott értéket (ahogy kell):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Tehát ha egyszer áthúzódott az i = 0. .99 a listában csak az i címe van 100-szor. Amikor visszaolvassa az adatokat, újra a i ciklusváltozót használja, és az értékét 0..99 értékre módosítja, és a kinyomtatott érték jól néz ki. De valójában csak azt látja, hogy a ciklusváltozó értékét a hurok módosítja.
Ha nem hiszed, nyomtass ki bármilyen rögzített tömb bejegyzést, például 50-et, mint a következőben:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); kinyomtat 100 (vagy bármi is legyen az i értéke jelenleg).
Ehelyett a valós értéket kell tárolnia:
arraylist_add(list, (void*) i); és a nyomtatáshoz ki kell adnod az értéket arra a típusra, amelyik akkor volt, amikor belépett:
printf("i: %d\n", (int)arraylist_get(list, t)); Sok más probléma van a kóddal, amint mások megjegyezték . A arraylist_setdata eszköz minden módosítás elvégzésének alapja meghibásodott. Helytelen az átcsoportosítás minden változásnál – realloc drága. És A lista alapötlete, amely úgy tárol dolgokat, hogy úgy tesz, mintha void* lenne, számomra zavaró és rossz ötletnek tűnik.
Megjegyzések
- Nos, lehet, hogy nem veszi észre, de ez ‘ pontosan olyan, amit tesztelni szerettem volna. Hogy a mutatókat tárolják és lekérik helyesen a funkcióburkolatokon keresztül ..
- A dolgok
void *tárolása nem ‘ valójában olyan rossz, mint amilyennek látszik.Gondoljon csak bele:void *egyszerűen eltárol egy memóriacímet, amelyet nem érdekel a div tárolt érték típusa. ‘ Röviden: a tömb csak állítólag memóriacímeket tárol, és ez ‘ gyakorlatilag az egyetlen módja annak, hogy C egyetlen tömbben kezelje a különféle típusokat. - A
reallocnévről egyetértek veled, de nem tudtam ‘ megtalálni a dinamikus tömb. Mindenesetre követtem a glampert ‘ tanácsát, hogy csomagoljak egy speciális függvényt, ashrink_to_fitfüggvényt. - Úgy képzeltem, hogy változó méretű skaláris adatokat próbál meg menteni egy
void*fájlban való tárolással (ehhez különféle emberek küldtek kódot). Ha valóban mutatókat szeretett volna tárolni, akkor jobb teszt lenne, ha számos különböző mutatót tárolna ismert sorrendben, és ellenőrizné, hogy ugyanabban a sorrendben kapja-e vissza őket – ahelyett, hogy ugyanazokat mentené mutató 100-szor. A mutatók tárolásával az a probléma, hogy a mutatott objektumnak állandónak kell lennie a tömbben lévő címe fennállásának élete során. A void * ellenére természetesen nem keverhet össze típusokat egy tömbön belül. - Csak ugyanaz a dolog más módja, ahol a tömb közvetlenül a szerkezet vége után következik. Ennek a módszernek megvannak a maga problémái, ezért felejtsd el, hogy említettem.
vectornéven hivatkoznak C / C ++, nem pedigArrayListnéven a Java világból.