Эффективное использование STL полностью

Оператор new отличается от allocator:: allocate и типом возвращаемого значения. Оператор new возвращает void*, традиционный способ представления указателя на неинициализированную память в С++. Функция allocator:: allocate возвращает T* (через определение типа pointer), что не только нетрадиционно, но и отдает мошенничеством. Указатель, возвращаемый allocator:: allocate, не может указывать на объект Т, поскольку этот объект еще не был сконструирован! STL косвенно предполагает, что сторона, вызывающая allocator:: allocate, сконструирует в полученной памяти один или несколько объектов Т (вероятно, посредством allocator:: construct, uniniialized_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. Список состоит из узлов, каждый из которых содержит объект Т и два указателя (на следующий и предыдущий узлы списка).

template// Возможная реализация

typename Allocator=allocator // списка

class list {

private:

Allocator alloc;// Распределитель памяти для объектов типа Т

struct LstNode{// Узлы связанного списка

Т data;

ListNode *prev;

ListNode *next;

};

};

При включении в список нового узла необходимо получить для него память от распределителя, однако нам нужна память не для Т, а для структуры ListNode, содержащей Т. Таким образом, объект Allocator становится практически бесполезным, потому что он выделяет память не для ListNode, а для Т. Теперь становится понятно, почему list никогда не обращается к allocator за памятью — последний просто не способен предоставить то, что требуется list.

Следовательно, list нужны средства для перехода от имеющегося типа распределителя к соответствующему распределителю ListNode. Задача была бы весьма непростой, но по правилам распределитель памяти должен предоставить определение типа для решения этой задачи. Определение называется other, но не все так просто — это определение вложено в структуру с именем rebind, которая сама по себе является шаблоном, вложенным в распределитель, — причем последний тоже является шаблоном!