Какова схема памяти вектора массивов?

Question

Может кто-нибудь объяснить расположение памяти

std::vector<std::array<int, 5>> vec(2)

обеспечивает ли он непрерывный блок памяти двумерного массива с 2 рядами по 5 элементов?

Насколько я понимаю, вектор векторов

std::vector<std::vector<int>> vec(2, std::vector<int>(5))

обеспечивает расположение в памяти двух непрерывных массивов длины 5 элементов s в разных местах в памяти.

Будет ли то же самое для вектора массивов?

Answer 1

static_assert(sizeof(std::array<int,5>)==5*sizeof(int));

вышеупомянутое смягчает против наличия любого дополнения на конце std::array. Ни один крупный компилятор не приведет к сбою вышеизложенного до этой даты, и я готов поспорить, что в будущем это не так.

Если и только если вышеперечисленное не сработало, то std::vector<std::array<int,5>> v(2) будет иметь «пробел» между std::array с.

Это не так много, как хотелось бы; указатель, сгенерированный следующим образом:

int* ptr = &v[0][0];

имеет область действия только до ptr+5, а разыменование ptr+5 - неопределенное поведение.

Это связано с правилами наложения имен; вам не разрешается "проходить" через конец одного объекта в другой, даже если вы знаете, что он там есть, если только вы не совершите первое круговое путешествие к определенным типам (например, char*), где разрешена менее ограниченная арифметика указателей.

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

Итак:

struct bob {
  int x,y,z;
};

bob b {1,2,3};
int* py = &b.y;

независимо от того, что вы делаете с py как int*, вы не можете юридически изменить x или z с ним.

*py = 77;
py[-1]=3;
std::cout << b.x;

компилятор может оптимизировать строку std::cout, чтобы просто напечатать 1, поскольку py[-1]=3 может попытаться изменить b.x, но это означает, что поведение не определено.

Подобные ограничения не позволяют вам перейти от первого массива в вашем std::vector ко второму (т. Е. За пределы ptr+4).

Создание ptr+5 допустимо, но только в качестве указателя на один конец. Сравнение ptr+5 == &v[1][0] также не указывается в результате, даже если их двоичные значения будут абсолютно идентичны в каждом компиляторе в каждой основной аппаратной системе.

Если вы хотите пройти дальше по кроличьей норе, то даже в самом C ++ невозможно реализовать std::vector<int> из-за этих ограничений на наложение указателей. Последний раз я проверял (что было до c ++ 17 , но я не видел резолюции в C ++ 17), стандартный комитет работал над решением этой проблемы, но я не знаю состояния любое такое усилие. (Это меньшая проблема, чем вы думаете, потому что ничто не требует, чтобы std::vector<int> был реализован в стандартном C ++; он должен просто иметь стандартное поведение. Он может использовать специфичные для компилятора расширения внутри.)

Answer 2

Большая разница между std::vector и std::array заключается в том, что std::vector содержит указатель на память, которую он оборачивает, а std::array содержит сам фактический массив.

Это означает, что вектор векторов подобен зубчатому массиву .

Для вектора массивов объекты std::array будут размещаться смежно, но отдельно от векторного объекта. Обратите внимание, что сам объект std::array может быть больше, чем массив, который они содержат, и в этом случае данные не будут смежными.

Последний бит также означает, что массив (обычный стиль C или std::array) std::array также может не сохранять данные непрерывно. Объекты std::array в массиве будут смежными, но не данные.

Единственный способ гарантировать непрерывные данные для «многомерного» массива - это вложенные простые массивы в стиле C.

Answer 3

Стандарт C ++ не гарантирует, что std::array не содержит никакой полезной нагрузки в конце массива, поэтому, увы, вы не можете предположить, что первый элемент последующего массива находится сразу после последнего элемента предыдущего массива.

Даже если бы это было так, поведение при попытке получить доступ к любому элементу в массиве с помощью арифметики с указателем на указатель на элемент в другом массиве не определено. Это связано с тем, что арифметика с указателями действительна только для массивов.

Вышеуказанное также относится к std::array<std::array>.

Answer 4

Массивы не имеют косвенных указаний, а просто хранят свои данные «напрямую». То есть, std::array<int, 5> буквально содержит пять int с, плоский. И, как и векторы, они не помещают отступ между своими элементами, поэтому они "внутренне смежны".

Однако сам объект std::array может быть больше, чем набор его элементов ! Разрешается иметь конечные "вещи", такие как отступы. Таким образом, хотя, вероятно, это не обязательно так, что ваши данные будут все смежными в первом случае.

An int
+----+
|    |
+----+

A vector of 2 x int
+----+----+----+-----+        +----+----+
| housekeeping | ptr |        | 1  |  2 |
+----+----+----+-----+        +----+----+
                   |          ^
                   \-----------

An std::array<int, 5>
+----+----+----+----+----+----------->
| 1  |  2 |  3 |  4 |  5 | possible cruft/padding....
+----+----+----+----+----+----------->

A vector of 2 x std::array<int, 5>
+----+----+----+-----+        +----+----+----+----+----+----------------------------+----+----+----+----+----+----------->
| housekeeping | ptr |        | 1  |  2 |  3 |  4 |  5 | possible cruft/padding.... | 1  |  2 |  3 |  4 |  5 | possible cruft/padding....
+----+----+----+-----+        +----+----+----+----+----+----------------------------+----+----+----+----+----+----------->
                   |          ^
                   \-----------

И даже если бы из-за правил наложения имен вы могли бы использовать один int* для навигации по всем 10 номерам, это могло бы быть другим вопросом!

В целом, вектор из десяти int с будет более понятным, полностью упакованным и, возможно, более безопасным для использования.

В случае вектора векторов вектор - это просто указатель плюс некоторая служебная информация, отсюда и косвенное указание (как вы говорите).