Início / coding / Perguntas / 78701365
Accepted
Raildex
Asked: 2024-07-03 18:05:12 +0800 CST

problema em apagar elementos em um vetor usando C

  • 772

Eu queria "voltar ao básico" e tentar escrever uma implementação de vetor C. Ele está usando void* para armazenar os dados e tento imitar um pouco a parte do contador C++.

Estou tendo dificuldade em apagar elementos. precisamente o tamanho do vetor não parece corresponder ao esperado após apagar vários elementos.

Aqui está a implementação da função apagar:

typedef void* vector_iterator;

vector_iterator vector_begin(vector* vec) {
    return vec->data;
}

vector_iterator vector_end(vector* vec) {
    return ((unsigned char*)vec->data) + ((vec->element_size * (vec->size+1))); // "past the last element"
}

void vector_erase(vector* vec, vector_iterator iterator) {
    assert(iterator >= vector_begin(vec));
    assert(iterator < vector_end(vec));
    assert(((uintptr_t)iterator - (uintptr_t)vector_begin(vec)) % vec->element_size == 0);
    unsigned char* dest = (unsigned char*)iterator;
    unsigned char* src = dest + vec->element_size; // src is the element erased element + 1, since we want to pull all objects forward
    size_t bytes_to_copy= (unsigned char*)vector_end(vec) - (unsigned char*)src - vec->element_size;
    memcpy(dest, src, bytes_to_copy); // copy all elements from (iterator +1) forward
    vec->size--;
}

vector_iterator vector_iterator_offset(vector_iterator iterator,vector* vec, ptrdiff_t offset) {
    return (unsigned char*)iterator + (vec->element_size * offset);
}

O uso de apagar é usado assim.

vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase the second element

Quando apago 3 elementos, o tamanho relatado do vetor está correto, mas meu loop imprime tamanho+1 elementos.

    vector* vec = vector_create_capacity(sizeof(char), 10);
    //test for push back
    for(char i = 'A'; i < 'A'+10; ++i) {
        vector_push_back(vec, &i);
    }
    
    //...//
    
    fprintf(stdout, "Size: %zu\n",vector_size(vec));
    fflush(stdout);

    vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'C'
    fprintf(stdout, "Size: %zu\n",vector_size(vec));
    fflush(stdout);

    vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'D'
    fprintf(stdout, "Size: %zu\n",vector_size(vec));
    fflush(stdout);

    vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'E'
    fprintf(stdout, "Size: %zu\n",vector_size(vec));
    fflush(stdout);
    
    it = vector_begin(vec);
    for(;it != vector_end(vec); (it = vector_iterator_offset(it, vec, 1))) {
        
        char data = *(char*)it;
        fprintf(stdout,"%c\n", data);
        fflush(stdout);
    }
    fprintf(stdout,"%zu",vector_size(vec));
    fflush(stdout);
    //8 printed letters instead of 7 with double 'J'?
    vector_destroy(vec);

A saída no final é

A
B
F
G
H
I
J
J

Demonstração Godbolt, porque o código é muito longo

meu vector_end(vec) está incorreto ou o apagamento está incorreto?

c

1 respostas

  1. Best Answer
     // "past the last element"

    Mas size + 1aponta para o byte após o próximo elemento após o último. Portanto, não é "além do último elemento", é "o byte após um mais o último elemento".

    Quando você está no vec->data + vec->element_size * vec->sizevocê já está apontando para o byte após o último elemento. Não +1, o tamanho já é a contagem de elementos do vetor e os arrays indexam a partir de 0.

    meu vector_end(vec) está incorreto ou o apagamento está incorreto?

    Sim, vector_end é confuso. Apenas:

    vector_iterator vector_end(vector* vec) {
    return ((char *)vec->data) + vec->element_size * vec->size; // "past the last element"
}

    E então, naturalmente, você copia o intervalo entre o final e o início.

     size_t bytes_to_copy = (unsigned char*)vector_end(vec) - (unsigned char*)src;

    Meu link godbolt https://godbolt.org/z/z5TvWzM7T .

    Cosméticos subjetivos:

    • código incrível
    • ponteiros typedef ainda são uma bandeira vermelha para mim.
      • Eu faria isso typedef struct { vector *parent; void *pos; } vector_iteratorem vez de passar dois parâmetros de cada vez.
      • ou pelo menos typedef struct { void *pos; } vector_iterator; para que eu obtenha uma verificação de tipo rudimentar
      • mas com void *você temos uma boa !=comparação, então eu entendo que é bom ter
    • se você não planeja desreferencia-lo, basta usar char *para representar o byte, não há necessidade de digitar unsigned.
    • tantos ( ), eles não são necessários em alguns lugares
    • #include "assert.h"->#include <assert.h>
    • precisa vector_create_capacityalocar memória duas vezes e para o próprio vetor? Poderia simplesmente retornar por value vector vector_create_capacity(...).
    • alguns lugares estão faltando verificações de erro de alocação NULL, veja gcc -fanalyzerreclamação
    • geral ótimo código

    Além disso, ultimamente tenho me divertido cada vez mais com a biblioteca STC, você pode ver sua implementação vetorial aqui https://github.com/stclib/STC/blob/master/docs/vec_api.md .

    • 3

relate perguntas