Я хотел вернуться «к основам» и попробовать написать векторную реализацию на 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 элемента, сообщаемый размер вектора верен, но мой цикл печатает элементы размера +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, потому что код очень длинный
мой вектор_end(vec) неверен или стирание неверно?
Для выражения не нужны скобки на 3-м. Просто for (it = begin; it != end; it = vector_iterator_offset())
. -fanalyzer
жалуется на отсутствие проверок NULL.
В божьем болте, который вы разместили, size_to_end
и bytes_to_copy
равны (?)
Независимо от вашего вопроса, в настоящее время существуют другие способы реализовать это, создав шаблонное макрорешение на основе типов, используя _Generic
и typeof
и, возможно, X-макросы. Довольно зловещий на вид код, поэтому я бы не рекомендовал его, но вводите безопасно, и вы получите размеры, отсортированные компилятором.
Нереально, стильно, субъективно: не прячьте указатель за typedef
-- см., например, stackoverflow.com/questions/17135033/…
// "past the last element"
Но size + 1
указывает на байт, следующий за последним элементом. Так что это не «после последнего элемента», а «байт после одного плюс последний элемент».
Когда вы находитесь на vec->data + vec->element_size * vec->size
, вы уже указываете на байт после последнего элемента. Нет +1
, размер — это уже количество элементов в векторе, а индекс массива начинается с 0.
мой вектор_end(vec) неверен или стирание неверно?
Да, вектор_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;
Моя ссылка на богболт https://godbolt.org/z/z5TvWzM7T .
Субъективная косметика:
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_create_capacity(...)
.gcc -fanalyzer
Кроме того, в последнее время мне все больше нравится библиотека STC, ее векторную реализацию можно увидеть здесь https://github.com/stclib/STC/blob/master/docs/vec_api.md .
Вы опередили меня на одну минуту, поэтому я просто отменю свой ответ :) +1
вектор скрыт как непрозрачная структура, поэтому я выделяю вектор и данные. Спасибо за помощь. Это безумие, сколько C++ отнимает у вас по сравнению с C. Когда я применяю изменения к vector_erase
и vector_end
, я получаю ту же проблему, но вместо этого двойной I
. И если я правильно помню, только unsigend char
— это стандартный способ представления необработанных байтов. Но я могу ошибаться.
@Raildex Правильно, для этого вам нужно использовать тип символа. Это создает еще одну проблему: во время выделения новых типов вы должны обязательно «касаться» этой новой области памяти, используя доступ на запись предполагаемого типа, а не символьного типа. Потому что, если вы напишете доступ к нему с использованием символьного типа, а затем попытаетесь получить к нему доступ с использованием предполагаемого типа, вы получите строгое нарушение псевдонимов — неопределенное поведение.
but with a double I instead
ссылка на бога там печатает один I
. Не думаю, что я что-то еще поменял...
@Lundin Я всегда разыменовываю объекты только по их соответствующим адресам, не так ли? Почему другой T
не сработает?
@Raildex Из-за системы типов C каждый адрес имеет «эффективный тип», который является формальным именем того типа, который, по мнению компилятора, хранится там. Если вы получаете к нему доступ через другой тип, вы вызываете неопределенное поведение. stackoverflow.com/questions/98650/…
Примечание: (слегка ОТ)
memcpy
перекрывающихся областей памяти может привести к неопределенному поведению. Вместо этого используйтеmemmove
.