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

void* operator new(size_t bytes);

pointer allocator::allocate(size_type numObjects);

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

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

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

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

Пожалуйста, не пытайтесь вникать в смысл последней фразы. Вместо этого просто рассмотрите следующий фрагмент и переходите к дальнейшему объяснению:

template

class allocator {

public:

template

struct rebind{

typedef allocator other;

};

}

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

Allocator::rebind::other

А теперь будьте внимательны. Каждый шаблон распределителя А (например, std::allocato r, SpecialAllocatorи т. д.) должен содержать вложенный шаблон структуры с именем rebind. Предполагается, что rebindполучает параметр U и не определяет ничего, кроме определения типа othe r , где other— просто имя для А. В результате list может перейти от своего распределителя объектов Т (allocator ) к распределителю объектов ListNode по ссылке allocator ::r ebind:: other.

Может, вы разобрались во всем сказанном, а может, и нет (если думать достаточно долго, вы непременно разберетесь, но подумать придется — знаю по своему опыту). Но вам как пользователю STL, желающему написать собственный распределитель памяти, в действительности не нужно точно понимать суть происходящего. Достаточно знать простой факт: если вы собираетесь создать распределитель памяти и использовать его со стандартными контейнерами, ваш распределитель должен предоставлять шаблон rebind, поскольку стандартные шаблоны будут на это рассчитывать (для целей отладки также желательно понимать, почему узловые контейнеры Т никогда не запрашивают память у распределителей объектов Т).

Ура! Наше знакомство со странностями распределителей памяти закончено. Позвольте подвести краткий итог того, о чем необходимо помнить при программировании собственных распределителей памяти: