主页 / coding / 问题 / 78701365
Accepted
Raildex
Asked: 2024-07-03 18:05:12 +0800 CST

使用 C 擦除向量中的元素的问题

  • 772

我想“回归基础”，尝试编写一个 C 向量实现。它使用 void* 来存储数据，我尝试稍微模仿一下 C++ 计数器部分。

我在删除元素时遇到了困难。删除多个元素后，向量的大小似乎与预期的大小不匹配。

以下是擦除函数的实现：

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);
}

擦除的用法是这样的。

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

当我删除 3 个元素时，报告的向量大小是正确的，但我的循环打印 size+1 个元素。

    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
B
F
G
H
I
J
J

Godbolt演示，因为代码很长

我的 vector_end(vec) 不正确还是擦除不正确？

c

1 个回答

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

    但size + 1指向最后一个元素之后的下一个元素的字节。因此，它不是“最后一个元素之后的字节”，而是“一个元素加最后一个元素之后的字节”。

    当您位于时，vec->data + vec->element_size * vec->size您已经指向了最后一个元素之后的字节。不+1，大小已经是向量中元素的数量，并且数组索引从 0 开始。

    我的 vector_end(vec) 不正确还是擦除不正确？

    是的，vector_end 令人困惑。只需：

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

    然后自然地复制结束和开始之间的范围。

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

    我的 godbolt 链接https://godbolt.org/z/z5TvWzM7T。

    主观美容：

    • 惊人的代码
    • typedef 指针对我来说仍然是一个危险信号。
      • 我会这样做，typedef struct { vector *parent; void *pos; } vector_iterator而不是每次传递两个参数。
      • 或者至少 typedef struct { void *pos; } vector_iterator;让我进行基本的类型检查
      • 但void *你得到了很好的!=比较，所以我明白这是很好的
    • 如果不打算取消引用它，只需用来char *表示字节，无需输入unsigned。
    • 太多了( )，有些地方就不需要了
    • #include "assert.h"->#include <assert.h>
    • 是否vector_create_capacity需要为 vector 本身分配两次内存？它可以通过值返回自身vector vector_create_capacity(...)。
    • 有些地方缺少 NULL 分配错误检查，请参阅gcc -fanalyzer抱怨
    • 总体来说很棒的代码

    此外，我最近对 ​​STC 库越来越感兴趣，你可以在这里看到它的矢量实现https://github.com/stclib/STC/blob/master/docs/vec_api.md。

    • 3

相关问题