Ho implementato la funzionalità ArrayList in C come segue:
#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 “Lo sto provando in questo modo:
#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; } Funziona bene, anche se realloc a volte blocca il programma. Posso migliorare questo?
Commenti
Risposta
Innanzitutto, una parola sulla denominazione di :
Il nome che hai scelto il tuo tipo, _arraylist è un brutto nome per un tipo di interfaccia di libreria. I nomi che iniziano con _ non sono piacevoli da utilizzare nel codice utente. Sono comunemente usati allinterno delle librerie. I nomi migliori sarebbero ArrayList o array_list.
In realtà, nel tuo esempio di utilizzo, hai ArrayList. Questo significa che nellintestazione, che non è inclusa qui, hai qualcosa di simile?
typedef _arraylist ArrayList; Se hai definito un tipo opaco nellintestazione, come sopra, sarebbe una buona pratica. Ma poi non dovresti usare alcun riferimento a _arraylist nel tuo codice. Usa sempre il nome typedef “d per evitare confusione.
Anche il prefisso del nome della funzione dovrebbe seguire esattamente il nome del tipo, quindi per ArrayList tutte le funzioni dovrebbero essere prefisso ArrayList_, ad esempio:
ArrayList * ArrayList_create(); Inoltre, ti suggerirei di evitare tightlypacked nomi, come in arraylist_getsize(). Laggiunta di un trattino basso per separare le parole le rende molto più leggibili. Ad esempio: ArrayList_get_size() .
Problemi con la memoria :
Diamo unocchiata 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; } La prima cosa insolita qui sono le asserzioni. Le asserzioni non sono il modo corretto per gestire un errore di allocazione della memoria. Inoltre , sono comunemente disabilitati nelle build di rilascio, quindi al rilascio, se ti capita di esaurire la memoria, il programma si bloccherebbe silenziosamente. In questo caso dovresti probabilmente restituire un NULL (magari anche accedere a stderr) e lasciare che il chiamante gestisca questo errore come vede fit.
Il secondo problema qui è con calloc(). Stai allocando 2 puntatori void, tuttavia, size è impostato su zero. Non capisco davvero il punto. Poiché la tua struttura è più simile a un array di array che a un elenco, quello che dovresti fare è allocare larray di puntatori con una dimensione predefinita predefinita, quindi allocare i singoli array secondo necessità. larray di puntatori su richiesta. Come dovrebbe apparire 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; } Un altro grosso problema di memoria è la costante riassegnazioni eseguite da arraylist_add() e arraylist_remove().
La rimozione non dovrebbe ridurre la sequenza. Mantieni lo spazio se larray cresce di nuovo in futuro. Puoi aggiungere un modo esplicito per consentire allutente di ridurre lo spazio di archiviazione se necessario (a la std::vector::shrink_to_fit()).
Aggiungendo al Larray può essere eseguito in un tempo costante ammortizzato se prealloggi lo spazio di archiviazione con una dimensione maggiore rispetto a quella richiesta (di nuovo ispirato allSTL vector).
sizeof errore :
Questo non restituirà quello che ti aspetti:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } Il sizeof Loperatore restituisce sempre la dimensione del tipo a cui è applicato. Non può dedurre la dimensione di un array puntato da un puntatore, perché è unoperazione in fase di compilazione. arraylist_getsizeof() restituirà sempre lo stesso valore, la dimensione di un puntatore void, che sarà 4 o 8, a seconda dellarchitettura.
Utilizza le asserzioni per verificare la presenza di invarianti :
Dovresti assert che *list il parametro di ogni funzione è valido. Questa è una precondizione di ogni funzione, non possono funzionare senza unistanza ArrayList valida, quindi dovresti affermare che una volta che la funzione è inserita.
Varie :
Non è necessario controllare se il puntatore è null prima di liberarlo . In arraylist_deallocate() il controllo if (list->data != NULL) non è necessario.
arraylist_deallocate sarebbe più simmetrico con arraylist_create se denominato arraylist_destroy.
Commenti
- Come posso controllare correttamente se ho unistanza
ArrayListvalida?Quello che ho finora è una macro che controlla un valore specifico di un nuovo campo che ho aggiunto astruct _arraylist. Poiché la dichiarazione della struttura non è ‘ t disponibile nellintestazione, lutente dellinterfacciaArrayListnon può accedere direttamente a nessun campo (cioè deve utilizzare uno dei le funzioni wrapper). E specificamente non ho ‘ fornito alcun indizio su questo campo .. - @AmrAyman, dipende dalla tua definizione di valid, ma direi che la convalida minima sarebbe controllare che il puntatore
ArrayListnon sia nullo e che ancheArrayList::datanon sia nullo. Puoi anche verificare che ogni array indatanon sia nullo:assert( list->data[i] != NULL );
Rispondi
Parliamo di prestazioni
E se hai bisogno di usare il tuo elenco molto spesso?
Esaminiamo più da vicino la funzione arraylist_add; se ho bisogno di un elenco con 1 milione di byte, ovvero 1 MB, riallocherà il tuo data membro della struttura 1 milione di volte.
È la parte più bassa della tua lista!
Suggerimenti
Alloca la memoria per blocchi , ad esempio, C ++ std::vector utilizza dimensioni crescenti dei blocchi aggiunti a seconda della dimensione corrente di std::vector.
Ciò aumenterà eseguire alcune volte allo scopo di aggiungere nuovi elementi.
Parliamo del codice così comè
Prova a implementare un flusso di programma elegante ma semplice.
Crea il tipo di valore (int) ArrayList, che invece allocherà la memoria per blocchi di riallocare larray completo e aggiungere qualche comportamento allelenco sotto il cofano. Intendo un elenco di blocchi, devi ancora gestirlo.
Ecco la mia soluzione con un esempio di utilizzo di blocchi di dati per ogni nodo invece di riallocazione nodi. Diverse dimensioni di chunck possono essere le migliori per uno degli scopi: scrivere, leggere array lunghi; r \ w short array; rimuovere elementi; ecc.
#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]); } } } Commenti
- Rispetto il tuo interesse. Tuttavia, questo è C, non C ++. Se fosse C ++, userei solo i vettori per farlo ..
- @AmrAyman, controllalo
- Che ‘ è impressionante! Ma voglio avere un elenco di array non un elenco collegato. Sebbene limplementazione della tua lista concatenata qui sia più avanzata della normale implementazione di struct, glampert ha risolto il problema.
- Informazioni sullaumento delle prestazioni. Non cè ‘ così tanto: la mia implementazione si basa sullheap, normalmente perché si basa su un array; I tuoi dipendono fortemente dalla ricorsione e questo ‘ è naturale perché ‘ fai affidamento sui nodi. Inoltre, liberare lelenco sarebbe molto relativamente lento, perché ‘ usi la ricorsione (che è molto bassa per le prestazioni) o un metodo abbastanza complicato while loop ..
Risposta
Un problema non menzionato da altri è che il tuo test non funziona. Sembra funzionare ma in realtà non funziona. Quando aggiungi valori allelenco, stai passando lindirizzo della variabile i:
arraylist_add(list, &i); E arraylist_add salva semplicemente il valore passato (come dovrebbe):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Quindi, una volta che hai eseguito il loop di i = 0. .99 tutto quello che hai nella lista è lindirizzo di i 100 volte. Quando rileggi i dati, usi di nuovo la variabile di ciclo i e modifichi il suo valore da 0..99 e il valore stampato sembra corretto. Ma in realtà stai solo vedendo il valore della variabile del ciclo che viene modificato dal ciclo.
Se non mi credi, stampa qualsiasi voce di matrice fissa, ad esempio 50, come in:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); verrà stampata 100 (o qualunque sia il valore di i attualmente).
Dovresti invece memorizzare il valore reale:
arraylist_add(list, (void*) i); e stampare è necessario eseguire il cast del valore nel tipo che era quando è entrato:
printf("i: %d\n", (int)arraylist_get(list, t)); Ci sono molti altri problemi con il codice, come altri hanno notato . La progettazione di base dellutilizzo del tuo arraylist_setdata per eseguire tutte le modifiche è sbagliata. La riallocazione a ogni modifica è semplicemente pessima – realloc è costosa. E lidea di base di un elenco che memorizza le cose fingendo che siano void* mi confonde e sembra una cattiva idea.
Commenti
- Beh, potresti non accorgertene, ma ‘ è esattamente quello che volevo testare. Quei puntatori vengono memorizzati e recuperati correttamente attraverso i wrapper delle funzioni ..
- Memorizzare le cose come
void *non è ‘ così male come sembra.Pensaci,void *memorizza semplicemente un indirizzo di memoria, al quale ‘ non interessa il tipo di valore memorizzato. In breve, si suppone che larray memorizzi solo gli indirizzi di memoria e che ‘ è praticamente lunico modo in cui C gestirà vari tipi in un singolo array .. - Informazioni su
realloc, sono daccordo con te ma non sono riuscito ‘ a trovare un modo migliore per creare un dinamico array. Ad ogni modo, ho seguito il consiglio di glampert ‘ di includere una funzione speciale per questo, lashrink_to_fitfunzione .. - Ho immaginato che stessi cercando di salvare dati scalari di dimensioni variabili memorizzandoli in un
void*(varie persone hanno inviato il codice per farlo). Se vuoi davvero memorizzare i puntatori, allora un test migliore sarebbe memorizzare un numero di puntatori diversi in un ordine noto e controllare di recuperarli nello stesso ordine, invece di salvare lo stesso puntatore 100 volte. Il problema con la memorizzazione dei puntatori è che loggetto puntato deve essere persistente per tutta la durata dellesistenza del suo indirizzo nellarray. Nonostante il vuoto *, ovviamente non puoi mescolare i tipi allinterno di un array. - Solo un modo diverso di fare la stessa cosa, dove larray segue immediatamente dopo la fine della struttura. Questo metodo ha i suoi problemi, quindi dimentica di averlo menzionato.
vectorin C / C ++, non come unaArrayListdal mondo Java.