Скотт Мейерс - Эффективное использование STL

Выше уже говорилось о том, что распределители обладают определенным сходством с оператором new— они тоже занимаются выделением физической памяти, но имеют другой интерфейс. Чтобы убедиться в этом, достаточно рассмотреть объявления стандартных форм operator newи allocator::allocate:

void* operator new(size_t bytes);

pointer allocator::allocate(size_type numObjects);

// Напоминаю: pointer - определение типа.

//практически всегда эквивалентное T*

В обоих случаях передается параметр, определяющий объем выделяемой памяти, но в случае с оператором newуказывается конкретный объем в байтах, а в случае с allocator::allocateуказывается количество объектов T, размещаемых в памяти. Например, на платформе, где sizeof (int)==4, при выделении памяти для одного числа intоператору newпередается число 4, а allocator::allocate— число 1. Для оператора newпараметр относится к типу size_t, а для функции allocate— к типу allocator::size_type, В обоих случаях это целочисленная величина без знака, причем allocator::size_typeобычно является простым определением типа для size_t. В этом несоответствии нет ничего страшного, однако разные правила передачи параметров оператору newи allocator::allocateусложняют использование готовых пользовательских версий new в разработке нестандартных распределителей.

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