При включении в список нового узла необходимо получить для него память от распределителя, однако нам нужна память не для
T
, а для структуры
ListNode
, содержащей
T
. Таким образом, объект
Allocator
становится практически бесполезным,
потому что он выделяет память не для
ListNode
, а для
T
. Теперь становится понятно, почему
list
никогда не обращается к
Allocator
за памятью — последний просто не способен предоставить то, что требуется
list
.
Следовательно,
list
нужны средства для перехода от имеющегося типа распределителя к соответствующему распределителю
ListNode
. Задача была бы весьма непростой, но по правилам распределитель памяти должен предоставить определение типа для решения этой задачи. Определение называется
other
, но не все так просто — это определение вложено в структуру с именем
rebind
, которая сама по себе является шаблоном, вложенным в распределитель, — причем последний тоже является шаблоном!
Пожалуйста, не пытайтесь вникать в смысл последней фразы. Вместо этого просто рассмотрите следующий фрагмент и переходите к дальнейшему объяснению:
template<typename T>
class allocator {
public:
template<typename U>
struct rebind{
typedef allocator<U> other;
};
…
}
В программе, реализующей
list<T>
, возникает необходимость определить тип распределителя
ListNode
, соответствующего распределителю, существующему для
T
. Тип распределителя для
T
задается параметром
allocator
. Учитывая сказанное, тип распределителя для
ListNode
должен выглядеть так:
Allocator::rebind<ListNode>::other
А теперь будьте внимательны. Каждый шаблон распределителя
A
(например,
std::allocator, SpecialAllocator
и т. д.) должен содержать вложенный шаблон структуры с именем
rebind
. Предполагается, что
rebind
получает параметр
U
и не определяет ничего, кроме определения типа
other
, где
other
— просто имя для
A<U>
. В результате
list<T>
может перейти от своего распределителя объектов
T(Allocator)
к распределителю объектов
ListNode
по ссылке
Allocator::rebind<ListNode>::other.
Может, вы разобрались во всем сказанном, а может, и нет (если думать достаточно долго, вы непременно разберетесь, но подумать придется — знаю по своему опыту). Но вам как пользователю STL, желающему написать собственный распределитель памяти, в действительности не нужно точно понимать суть происходящего. Достаточно знать простой факт: если вы собираетесь создать распределитель памяти и использовать его со стандартными контейнерами, ваш распределитель должен предоставлять шаблон
rebind
, поскольку стандартные шаблоны будут на это рассчитывать (для целей отладки также желательно понимать,
почему узловые контейнеры
T
никогда не запрашивают память у распределителей объектов
T
).
Ура! Наше знакомство со странностями распределителей памяти закончено. Позвольте подвести краткий итог того, о чем необходимо помнить при программировании собственных распределителей памяти:
• распределитель памяти оформляется в виде шаблона с параметром
T
, представляющим тип объектов, для которых выделяется память;
• предоставьте определения типов
pointer
и
reference
, но следите за тем, чтобы pointer всегда был эквивалентен
T*
, а
reference
—
T&
;
• никогда не включайте в распределители данные состояния уровня объекта. В общем случае распределитель не может содержать нестатических переменных;
• помните, что функциям
allocate
передается количество объектов, для которых необходимо выделить память, а не объем памяти в байтах. Также помните, что эти функции возвращают указатели
T*
(через определение типа
pointer
) несмотря на то, что ни один объект
T
еще не сконструирован;
• обязательно предоставьте вложенный шаблон
rebind
, от наличия которого зависит работа стандартных контейнеров.
Написание собственного распределителя памяти обычно сводится к копированию приличного объема стандартного кода и последующей модификации нескольких функций (в первую очередь
allocate
и
deallocate
). Вместо того чтобы писать базовый код с самого начала, я рекомендую воспользоваться кодом с web-страницы Джосаттиса [23] или из статьи Остерна «What Are Allocators Good For?» [24].
Материал, изложенный в этом совете, дает представление о том, чего не могут сделать распределители памяти, но вас, вероятно, больше интересует другой вопрос — что они могут? Это весьма обширная тема, которую я выделил в совет 11.
Совет 11. Учитывайте область применения пользовательских распределителей памяти
Итак, в результате хронометража, профилирования и всевозможных экспериментов вы пришли к выводу, что стандартный распределитель памяти STL (то есть
allocator<T>
) работает слишком медленно, напрасно расходует или фрагментирует память, и вы лучше справитесь с этой задачей. А может быть,
allocator<T>
обеспечивает безопасность в многопоточной модели, но вы планируете использовать только однопоточную модель и не желаете расходовать ресурсы на синхронизацию, которая вам не нужна. Или вы знаете, что объекты некоторых контейнеров обычно используются вместе, и хотите расположить их рядом друг с другом в специальной куче, чтобы по возможности локализовать ссылки. Или вы хотите выделить блок общей памяти и разместить в нем свои контейнеры, чтобы они могли использоваться другими процессами. Превосходно! В каждом из этих сценариев уместно воспользоваться нестандартным распределителем памяти.
Предположим, у вас имеются специальные функции для управления блоком общей памяти, написанные по образцу
malloc
и
free
:
void* mallocShared(size_t bytesNeeded);
void freeShared(void *ptr);
Требуется, чтобы память для содержимого контейнеров STL выделялась в общем блоке. Никаких проблем: