Во время написания кода на языке C программист постоянно сталкивается с проблемой выделения и освобождения памяти, а также разыменовывания указателей. Отсутствие классов и шаблонов (в частности vector) порождает массу кода, затрудняющего его чтение и как следствие сопровождение. Нередко задача усложняется использованием в качестве элемента массива сложной структуры данных, которая в свою очередь также содержит динамические массивы.

Для устранения недостатков появилась идея создать аналог std::vector для использования его в языке C. Реализацию этого типа рассмотрим ниже, а сейчас рассмотрим его использование для упрощения работы со строками и массивами:


#include “clib/vector.h” //подключение заголовочного файла с реализацией вектора

// тест создания массивов байт
void can_create_vectors(TestFramework* framework)
{
	const unsigned char data[]={0,1,2,3,4,5,6,7,8,9};

	vector v1 = vector_create(5); // создание вектора нулей размером 5
	vector v2 = vector_from(data,10); // создание из массива 
	vector v3 = vector_from(vector_cbegin(v2),vector_size(v2)); //создание из другого вектора

	// методы для простого тестирования 	
	test(framework,"CanCreateVector1", *vector_at(v1,3)==0); // первый вектор содержит нули
	test(framework,"CanCreateVector2", *vector_at(v2,9)==9); // второй вектор в позиции 9 содержит число 9
	test(framework,"CanCreateVector3", *vector_at(v3,5)==5); // третий вектор в позиции 5 содержит число 5

	// удаление векторов
	vector_free(v1);
	vector_free(v2);
	vector_free(v3);
}

// тест создания строк
void can_create_strings(TestFramework* framework)
{
	string s1 = string_create(0); // пустая строка
	string s2 = string_froms("ABCDEFG"); // строка из константы
	string s3 = string_froms(string_cbegin(s2)); // строка из другой строки
	string s4 = string_froms(string_cbegin(s1));

	test(framework,"CanCreateStrings1", strcmp(string_cbegin(s2),"ABCDEFG")==0);
	test(framework,"CanCreateStrings2", strcmp(string_cbegin(s3),"ABCDEFG")==0);
	test(framework,"CanCreateStrings3", strcmp(string_cbegin(s4),"")==0);

	string_free(s1);
	string_free(s2);
	string_free(s3);
	string_free(s4);
}


Отдельно стоит отметить возможность использования сложных структур данных для элементов массива, которые также могут содержать вектора и строки. Для этого объявляется сама структура данных и вспомогательные методы инициализации (конструктор), деинициализации (деструктор) и копирования:


// Сложная структура данных
typedef struct 
{
	string name;
	vector data;
	int type;
} TMyItem;

// функция инициализации
__inline void vector_my_item_initialize(TMyItem* data) 
{
	data->type=0;
	data->name = string_create(0);
	data->data = vector_create(0);
}
// функция-деструктор
__inline void vector_my_item_deinitialize(TMyItem* item)
{
	string_free(item->name);
	vector_free(item->data);
}
// функция копирования
__inline void vector_my_item_clone(TMyItem* destination, const TMyItem* source) 
{
	destination->type = source->type;
	destination->data = vector_clone(source->data);
	destination->name = string_clone(source->name);
}
// объявление массива vector_my с элементами TMyItem
_CLIB_VECTOR(TMyItem,vector_my,0);


Работать с вновь созданным вектором (vector) достаточно просто:


void can_create_structs(TestFramework* framework)
{
	TMyItem item;
	vector_my v1,v2;
	// инициализация элемента для проведения теста
	item.type=5; 
	item.name=0;
	item.data = vector_create(0);
	vector_push(item.data,5); // добавление в массив элемента числа 5

	v1 = vector_my_create(5); // создание вектора структур со значениями по умолчанию
	v2 = vector_my_from(&item,1); // создание из существующих данных
	vector_free(item.data); // освобождение данных тестовой структуры
		
	test(framework,"CanCreateStruct1", vector_my_at(v1,3)->type==0); // значение по умолчанию
	test(framework,"CanCreateStruct2", vector_my_at(v2,0)->type==5); // должно быть значение 5 (которое присвоили ранее)
	test(framework,"CanCreateStruct3", *vector_at(vector_my_at(v2,0)->data,0)==5); // первый элемент массива в структуре должен быть равен пяти (вставили ранее)

	// освобождение созданных структур
	vector_my_free(v1);
	vector_my_free(v2);
}


Поддерживается операция вставки (на примере string):


void can_insert_strings(TestFramework* framework)
{
	string s1 = string_create(0);
	string_inserts(s1,0,"abc");

	test(framework,"CanInsertStrings1",strcmp(string_cbegin(s1),"abc")==0);

	string_inserts(s1,2,"AB");
	test(framework,"CanInsertStrings2",strcmp(string_cbegin(s1),"abABc")==0);

	string_free(s1);
}


Поддерживается операция клонирования (на примере vector):


void can_clone_vectors(TestFramework* framework)
{
	const unsigned char data[]={0,1,2,3,4,5,6,7,8,9};

	vector v1 = vector_from(data,10);
	vector v2 = vector_clone(v1);

	test(framework,"CanCloneVectors1",vector_size(v2)==10);
	test(framework,"CanCloneVectors2",*vector_at(v2,5)==5);

	vector_free(v1);
	vector_free(v2);
}


Заголовочный файл vector.h дополнительно содержит объявления vector_int и vector_uint:


__inline void vector_uint_item_initialize(unsigned int* data) {*data=0;}
__inline void vector_uint_item_deinitialize(unsigned int* data) {};
__inline void vector_uint_item_clone(unsigned int* destination, const unsigned int* source) {*destination=*source;}
_CLIB_VECTOR(unsigned int,vector_uint,0);

__inline void vector_int_item_initialize(int* data) {*data=0;}
__inline void vector_int_item_deinitialize(int* data) {};
__inline void vector_int_item_clone(int* destination, const int* source) {*destination=*source;}
_CLIB_VECTOR(int,vector_int,0);


Тест производительности показал одинаковые результаты с STL. Для проведения теста использовалась вставка 10 символов в строку 100000 раз.

Исходный код vector.h:


#ifndef _CLIB_VECTOR_H
#define _CLIB_VECTOR_H

#include <memory.h>
#include <malloc.h>
#include <string.h>

#define _CLIB_VECTOR(item_type, type_name, nullterminated) \
\
typedef void* type_name; \
\
typedef struct {\
	item_type* data;\
	size_t size;\
	size_t capacity;\
} _##type_name;\
__inline type_name type_name##_create(size_t size) \
{\
	size_t i;\
	_##type_name* result = (_##type_name*)malloc(sizeof(_##type_name));\
	result->data=0;\
	result->size=size;\
	result->capacity=size+nullterminated;\
	if (result->capacity>0)\
	{\
		result->data = (item_type*)malloc(result->capacity*sizeof(item_type));\
		for (i=0;i<result->size;i++) type_name##_item_initialize(&result->data[i]);\
		if (nullterminated)\
		{\
			memset(&result->data[result->size],0,sizeof(item_type));\
		}\
	}\
	return result;\
}\
__inline void type_name##_free(type_name v) \
{\
	size_t i;\
	_##type_name* s = (_##type_name*)v;\
	if (s!=0)\
	{\
		if (s->data!=0)\
		{\
			for (i=0;i<s->size;i++) type_name##_item_deinitialize(&s->data[i]);\
			free(s->data);\
		}\
		free(s);\
	}\
}\
\
__inline size_t type_name##_size(type_name v)\
{\
	_##type_name* s = (_##type_name*)v;\
	return s!=0 ? s->size : 0;\
}\
\
__inline size_t type_name##_capacity(type_name v)\
{\
	_##type_name* s = (_##type_name*)v;\
	return s!=0 ? s->capacity : 0;\
}\
__inline type_name type_name##_clone(type_name v)\
{\
	size_t i;\
	_##type_name* source = (_##type_name*)v;\
	_##type_name* result;\
	if (source==0) return 0;\
	result = (_##type_name*)malloc(sizeof(_##type_name));\
	result->data=0;\
	result->size=source->size;\
	result->capacity=source->capacity;\
	if (result->capacity>0)\
	{\
		result->data = (item_type*)malloc(result->capacity*sizeof(item_type));\
		for (i=0;i<result->size;i++) type_name##_item_clone(&result->data[i], &source->data[i]);\
		if (nullterminated)\
		{\
			memset(&result->data[result->size],0,sizeof(item_type));\
		}\
	}\
	return result;\
}\
__inline void type_name##_resize(type_name v, size_t size)\
{\
	size_t i,min_index;\
	size_t old_size;\
	item_type* old_ptr;\
	_##type_name* source = (_##type_name*)v;\
	if (source==0) return;\
	old_size = source->size;\
	old_ptr = source->data;\
	source->data=0;\
	source->size=size;\
	source->capacity=size+nullterminated;\
	if (source->capacity>0)\
	{\
		min_index=old_size<size?old_size:size;\
		source->data = (item_type*)realloc(source->data,source->capacity*sizeof(item_type));\
		for (i=min_index;i<source->size;i++) type_name##_item_initialize(&source->data[i]);\
		if (nullterminated)\
		{\
			memset(&source->data[source->size],0,sizeof(item_type));\
		}\
	}\
	free(old_ptr);\
}\
__inline void type_name##_clear(type_name v) \
{\
	_##type_name* source = (_##type_name*)v;\
	if (source!=0)\
	{\
		free(source->data);\
		source->size=0;\
		source->capacity=nullterminated;\
		if (nullterminated)\
		{\
			memset(&source->data[source->size],0,sizeof(item_type));\
		}\
	}\
}\
__inline void type_name##_push(type_name v, item_type value) \
{\
	_##type_name* source = (_##type_name*)v;\
	if (source==0) return;\
	if ((source->size+nullterminated)>=source->capacity)\
	{\
		if (source->capacity==0) \
		{\
			source->capacity=1;\
		}\
		else\
		{\
			source->capacity=source->capacity<<1;\
		}\
		source->capacity+=nullterminated;\
		source->data=(item_type*)realloc(source->data,source->capacity*sizeof(item_type));\
	}\
	source->size++;\
	type_name##_item_clone(&source->data[source->size-1], &value);\
	if (nullterminated)\
	{\
		memset(&source->data[source->size],0,sizeof(item_type));\
	}\
}\
__inline void type_name##_insert(type_name v, size_t index, const item_type* data, size_t size) \
{\
	size_t i,len;\
	_##type_name* source = (_##type_name*)v;\
	if (source==0) return;\
	if (data==0) return;\
	if (size==0) return;\
	if (index>source->size) return;\
	if ((source->size+size+nullterminated)>=source->capacity)\
	{\
		if (source->capacity==0) \
		{\
			source->capacity=size;\
		}\
		else\
		{\
			source->capacity=(size+source->capacity)<<1;\
		}\
		source->capacity+=nullterminated;\
		source->data=(item_type*)realloc(source->data,source->capacity*sizeof(item_type));\
	}\
	len=source->size-index;\
	source->size+=size;\
	if (len>0)\
	{\
		memcpy(&source->data[index+size],&source->data[index],len*sizeof(item_type));\
	}\
	for (i=index;i<(index+size);i++) type_name##_item_clone(&source->data[i], &data[i-index]);\
	\
	if (nullterminated)\
	{\
		memset(&source->data[source->size],0,sizeof(item_type));\
	}\
}\
__inline type_name type_name##_from(const item_type* data, size_t size) \
{\
	_##type_name* result = type_name##_create(0);\
	type_name##_insert(result,0,data,size);\
	return result;\
}\
__inline item_type* type_name##_begin(type_name v) \
{\
	_##type_name* source = (_##type_name*)v;\
	if (source==0) return 0;\
	return source->data;\
}\
__inline const item_type* type_name##_cbegin(type_name v) \
{\
	_##type_name* source = (_##type_name*)v;\
	if (source==0) return 0;\
	return (const item_type*)source->data;\
}\
__inline item_type* type_name##_end(type_name v) \
{\
	_##type_name* source = (_##type_name*)v;\
	if (source==0) return 0;\
	return (source->data + source->size);\
}\
__inline const item_type* type_name##_cend(type_name v) \
{\
	_##type_name* source = (_##type_name*)v;\
	if (source==0) return 0;\
	return (const item_type*)(source->data+source->size);\
}\
__inline item_type* type_name##_at(type_name v, size_t index)\
{\
	_##type_name* source = (_##type_name*)v;\
	if (source==0) return 0;\
	return &source->data[index];\
}\
__inline const item_type* type_name##_cat(type_name v, size_t index)\
{\
	_##type_name* source = (_##type_name*)v;\
	if (source==0) return 0;\
	return (const item_type*)&source->data[index];\
}


__inline void vector_uint_item_initialize(unsigned int* data) {*data=0;}
__inline void vector_uint_item_deinitialize(unsigned int* data) {};
__inline void vector_uint_item_clone(unsigned int* destination, const unsigned int* source) {*destination=*source;}
_CLIB_VECTOR(unsigned int,vector_uint,0);

__inline void vector_int_item_initialize(int* data) {*data=0;}
__inline void vector_int_item_deinitialize(int* data) {};
__inline void vector_int_item_clone(int* destination, const int* source) {*destination=*source;}
_CLIB_VECTOR(int,vector_int,0);

__inline void vector_item_initialize(unsigned char* data) {*data=0;}
__inline void vector_item_deinitialize(unsigned char* data) {};
__inline void vector_item_clone(unsigned char* destination, const unsigned char* source) {*destination=*source;}
_CLIB_VECTOR(unsigned char,vector,0);

__inline void string_item_initialize(char* data) {*data=0;}
__inline void string_item_deinitialize(char* data) {};
__inline void string_item_clone(char* destination, const char* source) {*destination=*source;}
_CLIB_VECTOR(char,string,1);
__inline string string_froms(const char* data)
{
	size_t len = data!=0 ? strlen(data) : 0;
	return string_from(data,len);
}
__inline void string_inserts(string s, size_t index, const char* data)
{
	size_t len = data!=0 ? strlen(data) : 0;
	string_insert(s,index,data,len);
}

#endif


В ближайшее время будет реализован «препроцессорный» list и map.