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

Ответ 1

Массивы не имеют какой-либо косвенности, а просто хранят свои данные "напрямую". Таким образом, 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 будет более понятным, полностью упакованным и, возможно, более безопасным для использования.

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

Ответ 2

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

Это означает, что вектор векторов похож на неровный массив.

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

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 может пытаться изменить bx, но это означает, что поведение не определено.

Ограничения такого же типа не позволяют вам перейти от первого массива в вашем std::vector ко второму (т. ptr+4).

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

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