Вектор векторов, резерв

Question

Предположим, я хочу, чтобы представить двумерную матрицу int как вектор векторов:

std::vector<std::vector<int> > myVec; 

Внутренний размер постоянен, скажем, 5, а внешний размер меньше или равным N. Чтобы свести к минимуму перераспределение, я хотел бы зарезервировать место:

myVec.reserve(N); 

Какой размер предполагается для внутреннего вектора? Является ли эта чисто реализация зависимой? Как это влияет на пространственную локальность данных? Поскольку внутренний размер является константой, есть ли способ сказать компилятору использовать этот постоянный размер? Как эти ответы изменяются, если изменяется размер внутреннего вектора?

Answer 1

Поскольку ваш внутренний размер постоянен, я думаю, что вы хотите

std::vector< std::array<int, 5> > vecs; 
vecs.reserve(N); 

Это даст вам непрерывное хранение выделяется заранее, что является оптимальным для исполнения.

Answer 2

Размер внутренних векторов совершенно не имеет значения для изменения внешнего вектора. Для вашего пакета векторов нет никаких локальных гарантий, гарантия локальности (т. Е. Непрерывный блок в памяти) существует только для одного вектора.

Помните, что сам векторный объект имеет постоянный sizeof -размер, его фактические данные обычно динамически распределяются. Внешний вектор, в первом приближении, является смежным блоком N 'указателей' на внутренние векторы. Ваш вызов reserve не резервирует память для возможных элементов внутренних векторов, но только для самих внутренних векторных объектов (т. Е. Их учетных данных и их указателей для их динамически распределенного блока данных).

Answer 3

Внутренние векторы инициализируются конструктором по умолчанию. Так что если вы пишете:

vector<vector<int> > vecs; 
vecs.reserve(10); 

Это эквивалентно вызову constuctor из vector<int> или vector<int>() для каждого элемента. Это означает, что у вас будут векторы нулевого размера. Но помните, вы не можете использовать их, если вы не измените размер (не резервируете) свои векторы.

Помните, что иногда бывает более эффективным изменять размер с первоначальным размером, который вам понадобится. Так что это полезно делать что-то вроде

vector<vector<int> > vecs(3,vector<int>(5)); 

Это создаст вектор с размером 3, и каждый элемент будет содержать вектор размера 5.

Помните также, что это может быть более эффективно использовать Deque а не вектор, если вы собираетесь изменять размеры ваших векторов часто. Они просты в использовании (как векторы), и вам не нужно резервировать, поскольку элементы не смежны в памяти.