Pessoal tô começando a fazer o EP08 porém tenho algumas dúvidas.
na função put diz que preciso copiar key e val e inserir as cópias na árvore. Até a parte de alocar memória usando nVal e nKey eu entendi, porém não sei como devo fazer pra copiar o conteúdo de key e val para as novas posições de memórias alocadas...
Eu implementei a árvore usando dois vetores, keys[] e vals[], que são vetores de ponteiros void. É assim mesmo que deve ser feito?
Oi Alessandro,
na função put diz que preciso copiar key e val e inserir as cópias na árvore.
Você quis dizer no vetor e não árvore, certo?
Essa implementação será em vetor ordenado + buscas binária.
Até a parte de alocar memória usando nVal e nKey eu entendi, porém não sei como devo fazer pra copiar o conteúdo de key e val para as novas posições de memórias alocadas...
Legal que você perguntou.
Para clonarmos uma objeto apontado por obj e que possui nObj podemos fazer o seguinte.
/* o include abaixo já está no arquivo binarysearchst.c */ #include <string.h> /* memcpy() */ /* alocamos espaço para o clone/copia */ void *clone = emalloc(nObj); /* copiamos nObj bytes a partir da posição apontada por obj para a posição * apontada por clone */ memcpy(clone, obj, nObj);
A man page do memcpy() diz o seguinte
% man memcpy
MEMCPY(3) Linux Programmer's Manual MEMCPY(3)
NAME
memcpy - copy memory area
SYNOPSIS
#include <string.h>
void *memcpy(void *dest, const void *src, size_t n);
DESCRIPTION
The memcpy() function copies n bytes from memory area src to memory
area dest. The memory areas must not overlap. Use memmove(3) if the
memory areas do overlap.
RETURN VALUE
The memcpy() function returns a pointer to dest.
[...]
Eu implementei a árvore usando dois vetores, keys[] e vals[], que são vetores de ponteiros void. É assim mesmo que deve ser feito?
É isso mesmo.
É para implementar usando vetores.
Valeu pelos esclarecimentos...
Fiquei falando árvore toda hora pq pensei que a estrutura fosse algo parecido com um heap...
enfim, tenho outra dúvida... o que a função visitST deve fazer? varrer todos os nós? mas isso a função keys não faz?
Oi Alessandro,
Fiquei falando árvore toda hora pq pensei que a estrutura fosse algo parecido com um heap...
Legal que você comentou.
Heaps são usados quando desejamos armazenar valores e realizar rapidamente operações como max(), se for uma max-heap, ou min(), se for um min-heap.
A estrutura não foi projetada para armazena pares key-value e realizar eficientemente operações com como get(key). Para isso usamos ST.
o que a função visitST deve fazer?
Por favor, veja a especificação no esqueleto de binarysearchst.c
varrer todos os nós? mas isso a função keys não faz?
keys() é a implementação em C de um iterador.
Não recebe uma função como argumento.
professor, eu já havia lido a documentação antes de perguntar aqui.
gostaria que me dissesse se o que estou pensando está certo:
a função visitST recebe outra função visit como argumento. Daí essa função, a visitST, chama o iterador keysST e para cada par <key,val> sendo key retornado por keysST, chamo a função visit. Dai enquanto visit retornar algo != 0 ou enquanto houver chaves, a iteração prossegue. No final, retorno 0 se a iteração parou por causa de visit, ou algo != 0 se a iteração parou pq acabaram as chaves.
É isso mesmo ?? meu inglês é ruim...
Salve,
..Daí essa função, a visitST, chama o iterador keysST e para cada par <key,val>
Dá para fazer usando keys() e get(), como você disse.
Outra maneira é na função visitST() percorrer diretamente a parte da struct binarysearchst que armazera os vetores de key-val.
Deve ter outras maneiras de implementar.
Bom dia,
quando diz que "As chaves e valores desta implementação são mais ou menos genéricos", o que eu posso entender por mais ou menos?
Mais ou menos seria (int || char || string)?
Oi Sérgio,
quando diz que "As chaves e valores desta implementação são mais ou menos genéricos", o que eu posso entender por mais ou menos?
Legal!
Mais ou menos seria (int || char || string)?
Não.
Mais ou menos é mais do que isso.
Os tipos podem ser vetores ... mais ou menos.
Podem ser struct ... mais ou menos
Podem ser vetores de struct ...mais ou menos.
Não podem ser vetores ou struct com algum componente alocado dinamicamente.
Por exemplo, não podem ser vetores de String.
Alguém chuta a razão dessa restrição que corresponde ao menos dos mais ou menos?
Alguém chuta a razão dessa restrição que corresponde ao menos dos mais ou menos?
Olá, vou arriscar um palpite:
Como estamos usando memcpy, Imagino que a cópia de key que armazenamos teria ponteiros apontando para as mesmas regiões de memória para as quais a key original apontava no momento em que a cópia foi feita. Sendo assim, caso o responsável por gerenciar a key original decida por algum motivo desalocar a memória apontada pelos elementos de key, poderíamos ter problemas com a função de comparação passada para a st, caso esta tentasse acessar o conteúdo dos ponteiros da nossa cópia de key, que foram desalocados.
Oi Rafael,
Olá, vou arriscar um palpite:
[...]
Perfeito!
O que o EP08 (e EP09) fazem para copiar/clonar objetos é chamado de cópia rasa (shallow copy) .
Para clonar mesmo precisaríamos fazer cópia profunda (deep copy).
Essas coisas estão mais ou menos relacionadas ao object overhead do Java e que são comentadas na página 1.4 Analysis of Algorithms do algs4.
Nas implementações que estamos fazendo simplesmente não temos informação suficiente para fazermos deep copy.nKey e nVal nos permitem fazermos shallow copy.