Eu implementei a funcionalidade ArrayList em C da seguinte maneira:
#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 “Estou testando assim:
#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; } Funciona bem, embora realloc às vezes bloqueie o programa. Posso melhorar isso?
Comentários
Resposta
Primeiro, uma palavra sobre como nomear :
O nome que você” escolheu seu tipo, _arraylist é um nome ruim para um tipo de interface de biblioteca. Nomes começando com _ não são agradáveis de trabalhar no código do usuário. Eles são comumente usados no interior da biblioteca. Nomes melhores seriam ArrayList ou array_list.
Na verdade, em seu exemplo de uso, você tem ArrayList. Isso significa que no cabeçalho, que não está incluído aqui, você tem algo como isso?
typedef _arraylist ArrayList; Se você definiu um tipo opaco no cabeçalho, como acima, seria uma boa prática. Mas então você não deve usar nenhuma referência a _arraylist em seu código. Use sempre o nome typedef “d para evitar confusão.
O prefixo do nome da função também deve seguir exatamente o nome do tipo, portanto, para ArrayList todas as funções devem ser prefixado ArrayList_, por exemplo:
ArrayList * ArrayList_create(); Além disso, sugiro que você evite tightlypacked nomes, como em arraylist_getsize(). Adicionar um sublinhado para separar palavras torna-as muito mais legíveis. Por exemplo: ArrayList_get_size() .
Problemas com a memória :
Vamos examinar 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; } A primeira coisa incomum aqui são as afirmações. As afirmações não são a maneira adequada de lidar com uma falha de alocação de memória. , eles são geralmente desabilitados em compilações de lançamento, portanto, no lançamento, se por acaso você ficar sem memória, o programa travaria silenciosamente. Você provavelmente deve retornar um NULL neste caso (talvez também logar em stderr) e deixar o chamador lidar com este erro como ele vê apto.
O segundo problema aqui é com calloc(). Você está alocando 2 ponteiros vazios, no entanto, size está definido como zero. Eu realmente não entendo o ponto disso. Como sua estrutura é mais parecida com um array de arrays do que uma lista, o que você deve fazer é alocar o array de ponteiros com algum tamanho padrão predefinido e, em seguida, alocar os arrays individuais conforme necessário. a matriz de ponteiros sob demanda. Como arraylist_create() deve ser semelhante a:
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; } Outro grande problema de memória é a constante realocações feitas por arraylist_add() e arraylist_remove().
A remoção não deve reduzir a sequência. Mantenha esse espaço se a matriz crescerá novamente no futuro. Você pode adicionar uma maneira explícita de permitir que o usuário reduza o armazenamento, se necessário (a la std::vector::shrink_to_fit()).
Adicionando ao pode ser feito para executar em tempo constante amortizado se você pré-alocar armazenamento com um tamanho maior do que o solicitado. (Mais uma vez inspirado no STL vector).
sizeof erro :
Isso não retornará o que você espera:
size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } O sizeof operador sempre retorna o tamanho do tipo ao qual é aplicado. Ele não pode inferir o tamanho de uma matriz apontada por um ponteiro, porque é uma operação de tempo de compilação. arraylist_getsizeof() sempre retornará o mesmo valor, o tamanho de um ponteiro vazio, que será 4 ou 8, dependendo da arquitetura.
Use asserções para verificar invariantes :
Você deve assert que o *list parâmetro de cada função é válido. Esta é uma pré-condição de todas as funções, eles não podem funcionar sem uma instância ArrayList válida, então você deve afirmar isso assim que a função entrar.
Diversos :
Você não precisa verificar se o ponteiro é null antes de liberá-lo . Em arraylist_deallocate() a if (list->data != NULL) verificação é desnecessária.
arraylist_deallocate seria mais simétrico com arraylist_create se nomeado arraylist_destroy.
Comentários
- Como posso corretamente verificar se tenho uma instância
ArrayListválida?O que tenho até agora é uma macro que verifica se há um valor específico de um novo campo que adicionei astruct _arraylist. Uma vez que a declaração de struct não está ‘ disponível no cabeçalho, o usuário da interfaceArrayListnão pode acessar nenhum campo diretamente (ou seja, ele deve usar um dos as funções do wrapper). E eu especificamente não ‘ dei nenhuma pista sobre este campo. - @AmrAyman, depende da sua definição de válido, mas eu diria que a validação mínima seria verifique se o ponteiro
ArrayListnão é nulo e seArrayList::datatambém não é nulo. Você também pode verificar se cada matriz emdatanão é nula:assert( list->data[i] != NULL );
Resposta
Vamos falar sobre desempenho
E se você precisar usar sua lista com muita frequência?
Vejamos mais de perto a função arraylist_add; se eu precisar de uma lista com 1 milhão de bytes, que é 1 MB, ela realocará seu data membro da estrutura 1 milhão de vezes.
É a parte mais baixa da sua lista!
Sugestões
Alocar memória por blocos , por exemplo, C ++ std::vector usa um tamanho crescente de blocos anexados dependendo do tamanho atual de std::vector.
Isso aumentará execute-o algumas vezes com o propósito de adicionar novos elementos.
Vamos falar sobre o código como está
Tente implementar um fluxo de programa simples, mas elegante.
Crie o tipo de valor (int) ArrayList, que alocará memória por chuncks. de realocar a matriz completa e adicionar algum comportamento de lista nos bastidores. Quero dizer, lista de blocos, você ainda precisa gerenciá-la.
Aqui está minha solução com um exemplo de uso de blocos de dados para cada nó em vez de realocar nós. Diferentes tamanhos de chunck podem ser melhores para um dos seguintes propósitos: escrever, ler matrizes longas; r \ w matrizes curtas; removendo 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]); } } } Comentários
- Respeito o seu interesse. No entanto, isso é C, não C ++. Se fosse C ++, eu usaria apenas vetores para fazer isso.
- @AmrAyman, verifique
- Esse ‘ é impressionante! Mas eu quero ter um arraylist, não uma lista vinculada. Embora sua implementação de lista vinculada aqui seja mais avançada do que a implementação normal de struct, glampert resolveu o problema.
- Sobre o ganho de desempenho. Não existe ‘ realmente tanto: Minha implementação depende do heap, normalmente porque depende de um array; O seu depende fortemente da recursão, e isso ‘ é natural porque você ‘ depende de nós. Além disso, liberar a lista seria um muito lento relativamente, porque você ‘ d usaria recursão (que tem desempenho realmente baixo) ou um loop while ..
Resposta
Um problema não mencionado por outros é que seu teste não funciona. Parece funcionar, mas na realidade não. Ao adicionar valores à lista, você está passando o endereço da variável i:
arraylist_add(list, &i); E arraylist_add apenas salva o valor passado (como deveria):
void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; Assim, uma vez que você fez o loop através de i = 0. 0,99 tudo que você tem na lista é o endereço de i 100 vezes. Quando você lê os dados de volta, você usa a variável de loop i e modifica seu valor de 0..99 e o valor impresso parece correto. Mas você está apenas vendo o valor da variável de loop sendo modificada pelo loop.
Se você não acredita em mim, imprima qualquer entrada de array fixo, por exemplo, 50, como em:
printf("i: %d\n", *(int *)arraylist_get(list, 50)); ele imprimirá 100 (ou qualquer que seja o valor de i atualmente).
Em vez disso, você deve armazenar o valor real:
arraylist_add(list, (void*) i); e para imprimir você precisa converter o valor para o tipo que era quando foi inserido:
printf("i: %d\n", (int)arraylist_get(list, t)); Existem muitos outros problemas com o código, como outros notaram . O design básico de usar seu arraylist_setdata para fazer todas as modificações está errado. Realocar a cada alteração é simplesmente ruim – realloc é caro. E a ideia básica de uma lista que armazena coisas fingindo que são void* é confusa para mim e parece uma má ideia.
Comentários
- Bem, você pode não notar, mas que ‘ é exatamente o que eu queria testar. Esses ponteiros são armazenados e recuperados corretamente por meio dos wrappers de função.
- Armazenar coisas como
void *não ‘ é realmente tão ruim quanto parece.Pense nisso,void *simplesmente armazena um endereço de memória, que eu não ‘ não me importo com o tipo de valor armazenado. Em suma, a matriz deve armazenar apenas endereços de memória, e que ‘ é praticamente a única maneira que C lidaria com vários tipos em uma única matriz. - Sobre
realloc, concordo com você, mas não consegui ‘ encontrar uma maneira melhor de criar um dinâmico array. De qualquer forma, segui o conselho de glampert ‘ de encapsular uma função especial para isso, ashrink_to_fitfunção .. - Imaginei que você estava tentando salvar dados escalares de tamanho variável, armazenando-os em um
void*(várias pessoas enviaram códigos para fazer isso). Se você realmente quisesse armazenar ponteiros, um teste melhor seria armazenar vários ponteiros diferentes em uma ordem conhecida e verificar se você os recuperou na mesma ordem – em vez de salvá-los ponteiro 100 vezes. O problema com o armazenamento de ponteiros é que o objeto apontado deve ser persistente durante todo o tempo de existência de seu endereço no array. Apesar do vazio *, é claro que você não pode misturar tipos dentro de um array. - Apenas uma maneira diferente de fazer a mesma coisa, onde o array segue imediatamente após o final da estrutura. Esse método tem seus próprios problemas, então esqueça que o mencionei.
vectorem C / C ++, não como umaArrayListdo mundo Java.