Toteutin ArrayList-toiminnot C: ssä seuraavasti:
#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 ”Testaan sitä näin:
#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; } Se toimii hyvin, vaikka realloc joskus kaataa ohjelman. Voinko paranna tätä?
Kommentit
Vastaa
Ensinnäkin sana nimeämisestä:
Nimi, jolle olet valinnut tyyppiäsi, _arraylist on kirjastoliittymän tyypin huono nimi. Nimien, jotka alkavat _, ei ole miellyttävää työskennellä käyttäjän koodissa. Niitä käytetään yleisesti kirjaston sisäpuolella. Paremmat nimet olisivat ArrayList tai array_list.
Itse asiassa käyttöesimerkissäsi on ArrayList. Tarkoittaako tämä, että otsikossa, jota ei ole tässä, sinulla on jotain tällaista?
typedef _arraylist ArrayList; Jos määritit otsikossa läpinäkymättömän tyypin, kuten edellä, se olisi hyvä käytäntö. Mutta silloin sinun ei pidä käyttää koodissasi mitään viittausta _arraylist -kohtaan. Käytä aina typedef ”d-nimeä sekaannusten välttämiseksi.
Funktion nimen etuliitteen tulisi myös seurata tarkalleen tyypin nimeä, joten ArrayList -kohdassa kaikkien toimintojen tulisi olla etuliite ArrayList_, esim .:
ArrayList * ArrayList_create(); Ehdotan myös, että vältät tightlypacked nimet, kuten arraylist_getsize() -kohdassa. Alaviivan lisääminen erillisiin sanoihin tekee niistä paljon helpommin luettavia. Esimerkiksi: ArrayList_get_size() .
Muistiongelmat :
Tarkastellaan kohdetta 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; } Ensinnäkin tässä väitteet ovat väitteitä. Väitteet eivät ole oikea tapa käsitellä muistin kohdennusvirhettä. Plus , ne ovat yleensä poissa käytöstä julkaisurakenteissa, joten julkaisun yhteydessä, jos muistisi loppuu, ohjelma kaatuu hiljaa. Sinun pitäisi todennäköisesti palauttaa NULL tässä tapauksessa (ehkä myös kirjautua osoitteeseen stderr) ja antaa soittajan hoitaa tämä virhe näkemällään sovi.
Toinen ongelma on tässä calloc(). Jaat 2 tyhjää osoitinta, mutta size on nolla. En todellakaan ymmärrä tämän asemaa. Koska rakenteesi on enemmän kuin taulukoiden joukko ja luettelo, sinun on tehtävä allokointiryhmä jollakin ennalta määritetyllä oletuskoolla ja jaettava sitten yksittäiset taulukot tarpeen mukaan. Kasvava taulukon taulukko pyynnöstä. Kuinka arraylist_create() pitäisi näyttää:
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; } Toinen iso muistiongelma on vakio uudelleen kohdentaminen, jonka suorittivat arraylist_add() ja arraylist_remove().
Poistamisen ei pitäisi kutistua järjestystä. Pidä tämä tila ympärillä, jos taulukko kasvaa uudelleen tulevaisuudessa. Voit lisätä nimenomaisen tavan antaa käyttäjän kutistaa tallennustilaa tarvittaessa (a la std::vector::shrink_to_fit()).
Lisää matriisi voidaan suorittaa juoksevana vakiona, jos varat varat ennalta suuremman koon kuin pyydetty. (Jälleen STL vector innoittamana).
sizeof virhe :
Tämä ei palauta odottamaasi:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } sizeof operaattori palauttaa aina sen tyypin koon, johon sitä käytetään. Se ei voi päätellä osoittimen osoittaman taulukon kokoa, koska se on kääntöaikatoiminto. arraylist_getsizeof() palauttaa aina saman arvon, tyhjän osoittimen koon, joka on 4 tai 8 arkkitehtuurista riippuen.
Käytä väitteitä tarkistaaksesi invariantit :
Sinun tulisi assert että *list -parametri on kelvollinen. Tämä on kaikkien toimintojen ennakkoedellytys. Ne eivät voi toimia ilman kelvollista ArrayList -esiintymää, joten sinun on väitettävä, että kun funktio tulee sisään.
Muut :
Sinun ei tarvitse tarkistaa, onko osoitin null ennen sen vapauttamista . arraylist_deallocate() -kohdassa if (list->data != NULL) -valintaa ei tarvita.
arraylist_deallocate olisi symmetrinen arraylist_create kanssa, jos nimi olisi arraylist_destroy.
Kommentit
- Kuinka voin oikein tarkistaa, onko minulla kelvollinen
ArrayList-esiintymä?Minulla on toistaiseksi makro, joka tarkistaastruct _arraylist-kenttään lisäämäni uuden kentän tietyn arvon. Koska struct-deklarointi ei ole ’ t saatavilla otsikossa, käyttöliittymänArrayListkäyttäjä ei voi käyttää mitään kenttää suoraan (ts. Hänen on käytettävä yhtä käärintätoiminnot). En nimenomaisesti ’ antanut mitään vihjeitä tästä kentästä. - @AmrAyman, riippuu määritelmästä voimassa oleva, mutta sanoisin, että vähimmäistarkistus olisi tarkista, että
ArrayList-osoitin ei ole nolla ja ettäArrayList::dataei myöskään ole nolla. Voit myös tarkistaa, että kukin ryhmändatataulukko ei ole tyhjä:assert( list->data[i] != NULL );
Vastaa
Puhutaan esityksestä
Entä jos sinun on käytettävä luetteloasi hyvin usein?
Tarkastellaan tarkemmin funktiota arraylist_add; jos tarvitsen miljoonan tavun (1 Mt) luettelon, se kohdistaa data struct-jäsen miljoona kertaa.
Se on luettelosi alin osa!
Ehdotukset
Kohdista muisti paloina , esim. C ++ std::vector käyttää lisääntynyttä liitettyjen palojen kokoa std::vector -koon nykyisestä koosta riippuen.
Tämä lisää Suorita se muutaman kerran lisäämällä uusia elementtejä.
Puhutaan koodista sellaisenaan
Yritä toteuttaa tyylikäs, mutta yksinkertainen ohjelmavirta.
Luo arvotyyppi (int) ArrayList, joka jakaa muistin sen sijaan paloina jaa koko taulukko uudelleen ja lisää luettelon käyttäytymistä hupun alle. Tarkoitan palahakeluetteloa, sinun on silti hallittava sitä.
Tässä on ratkaisuni, jossa on esimerkki datan palojen käyttämisestä jokaiselle solmulle uudelleenjaon sijasta. solmut. Eri palan koko voi olla paras yhteen tarkoitukseen: kirjoittamiseen, pitkien taulukoiden lukemiseen; r \ w lyhyet taulukot; elementtien poistaminen; jne.
#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]); } } } Kommentit
- Kunnioitan kiinnostustasi. Tämä on kuitenkin C, ei C ++. Jos se olisi C ++, tekisin vain vektorien avulla siihen.
- @AmrAyman, tarkista se
- Se on ’ vaikuttava! Mutta haluan, että taulukko ei ole linkitetty luettelo. Vaikka linkitetyn luettelosi toteutus on tässä edistyneempi kuin normaali struct-toteutus, glampert ratkaisi ongelman.
- Tietoja suorituskyvyn kasvusta. Ei ole ’ t oikeastaan niin paljon: Toteutukseni riippuu kasasta, yleensä koska se perustuu matriisiin; Luotat voimakkaasti rekursioon, ja se on ’ luonnollista, koska ’ luotat solmuihin. Luettelon vapauttaminen olisi myös paljon hidasta suhteellisen, koska ’ d joko käyttää rekursiota (joka on suorituskyvyssä todella heikkoa) tai melko monimutkaista while loop ..
Vastaa
Ongelma, jota muut eivät mainitse, on se, että testi ei toimi. Se näyttää toimivan, mutta todellisuudessa se ei ”t”. Kun lisäät arvoja luetteloon, välität muuttujan i osoitteen:
arraylist_add(list, &i); Ja arraylist_add vain tallentaa välitetyn arvon (kuten pitääkin):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Joten kun olet siirtynyt i = 0: n läpi. .99 vain luettelossa on i: n osoite 100 kertaa. Kun luet tiedot takaisin, käytät taas silmukamuuttujaa i ja muokkaat sen arvoa 0..99, ja tulostettu arvo näyttää oikealta. Mutta näet oikeastaan vain silmukan muuttuvan silmukan muuttujan arvon.
Jos et usko minua, tulosta kaikki kiinteät taulukot, esim. 50, kuten:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); se tulostaa 100 (tai mikä tahansa i: n arvo on tällä hetkellä).
Sen sijaan sinun tulisi tallentaa todellinen arvo:
arraylist_add(list, (void*) i); ja tulostaa Sinun on heitettävä arvo siihen tyyppiin, joka se oli, kun se meni sisään:
printf("i: %d\n", (int)arraylist_get(list, t)); Koodissa on monia muita ongelmia, kuten muut ovat huomanneet . Perusrakenne arraylist_setdata -palvelun käyttämisestä kaikkien muutosten tekemiseen on väärä. Jokaisen muutoksen kohdentaminen uudelleen on vain huono – realloc on kallista. perusajatus luettelosta, joka tallentaa asiat teeskentelemällä, että ne ovat void*, on minulle hämmentävä ja vaikuttaa huonolta.
Kommentit
- No, et ehkä huomaa sitä, mutta se ’ on täsmälleen mitä halusin testata. Että osoittimet tallennetaan ja haetaan oikein kääreiden kautta.
- Asemien tallentaminen
void *ei ole ’ ei niin huono kuin miltä näyttää.Ajattele asiaa:void *tallentaa yksinkertaisesti muistiosoitteen, josta en välitä ’, mihin arvo tallennetaan. Lyhyesti sanottuna taulukon on tarkoitus tallentaa vain muistiosoitteita, ja ’ on käytännössä ainoa tapa, jolla C käsittelee erilaisia tyyppejä yhdessä taulukossa. - Tietoja
realloc, olen kanssasi samaa mieltä, mutta en vain voinut ’ löytää parempaa tapaa luoda dynaaminen taulukko. Joka tapauksessa seurasin glampert ’ n neuvoja käärimällä erityistoiminto,shrink_to_fit-toiminto .. - Kuvittelin, että yritit tallentaa vaihtelevan kokoisia skalaarisia tietoja tallentamalla ne
void*-kansioon (monet ihmiset ovat lähettäneet koodia tekemään niin). Jos todella halusit tallentaa osoittimia, parempi testi olisi tallentaa useita eri viitteitä tunnetussa järjestyksessä ja tarkistaa, että saat ne takaisin samassa järjestyksessä – sen sijaan, että tallennat samat osoitin 100 kertaa. Osoitteiden tallentamisen ongelmana on, että osoitetun objektin on oltava pysyvä koko osoitteensa olemassaolon matriisissa. Huolimatta tyhjyydestä *, et tietenkään voi sekoittaa tyyppejä yhdessä taulukossa. - Vain erilainen tapa tehdä sama asia, jossa taulukko jatkuu heti rakenteen päättymisen jälkeen. Tällä menetelmällä on omat ongelmansa, joten unohda mainitsin sen.
vectorC / C ++, eiArrayListJava-maailmasta.