vi_is_raven 7 мая в 12:15

std::vector в C?

Простой

3 мин

6.2K

C*C++*Ненормальное программирование*Программирование*

Во время разработки одного из своих проектов я обнаружил, что мне нужен контейнер, способный менять свой размер по мере необходимости. Так как я большую часть времени разрабатываю на С++, а не на С, я очень хотел получить что-то похожее на 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 минут.как можно заметить, я реализовал с помощью макросов систему, похожую на шаблоны из С++, правда, конечно, моя версия для С очень далека до того, что есть в С++.

Ссылки

Изменено

Спасибо всем за тестирование моей библиотеки! Очень рад тому, что кто-то действительно исследовал мою работу. Вы нашли много багов и недоработок, которые в ближайшее время будут исправлены.

Хабы: