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

• Название: Эффективное использование STL
• Автор: Скотт Мейерс
• Издательство: Питер
• Жанр: Программирование
• Год: 2002
• ISBN: ISBN 5-94723-382-7

В этой книге известный автор Скотт Мейерс раскрывает секреты настоящих мастеров, позволяющие добиться максимальной эффективности при работе с библиотекой STL.

Во многих книгах описываются возможности STL, но только в этой рассказано о том, как работать с этой библиотекой. Каждый из 50 советов книги подкреплен анализом и убедительными примерами, поэтому читатель не только узнает, как решать ту или иную задачу, но и когда следует выбирать то или иное решение — и почему именно такое.

---

Мы подошли к последней странности распределителей памяти в 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.

Совет 11. Учитывайте область применения пользовательских распределителей памяти

Итак, в результате хронометража, профилирования и всевозможных экспериментов вы пришли к выводу, что стандартный распределитель памяти STL (то есть allocator<T>) работает слишком медленно, напрасно расходует или фрагментирует память, и вы лучше справитесь с этой задачей. А может быть, allocator<T> обеспечивает безопасность в многопоточной модели, но вы планируете использовать только однопоточную модель и не желаете расходовать ресурсы на синхронизацию, которая вам не нужна. Или вы знаете, что объекты некоторых контейнеров обычно используются вместе, и хотите расположить их рядом друг с другом в специальной куче, чтобы по возможности локализовать ссылки. Или вы хотите выделить блок общей памяти и разместить в нем свои контейнеры, чтобы они могли использоваться другими процессами. Превосходно! В каждом из этих сценариев уместно воспользоваться нестандартным распределителем памяти.

Предположим, у вас имеются специальные функции для управления блоком общей памяти, написанные по образцу malloc и free:

void* mallocShared(size_t bytesNeeded);

void freeShared(void *ptr);

Требуется, чтобы память для содержимого контейнеров STL выделялась в общем блоке. Никаких проблем:

template<typename Т>

class SharedMemoryAllocator{

public:

...

pointer allocate(size_type numObjects, const void* localityHint=0)

{

return static_cast<pointer>(mal1ocShared(numObjects *szeof(T)));

}

void deallocate(pointer ptrToMemory, size_type numObjects) {

freeShared(ptrToMemory);

}

}:

За информацией о типе pointer, а также о преобразовании типа и умножении при вызове allocate обращайтесь к совету 10. Пример использования SharedMemoryAllocator:

// Вспомогательное определение типа

typedef

vector<double.SharedMemoryAllocator<double> > SharedDoubleVec:

{// Начало блока

SharedDoubleVec v;// Создать вектор, элементы которого

// находятся в общей памяти

}// Конец блока

Обратите особое внимание на формулировку комментария рядом с определением v. Вектор v использует SharedMemoryAllocator, потому память для хранения элементов v будет выделяться из общей памяти, однако сам вектор v (вместе со всеми переменными класса) почти наверняка не будет находиться в общей памяти. Вектор v — обычный стековый объект, поэтому он будет находиться в памяти, в которой исполнительная система хранит все обычные стековые объекты. Такая память почти никогда не является общей. Чтобы разместить в общей памяти как содержимое v, так и сам объект v, следует поступить примерно так: