Gerenciando uma variedade de tipos indeterminados com indicadores de vazios

Question

Estou tentando escrever minha própria função de mesclagem da mesma maneira que a função QSORT de C. Se eu estivesse escrevendo Mergesort para uma variedade de itens conhecidos, não teria um problema, mas como não sei o que eles serão, está me jogando em um loop.

A especificação dada pelo meu professor não queria que eu usasse uma função separada para fusão, por isso estou escrevendo essa implementação dentro da própria função de Mergesort. Isso significa que terei as mesmas informações Qsort () teriam:

• void* base - um ponteiro para o primeiro elemento da matriz a ser classificado
• size_t nel - O número de elementos na matriz
• size_t width - O tamanho de cada elemento
• int (*compar)( const void*, const void* ) - uma função que informa como comparar cada elemento

O problema que estou tendo é com a parte de mesclagem. Toda implementação que eu vi usou uma matriz temporária para armazenar itens enquanto eles são classificados. Não estou tão acostumado a trabalhar com ponteiros vazios, e o maior obstáculo que encontrei está passando e atribuindo valores às matrizes. Como eu encontraria o valor no segundo índice na matriz apontada por base? Como eu poderia atribuir um valor dessa matriz em uma matriz temporária? Como eu criaria essa matriz temporária?

Funcionaria se eu lançasse as dicas vazias para char e apenas os incrementassem pela largura? Não tenho certeza de como a tarefa funcionaria.

Answer 1

Como eu encontraria o valor no segundo índice na matriz apontada pela base?

Usar (char *)base + (width*i). Isso lhe dará o endereço do i-ésimo elemento.

Como eu poderia atribuir um valor dessa matriz em uma matriz temporária?

Você apenas copia os dados. for (int n=0;n<width;n++) { //copy one byte from }

Como eu criaria a matriz temporária?

Algo como:

C - void* tempArray = malloc(width*elementsNeeded);

C ++ - void* tempArray = (void*) (new char[width*elementsNeeded]);

EDITAR:

Para explicar um pouco mais de cópia, você precisa fazer:

for (int n=0;n<width;n++) {
  adressTo[n] = addressFrom[n];
}
// This will copy the contents of pointer addressFrom to addressTo.

Answer 2

Como eu encontraria o valor no segundo índice na matriz apontada pela base? Funcionaria se eu lançasse as dicas vazias para char e apenas os incrementassem pela largura?

Sim está certo. O tamanho de um char é definido pelo padrão como 1; portanto, a "largura" que você recebe é, por definição, o tamanho de cada elemento em chars. Então você pode encontrar o endereço da seguinte maneira:

void *second_element_ptr = ((char*)base) + width;

Você não pode encontrar o valor, porque você não sabe o tipo e, portanto, não pode entender a memória que ele ocupa. Mas tudo bem, para classificar objetos em C com esta interface, você não precisa conhecer os valores deles: você precisa de ponteiros para eles, que pode passar para a função do comparador e precisa copiar objetos.

Como eu poderia atribuir um valor dessa matriz em uma matriz temporária?

char temporary_array[width]; // this is a C99 VLA, you might want to 
                             // allocate the array differently
memcpy(temporary_array, second_element_ptr, width);

Como eu criaria essa matriz temporária?

Ah, acho que levei essas perguntas na ordem errada. Para uma pequena matriz contendo um único elemento, você pode arriscar em um VLA. Ou você pode usar o Malloc da seguinte maneira:

// an array half the size of the input
// using char*, since unlike void* we can do arithmetic on it
char *big_temp_array = malloc(width * (nel + 1)/2);

BTW, o GCC suporta aritmética em void* como uma extensão do compilador, tratando -o como aritmética em char*. Depende de você decidir se você pode/usará isso.