Во время разработки одного из своих проектов я обнаружил, что мне нужен контейнер, способный менять свой размер по мере необходимости. Так как я большую часть времени разрабатываю на С++, а не на С, я очень хотел получить что-то похожее на std::vector<T> из С++. Я начал искать в интернете реализации, но они мне не подходили по разным причинам. Тогда я решил разработать свой вариант.
Не мы первые, не мы последние
Стоит всё таки упомянуть другие реализации, которые я рассматривал. Вот их список:
Все эти реализации имеют один или более перечисленных ниже недостатков:
Макросы-функции. Всем известно, что их сложно отлаживать, они не умеют возвращать значение (кроме расширения GNU, но я пользуюсь Clang с предупреждениями об использовании расширений GNU, либо отдельного аргумента-указателя, что тоже не очень практично), из-за них возрастает размер исполняемого файла и на них нельзя взять указатель.
Определение вектора как структуры. Это принуждает пользователя обращаться к данным через поле (например,
vector->data[index]
), что тоже неудобно, из-за чего увеличивается исполняемый файл и засоряется код.
Итого, задача: разработать аналог std::vector из С++ для языка С, обладающий следующими функциями:
Обращение к элементам напрямую
Инкапсуляция метаданных вектора от пользователя
Реализация без злоупотребления макросами (т. е. отказ от использования макросов-функций)
Как?
Как соблюсти все три пункта? Предлагаю разобрать каждый из них по отдельности, и позже приступить к полноценной реализации:
Обращение к элементам напрямую
Для того, чтобы сделать это, можно передавать пользователю ссылку на массив данных, а не на саму структуру вектора. Но при этом, нужно учесть возможность получения структуры из адреса данных. Можно сделать это крайне примитивным и хорошо работающим способом: при инициализации выделить память под структуру + данные и вернуть указатель на данные, которые идут сразу после структуры. Так можно обращаться к элементам напрямую, при этом всё ещё имея эффективный доступ к метаданным. Пример:
100 | 101 | 102 | 103 | 104 | 105 | 106 |
... | размер | ещё | другие | данные | элем. 0 | элем. 1 |
указатель |
Инкапсуляция метаданных вектора от пользователя
Сначала я хотел выделить это в отдельный механизм, но потом обнаружил, что реализация пункта 1 уже выполняет и этот пункт. Идём дальше.
Реализация без злоупотребления макросами
Я специально выбрал такую размытую формулировку. Дело в том, что если обойтись вообще без макросов, то получится крайне неудобно. Я запрещу себе использовать конкретно макросы-функции (с {}). каждый макрос будет равен одному вызову функции, чтобы препроцессинг был тривиальным и исполняемый файл не разбухал.
Итог и пример использования
На исследование темы я потратил порядка 2-3 часов, на реализацию ~час времени, на написание данной статьи тоже. Но большую часть времени я потратил на упаковку своего решения. Я сделал pacman пакет и опубликовал его в AUR. Позже планируется так же сделать apt-пакет и rpm-пакет, но увы, я не знаю аналогов AUR для Debian и других, так что эти пакеты просто можно будет собрать из исходных текстов (в будущем). Теперь, пример использования:
#include "cvec.h"
#include <stdio.h>
#include <stdlib.h>
int main() {
cvec(int) vec = cvec_new(int, 10);
if (!vec) {
printf("failed to create cvec\n");
return 1;
}
for (int i = 0; i < 10; i++) {
int j = i + 1;
cvec_push(int, vec, &j);
}
vec[0] = 20;
vec[9] = 30;
vec[5] = 40;
for (int i = 0; i < 10; i++) {
int *item = cvec_pop(int, vec);
if (!item) {
printf("failed to pop item\n");
continue;
}
printf("%d\n", *item);
}
cvec_delete(vec);
return 0;
}
Документация к библиотеке пока что не планируется: она настолько мала, что изучение исходного кода займет не более 10 минут.как можно заметить, я реализовал с помощью макросов систему, похожую на шаблоны из С++, правда, конечно, моя версия для С очень далека до того, что есть в С++.
Ссылки
Изменено
Спасибо всем за тестирование моей библиотеки! Очень рад тому, что кто-то действительно исследовал мою работу. Вы нашли много багов и недоработок, которые в ближайшее время будут исправлены.