Implementação Pure C Vector

5

Estou implementando um vetor em C. Estou fazendo isso pela diversão da programação, pela diversão do aprendizado e pelo uso da estrutura de dados em projetos posteriores. Isso não é lição de casa. Minha pergunta é sobre metodologia, não necessariamente implementação, portanto, não estou realmente procurando uma revisão de código.

Agora, eu li muitos exemplos de implementação e a maioria deles usa o tamanho de um elemento individual como um argumento para a função Vector_create() e usa isso para as chamadas memmove() / memcpy() posteriores e quais não e mais ou menos manter (por exemplo) os elementos do vetor na memória contígua. Em outras palavras, o array subjacente é essencialmente um único void* .

Na implementação que escrevi antes de analisar como as outras pessoas fizeram isso, eu permito (forçar) o código do cliente para alocar um "objeto" e passar isso como um ponteiro para a função Vector_append() . Então, meu array subjacente é um void** . Então, eu acho que a verdadeira pergunta que estou fazendo é se isso está errado. Errado como nas melhores práticas erradas.

Vejo que a maneira "normal" de fazer isso não usa uma matriz de ponteiros e apenas copia a memória de uma estrutura (por exemplo) na matriz void* subjacente e, assim, mantém os dados reais da matriz elementos contíguos, como mencionado anteriormente. Meu caminho evita uma carga de porcaria de memmove() / memcpy() porque eu apenas copio valores de ponteiro, no entanto, estou forçando o cliente a malloc() tudo que é enviado para o vetor e, assim, fazer um monte de enroscando no heap.

Nessa linha, eu chamo free() no item de dados subjacente quando o item é removido, portanto, a biblioteca de vetores faz um free() que a biblioteca de vetores nunca fez o original malloc() on. Esta é uma prática ruim também? O único problema que parece entrar é se havia uma variável de membro (por falta de um termo melhor) que aponta para a memória dinâmica dentro da estrutura. Em seguida, ele se torna a responsabilidade do cliente em free() desses dados, mas, novamente, a própria estrutura é liberada de dentro da chamada da biblioteca de vetores Vector_remove() .

    
por isolier 31.07.2013 / 05:28
fonte

1 resposta

7

Sim, o design do seu Vector está "errado".

  • Esse vetor geralmente é considerado como uma matriz redimensionável, com a expectativa associada de que, como uma matriz, ele contém diretamente os elementos. Sua exigência de que Vector armazena ponteiros para elementos alocados quebra essa expectativa.
  • Armazenar ponteiros é ineficiente se os elementos a serem armazenados forem pequenos (por exemplo, inteiros ou duplos), porque a sobrecarga da alocação dinâmica se torna significativa (2 a 3 vezes o tamanho dos dados) e você precisa armazenar o ponteiro e os dados reais, onde no design tradicional, você precisa apenas armazenar os poucos bytes para os dados reais. Além disso, no design tradicional, todos os elementos estão em locais de memória adjacentes, o que faz com que os padrões de acesso típicos (looping nos itens) sejam muito mais favoráveis ao cache do que seu design, onde os elementos estão espalhados na memória. / li>
  • Às vezes, é necessário armazenar itens conceitualmente em vários contêineres. Com o design convencional, isso pode ser acomodado armazenando ponteiros nos contêineres e gerenciando os objetos reais por conta própria. Essa técnica também pode ser usada para limitar a quantidade de cópias que precisam ser feitas, se o usuário do contêiner achar que é uma compensação razoável. Com seu design, você precisaria alocar dinamicamente os ponteiros que são armazenados no contêiner, o que está longe de ser conveniente e completamente contra-intuitivo para a maioria dos desenvolvedores.
  • Qualquer interface que requer um ponteiro para a memória alocada é propensa a uso indevido, porque o compilador não pode ver que Vector_append(&a) é um erro e para um revisor humano também não é imediatamente óbvio. Se você tiver sorte, isso é detectado durante o teste, mas em alguns casos ele não será detectado por muito tempo.
  • O fato de Vector_remove() excluir o item de dados também não ficará bem na maioria dos círculos de desenvolvimento, porque
    • Muitas diretrizes de codificação exigem que as chamadas malloc e free correspondentes sejam feitas a partir do mesmo módulo. Seu design torna impossível manter essa exigência.
    • É uma prática comum criar, para estruturas complexas que contêm ponteiros para a memória alocada, criar um par de funções de 'construtor' / 'destrutor' que cuidam de todas as alocações / limpezas de uma só vez, incluindo a 'raiz 'struct. Isso também não funciona corretamente com Vector_remove calling free .
por 31.07.2013 / 10:47
fonte