Jai implémenté la fonctionnalité ArrayList en C comme suit:
#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 « Je le teste comme ceci:
#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; } Cela fonctionne bien, même si realloc plante parfois le programme. Puis-je améliorer cela?
Commentaires
Réponse
Tout dabord, un mot sur la dénomination :
Le nom que vous avez choisi votre type, _arraylist est un mauvais nom pour un type dinterface de bibliothèque. Les noms commençant par _ ne sont pas agréables à utiliser dans le code utilisateur. Ils sont couramment utilisés à lintérieur des bibliothèques internes. De meilleurs noms seraient ArrayList ou array_list.
En fait, dans votre exemple dutilisation, vous avez ArrayList. Cela signifie-t-il que dans len-tête, qui nest pas inclus ici, vous avez quelque chose comme ça?
typedef _arraylist ArrayList; Si vous avez défini un type opaque dans len-tête, comme ci-dessus, ce serait une bonne pratique. Mais alors vous ne devriez pas utiliser de référence à _arraylist dans votre code. Utilisez toujours le nom typedef « d pour éviter toute confusion.
Le préfixe du nom de la fonction doit également suivre exactement le nom du type, donc pour ArrayList toutes les fonctions doivent être préfixé le ArrayList_, par exemple:
ArrayList * ArrayList_create(); Aussi, je vous suggère déviter tightlypacked noms, comme dans arraylist_getsize(). Lajout dun trait de soulignement pour séparer les mots les rend beaucoup plus lisibles. Par exemple: ArrayList_get_size() .
Problèmes de mémoire :
Regardons 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 première chose inhabituelle ici est les assertions. Les assertions ne sont pas la bonne façon de gérer un échec dallocation de mémoire. , ils sont généralement désactivés sur les versions de version, donc lors de la publication, si vous manquez de mémoire, le programme se planterait silencieusement. Vous devriez probablement renvoyer un NULL dans ce cas (peut-être aussi vous connecter à stderr) et laisser lappelant gérer cette erreur comme il le voit ajustement.
Le deuxième problème ici est avec calloc(). Vous allouez 2 pointeurs vides, cependant, size est mis à zéro. Je ne comprends pas vraiment le point. Puisque votre structure ressemble plus à un tableau de tableaux quà une liste, ce que vous devez faire est dallouer le tableau de pointeurs avec une taille par défaut prédéfinie, puis dallouer les tableaux individuels selon les besoins. le tableau de pointeurs à la demande. À quoi devrait ressembler 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 autre gros problème de mémoire est la constante les réaffectations effectuées par arraylist_add() et arraylist_remove().
La suppression ne devrait pas réduire la séquence. Conservez cet espace si le tableau sagrandit à nouveau dans le futur. Vous pouvez ajouter un moyen explicite pour permettre à lutilisateur de réduire le stockage si nécessaire (a la std::vector::shrink_to_fit()).
Ajout à la Le tableau peut être conçu pour fonctionner en temps constant amorti si vous pré-allouez du stockage avec une taille plus grande que celle demandée. (Encore une fois inspiré par la STL vector).
sizeof erreur :
Cela ne retournera pas ce que vous attendez:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } Le sizeof Lopérateur renvoie toujours la taille du type auquel il est appliqué. Il ne peut pas déduire la taille dun tableau pointé par un pointeur, car il sagit dune opération à la compilation. arraylist_getsizeof() renverra toujours la même valeur, la taille dun pointeur void, qui sera de 4 ou 8, selon larchitecture.
Utilisez des assertions pour vérifier les invariants :
Vous devez assert que *list de chaque fonction est valide. Ceci est une condition préalable de chaque fonction, elles ne peuvent pas fonctionner sans une instance ArrayList valide, vous devez donc affirmer quune fois la fonction entrée.
Divers :
Vous navez pas besoin de vérifier si le pointeur est null avant de le libérer . Dans arraylist_deallocate() la vérification if (list->data != NULL) nest pas effectuée.
arraylist_deallocate serait plus symétrique avec arraylist_create sil était nommé arraylist_destroy.
Commentaires
- Comment puis-je correctement vérifier si jai une instance
ArrayListvalide?Ce que jai jusquà présent est une macro qui vérifie une valeur spécifique dun nouveau champ que jai ajouté àstruct _arraylist. Puisque la déclaration de structure nest ‘ t disponible dans len-tête, lutilisateur de linterfaceArrayListne peut accéder directement à aucun champ (cest-à-dire quil doit utiliser lun des les fonctions wrapper). Et je nai spécifiquement ‘ donné aucun indice sur ce champ .. - @AmrAyman, dépend de votre définition de valide, mais je dirais que la validation minimale serait vérifiez que le pointeur
ArrayListnest pas nul et queArrayList::datanest pas non plus nul. Vous pouvez également vérifier que chaque tableau dedatanest pas nul:assert( list->data[i] != NULL );
Réponse
Parlons de la performance
Et si vous avez besoin dutiliser votre liste très fréquemment?
Regardons de plus près la fonction arraylist_add; si jai besoin dune liste de 1 million doctets, soit 1 Mo, elle réallouera votre data struct membre 1 million de fois.
Cest la partie la plus basse de votre liste!
Suggestions
Allouer de la mémoire par blocs , par exemple, C ++ std::vector utilise une taille croissante des blocs ajoutés en fonction de la taille actuelle de std::vector.
Cela augmentera exécutez-le plusieurs fois dans le but dajouter de nouveaux éléments.
Parlons du code tel quel
Essayez dimplémenter un flux de programme élégant mais simple.
Créez le type de valeur (int) ArrayList, qui allouera de la mémoire par chuncks à la place de réallouer le tableau complet et ajouter un comportement de liste sous le capot. Je veux dire la liste des morceaux, vous devez toujours la gérer.
Voici ma solution avec un exemple dutilisation de morceaux de données pour chaque nœud au lieu de réallouer nœuds. Une taille de chunck différente peut être la meilleure pour lun des objectifs: écrire, lire de longs tableaux; r \ w tableaux courts; supprimer des éléments; 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]); } } } Commentaires
- Je respecte votre intérêt. Cependant, cest C, pas C ++. Si cétait C ++, jutiliserais simplement des vecteurs pour faire ça ..
- @AmrAyman, vérifiez-le
- Cest ‘ impressionnant! Mais je veux avoir un arraylist pas une liste chaînée. Bien que votre implémentation de liste chaînée ici soit plus avancée que limplémentation normale de struct, glampert a résolu le problème.
- À propos du gain de performances. Il ny a pas ‘ t vraiment autant: mon implémentation repose sur le tas, normalement parce quelle repose sur un tableau; Le vôtre compte fortement sur la récursivité, et cela ‘ est naturel parce que vous ‘ comptez sur des nœuds. De plus, libérer la liste serait beaucoup relativement lent, car vous ‘ utilisez la récursivité (qui est vraiment faible en performances), ou une méthode assez compliquée boucle while ..
Réponse
Un problème non mentionné par les autres est que votre test ne fonctionne pas. Cela semble fonctionner mais en réalité, cela ne fonctionne pas. Lorsque vous ajoutez des valeurs à la liste, vous transmettez ladresse de la variable i:
arraylist_add(list, &i); Et arraylist_add enregistre simplement la valeur passée (comme il se doit):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Donc, une fois que vous avez bouclé sur i = 0. .99 tout ce que vous avez dans la liste est ladresse de i 100 fois. Lorsque vous relisez les données, vous utilisez à nouveau la variable de boucle i et modifiez sa valeur de 0..99 et la valeur imprimée semble correcte. Mais vous ne voyez que la valeur de la variable de boucle modifiée par la boucle.
Si vous ne me croyez pas, imprimez nimporte quelle entrée de tableau fixe, par exemple 50, comme dans:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); il sera imprimé 100 (ou quelle que soit la valeur de i actuellement).
Au lieu de cela, vous devriez stocker la valeur réelle:
arraylist_add(list, (void*) i); et imprimer vous devez convertir la valeur dans le type où elle était quand elle est entrée:
printf("i: %d\n", (int)arraylist_get(list, t)); Il y a beaucoup dautres problèmes avec le code, comme dautres lont noté . La conception de base consistant à utiliser votre arraylist_setdata pour effectuer toutes les modifications est erronée. Réallouer à chaque changement est tout simplement mauvais – realloc coûte cher. Et lidée de base dune liste stockant des choses en prétendant quelles sont void* me déroute et me semble une mauvaise idée.
Commentaires
- Eh bien, vous ne le remarquerez peut-être pas, mais ‘ est exactement ce que je voulais tester. Ces pointeurs sont stockés et récupérés correctement via les wrappers de fonction.
- Stocker des choses comme
void *nest pas ‘ vraiment aussi mauvais quil y paraît.Pensez-y,void *stocke simplement une adresse mémoire, dont je ne me soucie ‘ du type de valeur stockée. En bref, le tableau nest censé stocker que des adresses mémoire, et que ‘ est pratiquement la seule façon dont C traiterait différents types dans un seul tableau. - À propos de
realloc, je suis daccord avec vous mais je nai pas pu ‘ trouver un meilleur moyen de créer une dynamique tableau. Quoi quil en soit, jai suivi les conseils de glampert ‘ dencapsuler une fonction spéciale pour cela, la fonctionshrink_to_fit.. - Jai imaginé que vous essayiez de sauvegarder des données scalaires de taille variable en les stockant dans un
void*(plusieurs personnes ont soumis du code pour cela). Si vous voulez vraiment stocker des pointeurs, alors un meilleur test serait de stocker un certain nombre de pointeurs différents dans un ordre connu et de vérifier que vous les récupérez dans le même ordre – au lieu de les sauvegarder pointeur 100 fois. Le problème avec le stockage des pointeurs est que lobjet pointé doit être persistant pendant toute la durée de vie de son adresse dans le tableau. Malgré le vide *, vous ne pouvez bien sûr pas mélanger les types dans un seul tableau. - Juste une façon différente de faire la même chose, où le tableau suit immédiatement après la fin de la structure. Cette méthode a ses propres problèmes, alors oubliez de lavoir mentionnée.
vectordans C / C ++, pas comme uneArrayListdu monde Java.