(конечно, не считая заполнения для выравнивания; заметим, что в случае вектора "последовательное размещение" имеет тот же смысл, что и у С-массива, как показано на рис. 21.2).

• deque<T> можно рассматривать как vector<T>, чья внутренняя память разделена на части. deque<T> хранит блоки, или "страницы" объектов; реальный размер страниц стандартом не определяется и зависит в первую очередь от размера объекта т и от выбора, сделанного разработчиком вашей стандартной библиотеки. Такое разбиение на страницы требует хранения одного дополнительного указателя на страницу, что приводит к дополнительным расходам, составляющим доли бита на один объект. Напри.мер, в системе с 8-битовыми байтами и 4-битовыми целыми числами и указателями deque<int> с 4-Кбайтовой страницей приводит к расходам памяти, равным 1/32=0.03125 бита на один int. Других накладных расходов не имеется, поскольку deque<T> не хранит никаких дополнительных указателей или другой информации для отдельных объектов т. В стандарте нет требования, чтобы страницы deque<T> представляли собой С-массивы, однако это - общепринятый способ реализации.

• 1ist<T> представляет собой двухсвязный список узлов, хранящих элементы типа т. Это означает, что для каждого элемента т в 1ist<T> хранятся также два указателя на предьщущий и последующий узлы в списке. Каждый раз при вставке нового элемента т мы также создаем два указателя, так что list<T> требует как минимум двух указателей накладных расходов памяти на один элемент.

• set<T> (а также аналогичные в этом отношении mu1tiset<T>, тар<кеу,т> и multimap<Key,T>) тоже хранят узлы, в которых содержатся объекты типа т (или pai r<const Key ,т>). Обычная реализация set представляет собой дерево с тремя дополнительными указателями на один узел дерева. Зачасгую, услышав об этом, многие спрашивают: "Почему три указателя? Разве недостаточно двух -- на левый и правый дочерние узлы?" Дело в том, что требуется еще один указатель на родительский узел, иначе задача определения "следующего" узла по отношению к некоторому произвольно взятому не может быть решена достаточно эффективно. (Возможны и другие способы реализации этих контейнеров; например, можно использовать т.н. alternating skip list - но и в этом случае требуется как минимум три указателя на каждый элемент (см. [МагпеОО]).)

В табл. 21.1 приведены дополнительные расходы памяти на хранение одного элемента в различных стандартных контейнерах. Заметим, что иногда можно снизить расходы на хранение объектов, перенеся их на итераторы - т.е. часть работы может быть перенесена в итераторы, что даст нам "толстые" итераторы в обмен на "худые" контейнеры. Впрочем, я не знаком ни с одной коммерческой реализацией стандартной библиотеки, которая бы придерживалась этой методики.

Таблица 21.1. Дополнительные расходы памяти на хранение одного объекта

у разных контейнеров

Память и стандартные контейнеры: практика

Теперь мы перейдем к самой интересной части. Не будем спешить делать выводы из табл. 21.1. Например, исходя из приведенных данных, вы можете сделать вывод б том, что list требует меньших расходов памяти, чем set - ведь первому требуется только два дополнительных указателя, а последнему - три. Интересно, что это может оказаться неверным, если принять во внимание стратегию распределения памяти.

Рассмотрим вопрос более детально, для чего обратимся к табл. 21.2. в которой приведены типичные структуры узлов, используемые реализациями list, set/ multiset и map/multimap.

Таблица 21.2. Блоки динамической памяти, используемые для хранения объектов в разных контейнерах

Теперь рассмотрим, что происходит в реальной ситуации при приведенных далее предположениях, которые справедливы для большинства расп ро с тра н с н и ы х в настоящее время платформ.

• Указатели и целые числа имеют размер 4 байта (типично для 32-битовых платформ).

• si zeof (stri ng) равно 16. Заметим, что это просто размер непосредственно объекта stri ng, здесь не учитываются буферы данных, которые могут быть выделены строке; количество и размер внутренних буферов string варьируется от реализации к реализации, но это не влияет на приведенные далее сравнительные результаты. (Рассматриваемое значение si zeof (stri ng) представляет собой реальную величину, взятую из одной распространенной реализации стандартной библиотеки.)

• Стратегия распределения памяти по умолчанию использует выделение блоков фиксированного размера; размеры блоков кратны 16 байтам (типичное распределение памяти в Microsoft Visual С-ь+).

Таблица 21.3. Реальные расходы памяти на хранение объекта, рассматриваемые в предположении, что sizeof (string) == 16, указатели и int имеют размер 4 байта, и выделение памяти происходит 16-байтовыми блоками

В табл. 21.3 приведены результаты простого анализа с использованием рассмотренных выше предположений. Вы можете повторить эксперимент на своей платформе со своим компилятором - просто подставив собственные значения. Чтобы написать программу, которая определяет реальные накладные расходы при выделении блока определенного размера на вашей платформе, обратитесь к приложению 3 в книге Джона Бентли (Jon Bcntlcy) [BentleyOO].

Благодаря табл. 21.3 мы немедленно обнаруживаем один интересный результат: во многих случаях - примерно для 75% всех возможных размеров типа т - накладные расходы при использовании 1 i st и set/mul ti set в рассматриваемой среде оказываются одинаковы. Более того, вот результат, который еше интереснее, - list<char> и set<int> имеют в данной среде одни и тс же реальные накладные расходы, несмотря на то, что последний контейнер хранит данные большего размера и требует большего количества дополнительной информации для каждого узла.

Если используемое количество памяти является важным фактором при выборе вами структуры данных в конкретной ситуации, потратьте несколько минут на проведение подобного анализа для вашей системы и посмотрите на реальные различия в потреблении памяти разными контейнерами - иногда эти различия гораздо меньше, чем вы думаете!

Резюме

Для каждого вида контейнера определяются свои компромиссы между расходами памяти и производительностью. При использовании vector и set можно быстро решить те задачи, которые невозможно столь же эффективно решить при использовании 1 ist - например, поиск за время 0(log N); при использовании vector можно сделать веши, невозможные при применении list или set - например, произвольный доступ. Вставка элемента в средину легко выполняется в 1 i st, менее эффективно-в set, и очень медленно - в vector. Словом, примеров таких по-разному выполняющихся задач очень много. Большая гибкость зачастую требует больших накладных расходов памяти, но если учесть выравнивание данных и возможные стратегии распределения памяти, то различие может оказаться куда меньшим, чем вы думаете! Вопросы выравнивания данных и оптимизации использования памяти рассматривались также в книге [SutterOO].

Если содержимое вектора отсортировано. Задача 21. Контейнеры в памяти. Часть 2: какие они на самом деле?