Эффективное использование STL - [26]

(вероятно, посредством allocator::construct, uninitialized_fill или raw_storage_iterator), хотя в случае vector::reseve или string::reseve этого может никогда не произойти (совет 13). Различия в типах возвращаемых значений оператора new и allocator::allocate означают изменение концептуальной модели неинициализированной памяти, что также затрудняет применение опыта реализации оператора new к разработке нестандартных распределителей.

Мы подошли к последней странности распределителей памяти в STL: большинство стандартных контейнеров никогда не вызывает распределителей, с которыми они ассоциируются. Два примера:

list L; // То же, что и list
             // Контейнер никогда не вызывает
             // allocator для выделения памяти!
set s;// SAW представляет собой определение типа
                  // для SpeciаlAllосаtor, однако
                  // ни один экземпляр SAW не будет
                  // выделять память!
Данная странность присуща list и стандартным ассоциативным контейнерам (set, multiset, map и multimap). Это объясняется тем, что перечисленные контейнеры являются узловыми, то есть основаны на структурах данных, в которых каждый новый элемент размещается в динамически выделяемом отдельном узле. В контейнере list узлы соответствуют узлам списка. В стандартных ассоциативных контейнерах узлы часто соответствуют узлам дерева, поскольку стандартные ассоциативные контейнеры обычно реализуются в виде сбалансированных бинарных деревьев.
Давайте подумаем, как может выглядеть типичная реализация list. Список состоит из узлов, каждый из которых содержит объект T и два указателя (на следующий и предыдущий узлы списка).
template,           // Возможная реализация
typename Allocator=allocator // списка
class list {
private:
 Allocator alloc;// Распределитель памяти для объектов типа T
 struct ListNode{// Узлы связанного списка
  T data;
  ListNode *prev;
  ListNode *next;
 };
 …
};
При включении в список нового узла необходимо получить для него память от распределителя, однако нам нужна память не для T, а для структуры ListNode, содержащей T. Таким образом, объект Allocator становится практически бесполезным, потому что он выделяет память не для ListNode, а для T. Теперь становится понятно, почему list никогда не обращается к Allocator за памятью — последний просто не способен предоставить то, что требуется list.
Следовательно, list нужны средства для перехода от имеющегося типа распределителя к соответствующему распределителю ListNode. Задача была бы весьма непростой, но по правилам распределитель памяти должен предоставить определение типа для решения этой задачи. Определение называется other, но не все так просто — это определение вложено в структуру с именем rebind, которая сама по себе является шаблоном, вложенным в распределитель, — причем последний тоже является шаблоном!
Пожалуйста, не пытайтесь вникать в смысл последней фразы. Вместо этого просто рассмотрите следующий фрагмент и переходите к дальнейшему объяснению:
template
class allocator {
public:
 template
 struct rebind{
  typedef allocator other;
 };
 …
}
В программе, реализующей list, возникает необходимость определить тип распределителя ListNode, соответствующего распределителю, существующему для T. Тип распределителя для T задается параметром allocator. Учитывая сказанное, тип распределителя для ListNode должен выглядеть так:
Allocator::rebind::other
А теперь будьте внимательны. Каждый шаблон распределителя A (например, std::allocator, SpecialAllocator и т. д.) должен содержать вложенный шаблон структуры с именем rebind. Предполагается, что rebind получает параметр U и не определяет ничего, кроме определения типа other, где other — просто имя для A. В результате list может перейти от своего распределителя объектов T(Allocator) к распределителю объектов ListNode по ссылке Allocator::rebind::other.
Может, вы разобрались во всем сказанном, а может, и нет (если думать достаточно долго, вы непременно разберетесь, но подумать придется — знаю по своему опыту). Но вам как пользователю STL, желающему написать собственный распределитель памяти, в действительности не нужно точно понимать суть происходящего. Достаточно знать простой факт: если вы собираетесь создать распределитель памяти и использовать его со стандартными контейнерами, ваш распределитель должен предоставлять шаблон rebind, поскольку стандартные шаблоны будут на это рассчитывать (для целей отладки также желательно понимать, почему узловые контейнеры T никогда не запрашивают память у распределителей объектов T).
Ура! Наше знакомство со странностями распределителей памяти закончено. Позвольте подвести краткий итог того, о чем необходимо помнить при программировании собственных распределителей памяти:
• распределитель памяти оформляется в виде шаблона с параметром T, представляющим тип объектов, для которых выделяется память;
• предоставьте определения типов pointer и reference, но следите за тем, чтобы pointer всегда был эквивалентен