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

Справедливости ради стоит отметить, что сразу же за положением об эквивалентности однотипных распределителей памяти в Стандарт включен следующий текст: «...Авторам реализаций рекомендуется создавать библиотеки, которые... поддерживают неэквивалентные распределители. В таких реализациях... семантика контейнеров и алгоритмов для неэквивалентных экземпляров распределителей определяется самой реализацией».

Трогательное проявление заботы, однако пользователю STL, рассматривающему возможность создания нестандартного распределителя с состоянием, это не дает практически ничего. Этим положением можно воспользоваться только в том случае, если вы уверены в том, что используемая реализация STL поддерживает неэквивалентные распределители, готовы потратить время на углубленное изучение документации, чтобы узнать, подходит ли вам «определяемое самой реализацией» поведение неэквивалентных распределителей, и вас не беспокоят проблемы с переносом кода в реализации STL, в которых эта возможность может отсутствовать. Короче говоря, это положение (для особо любознательных — абзац 5 раздела 20.1.5) лишь выражает некие благие намерения по поводу будущего распределителей. До тех пор пока эти благие намерения не воплотятся в жизнь, программисты, желающие обеспечить переносимость своих программ, должны ограничиваться распределителями без состояния.

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

void* operator new(size_t bytes);
pointer allocator<T>::allocate(size_type numObjects);
// Напоминаю: pointer - определение типа.
//практически всегда эквивалентное Т*

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

Оператор new отличается от allocator<T>:: allocate и типом возвращаемого значения. Оператор new возвращает void*, традиционный способ представления указателя на неинициализированную память в С++. Функция allocator<T>:: allocate возвращает T* (через определение типа pointer), что не только нетрадиционно, но и отдает мошенничеством. Указатель, возвращаемый allocator<T>:: allocate, не может указывать на объект Т, поскольку этот объект еще не был сконструирован! STL косвенно предполагает, что сторона, вызывающая allocator<T>:: allocate, сконструирует в полученной памяти один или несколько объектов Т (вероятно, посредством allocator<T>:: construct, uniniialized_fill или raw_storage_iterator), хотя в случае vector::reseve или string::reseve этого может никогда не произойти (совет 13). Различия в типах возвращаемых значений оператора new и allocator<T>:: allocate означают изменение концептуальной модели неинициализированной памяти, что также затрудняет применение опыта реализации оператора new к разработке нестандартных распределителей.

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

list<int> L;// То же, что и list<int,allocator<int».
// Контейнер никогда не вызывает
// allocator<int> для выделения памяти!
set<Widget.SAW> s;// SAW представляет собой определение типа
// для SpeciаlAllосаtor<Widget>, однако
// ни один экземпляр SAW не будет
// выделять память!

Данная странность присуща list и стандартным ассоциативным контейнерам (set, multiset, map и multimap). Это объясняется тем, что перечисленные контейнеры являются узловыми, то есть основаны на структурах данных, в которых каждый новый элемент размещается в динамически выделяемом отдельном узле. В контейнере list узлы соответствуют узлам списка. В стандартных ассоциативных контейнерах узлы часто соответствуют узлам дерева, поскольку стандартные ассоциативные контейнеры обычно реализуются в виде сбалансированных бинарных деревьев.

Давайте подумаем, как может выглядеть типичная реализация list<T>. Список состоит из узлов, каждый из которых содержит объект Т и два указателя (на следующий и предыдущий узлы списка).

template<typename Т>// Возможная реализация
	typename Allocator=allocator<T> // списка
class list {
   private:
Allocator alloc;// Распределитель памяти для объектов типа Т
	struct LstNode{// Узлы связанного списка
		Т data;
		ListNode *prev;
		ListNode *next;
	};
};

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

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

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

template<typename Т>
class allocator {
public:
	template<typename U>
	struct rebind{
		typedef allocator<U> other;
	};
}

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

Allocator::rebind<ListNode>::other

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

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

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

•распределитель памяти оформляется в виде шаблона с параметром Т, представляющим тип объектов, для которых выделяется память;

•предоставьте определения типов pointer и reference, но следите за тем, чтобы pointer всегда был эквивалентен Т*, а reference — Т&;

•никогда не включайте в распределители данные состояния уровня объекта. В общем случае распределитель не может содержать нестатических переменных;

•помните, что функциям allocate передается количество объектов, для которых необходимо выделить память, а не объем памяти в байтах. Также помните, что эти функции возвращают указатели Т* (через определение типа pointer) несмотря на то, что ни один объект Т еще не сконструирован;

•обязательно предоставьте вложенный шаблон rebind, от наличия которого зависит работа стандартных контейнеров.

Написание собственного распределителя памяти обычно сводится к копированию приличного объема стандартного кода и последующей модификации нескольких функций (в первую очередь allocate и deallocate). Вместо того чтобы писать базовый код с самого начала, я рекомендую воспользоваться кодом с web-страницы Джосаттиса [23] или из статьи Остерна «What Are Allocators Good For?» [24].

Материал, изложенный в этом совете, дает представление о том, чего нe могут сделать распределители памяти, но вас, вероятно, больше интересует другой вопрос — что они могут! Это весьма обширная тема, которую я выделил в совет 11.