Проблема стирания элементов в векторе с помощью C

Я хотел вернуться «к основам» и попробовать написать векторную реализацию на 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) неверен или стирание неверно?

Примечание: (слегка ОТ) memcpy перекрывающихся областей памяти может привести к неопределенному поведению. Вместо этого используйте memmove.

teapot418 03.07.2024 12:15

Для выражения не нужны скобки на 3-м. Просто for (it = begin; it != end; it = vector_iterator_offset()) . -fanalyzer жалуется на отсутствие проверок NULL.

KamilCuk 03.07.2024 12:38

В божьем болте, который вы разместили, size_to_end и bytes_to_copy равны (?)

KamilCuk 03.07.2024 12:43

Независимо от вашего вопроса, в настоящее время существуют другие способы реализовать это, создав шаблонное макрорешение на основе типов, используя _Generic и typeof и, возможно, X-макросы. Довольно зловещий на вид код, поэтому я бы не рекомендовал его, но вводите безопасно, и вы получите размеры, отсортированные компилятором.

Lundin 03.07.2024 12:53

Нереально, стильно, субъективно: не прячьте указатель за typedef -- см., например, stackoverflow.com/questions/17135033/…

pmg 03.07.2024 13:11
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
5
81
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий
 // "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 по-прежнему являются для меня тревожным сигналом.
    • Я бы сделал 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(...).
  • в некоторых местах отсутствуют проверки ошибок распределения NULL, см. жалобы gcc -fanalyzer
  • в целом отличный код

Кроме того, в последнее время мне все больше нравится библиотека STC, ее векторную реализацию можно увидеть здесь https://github.com/stclib/STC/blob/master/docs/vec_api.md .

Вы опередили меня на одну минуту, поэтому я просто отменю свой ответ :) +1

Lundin 03.07.2024 12:51

вектор скрыт как непрозрачная структура, поэтому я выделяю вектор и данные. Спасибо за помощь. Это безумие, сколько C++ отнимает у вас по сравнению с C. Когда я применяю изменения к vector_erase и vector_end, я получаю ту же проблему, но вместо этого двойной I. И если я правильно помню, только unsigend char — это стандартный способ представления необработанных байтов. Но я могу ошибаться.

Raildex 03.07.2024 12:56

@Raildex Правильно, для этого вам нужно использовать тип символа. Это создает еще одну проблему: во время выделения новых типов вы должны обязательно «касаться» этой новой области памяти, используя доступ на запись предполагаемого типа, а не символьного типа. Потому что, если вы напишете доступ к нему с использованием символьного типа, а затем попытаетесь получить к нему доступ с использованием предполагаемого типа, вы получите строгое нарушение псевдонимов — неопределенное поведение.

Lundin 03.07.2024 13:07
but with a double I instead ссылка на бога там печатает один I. Не думаю, что я что-то еще поменял...
KamilCuk 03.07.2024 13:10

@Lundin Я всегда разыменовываю объекты только по их соответствующим адресам, не так ли? Почему другой T не сработает?

Raildex 04.07.2024 13:39

@Raildex Из-за системы типов C каждый адрес имеет «эффективный тип», который является формальным именем того типа, который, по мнению компилятора, хранится там. Если вы получаете к нему доступ через другой тип, вы вызываете неопределенное поведение. stackoverflow.com/questions/98650/…

Lundin 04.07.2024 15:46

Другие вопросы по теме

Могу ли я доказать монотонность ассигнований с помощью Rust Borrow Checker
Почему нам следует устанавливать для -XX:InitialRAMPercentage и -XX:MaxRAMPercentage одно и то же значение для облачной среды?
Есть ли что-то вроде указателя для массивов numpy?
C Могу ли я использовать данные, которые я освободил сразу после освобождения?
Веб-скрапинг в R с использованием циклов while. Ошибка в open.connection(x, «rb»): ошибка HTTP 429, когда веб-страница существует
Как обрабатывать данные о ценах на криптовалюту и токены в режиме реального времени на сервере, память моего сервера через некоторое время переполняется
Fread() читает неправильные данные, хотя предыдущий фрагмент был прочитан правильно
Vec-подобные контейнеры разных типов, которые могут использовать один и тот же блок памяти в куче
Как изменить биты в записи таблицы страниц (PTE) в ядре Linux на ARM64?
Когда использовать Span<T> вместо Marshal при вызове собственных API Win32?