векторный резерв c ++

Question

У меня очень большой многомерный вектор, размер которого постоянно меняется.Есть ли смысл использовать функцию vector.reserve (), когда я знаю только хорошее приближение размеров.

Так что в принципе у меня есть вектор

A[256*256][x][y]

где x переходит от 0 до 50 для каждой итерации в программе, а затем снова возвращается к 0.Значения y могут отличаться каждый раз, что означает, что для каждого из [256*256][y] элементов вектор y может иметь различный размер, но все же меньше 256;

Итак, чтобы прояснить мою проблему, это то, что у меня есть:

vector<vector<vector<int>>> A;
for(int i =0;i<256*256;i++){
  A.push_back(vector<vector<int>>());
  A[i].push_back(vector<int>());
  A[i][0].push_back(SOME_VALUE);
}

Добавить элементы в вектор ...

A.clear();

И после этого я снова делаю то же самое сверху.

Когда и как следуетЯ резервирую место для векторов.Если бы я понял это правильно, я бы сэкономил много времени, если бы использовал резерв, поскольку я постоянно меняю размеры?

Какими были бы отрицательные / положительные стороны резервирования максимального размера, который может иметь мой вектор?в некоторых случаях это будет [256*256][50][256].

Кстати.Мне известны различные Matrix Templates и Boost, но я решил использовать векторы на этом ...

EDIT: Мне также было интересно, как использовать функцию резерва в многомерных массивах,Если я зарезервирую вектор только в двух измерениях, скопирует ли он все это, если я превыслю его емкость в третьем измерении?

Answer 1

Чтобы помочь с обсуждением, вы можете рассмотреть следующие typedefs:

typedef std::vector<int> int_t;   // internal vector
typedef std::vector<int_t> mid_t; // intermediate
typedef std::vector<mid_t> ext_t; // external

Стоимость роста (увеличение емкости вектора) int_t влияет только на содержимое этого конкретного вектора и не влияет на другие элементы. Стоимость выращивания mid_t требует копирования всех сохраненных элементов в этом векторе, то есть потребуется весь вектор int_t, что обходится гораздо дороже. Стоимость выращивания ext_t огромна: потребуется скопировать все элементов, уже сохраненных в контейнере.

Теперь, чтобы повысить производительность, было бы гораздо важнее получить правильный ext_t размер (кажется, фиксированный 256 * 256 в вашем вопросе). Затем получите правильный средний размер mid_t, чтобы дорогостоящие перераспределения были редкими.

Объем памяти, о котором вы говорите, огромен, поэтому вы можете подумать о менее стандартных способах решения вашей проблемы. Первое, что приходит на ум, это добавление и дополнительный уровень косвенности. Если вместо удержания фактических векторов вы удерживаете интеллектуальные указатели на векторах, вы можете уменьшить стоимость увеличения векторов mid_t и ext_t (если размер ext_t фиксирован, просто используйте вектор mid_t). Теперь это будет означать, что код, который использует вашу структуру данных, будет более сложным (или лучше добавить оболочку, которая заботится о косвенных ссылках). Каждый int_t вектор будет выделен один раз в памяти и никогда не будет перемещаться ни в mid_t, ни ext_t перераспределениях. Стоимость перераспределения mid_t пропорциональна количеству выделенных int_t векторов, а не фактическому количеству вставленных целых чисел.

using std::tr1::shared_ptr; // or boost::shared_ptr
typedef std::vector<int> int_t;
typedef std::vector< shared_ptr<int_t> > mid_t;
typedef std::vector< shared_ptr<mid_t> > ext_t;

Еще одна вещь, которую вы должны принять во внимание, это то, что std::vector::clear() не освобождает выделенное внутреннее пространство в векторе, только уничтожает содержащиеся в нем объекты и устанавливает размер равным 0. То есть вызов clear() никогда не освободит память , Шаблон для фактического освобождения выделенной памяти в векторе:

typedef std::vector<...> myvector_type;
myvector_type myvector;
...
myvector.swap( myvector_type() ); // swap with a default constructed vector

Answer 2

Когда вы помещаете вектор в другой вектор, задайте размер в конструкторе помещенных векторов:

 A.push_back(vector<vector<int>>( somesize ));

Answer 3

Если вы знаете размер вектора во время построения, передайте размер в c'or и назначьте, используя operator[] вместо push_back.Если вы не совсем уверены насчет окончательного размера, сделайте предположение (возможно, добавьте немного больше) и используйте reserve, чтобы вектор резервировал достаточно памяти заранее.

Что будетотрицательные / положительные стороны резервирования максимального размера, который может иметь мой вектор, который в некоторых случаях будет [256 * 256] [50] [256].

Отрицательная сторона: потенциальная потеря памяти.Положительная сторона: меньше процессорного времени, меньше фрагментации кучи.Это компромисс между памятью и процессором, оптимальный выбор зависит от вашего приложения.Если вы не ограничены памятью (на большинстве компьютеров-потребителей ОЗУ более чем достаточно), подумайте о резервировании авансом.

Чтобы определить объем резервируемой памяти, посмотрите на среднее потребление памяти, а не на пик (резервирование 256 * 256 * 50 * 256 не является хорошей идеей, если такие размеры не требуются регулярно)

Answer 4

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

См. пример работы со динамическими многомерными массивами в c для примера

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

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