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

Во многих приложениях структуры данных используются не столь непредсказуемо. Операции со структурами данных делятся на три раздельные фазы.

1.Подготовка. Создание структуры данных и вставка большого количества элементов. В этой фазе со структурой данных выполняются только операции вставки и удаления. Поиск выполняется редко или полностью отсутствует.

2.Поиск. Выборка нужных данных из структуры. В этой фазе выполняются только операции поиска. Вставка и удаление выполняются редко или полностью отсутствуют.

3.Реорганизация. Модификация содержимого структуры данных (возможно, со стиранием всего текущего содержимого и вставкой новых элементов). По составу выполняемых операций данная фаза эквивалентна фазе 1. После ее завершения приложение возвращается к фазе 2.

В приложениях, использующих эту схему работы со структурами данных, контейнер vector может обеспечить лучшие показатели (как по времени, так и по затратам памяти), чем ассоциативный контейнер. С другой стороны, выбор vector не совсем произволен — подходят только сортированные контейнеры vector, поскольку лишь они правильно работают с алгоритмами binary_search, lower_bound, equal_range и т. д. (совет 34). Но почему бинарный поиск через вектор (может быть, отсортированный) обеспечивает лучшее быстродействие, чем бинарный поиск через двоичное дерево? Прежде всего из-за банального принципа «размер имеет значение». Существуют и другие причины, не столь банальные, но не менее истинные, и одна из них — локализованность ссылок.

Начнем с размера. Допустим, нам нужен контейнер для хранения объектов Widget. Скорость поиска является важным фактором, поэтому рассматриваются два основных кандидата: ассоциативный контейнер объектов Widget и сортированный vector. В первом случае почти наверняка будет использоваться сбалансированное бинарное дерево, каждый узел которого содержит не только Widget, но и указатели на левого и правого потомков и (обычно) указатель на родительский узел. Следовательно, при хранении одного объекта Widget в ассоциативном контейнере должны храниться минимум три указателя.

С другой стороны, при сохранении Widget в контейнере vector непроизводительные затраты отсутствуют. Конечно, контейнер vector сам по себе требует определенных затрат памяти, а в конце вектора может находиться зарезервированная память (см. совет 14), но затраты первой категории как правило невелики (обычно это три машинных слова — три указателя или два указателя с одним числом int), а пустое место при необходимости отсекается при помощи «фокуса с перестановкой» (см. совет 17). Но даже если зарезервированная память и не будет освобождена, для нашего анализа ее наличие несущественно, поскольку в процессе поиска ссылки на эту память не используются.

Большие структуры данных разбиваются на несколько страниц памяти, однако для хранения vector требуется меньше страниц, чем для ассоциативного контейнера. Это объясняется тем, что в vector объект Widget хранится без дополнительных затрат памяти, тогда как в ассоциативном контейнере к каждому объекту Widget прилагаются три указателя. Предположим, вы работаете в системе, где объект Widget занимает 12 байт, указатели — 4 байт, а страница памяти содержит 4096 байт. Если не обращать внимания на служебную память контейнера, vector позволяет разместить на одной странице 341 объект Widget, но в ассоциативном контейнере это количество уменьшается до 170. Следовательно, по эффективности расходования памяти vector вдвое превосходит ассоциативный контейнер. В средах с виртуальной памятью это увеличивает количество подгрузок страниц, что значительно замедляет работу с большими объемами данных.

В действительности я несколько оптимистично подошел к ассоциативным контейнерам — приведенное описание предполагает, что узлы бинарных деревьев сгруппированы в относительно малом наборе страниц памяти. В большинстве реализаций STL подобная группировка достигается при помощи нестандартных диспетчеров памяти, работающих поверх распределителей памяти контейнеров (см. советы 10 и И), но если реализация не следит за локализованностью ссылок, узлы могут оказаться разбросанными по всему адресному пространству. Это приведет к росту числа подгрузок страниц. Даже при использовании группирующих диспетчеров памяти в ассоциативных контейнерах обычно чаще возникают проблемы с подгрузкой страниц, поскольку узловым контейнерам, в отличие от блоковых (таких как vector), труднее обеспечить близкое расположение соседних элементов контейнера в физической памяти. Однако именно эта организация памяти сводит к минимуму подгрузку страниц при выполнении бинарного поиска.

Мораль: данные, хранящиеся в сортированном векторе, обычно занимают меньше памяти, чем те же данные в стандартном ассоциативном контейнере; бинарный поиск в сортированном векторе обычно происходит быстрее, чем поиск в стандартном ассоциативном контейнере (с учетом подгрузки страниц).

Конечно, сортированный vector обладает серьезным недостатком — он должен постоянно сохранять порядок сортировки! При вставке нового элемента все последующие элементы сдвигаются на одну позицию. Операция сдвига обходится довольно дорого и становится еще дороже при перераспределении памяти (см. совет 14), поскольку после этого обычно приходится копировать все элементы вектора. С другой стороны, при удалении элемента из вектора все последующие элементы сдвигаются на одну позицию к началу. Операции вставки-удаления дорого обходятся для контейнеров vector, но относительно дешевы для ассоциативных контейнеров. По этой причине сортированные контейнеры vector используются вместо ассоциативных контейнеров лишь в том случае, если вы знаете, что при использовании структуры данных операции поиска почти не смешиваются со вставкой и удалением.

В этом совете было много текста, но катастрофически не хватало примеров. Давайте рассмотрим базовый код использования сортированного vector вместо set:

vector vw;// Альтернатива для set

// Подготовительная фаза: много вставок,

// мало операций поиска

sort(vw.begin().vw.end()); // Конец подготовительной фазы (при эмуляции

// multiset можно воспользоваться

// алгоритмом stable_sort - см. совет 31).

Widget w;// Объект с искомым значением

// Начало фазы поиска

if (binary_search(vw.begin(),vw.end(),w))... // Поиск с применением

// binary_search

vector::iterator i = lower_bound(vw.begin(),vw.end(),w); // Поиск с применением

if (i!=vw.end() && !(*i

// !(*i

pair::iterator.

vector::iterator> range = equal_range(vw.begin().vw.end(),w): // Поиск с применением if (range, first !- range, second)...// equal_range