C alocação dinamica de array, inclusão, exclusão e free

[codigo rapido]

Eu encontrei um post bem legal mostrando como fazer alocacao dinamica de arrays e quis compartilhar minha adaptação.
Eu achei interessante o insertInArray porque ele só faz o tamanho do array dobrar quando a quantidade usada ating e a quantidade limite.
Mas na deleção ele corrige para o tamanho em uso. Será que isso é uma boa ideia ou não vale a pena reduzir o tamanho depois da remoção de algum item?

 

// fonte da ideia:
// https://stackoverflow.com/questions/3536153/c-dynamically-growing-array/3536261

#include <stdio.h>
#include <stdlib.h>


typedef struct 
{
	int index;
	char *name;
} myData;


typedef struct 
{
	myData *array;
	size_t used;
	size_t size;
} Array;


void initArray(Array *a) 
{
	myData *pointer;

	pointer = (myData *)malloc(sizeof(myData));

	if (pointer == NULL)
	{
		printf("Unable to allocate memory, exiting.\n");
		free(pointer);
		exit(0);
	}
	else
	{
		a->array = pointer; 
		a->size = 0;
		a->used = 0;
	}
}

void insertInArray(Array *a, myData element) 
{
	// a->used é o numero usado
	// a->size é o limite
	if (a->used == a->size) 
	{
		if(a->size==0)a->size=1;
		else a->size *= 2;
		a->array = realloc(a->array, a->size * sizeof(myData));
	}
	a->array[a->used++] = element;
}

int deleteByIndexInArray(Array *a, int item) 
{
	Array temp;
	myData *pointer;
	initArray(&temp);


	for(int i=item; i<a->used; i++)
	{
		a->array[i] = a->array[i + 1];
	}
	a->used -= 1;


	for (int i=0; i<a->used; i++)
	{
		insertInArray(&temp, a->array[i]);
	}
	pointer = (myData *)realloc(temp.array, (temp.used) * sizeof(myData));


	if (pointer == NULL)
	{
		printf("Não foi possivel realocar memoria.\n");
		free(pointer);
		return -1;
	}
	printf("item %i deletado do array.\n", item );
	a->array = pointer;
	return 0; 
}

void deleteByDataInArray(Array *a, myData element) 
{
	myData data;
	for(int i=0; i<a->size; i++)
	{
		data = a->array[i];
		if( !strcasecmp(data.name, element.name) )
		{
			printf("%s deletado do array.\n", data.name );
			deleteByIndexInArray(a, i);
			break;
		}
	}
}

void freeArray(Array *a) 
{
	free(a->array);
	a->array = NULL;
	a->used = a->size = 0;
}

int main() 
{
	myData d1, d2, d3, d4, d5, d6;
	Array pointers;
	initArray(&pointers);

	d1.index=1;
	d1.name="Luiz";
	insertInArray(&pointers, d1);

	d2.index=3;
	d2.name="Sofia";
	insertInArray(&pointers, d2);

	d3.index=4;
	d3.name="Flavia";
	insertInArray(&pointers, d3);

	d4.index=5;
	d4.name="Daniele";
	insertInArray(&pointers, d4);

	d5.index=7;
	d5.name="Claudia";
	insertInArray(&pointers, d5);

	printf("======================================\n");
	for (int i = 0; i < pointers.used; i++)
	{
		printf("Index: %i Name: %s\n", pointers.array[i].index, pointers.array[i].name);
	}

	printf("======================================\n");
	deleteByIndexInArray(&pointers, 3);

	printf("======================================\n");
	for (int i = 0; i < pointers.used; i++)
	{
		printf("Index: %i Name: %s\n", pointers.array[i].index, pointers.array[i].name);
	}
	printf("======================================\n");
	deleteByDataInArray(&pointers, d5);

	printf("======================================\n");
	for (int i = 0; i < pointers.used; i++)
	{
		printf("Index: %i Name: %s\n", pointers.array[i].index, pointers.array[i].name);
	}

	freeArray(&pointers);
	return (EXIT_SUCCESS);
}

Certamente deve ter alguém com exemplos mais legais.

[V!OLADOR]

Em 20/08/2021 às 21:21, codigo rápido disse:

Será que isso é uma boa ideia ou não vale a pena reduzir o tamanho depois da remoção de algum item?

 

Não vale a pena. Alocação dinâmica é muito custosa. É mais eficiente alocar um bom pedaço de memória no inicio e apenas dobrar esse pedaço quando tiver esgotado todo o espaço. Na hora de reduzir você apenas define o índice que referencia o "topo" da parte utilizável de maneira que os índices acima referem-se a parte da memória alocada (e pronta pra uso) mas não utilizada. Esse método previne também a fragmentação da memória que vai ocorrer com as sucessivas chamadas de malloc, realloc e free.

De forma geral, essa ideia transforma o processo relativamente ineficiente de alocar, realocar e liberar memória numa simples manipulação de ponteiros, ou seja, super rápido. Na industria de games AAA, por exemplo, malloc, realloc, free, new e delete não são utilizados nas partes críticas do projeto.

[codigo rapido]

11 horas atrás, V!OLADOR disse:

 

Não vale a pena. Alocação dinâmica é muito custosa. É mais eficiente alocar um bom pedaço de memória no inicio e apenas dobrar esse pedaço quando tiver esgotado todo o espaço. Na hora de reduzir você apenas define o índice que referencia o "topo" da parte utilizável de maneira que os índices acima referem-se a parte da memória alocada (e pronta pra uso) mas não utilizada. Esse método previne também a fragmentação da memória que vai ocorrer com as sucessivas chamadas de malloc, realloc e free.

De forma geral, essa ideia transforma o processo relativamente ineficiente de alocar, realocar e liberar memória numa simples manipulação de ponteiros, ou seja, super rápido. Na industria de games AAA, por exemplo, malloc, realloc, free, new e delete não são utilizados nas partes críticas do projeto.

Eu tava pensando em casos em que se insere um dado e a deleção dele só acontece quando se abaixa uma flag nos dados, representando a exclusão. Nos casos em que se insere, imaginei que eu deveria já criar uma tabela vazia e ir adicionando o mais disperso possivel, para que se eu tiver a necessidade de inserir entre algum valor, eu ter os espaços vazios para ir jogando pra frente os que estiverem atrapalhando...
Eu to cheio de ideias pra fazer uns programas sobre isso. É um assunto muito legal e interessante. Mas infelizmente o o pouco tempo que tenho vai me obrigar a deixar isso pra depois.

Valeu! Ogrigado!