Funkcję ArrayList zaimplementowałem w języku C w następujący sposób:
#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 „m testuję to w ten sposób:
#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; } Działa dobrze, chociaż realloc czasami powoduje awarię programu. Czy mogę poprawić to?
Komentarze
Odpowiedź
Najpierw słowo o nazewnictwie :
Nazwa, którą wybrałeś Twój typ, _arraylist to zła nazwa dla typu interfejsu biblioteki. Nazwy zaczynające się od _ nie są przyjemne w użyciu w kodzie użytkownika. Są powszechnie używane wewnątrz bibliotek. Lepszymi nazwami byłyby ArrayList lub array_list.
W swoim przykładzie użycia masz ArrayList. Czy to oznacza, że w nagłówku, którego tutaj nie ma, masz coś takiego?
typedef _arraylist ArrayList; Jeśli zdefiniowałeś nieprzezroczysty typ w nagłówku, tak jak powyżej, byłaby to dobra praktyka. Ale wtedy nie powinieneś używać w kodzie żadnego odniesienia do _arraylist. Zawsze używaj nazwy typedef „d, aby uniknąć nieporozumień.
Prefiks nazwy funkcji powinien również występować dokładnie po nazwie typu, więc dla ArrayList wszystkie funkcje powinny być poprzedzony prefiksem ArrayList_, np .:
ArrayList * ArrayList_create(); Ponadto sugerowałbym unikanie tightlypacked nazwy, na przykład arraylist_getsize(). Dodanie podkreślenia do oddzielnych słów sprawia, że są one bardziej czytelne. Np .: ArrayList_get_size() .
Problemy z pamięcią :
Spójrzmy 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; } Pierwszą niezwykłą rzeczą są tutaj asercje. Asercje nie są właściwym sposobem radzenia sobie z awarią alokacji pamięci. Plus , są one zwykle wyłączane w kompilacjach wydania, więc w momencie wydania, jeśli zabraknie pamięci, program po prostu cicho zawiesiłby się. W tym przypadku prawdopodobnie powinieneś zwrócić NULL (może również zalogować się do stderr) i pozwolić dzwoniącemu obsłużyć ten błąd tak, jak widzi fit.
Drugi problem dotyczy calloc(). Przydzielasz 2 void pointers, jednak size jest ustawione na zero. Naprawdę nie rozumiem, o co chodzi. Ponieważ twoja struktura jest bardziej podobna do tablicy tablic niż listy, powinieneś przydzielić tablicę wskaźników z pewnym wstępnie zdefiniowanym domyślnym rozmiarem, a następnie przydzielić poszczególne tablice według potrzeb. tablica wskaźników na żądanie. Jak arraylist_create() powinna wyglądać:
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; } Kolejną poważną kwestią związaną z pamięcią jest stała ponowne alokacje wykonane przez arraylist_add() i arraylist_remove().
Usunięcie nie powinno zmniejszać sekwencji. Zachowaj tę przestrzeń, jeśli tablica ponownie się powiększy w przyszłości. Możesz dodać wyraźny sposób, aby umożliwić użytkownikowi zmniejszenie pamięci, jeśli to konieczne (a la std::vector::shrink_to_fit()).
Dodanie do tablica może być uruchamiana w stałym zamortyzowanym czasie, jeśli wstępnie przydzieli się pamięć o rozmiarze większym niż żądany (ponownie zainspirowany STL vector).
sizeof błąd :
To nie zwróci tego, czego oczekujesz:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } sizeof zawsze zwraca rozmiar typu, do którego jest stosowany. Nie może wywnioskować rozmiaru tablicy wskazywanej przez wskaźnik, ponieważ jest to operacja w czasie kompilacji. arraylist_getsizeof() zawsze zwraca tę samą wartość, rozmiar pustego wskaźnika, który będzie wynosił 4 lub 8, w zależności od architektury.
Użyj asercji, aby sprawdzić niezmienniki :
Należy assert, że *list parametr każdej funkcji jest prawidłowy. Jest to warunek wstępny każdej funkcji, nie mogą one działać bez prawidłowej instancji ArrayList, więc należy zapewnić, że po wejściu funkcji.
Różne :
Nie musisz sprawdzać, czy wskaźnik to null przed zwolnieniem go . W arraylist_deallocate() czek if (list->data != NULL) nie jest potrzebny.
arraylist_deallocate byłoby bardziej symetryczne z arraylist_create o nazwie arraylist_destroy.
Komentarze
- Jak mogę poprawnie sprawdzić, czy mam prawidłową instancję
ArrayList?Do tej pory mam makro, które sprawdza określoną wartość nowego pola, które dodałem dostruct _arraylist. Ponieważ deklaracja struct nie jest ' dostępna w nagłówku, użytkownik interfejsuArrayListnie ma bezpośredniego dostępu do żadnego pola (tzn. Musi użyć jednego z funkcje opakowania). W szczególności nie ' nie dawałem żadnych wskazówek na temat tego pola. - @AmrAyman, zależy od Twojej definicji ważności, ale powiedziałbym, że minimalna walidacja sprawdzać, czy wskaźnik
ArrayListnie ma wartości NULL i czyArrayList::datarównież nie ma wartości NULL. Możesz również sprawdzić, czy każda tablica wdatanie jest pusta:assert( list->data[i] != NULL );
Odpowiedz
Porozmawiajmy o wydajności
A jeśli będziesz bardzo często korzystać z listy?
Przyjrzyjmy się bliżej funkcji arraylist_add; jeśli potrzebuję listy zawierającej 1 milion bajtów, czyli 1 MB, zostanie ona ponownie przydzielona data struct member 1 milion razy.
To najniższa część Twojej listy!
Sugestie
Przydziel pamięć fragmentami , np. C ++ std::vector używa rosnącego rozmiaru dołączanych fragmentów w zależności od aktualnego rozmiaru std::vector.
Zwiększy się Wykonaj to kilka razy w celu dodania nowych elementów.
Porozmawiajmy o kodzie takim, jaki jest
Spróbuj zaimplementować elegancki, ale prosty przepływ programu.
Utwórz typ wartości (int) ArrayList, który zamiast tego przydzieli pamięć według fragmentów ponownie przydziel całą tablicę i dodaj zachowanie listy pod maską. Mam na myśli listę fragmentów, nadal musisz nią zarządzać.
Oto moje rozwiązanie z przykładem wykorzystania fragmentów danych dla każdego węzła zamiast ponownego przydzielania węzły. Różne rozmiary fragmentów mogą być najlepsze do jednego z celów: pisania, czytania długich tablic; r \ w krótkie tablice; usuwanie elementów; itp.
#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]); } } } Komentarze
- Szanuję Twoje zainteresowanie. Jednak to jest C, a nie C ++. Gdyby to był C ++, użyłbym do tego po prostu wektorów …
- @AmrAyman, sprawdź to
- To ' robi wrażenie! Ale chcę mieć listę arraylistę, a nie połączoną listę. Chociaż implementacja listy połączonej tutaj jest bardziej zaawansowana niż zwykła implementacja struktury, glampert rozwiązał problem.
- O wzroście wydajności. Tak naprawdę nie ma ' tak bardzo: moja implementacja opiera się na stercie, zwykle dlatego, że opiera się na tablicy; W Twoim przypadku bardzo polegasz na rekurencji, a ' jest naturalne, ponieważ ' polegasz na węzłach. Ponadto zwolnienie listy byłoby stosunkowo powolne dużo , ponieważ ' d albo użyjesz rekurencji (która ma naprawdę niską wydajność), albo dość skomplikowanego while loop ..
Odpowiedź
Problem, o którym inni nie wspominali, polega na tym, że Twój test nie działa. Wydaje się, że działa, ale w rzeczywistości tak nie jest. Dodając wartości do listy, przekazujesz adres zmiennej i:
arraylist_add(list, &i); I arraylist_add po prostu zapisuje przekazaną wartość (tak jak powinna):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Więc po przejściu przez i = 0. .99 wszystko, co masz na liście, to adres i 100 razy. Kiedy ponownie odczytujesz dane, użyj zmiennej pętli i i zmodyfikuj jej wartość z 0..99, a wydrukowana wartość będzie wyglądać poprawnie. Ale tak naprawdę po prostu widzisz, jak wartość zmiennej pętli jest modyfikowana przez pętlę.
Jeśli mi nie wierzysz, wypisz dowolny wpis w tablicy, np. 50, jak w:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); wydrukuje 100 (lub jakąkolwiek aktualną wartość i).
Zamiast tego powinieneś przechowywać rzeczywistą wartość:
arraylist_add(list, (void*) i); i wydrukować musisz rzucić wartość na typ, który był w momencie wprowadzenia:
printf("i: %d\n", (int)arraylist_get(list, t)); Jest wiele innych problemów z kodem, jak zauważyli inni . Podstawowy projekt używania arraylist_setdata do wprowadzania wszystkich modyfikacji jest zły. Ponowna alokacja przy każdej zmianie jest po prostu zła – realloc jest kosztowna. podstawowa idea listy przechowującej rzeczy przez udawanie, że są void*, jest dla mnie myląca i wydaje się złym pomysłem.
Komentarze
- Cóż, możesz tego nie zauważyć, ale ' jest dokładnie tym, co chciałem przetestować. Te wskaźniki są przechowywane i pobierane poprawnie poprzez opakowania funkcji.
- Przechowywanie rzeczy jako
void *nie jest ' naprawdę tak złe, jak się wydaje.Pomyśl o tym,void *po prostu przechowuje adres pamięci, na którym nie ' nie obchodzi mnie typ przechowywanej wartości. Krótko mówiąc, tablica powinna przechowywać tylko adresy pamięci, a ' jest praktycznie jedynym sposobem, w jaki C radzi sobie z różnymi typami w jednej tablicy. - Co do
realloc, zgadzam się z tobą, ale po prostu nie mogłem ' znaleźć lepszego sposobu na utworzenie dynamiki tablica. W każdym razie, postąpiłem zgodnie z radą glamperta ' dotyczącą pakowania specjalnej funkcji, funkcjishrink_to_fit.. - Wyobrażałem sobie, że próbujesz zapisać dane skalarne o zmiennej wielkości, przechowując je w pliku
void*(różne osoby przesłały w tym celu kod). Jeśli naprawdę chcesz przechowywać wskaźniki, lepszym testem byłoby przechowywanie wielu różnych wskaźników w znanej kolejności i sprawdzenie, czy otrzymujesz je z powrotem w tej samej kolejności – zamiast zapisywać tę samą wskaźnik 100 razy. Problem z przechowywaniem wskaźników polega na tym, że wskazywany obiekt musi być trwały przez cały okres istnienia jego adresu w tablicy. Pomimo void * oczywiście nie możesz mieszać typów w jednej tablicy. - Po prostu inny sposób robienia tego samego, gdzie tablica następuje natychmiast po zakończeniu struktury. Ta metoda ma swoje własne problemy, więc zapomnij, że o niej wspomniałem.
vectorw C / C ++, a nieArrayListze świata Java.