Funkci ArrayList v C jsem implementoval takto:
#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 „Testuji to takto:
#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; } Funguje to dobře, i když realloc někdy program spadne. Mohu vylepšit to?
Komentáře
Odpověď
Nejprve slovo o pojmenování :
Jméno, pro které jste se rozhodli váš typ, _arraylist je špatný název pro typ rozhraní knihovny. S názvy začínajícími _ se v uživatelském kódu nepracuje příjemně. Obvykle se používají uvnitř interních knihoven. Lepší názvy by byly ArrayList nebo array_list.
Ve vašem příkladu použití vlastně máte ArrayList. Znamená to, že v záhlaví, které zde není zahrnuto, máte něco takového?
typedef _arraylist ArrayList; Pokud jste v záhlaví definovali neprůhledný typ, stejně jako výše by to byl dobrý postup. Ale pak byste ve svém kódu neměli používat žádný odkaz na _arraylist. Abyste předešli nejasnostem, používejte vždy typedef „d name.
Předpona názvu funkce by měla také přesně následovat za názvem typu, takže pro ArrayList by měly být všechny funkce s předponou ArrayList_, např .:
ArrayList * ArrayList_create(); Navrhuji také, abyste se vyhnuli tightlypacked jména, jako v arraylist_getsize(). Přidání podtržítka k samostatným slovům je činí mnohem čitelnějšími. Např .: ArrayList_get_size() .
Problémy s pamětí :
Podívejme se na 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; } První věcí, která je zde neobvyklá, jsou tvrzení. Tvrzení nejsou správným způsobem, jak vyřešit selhání přidělení paměti. Plus , jsou při sestaveních vydání obvykle zakázány, takže při vydání, pokud by vám došlo paměť, program by se tiše zhroutil. Pravděpodobně byste v tomto případě měli vrátit NULL (možná se také přihlásit na stderr) a nechat volajícího zpracovat tuto chybu, jak vidí fit.
Druhým problémem je calloc(). Přidělujete 2 neplatné ukazatele, size je však nastaven na nulu. Opravdu to nechápu. Jelikož je vaše struktura spíše podobná a pole polí než seznam, měli byste přidělit pole ukazatelů s nějakou předdefinovanou výchozí velikostí a poté podle potřeby přidělit jednotlivá pole. pole ukazatelů na vyžádání. Jak by měl vypadat 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; } Dalším velkým problémem s pamětí je konstanta nové přidělení provedené arraylist_add() a arraylist_remove().
Odebrání by nemělo zmenšit sekvenci. Pokud je toto místo prázdné pole v budoucnu opět naroste. Můžete přidat explicitní způsob, jak umožnit uživateli v případě potřeby zmenšit úložiště (a la std::vector::shrink_to_fit()).
Přidání do pole lze nastavit tak, aby běhalo v konstantní době, pokud předem přidělíte úložiště s větší velikostí, než je požadováno. (Opět inspirováno STL vector).
sizeof chyba :
To nevrátí to, co očekáváte:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } sizeof operátor vždy vrátí velikost typu, na který je aplikován. Nemůže odvodit velikost pole, na které ukazuje ukazatel, protože se jedná o operaci kompilace. arraylist_getsizeof() vždy vrátí stejnou hodnotu, velikost prázdného ukazatele, která bude 4 nebo 8, v závislosti na architektuře.
Použijte tvrzení ke kontrole invariants :
Měli byste assert že *list každé funkce je platný. Toto je předpoklad každé funkce, nemohou fungovat bez platné ArrayList instance, takže byste měli tvrdit, že jakmile funkce vstoupí.
Různé :
Není třeba kontrolovat, zda je ukazatel null before freeing it . V arraylist_deallocate() je kontrola if (list->data != NULL) neoznačená.
arraylist_deallocate by bylo více symetrické s arraylist_create, pokud je pojmenováno arraylist_destroy.
Komentáře
- Jak mohu správně zkontrolovat, zda mám platnou
ArrayListinstanci?To, co zatím mám, je makro, které kontroluje konkrétní hodnotu nového pole, které jsem přidal dostruct _arraylist. Protože deklarace struktury není v záhlaví k dispozici ‚ t, nemůže uživatel rozhraníArrayListpřímo přistupovat k žádnému poli (tj. Musí použít jedno z funkce obálky). A konkrétně jsem o tomto poli nedělal ‚ ponětí. - @AmrAyman, záleží na vaší definici platného, ale řekl bych, že minimální validace by zkontrolujte, zda ukazatel
ArrayListnení null a žeArrayList::datataké není null. Můžete také zkontrolovat, zda každé pole vdatanení null:assert( list->data[i] != NULL );
Odpověď
Pojďme si promluvit o výkonu
Co když potřebujete seznam používat velmi často?
Pojďme se blíže podívat na funkci arraylist_add; pokud potřebuji seznam s 1 milionem bajtů, což je 1 MB, přidělí vaše data člen struktury 1 milionkrát.
Je to nejnižší část vašeho seznamu!
Návrhy
Přidělte paměť po částech např. C ++ std::vector používá rostoucí velikost připojených bloků v závislosti na aktuální velikosti std::vector.
Tím se zvýší proveďte to několikrát za účelem přidání nových prvků.
Pojďme mluvit o kódu tak, jak je
Zkuste implementovat nějaký elegantní, ale jednoduchý tok programu.
Vytvořit typ hodnoty (int) ArrayList, který místo toho přidělí paměť chuncks přerozdělit celé pole a přidat nějaké chování seznamu pod kapotu. Mám na mysli seznam diskových bloků, stále je potřeba je spravovat.
Zde je moje řešení s příkladem použití bloků dat pro každý uzel namísto přerozdělení uzly. Různé velikosti chunck může být nejlepší pro jeden z účelů: psaní, čtení dlouhých polí; krátká pole; odstraňování prvků; atd.
#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]); } } } Komentáře
- Respektuji váš zájem. Toto je však C, ne C ++. Pokud by to bylo C ++, použil bych k tomu pouze vektory.
- @AmrAyman, zkontrolujte to
- to je ‚ působivé! Chci ale mít seznam skladeb, nikoli propojený seznam. Ačkoli vaše implementace propojeného seznamu je zde pokročilejší než běžná implementace struktury, glampert problém vyřešil.
- O zvýšení výkonu. ‚ toho opravdu není tolik: Moje implementace se spoléhá na hromadu, obvykle proto, že se spoléhá na pole; Vaše se do značné míry spoléhá na rekurzi a to je ‚ přirozené, protože ‚ spoléháte na uzly. Uvolnění seznamu by bylo také relativně relativně pomalé, protože ‚ d používáte rekurzi (která má opravdu nízký výkon), nebo je to docela komplikované while loop ..
Odpověď
Jiní nezmínili problém, že váš test nefunguje. Vypadá to, že funguje, ale ve skutečnosti to nefunguje. Když do seznamu přidáte hodnoty, předáváte adresu proměnné i:
arraylist_add(list, &i); And arraylist_add pouze uloží předanou hodnotu (jak by měla):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Takže jakmile projdete smyčkou i = 0. 0,99 vše, co máte v seznamu, je adresa i 100krát. Když čtete data zpět, znovu použijete proměnnou smyčky i a upravíte její hodnotu od 0..99 a vytištěná hodnota vypadá správně. Ale ve skutečnosti právě vidíte hodnotu proměnné smyčky, kterou smyčka upravuje.
Pokud mi nevěříte, vytiskněte jakoukoli položku pevného pole, např. 50, jako v:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); vytiskne se 100 (nebo jakákoli hodnota i aktuálně je).
Místo toho byste měli ukládat skutečnou hodnotu:
arraylist_add(list, (void*) i); a tisknout zjistíte, že musíte vložit hodnotu typu, jaký byl, když vstoupil:
printf("i: %d\n", (int)arraylist_get(list, t)); Existuje mnoho dalších problémů s kódem, jak poznamenali jiní . Základní design používání arraylist_setdata k provádění všech úprav je špatný. Přerozdělení při každé změně je prostě špatné – realloc je drahý. A základní myšlenka seznamu ukládajících věci předstíráním, že jsou void*, je pro mě matoucí a zdá se být špatným nápadem.
Komentáře
- Možná si to nevšimnete, ale to ‚ je přesně to, co jsem chtěl otestovat. Tyto ukazatele se ukládají a načítají správně přes obálky funkcí ..
- Ukládání věcí jako
void *není ‚ opravdu tak špatné, jak se zdá.Přemýšlejte o tom,void *jednoduše uloží adresu paměti, která mě ‚ nezajímá o typ hodnoty uložené na. Stručně řečeno, pole má pouze ukládat adresy paměti, a to je ‚ prakticky jediný způsob, jak by se C zabývalo různými typy v jednom poli .. - O
realloc, souhlasím s vámi, ale nemohl jsem ‚ najít lepší způsob, jak vytvořit dynamický pole. Každopádně jsem se řídil radou glampert ‚ zabalit k tomu speciální funkci, funkcishrink_to_fit.. - Představoval jsem si, že se pokoušíte uložit skalární data proměnné velikosti jejich uložením do
void*(k tomu odeslali kód různí lidé). Pokud jste opravdu chtěli ukládat ukazatele, lepší test by bylo uložit několik různých ukazatelů ve známém pořadí a zkontrolovat, zda je dostanete zpět ve stejném pořadí – místo uložení stejných ukazatel 100krát. Problém s ukládáním ukazatelů spočívá v tom, že objekt, na který ukázal, musí být trvalý po celou dobu existence jeho adresy v poli. Přes prázdnotu * samozřejmě nemůžete kombinovat typy v jednom poli. - Jen jiný způsob, jak dělat totéž, kde pole navazuje bezprostředně po konci struktury. Tato metoda má své vlastní problémy, takže zapomenout, že jsem ji zmínil.
vectorv C / C ++, nikoli jakoArrayListze světa Java.