концом объекта имишне, но оно необходимо, например, когда вы работаете с массивом объектов х1, располагающихся в памяти один за другим, чтобы обеспечить выравнивание данных типа long по 4-байтовой границе. Такое выравнивание за концом данных зачастую удивляет людей, впервые сталкивающихся с размещением данных в памяти. Особенно может удивить следующий результат перестановки полей структуры:

Пример 21-2: измененная структура из примера 21-1

struct Х2 {

long 1; Байты 0-3

char cl; Байт 4

char с2; Байт 5

Байты 6-7: 2 заполняющих байта }; sizeof(x2) == 8

Теперь члены -данные действительно располагаются в памяти непрерывно (п == б), но все еще имеется дополнительное пространство за концом объекта. Это делает размер объекта равным m == si zeof (х2) == 8. Это заполнение за концом объекта оказывается наиболее заметным при создании массива объектов х2. Заполняющие шестой и седьмой байты показаны на рис. 21.2 нсзаштрихованными квадратами.

Кстати, именно поэтому при написании стандарта было достаточно трудно сформулировать требование последовательного расположения элементов vector в том же смысле, что и массивы. На рис. 21.2 память рассматривается как непрерывная, несмотря на наличие областей неиспользуемой памяти. Так что же в действительности означает последовательное расположение ? По cyfn, последовательно расположены отдельные блоки памяти размером si zeof (struct), й такое определение вполне работоспособно, поскольку sizeof (struct) включает дополнительную заполняющую память.

Стандарт С++ гарантирует, что вся память, выделенная оператором new или функцией malloc, будет надлежащим образом выровнена для всех воз.можных объектов, которые вы можете захотеть в ней сохранить, а это означает, что оператор new и функция malloc должны удовлетворять самому строгому типу выравнивания на данной платформе.

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

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

Теперь мы перейдем к главному вопросу данной задачи.

2. Сколько памяти используют различные стандартные контейнеры для хранения одинакового количества объектов одного и того же типа т?

Каждый стандартный контейнер использует собственную структуру памяти, что приводит к различным накладным расходам памяти на один хранимый объект.

Внутреннее представление, используемое vector<T> для хранения данных, представляет собой непрерывный С-массив объектов типа т, так что никаких дополнительных расходов памяти на хранение элементов у этого контейнера нет

Компилятор не может самостоятельно выполнить перестановку данных из примера 21-1 к виду из примера 21-2. Стандарт требует, чтобы все данные, располагающиеся в одной и той же группе public, protected или private располагались компилятором в указанном порядке. Если же вы предваряете ваши данные спецификаторами доступа, то компилятор может выполнить перестановку в пределах групп данных, разделенных спецификаторами доступа для улучшения размещения. Это является одной из причин, по которой некоторые программисты предпочитают предварять каждый член-данные спецификатором доступа.

(конечно, не считая заполнения для выравнивания; заметим, что в случае вектора последовательное размещение имеет тот же смысл, что и у С-массива, как показано на рис. 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 С-ь+).