Ik heb de ArrayList-functionaliteit in C als volgt geïmplementeerd:
#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 “Ik test het als volgt:
#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; } Het werkt prima, hoewel realloc soms het programma laat crashen. Kan ik dit verbeteren?
Reacties
Antwoord
Allereerst een woord over het benoemen van :
De naam waarvoor je hebt gekozen jouw type, _arraylist is een slechte naam voor een type bibliotheekinterface. Namen die beginnen met _ zijn niet prettig om mee te werken in gebruikerscode. Ze worden vaak gebruikt in bibliotheekinternals. Betere namen zijn ArrayList of array_list.
In uw gebruiksvoorbeeld heeft u eigenlijk ArrayList. Betekent dit dat je in de header, die hier niet is opgenomen, zoiets als dit hebt?
typedef _arraylist ArrayList; Als je een ondoorzichtig type in de header hebt gedefinieerd, zoals hierboven, zou dat een goede gewoonte zijn. Maar gebruik dan geen enkele verwijzing naar _arraylist in uw code. Gebruik altijd de typedef “d name om verwarring te voorkomen.
Het functienaamvoorvoegsel moet ook exact de naam van het type volgen, dus voor ArrayList zouden alle functies moeten zijn voorafgegaan door het ArrayList_, bijvoorbeeld:
ArrayList * ArrayList_create(); Ik zou ook willen voorstellen om tightlypacked namen, zoals in arraylist_getsize(). Door een onderstrepingsteken toe te voegen aan afzonderlijke woorden, worden ze veel leesbaarder. Bijv .: ArrayList_get_size() .
Problemen met geheugen :
Laten we eens kijken naar 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; } Het eerste wat ongebruikelijk is hier zijn de beweringen. Beweringen zijn niet de juiste manier om een geheugentoewijzing te verhelpen. Plus , worden ze gewoonlijk uitgeschakeld bij release-builds, dus als je bij release “toevallig geen geheugen meer had, crashte het programma gewoon stil. U moet in dit geval waarschijnlijk een NULL retourneren (misschien ook loggen naar stderr) en de beller deze fout laten afhandelen zoals hij / zij ziet fit.
Tweede probleem hier is met calloc(). U wijst 2 lege verwijzingen toe, maar size wordt op nul gezet. Ik begrijp hier niet echt het punt van. Aangezien je structuur meer lijkt op een array van arrays dan op een lijst, moet je de array met pointers toewijzen met een vooraf gedefinieerde standaardgrootte en vervolgens de individuele arrays naar behoefte toewijzen. de reeks pointers op aanvraag. Hoe arraylist_create() eruit zou moeten zien:
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; } Een ander groot geheugenprobleem is de constante hertoewijzingen gedaan door arraylist_add() en arraylist_remove().
Verwijderen mag de reeks niet verkleinen. Houd die ruimte rond als de array groeit in de toekomst weer. U kunt een expliciete manier toevoegen om de gebruiker de opslagruimte te laten verkleinen indien nodig (a la std::vector::shrink_to_fit()).
Toevoegen aan de array kan worden uitgevoerd in afgeschreven constante tijd als u opslag vooraf toewijst met een grotere omvang dan de aangevraagde. (Opnieuw geïnspireerd door de STL vector).
sizeof fout :
Dit levert niet op wat je verwacht:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } De sizeof operator geeft altijd de grootte terug van het type waarop het wordt toegepast. Het kan de grootte van een array die door een pointer wordt aangeduid, niet afleiden, omdat het een compilatiebewerking is. arraylist_getsizeof() retourneert altijd dezelfde waarde, de grootte van een lege pointer, die 4 of 8 zal zijn, afhankelijk van de architectuur.
Gebruik beweringen om te controleren op invarianten :
Je moet assert dat de *list parameter van elke functie is geldig. Dit is een voorwaarde voor elke functie, ze kunnen niet werken zonder een geldige ArrayList -instantie, dus je zou moeten beweren dat zodra de functie binnenkomt.
Diversen :
Je hoeft niet te controleren of de pointer null voordat het wordt vrijgegeven . In arraylist_deallocate() is de if (list->data != NULL) controle niet nodig.
arraylist_deallocate zou meer symmetrisch zijn met arraylist_create indien genoemd arraylist_destroy.
Opmerkingen
- Hoe kan ik correct controleren of ik een geldige
ArrayListinstantie heb?Wat ik tot nu toe heb, is een macro die controleert op een specifieke waarde van een nieuw veld dat ik heb toegevoegd aanstruct _arraylist. Aangezien de struct-declaratie n ‘ t beschikbaar is in de koptekst, kan deArrayList-interfacegebruiker geen enkel veld rechtstreeks openen (dwz hij moet een van de wrapper-functies). En ik heb specifiek ‘ geen idee gegeven over dit veld .. - @AmrAyman, hangt af van je definitie van geldig, maar ik zou zeggen dat de minimale validatie zou zijn controleer of de
ArrayList-aanwijzer niet nul is en datArrayList::dataook niet nul is. U kunt ook controleren of elke array indataniet null is:assert( list->data[i] != NULL );
Antwoord
Laten we het hebben over prestaties
Wat moet je doen als je je lijst heel vaak moet gebruiken?
Laten we de functie arraylist_add eens nader bekijken; als ik een lijst met 1 miljoen bytes nodig heb, wat 1 MB is, zal het uw data struct lid 1 miljoen keer.
Het is het laagste deel van je lijst!
Suggesties
Wijs geheugen toe door middel van chunks , bijv. C ++ std::vector gebruikt toenemende grootte van toegevoegde brokken afhankelijk van de huidige grootte van std::vector.
Dit zal toenemen voer het een paar keer uit om nieuwe elementen toe te voegen.
Laten we het hebben over code zoals ze is
Probeer een elegante, maar eenvoudige programmastroom te implementeren.
Creëer waardetype (int) ArrayList, die in plaats daarvan geheugen toewijst door middel van blokken van de volledige array opnieuw toewijzen en wat lijstgedrag onder de motorkap toevoegen. Ik bedoel een lijst met brokken, je moet het nog steeds beheren.
Hier is mijn oplossing met een voorbeeld van het gebruik van brokken gegevens voor elk knooppunt in plaats van opnieuw toewijzen knooppunten. Een verschillende chunck-grootte kan het beste zijn voor een van de volgende doeleinden: schrijven, lezen van lange arrays; r \ w korte arrays; elementen verwijderen; 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]); } } } Reacties
- Ik respecteer uw interesse. Dit is echter C, niet C ++. Als het C ++ was, zou ik daarvoor gewoon vectoren gebruiken.
- @AmrAyman, controleer het
- Dat ‘ is indrukwekkend! Maar ik wil een arraylist hebben, geen gekoppelde lijst. Hoewel de implementatie van uw gekoppelde lijst hier geavanceerder is dan de normale struct-implementatie, heeft glampert het probleem opgelost.
- Over de prestatiewinst. Er is niet zoveel ‘ t echt: mijn implementatie is afhankelijk van de heap, normaal gesproken omdat het afhankelijk is van een array; De jouwe is sterk afhankelijk van recursie, en dat ‘ is natuurlijk omdat je ‘ afhankelijk bent van knooppunten. Bovendien zou het vrijmaken van de lijst veel relatief traag zijn, omdat u ‘ ofwel recursie zou gebruiken (wat erg weinig presteert), of een vrij gecompliceerde while loop ..
Answer
Een probleem dat niet door anderen is genoemd, is dat je test niet werkt. Het lijkt te werken, maar in werkelijkheid niet. Wanneer u waarden aan de lijst toevoegt, geeft u het adres van de variabele i door:
arraylist_add(list, &i); En arraylist_add slaat gewoon de doorgegeven waarde op (zoals het hoort):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Dus als je eenmaal door i = 0 bent gelooped. .99 alles wat je in de lijst hebt is het adres van i 100 keer. Wanneer u de gegevens terugleest, gebruikt u opnieuw de loopvariabele i en wijzigt u de waarde van 0..99 en de afgedrukte waarde ziet er goed uit. Maar je ziet eigenlijk alleen maar de waarde van de lusvariabele die door de lus wordt gewijzigd.
Als je me niet gelooft, print dan een vast array-item, bijvoorbeeld 50, zoals in:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); het zal worden afgedrukt 100 (of wat de waarde van i momenteel ook is).
In plaats daarvan zou je de echte waarde moeten opslaan:
arraylist_add(list, (void*) i); en om af te drukken het eruit moet je de waarde casten naar het type dat het was toen het binnenkwam:
printf("i: %d\n", (int)arraylist_get(list, t)); Er zijn veel andere problemen met de code, zoals anderen hebben opgemerkt . Het basisontwerp van het gebruik van uw arraylist_setdata om alle wijzigingen aan te brengen, is verkeerd. Het opnieuw toewijzen bij elke wijziging is gewoon slecht – realloc is duur. En het basisidee van een lijst waarin dingen worden opgeslagen door te doen alsof ze void* zijn, vind ik verwarrend en lijkt me een slecht idee.
Opmerkingen
- Nou, je merkt het misschien niet, maar dat ‘ is precies wat ik wilde testen. Dat pointers worden opgeslagen en opgehaald correct via de functie wrappers ..
- Dingen opslaan als
void *isn ‘ is niet echt zo erg als het lijkt.Denk er eens over na,void *slaat gewoon een geheugenadres op, dat me ‘ niet kan schelen in het type waarde dat is opgeslagen. Kortom, de array is alleen bedoeld om geheugenadressen op te slaan, en dat ‘ is praktisch de enige manier waarop C met verschillende typen in een enkele array zou omgaan. - Over
realloc, ik ben het met je eens, maar ik kon ‘ geen betere manier vinden om een dynamische matrix. Hoe dan ook, ik volgde het advies van glampert ‘ om daar een speciale functie voor in te pakken, deshrink_to_fit-functie. - Ik stelde me voor dat je scalaire gegevens met variabele grootte probeerde op te slaan door ze op te slaan in een
void*(verschillende mensen hebben hiervoor code ingediend). Als u wijzers echt wilt opslaan, dan is een betere test om een aantal verschillende aanwijzers in een bekende volgorde op te slaan en te controleren of u ze in dezelfde volgorde terugkrijgt – in plaats van dezelfde op te slaan wijzer 100 keer. Het probleem met het opslaan van pointers is dat het object waarnaar wordt verwezen persistent moet zijn gedurende de levensduur van het adres in de array. Ondanks de leegte * kun je natuurlijk geen typen binnen één array mixen. - Gewoon een andere manier om hetzelfde te doen, waarbij de array direct na het einde van de structuur volgt. Die methode heeft zijn eigen problemen, dus vergeet dat ik het heb genoemd.
vectorgenoemd in C / C ++, niet als eenArrayListuit de Java-wereld.