I wanted to go “back to the basics” and try writing a C vector implementation.
It is using void* to store the data and i try to mimic the C++ counter part a little bit.
I am having difficulty erasing elements. precisely the size of the vector does not seem to match of whats expected after erasing multiple elements.
Here is the implementation of the erase function:
<code>typedef void* vector_iterator;
vector_iterator vector_begin(vector* vec) {
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 size_to_end = (unsigned char*)vector_end(vec) - (unsigned char*)src - vec->element_size;
memcpy(dest, src, bytes_to_copy); // copy all elements from (iterator +1) forward
vector_iterator vector_iterator_offset(vector_iterator iterator,vector* vec, ptrdiff_t offset) {
return (unsigned char*)iterator + (vec->element_size * offset);
<code>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 size_to_end = (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);
}
</code>
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 size_to_end = (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);
}
The usage of erasing is used like this.
<code>vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase the second element
<code>vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase the second element
</code>
vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase the second element
When I erase 3 elements, the reported size of the vector is correct, but my loop prints size+1 elements.
<code> vector* vec = vector_create_capacity(sizeof(char), 10);
for(char i = 'A'; i < 'A'+10; ++i) {
vector_push_back(vec, &i);
fprintf(stdout, "Size: %zun",vector_size(vec));
vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'C'
fprintf(stdout, "Size: %zun",vector_size(vec));
vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'D'
fprintf(stdout, "Size: %zun",vector_size(vec));
vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'E'
fprintf(stdout, "Size: %zun",vector_size(vec));
for(;it != vector_end(vec); (it = vector_iterator_offset(it, vec, 1))) {
fprintf(stdout,"%cn", data);
fprintf(stdout,"%zu",vector_size(vec));
//8 printed letters instead of 7 with double 'J'?
<code> 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: %zun",vector_size(vec));
fflush(stdout);
vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'C'
fprintf(stdout, "Size: %zun",vector_size(vec));
fflush(stdout);
vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'D'
fprintf(stdout, "Size: %zun",vector_size(vec));
fflush(stdout);
vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'E'
fprintf(stdout, "Size: %zun",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,"%cn", data);
fflush(stdout);
}
fprintf(stdout,"%zu",vector_size(vec));
fflush(stdout);
//8 printed letters instead of 7 with double 'J'?
vector_destroy(vec);
</code>
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: %zun",vector_size(vec));
fflush(stdout);
vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'C'
fprintf(stdout, "Size: %zun",vector_size(vec));
fflush(stdout);
vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'D'
fprintf(stdout, "Size: %zun",vector_size(vec));
fflush(stdout);
vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'E'
fprintf(stdout, "Size: %zun",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,"%cn", data);
fflush(stdout);
}
fprintf(stdout,"%zu",vector_size(vec));
fflush(stdout);
//8 printed letters instead of 7 with double 'J'?
vector_destroy(vec);
Godbolt demo, because the code is very long
is my vector_end(vec) incorrect or is the erasing incorrect?