Часто мы имеем множество объектов одного семантического типа, но разных размеров, к примеру : строки, изображения, геометрия и тд. Предлагаю рассмотреть несколько паттернов которые позволяют упростить организацию, хранение и работу с такими объектами.
Для примеров будем брать хранение изображений в виде raw RGBA по 8 бит на канал.
Рассмотрим самый банальный вариант который приходит в голову :
struct image_t
{
unsigned short width, height;
unsigned char * raw;
void init(unsigned short setWidth, unsigned short setHeight, void * setRaw)
{
width = setWidth;
height = setHeight;
raw = (unsigned char*)malloc(width * height * 4);
memcpy(raw, setRaw, width * height * 4)
}
void clear()
{
free(raw);
width = 0;
height = 0;
}
};
...
std::vector<image_t*> images;
while(!eof())
{
...
image_t * image = (image_t*)malloc(sizeof(image_t));
image->init(...);
images.push_back(image);
}
Пример немного утрирован, но на практике и такой код попадается. Как мы видим тут происходит как минимум три типа аллокаций : в самом векторе, самой структуры изображения, самих данных. При большом количестве изображений это приводит к нас к излишней фрагментации хипа, излишним задержкам на аллокации и тд.
Первая оптимизация заключается в самом векторе, представим его так : (malloc для последующих нужд)
size_t count = ...;
image_t * images = (image_t*)malloc(sizeof(image_t) * count);
for(size_t i = 0; i < count; ++i)
{
...
images[i]->init(...);
}
Теперь у нас одна аллокация на пул, и N аллокаций на изображения, уже лучше.
Как теперь можно поместить данные изображения в этот пул ? самый банальный вариант это просто выделить место под все изображения, первую часть пула использовать как массив структур, а вторую часть пула для данных. В общем такой способ достаточно хорош, но не слишком уж и изящный.
Write in C (
видео)
Изящный подход будет основываться на хаке, который пришел к нам из системного программирования, официально утверждён только в C99, отсутствует в стандартах C++, но его поддерживают большинство современных компиляторов. Он называется flexible array member.
Суть в том что мы получаем структуру, с массивом на конце, но мы не указываем его размер. Банально да ?
Пример синтаксиса :
struct foo
{
int a, b, c;
int d[];
};
struct foo2
{
int a, b, c;
int * d;
};
Отличие состоит в том что sizeof(foo) = 12 (на 32 битах, при выравнивании в 4 байт), когда sizeof(foo2) = 16, те в первой структуре нет указателя, и данных нет
Но все операции работают как и с обычный массивом.
К примеру :
foo test;
test.a = 1;
test.d[100] = 5;
int * d2 = test.d;
Вполне рабочий код (вместо foo можете подставить foo2 и будет работать так же), а памяти кушает меньше.
Используя этот подход мы сможем организовать пул с такой схемой расположения в памяти : img_struct, img_data, img_struct, img_data ...
struct image_t
{
unsigned short width, height;
unsigned char raw[];
void init(unsigned short setWidth, unsigned short setHeight, void * setRaw)
{
width = setWidth;
height = setHeight;
memcpy(raw, setRaw, width * height * 4)
}
void clear()
{
width = 0;
height = 0;
}
inline size_t size() const
{
return sizeof(image_t) + width * height * 4;
}
};
...
// создание пула
size_t count = ...;
size_t totalImageSize = ...;
size_t totalBytes = sizeof(image_t) * count + totalImageSize;
unsigned char * images = (unsigned char*)malloc(totalBytes);
size_t offset = 0;
while(offset < totalBytes)
{
...
image_t * image = images + offset;
image->init(...);
offset += image->size();
}
...
// обходим все элементы
size_t totalBytes = ...;
size_t offset = 0;
while(offset < totalBytes)
{
image_t * image = images + offset;
...
offset += image->size();
}
Вот и всё ! Теперь такой пул можно просто сохранять на диск как бинарные данные, и читать с диска при загрузке за один fread, не нужно делать каких либо действий при загрузке.
Теперь разбор полётов, aka faq.
1) Мне нужен класс, а не структура, нужен конструктор и деструктор.
Без проблем, руками вызываем placement new и placement delete.
Синтаксис такой :
class foo
{
public:
foo() { ... }
~foo() { ... }
...
};
...
char temp[100];
foo * data = (foo*)temp;
// вызов конструктора
new (data) foo;
// вызов деструктора
foo->~foo();
2) Я хочу обращатся к элементам по индексу.
Если вам нужно постоянно обращатся к элементам переменного размера по индексу то проще всего будет использовать пул где в структуре используется указатель на массив данных (пример с unsigned char * raw, описан выше). Но если данных несколько (к примеру изображение с массивом мип-мапов) то дешевле всего в начало пула поместить массив указателей на структуры изображения в пуле, а сами данные размещать за структурой изображения как описано в этой статье, очевидно что описать все массивы с помощью поля переменного размера не получится, к второму и последующим массивам прийдется рассчитывать указатель руками.
Так же возможен немного другой обход указаний по индексу, переделайте свои индексы в указатели, когда данные на диске храните в указателях смещение в пуле (или всё же индекс элемента), а после загрузки пройдитесь по всем элементам и замените индексы на указатели, и во время работы вам не понадобится обращаться к элементам по индексам.
3) А как мне удалять элементы, создавать новые и тд ?
Пулы элементов переменного размера в общем не предназначены для динамического изменения. Вам нужно использовать другие структуры, например хип.