23 мая 2009

Container with a preallocated buffer

STL-ные контейнеры - замечательная вещь, вот только хранят они все на куче. А иногда ведь так хочется, чтобы они использовали какой-нибудь буфер внутри объекта. Что-то типа такого:
template <typename T, size_t N>
struct Container
{
size_t size; // сколько элементов в контейнере
T storage[N]; // заранее выделенный буфер для объектов
};
Такой контейнер будет полезен, например, когда создается временный контейнер на стеке, максимальное количество элементов в нем предполагается известным. Или, например, когда нам нужен контейнер на небольшое нефиксированное количество элементов. Ну правда, стоит ли из-за контейнера на 1-2 небольших элемента заниматься выделением-освобождением памяти на куче (что довольно затратно по времени)?

Есть похожие на это контейнеры:
- boost.array, но он хранит только фиксированное количество элементов, для переменного количества не подойдет
- boost.optional - это почти то, что нужно, но если нужно хранить не более 1 элемента ;)

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

В boost-е планируется к review нужный контейнер - auto_buffer. Его еще немного допилят по интерфейсу, но пользоваться уже можно смело. В добавок он может, как и basic_string, расти в кучу, если нужно.

5 комментариев:

bishop комментирует...

Я эту проблему решал очень просто в STL - созданием алокатора на стэке. Делается элементарно 1 раз, делается typedef читабельный и можно после этого с удовльствием пользоваться :)

Raider комментирует...

Это не совсем то.

Тебе помимо аллокатора потребуется еще контейнер. Допустим, ты возьмешь std::vector. Он, например, сначала выделит 16 элементов, ты их разместишь в своем буффере (допустим он на 50 элементов). Потом он попросит у тебя 32 элемента - ты ему опять дашь указатель на свой буфер, и вектор будет копировать 16 существующих элементов в "новое" старое место, потом он попросит у тебя 64 элемента - ты полезешь в кучу (в буфере места у тебя на 50 элементов всего), но в реальности куча могла быть и не нужна - вектору просто нужно было разместить 48 элементов, а расти он умеет только двухкратными шагами - он же ничего не знает о размере твоего буфера. Вобщем, по-моему, все это не то, что было нужно...

Константин Казимиров комментирует...

А если дополнить то, что Вы описали разумным(изменённым) использованием reserve для стандартных контейнеров, то по идее получится, то что Вы хотите. Ибо рост контейнера по 2-х кратной стратегии увеличения размера идёт по умолчанию, и его можно изменять, хотя бы с использованием того же reserve. Собственно сам так и делал, когда была нужна менее жадная стратегия роста контейнера.

Анонимный комментирует...

То, что вам необходимо - это класс auto_buffer из библиотеки stlsoft. Описание здесь http://www.synesis.com.au/software/stlsoft/doc-1.9/classstlsoft_1_1auto__buffer.html
Первый параметр шаблока - это тип элементов, а второй - число, показывающее зарезервированное место в стеке. Если необходимое число элементов будет превышено, то память выделится уже в куче.

Анонимный комментирует...

Вот такие недоработки есть:
отсутствую методы assign и resize,
в uninitialized_resize - ОШИБКА!