C语言Vector实现erase元素后大小与遍历输出不符问题排查

我尝试“回归基础”，用C语言实现一个类C++的Vector，采用void*存储数据。但在删除元素时遇到问题：多次执行erase操作后，Vector的size值显示正确，但遍历输出时会多一个元素（出现重复的J）。

相关函数实现 #

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

测试代码及输出 #

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

问题原因及修复方案 #

问题出在vector_end的实现和erase函数的字节计算两处：

1. vector_end的错误：
   C++风格的end迭代器应该指向最后一个元素的下一个位置，正确计算应为data + element_size * size。你当前的代码写成了element_size * (size+1)，导致end的位置多偏移了一个元素的大小，遍历循环会多执行一次，读到内存中未被更新的旧数据（也就是之前的最后一个元素J）。

修正后的vector_end：

vector_iterator vector_end(vector* vec) {
    return ((unsigned char*)vec->data) + (vec->element_size * vec->size); // 正确指向最后一个元素的下一位
}

2. erase函数中bytes_to_copy的计算错误：
   原代码中bytes_to_copy的计算依赖错误的vector_end，再额外减去element_size，会导致需要复制的字节数少了一个元素的大小，前移操作不完整。正确的计算应该是从src到正确end位置的总字节数，也就是：

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

或者用元素数量计算更直观：

// 计算当前迭代器对应的元素索引
size_t idx = ((uintptr_t)iterator - (uintptr_t)vec->data) / vec->element_size;
// 需要前移的元素数量：总元素数 - 当前索引 - 1
size_t elements_to_move = vec->size - idx - 1;
size_t bytes_to_copy = elements_to_move * vec->element_size;

同时修正这两处后，遍历循环会正确终止，erase操作也会完整前移后续元素，就不会出现重复的J了。

内容的提问来源于stack exchange，提问作者user3001150