Implementando una ArrayList

Primero, unas palabras sobre el nombre de :

El nombre que» ha elegido su tipo, _arraylist es un mal nombre para un tipo de interfaz de biblioteca. No es agradable trabajar con nombres que comienzan con _ en el código de usuario. Se utilizan comúnmente en el interior de la biblioteca. Los mejores nombres serían ArrayList o array_list.

En realidad, en su ejemplo de uso, tiene ArrayList. ¿Significa esto que en el encabezado, que no se incluye aquí, tiene algo como esto?

typedef _arraylist ArrayList; 

Si definió un tipo opaco en el encabezado, como arriba, sería una buena práctica. Pero entonces no debería usar ninguna referencia a _arraylist en su código. Utilice siempre el nombre typedef «d para evitar confusiones.

El prefijo del nombre de la función también debe seguir exactamente el nombre del tipo, por lo que para ArrayList todas las funciones deben ser prefijo el ArrayList_, por ejemplo:

ArrayList * ArrayList_create(); 

Además, te sugiero que evites tightlypacked nombres, como en arraylist_getsize(). Agregar un guión bajo para separar palabras las hace mucho más legibles. Por ejemplo: ArrayList_get_size() .

Problemas con la memoria :

Veamos 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; } 

Lo primero que es inusual aquí son las afirmaciones. Las afirmaciones no son la forma correcta de manejar una falla de asignación de memoria. Además , por lo general se desactivan en las versiones de lanzamiento, por lo que en el lanzamiento, si se queda sin memoria, el programa simplemente se bloqueará silenciosamente. Probablemente debería devolver un NULL en este caso (tal vez también inicie sesión en stderr) y deje que la persona que llama maneje este error como lo ve. encajar.

El segundo problema aquí es con calloc(). Está asignando 2 punteros vacíos, sin embargo, size se establece en cero. Realmente no entiendo el punto de esto. Dado que su estructura se parece más a una matriz de matrices que a una lista, lo que debe hacer es asignar la matriz de punteros con un tamaño predeterminado predefinido y luego asignar las matrices individuales según sea necesario. la matriz de punteros bajo demanda. Cómo debería verse 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; } 

Otro gran problema de memoria es la constante reasignaciones realizadas por arraylist_add() y arraylist_remove().

Eliminar no debería reducir la secuencia. Mantenga ese espacio alrededor si la matriz vuelve a crecer en el futuro. Puede agregar una forma explícita de permitir que el usuario reduzca el almacenamiento si es necesario (a la std::vector::shrink_to_fit()).

Agregar a la se puede hacer que la matriz se ejecute en un tiempo constante amortizado si preasigna almacenamiento con un tamaño mayor que el solicitado (nuevamente inspirado en STL vector).

sizeof error :

Esto no devolverá lo que esperaba:

size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } 

El sizeof operador siempre devuelve el tamaño del tipo al que se aplica. No puede inferir el tamaño de una matriz apuntada por un puntero, porque es una operación en tiempo de compilación. arraylist_getsizeof() siempre devolverá el mismo valor, el tamaño de un puntero vacío, que será 4 u 8, según la arquitectura.

Use aserciones para verificar invariantes :

Debe assert que el *list parámetro de cada función es válido. Esta es una condición previa para todas las funciones, no pueden funcionar sin una instancia válida de ArrayList, por lo que debe afirmar que una vez que la función entre.

Varios :

No es necesario que compruebe si el puntero es null antes de liberarlo . En arraylist_deallocate() la if (list->data != NULL) no se requiere la verificación.

arraylist_deallocate sería más simétrico con arraylist_create si se llama arraylist_destroy.

Comentarios

• ¿Cómo puedo verificar correctamente si tengo una instancia ArrayList válida?Lo que tengo hasta ahora es una macro que busca un valor específico de un nuevo campo que agregué a struct _arraylist. Dado que la declaración de estructura no está ‘ t disponible en el encabezado, el usuario de la interfaz ArrayList no puede acceder a ningún campo directamente (es decir, debe usar uno de las funciones de envoltura). Y específicamente no ‘ no di ninguna pista sobre este campo.
• @AmrAyman, depende de tu definición de válido, pero diría que la validación mínima sería compruebe que el puntero ArrayList no sea nulo y que ArrayList::data tampoco sea nulo. También puede verificar que cada matriz en data no sea nula: assert( list->data[i] != NULL );

Hablemos de rendimiento

¿Qué sucede si necesita usar su lista con mucha frecuencia?

Veamos más de cerca la función arraylist_add; si necesito una lista con 1 millón de bytes, que es 1 MB, reasignará su data miembro de estructura 1 millón de veces.

¡Es la parte más baja de tu lista!

Sugerencias

Asignar memoria por fragmentos , por ejemplo, C ++ std::vector usa un tamaño cada vez mayor de fragmentos agregados dependiendo del tamaño actual de std::vector.

Esto aumentará ejecutarlo varias veces con el propósito de agregar nuevos elementos.

Hablemos del código tal cual

Intente implementar un flujo de programa elegante pero simple.

Cree el tipo de valor (int) ArrayList, que asignará memoria por trozos en su lugar de reasignar la matriz completa y agregar algún comportamiento de lista debajo del capó. Me refiero a la lista de fragmentos, todavía necesita administrarla.

Aquí está mi solución con un ejemplo de uso de fragmentos de datos para cada nodo en lugar de reasignar nodos. Un tamaño de fragmento diferente puede ser mejor para uno de los siguientes propósitos: escribir, leer matrices largas; r \ w arreglos cortos; eliminar elementos; 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]); } } } 

Comentarios

• Respeto su interés. Sin embargo, esto es C, no C ++. Si fuera C ++, usaría vectores para hacer eso ..
• @AmrAyman, compruébalo
• ¡Eso ‘ es impresionante! Pero quiero tener una lista de matrices, no una lista vinculada. Aunque la implementación de su lista vinculada aquí es más avanzada que la implementación de estructura normal, glampert resolvió el problema.
• Acerca de la ganancia de rendimiento. No hay ‘ realmente tanto: Mi implementación se basa en el montón, normalmente porque se basa en una matriz; El suyo depende en gran medida de la recursividad, y eso ‘ es natural porque ‘ depende de los nodos. Además, liberar la lista sería mucho relativamente lento, porque ‘ usaría la recursividad (que tiene un rendimiento muy bajo) o un método bastante complicado while loop ..

Un problema no mencionado por otros es que su prueba no funciona. Parece que funciona, pero en realidad no. Cuando agrega valores a la lista, está pasando la dirección de la variable i:

arraylist_add(list, &i); 

Y arraylist_add simplemente guarda el valor pasado (como debería):

void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; 

Entonces, una vez que haya pasado por i = 0. .99 todo lo que tiene en la lista es la dirección de i 100 veces. Cuando vuelva a leer los datos, use de nuevo la variable de ciclo i y modifique su valor de 0..99 y el valor impreso se verá bien. Pero en realidad solo está viendo el valor de la variable de ciclo siendo modificado por el ciclo.

Si no me cree, imprima cualquier entrada de matriz fija, por ejemplo, 50, como en:

printf("i: %d\n", *(int *)arraylist_get(list, 50)); 

se imprimirá 100 (o cualquiera que sea el valor de i actualmente).

En su lugar, debería almacenar el valor real:

arraylist_add(list, (void*) i); 

e imprimir es necesario convertir el valor al tipo que tenía cuando entró:

printf("i: %d\n", (int)arraylist_get(list, t)); 

Hay muchos otros problemas con el código, como otros han notado . El diseño básico de usar su arraylist_setdata para hacer todas las modificaciones es incorrecto. Reasignar en cada cambio es simplemente malo: realloc es costoso. Y la idea básica de una lista que almacena cosas fingiendo que son void* me confunde y parece una mala idea.

Comentarios

• Bueno, puede que no lo notes, pero eso ‘ es exactamente lo que quería probar. Los punteros se almacenan y recuperan correctamente a través de los envoltorios de funciones.
• Almacenar cosas como void * no es ‘ tan malo como parece.Piénselo, void * simplemente almacena una dirección de memoria, que no ‘ me importa el tipo de valor almacenado en. En resumen, se supone que la matriz solo debe almacenar direcciones de memoria, y eso ‘ es prácticamente la única forma en que C trataría varios tipos en una sola matriz.
• Acerca de realloc, estoy de acuerdo con usted, pero no pude ‘ t encontrar una mejor manera de crear una dinámica matriz. De todos modos, seguí el consejo de glampert ‘ de incluir una función especial para eso, la shrink_to_fit función ..
• Me imaginé que estabas intentando guardar datos escalares de tamaño variable almacenándolos en un void* (varias personas han enviado código para hacerlo). Si realmente desea almacenar punteros, entonces una mejor prueba sería almacenar un número de punteros diferentes en un orden conocido y verificar que los recupera en el mismo orden, en lugar de guardar el mismo. puntero 100 veces. El problema con el almacenamiento de punteros es que el objeto apuntado debe ser persistente mientras dure la existencia de su dirección en la matriz. A pesar del vacío *, por supuesto, no puede mezclar tipos dentro de una matriz.
• Solo una forma diferente de hacer lo mismo, donde la matriz sigue inmediatamente después del final de la estructura. Ese método tiene sus propios problemas, así que olvídate de que lo mencioné.