Наконец-то, начинаю цикл статей о том, что меня больше всего привлекает - программирование.
Цепочка статей будет посвящена чистому языку С. Прежде чем начать программировать на языках с объектным подходом, необходимо научится хорошо это делать на процедурных языках. Язык С - это необходимая классика, которую нужно понимать, поскольку идеи данного языка лежат в основе многих других, в том числе объектно-ориентированных языках. Не говоря даже о синтаксисе, основной каркас которого, по сути, стал неким стандартом в мире программирования.
Поэтому, начнем с простого, но нетривиального для данного языка. А именно - структура данных вектор на основе динамических массивов. Вообще понятие структуры данных свойственно больше объектным языкам, где очень удобно воспользоваться классом для этой задачи. Но вот вдруг нам хочется написать игру под Linux с использованием библиотеки для подобия графики в терминалах ncurses и хранить структуры пуль в векторе? Но в таком случае хочется удобной и сладкой жизни с удобным интерфейсом для работы с памятью и массивами. Поэтому сделаем некое подобие вектора (vector в C++, ArrayList в Java и т.д) на основе структуры с несколькими полями, которая будет заменять нам объект вектора, и обычных функций, которые будут работать со "структурой-объектом" и выполнять роль методов класса. Сразу стоит отметить, что программировать будем как минимум на 99 стандартах языка, где уже есть for и т.д.
Углубляться в теоретические подробности - что за такая структура данных вектор, какая у нее трудоемкость поиска элемента и других операций - мы не будем. Это важно и нужно знать, но подобная теория неплохо разжевана и много где ее можно найти и почитать. У нас в данный момент присутствует лишь практический интерес к реализации этого дела на функциональном языке.
И так, начнем - сперва сделаем файлик заголовка, в котором будем все нужное нам объявлять. Я назвал cvector.h. В нем мы то как раз и объявим нужную нам структуру, которая будет выполнять роль объекта вектора. Какие поля нам нужны? Кончено же массив для хранения данных. Но мы делаем вектор, который должен хранить любой тип данных. Поэтому создаем массив указателей на тип void - void** data. Следующее поле - текущий размер вектора - сколько элементов в данный момент находится в векторе. Это просто целочисленная переменная - int size. Добавили элемент - увеличили size, удалили - уменьшили size. Далее мы должны хранить реальный, физический размер массива данных. То есть сколько элементов данных в нем реально может лежать. Поскольку вектор - структура динамическая, то эта величина физического размера массива также будет постоянно меняться. Обойдемся простым int capacity. И последнее поле - это размер элемента данных в байтах. Мы не знаем, какой тип будет лежать в векторе но, сколько выделять памяти под единицу элемента данных мы знать должны.
Пока вот так выглядит у меня заголовочный файл:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#ifndef CVECTOR_H_ #define CVECTOR_H_ #include // для функций работы с памятью #include // также для некоторых функций для работы с памятью //Стандартный размер вектора при инициализации #define CVECTOR_INIT_CAPACITY 4 /* * Структура, представляющая собой "объект" вектора. */ typedef struct{ void** data; int size; int capacity; size_t element_size; } cvector; #endif /* CVECTOR_H_ */ |
Теперь подумаем над интерфейсом вектора: какие функции у нас должны быть. Тут долго думать не будем, вектор должен уметь добавлять, удалять, изменять, предоставлять элементы, предоставлять текущий размер, менять свои размеры, очищаться. И конечно перед использованием вектор нужно инициализировать.
Вот так выглядит заголовочный файл со всеми объявлениями нужных нам функций:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#ifndef CVECTOR_H_ #define CVECTOR_H_ #include // для функций работы с памятью #include // также для некоторых функций для работы с памятью //Стандартный размер вектора при инициализации #define CVECTOR_INIT_CAPACITY 4 /* * Структура, представляющая собой "объект" вектора. * */ typedef struct{ void** data; int size; int capacity; size_t element_size; } cvector; /* * Инициализация структуры вектора. * * @param __v указатель на структуру вектора * @param __dataSize размер элемента данных в байтах */ void cvector_init(cvector* __v, size_t __dataSize); /* * Функция, которая возвращает текущее количество. * элементов в векторе * * @param __v указатель на структуру вектора */ int cvector_size(cvector* __v); /* * Функция добавления данных в конец вектора. * * @param __v указатель на структуру вектора * @param __data указатель на данные */ void cvector_push(cvector* __v, void* __data); /* * Функция изменения элемента вектора по индексу. * * @param __v указатель на структуру вектора * @param __index индекс элемента * @param __data указатель на новые данные */ int cvector_set(cvector* __v, int __index, void* __data); /* * Удаление элемента из вектора по индексу. * * @param __v указатель на структуру вектора * @param __index индекс удаляемого элемента */ int cvector_delete(cvector* __v, int __index); /* * Получение значения элемента по индексу. * * @param __v указатель на структуру вектора * @param __index индекс элемента */ void* cvector_get(cvector* __v, int __index); /* * Полная очистка вектора. * * @param __v указатель на структуру вектора */ void cvector_clear(cvector* __v); void cvector_resize(cvector* __v, int __newCap); #endif /* CVECTOR_H_ */ |
Теперь перейдем к реализации. В файле cvector.c загружаем наш заголовочный файл cvector.h (#include "cvector.h"), и начинаем функцию за функцией реализовывать. Полный код работающих функций приведен ниже, особо комментировать реализацию я не буду, поскольку она проста. Поясню лишь несколько моментов. Каждая функция, которая работает с вектором - получает указатель на нашу структуру "объекта" вектора, через которую функции получают доступ к массиву с данными, и проводят манипуляции с данным массивом. В функциях cvector_push и cvector_set вызывается memcpy(). Эта функция копирует данные из входных аргументов указателей в массив с данными. Зачем? Как мне верно подметили и подсказали коллеги, может случиться такая ситуация: представим, что данные мы не копируем. Где-нибудь в программе, где у нас используется данная реализация вектора без копирования, мы в определенной функции создали локальную переменную и решили ее сохранить в нашем векторе. Поскольку в векторе мы храним указатели, то при попытке доступа к данным по указателю, мы обращаемся в определенную область памяти. Если у нас локальная переменная - то время жизни памяти этой переменной - время работы функции, в которой она была объявлена. Поэтому после завершения функции, локальные переменные уничтожаются, память очищается автоматически, доступ к ней невозможен и подобная попытка завершается ошибкой. А в векторе то у нас указатели! Поэтому при попытке обращения по указателю к локальной переменной мы получаем обвал программы. Именно поэтому нужно копировать данные, чтобы избежать подобных ситуаций.
Также стоит взглянуть на реализацию функции удаления: cvector_delete(). При вызове этой функции, происходит очищение памяти указателя под номером __index. Далее в цикле происходит переприсваивание указателей, которые находятся дальше элемента __index на -1 позицию. То есть, мы просто сдвигаем все элементы, которые дальше _index влево на единицу. Таким образом, у нашего вектора осталась дырка в конце, обращение к которой непозволительно. Поэтому вызываем функцию перестроения размера массива указателей - вызов realloc с входным размером size - 1. То есть мы убираем эту дырку, поскольку realloc очистит нам все, что не входит в размер size - 1.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include "Cvector.h" void cvector_init(cvector* __v, size_t __dataSize){ __v->capacity = CVECTOR_INIT_CAPACITY; __v->size = 0; __v->element_size = __dataSize; __v->data = (void **) malloc(CVECTOR_INIT_CAPACITY * sizeof(void*)); } int cvector_size(cvector* __v){ return __v->size; } void cvector_push(cvector* __v, void* __data){ if(__v->size >= __v->capacity) cvector_resize(__v, __v->capacity + __v->capacity / 2); __v->data[__v->size] = (void*) malloc(__v->element_size); memcpy(__v->data[__v->size], __data, __v->element_size); __v->size++; } int cvector_set(cvector* __v, int __index, void* __data){ if(__index >= 0 && __index < __v->size){ memcpy(__v->data[__index], __data, __v->element_size); return 1; } return 0; } int cvector_delete(cvector* __v, int __index){ if(__index < 0 || __index > __v->size - 1 || __v->size <= 0) return 0; free(cvector_get(__v, __index)); for(int i = __index; i < __v->size - 1; i++) __v->data[i] = __v->data[i + 1]; cvector_resize(__v, __v->size - 1); __v->size--; return 1; } void* cvector_get(cvector* __v, int __index){ if(__index < 0 || __index > __v->size - 1 || __v->size <= 0) return NULL; return __v->data[__index]; } void cvector_clear(cvector* __v){ for(int i = 0; i < __v->size; i++) free(__v->data[i]); __v->size = 0; free(__v->data); } void cvector_resize(cvector* __v, int __newCap){ __v->capacity = __newCap; __v->data = realloc(__v->data, __newCap * sizeof(void *)); } |
Это рабочая версия аналога структуры данных вектора. Я тестировал все функции, работало все исправно. В случае, если будут найдены баги, буду признателен за оповещения меня и всех остальных читателей в комментариях.
Вот пример программы использования данного вектора с целочисленными элементами:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include #include "cvector.h" int main(){ cvector vector; cvector_init(&vector, sizeof(int)); for(int i = 0; i < 5; i++){ int elem = i * 2; cvector_push(&vector, (void*)&elem); } printf("Vector size: %d\n", cvector_size(&vector)); printf("Vector elements:\n"); for(int i = 0; i < cvector_size(&vector); i++){ int *elem = (int*) cvector_get(&vector, i); if(elem != NULL) printf("%d = %d\n", i, *elem); } if(cvector_delete(&vector, 2)) printf("Delete 3 element:\n"); else printf("Error in delete:\n"); printf("Vector elements:\n"); for(int i = 0; i < cvector_size(&vector); i++){ int *elem = (int*) cvector_get(&vector, i); if(elem != NULL) printf("%d = %d\n", i, *elem); } printf("Set last element to 777:\n"); int elem = 777; cvector_set(&vector, cvector_size(&vector) - 1, &elem); printf("Vector elements:\n"); for(int i = 0; i < cvector_size(&vector); i++){ int *elem = (int*) cvector_get(&vector, i); if(elem != NULL) printf("%d = %d\n", i, *elem); } cvector_clear(&vector); return 0; } |
Результат работы программы приведен на картинке ниже:
На этом все. Код в удобном виде вы можете найти на моем репозитории на Github: https://github.com/Tetraquark/Cvector. В случае если есть вопросы или замечания, дополнения - пожалуйста, пишите в комментариях, это будет полезно всем читателям, а особенно мне.
Жаль ,что ссылка на гит битая.