Почему я не должен использовать вектор <vector <vector<int> >>?

Question

Я только что прочитал вопрос об инициализации многомерных векторов (question), а Виктор Сер и Sbi рекомендовали вместо этого использовать один вектор и получить элемент с my_vector[x+y*100+z*100*100]. Почему это? Это по соображениям производительности? Если да, то как это повышает производительность? Спасибо заранее, ell.

Редактировать: Применяются ли эти причины, когда ширина/высота/глубина не совпадают и могут измениться?

Answer 1

Просто несколько причин:

Это тратит впустую пространства, это очень медленный процесс (непредсказуемо доступа к памяти, кэш отходов и т.д.), это громоздко

Главный недостаток производительности, вероятно, будет кэширование. При использовании плоских массивов вы гарантированно сохраняете память - кеш счастлив. С вектором векторов - кто знает!

Answer 2

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

vector<vector<vector<int> > > содержит большое количество кусков памяти: кусок для первого вектора, кусок для каждого элемента в vector<> и кусок для каждого элемента в vector<vector<>>. Это непросто кэшировать и может привести к едва ли прогнозируемому использованию памяти.

Answer 3

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

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

Если по каким-либо причинам вы не можете использовать Boost, я бы определенно typedef это:

typedef vector<vector<vector<int> > > My3DIntVector; 

My3DIntVector v; 

Answer 4

... Виктор Sehr и Sbi Рекомендуемые используя вместо одного вектора и получить элемент с my_vector [х + у * 100 + Z * 100 * 100]. Почему это?

Учитывая размеры, это логическая рекомендация , если размеры фиксированы.

По соображениям безопасности? Если да, то как это повышает производительность?

Рассмотрим:

• количество отчислений, необходимых для создания всех массивов
• время, чтобы скопировать хотя бы одно измерение
• сложность это добавляет к распределителю системы
• время, принимает
• сложность общих операций, таких как заполнение

Редактировать: Применяются ли эти причины, когда ширина/высота/глубина не совпадают и могут измениться?

Изменение размера массива (массивного!) Может быть очень медленным. Вы должны понимать, как ваша программа будет работать, если вы хотите, чтобы она была самой быстрой. Кроме того, сложность копирования и уничтожения элементов также рассматривается (при использовании чего-то более сложного, чем int). Если вы делаете много изменения размера или вставки/удаления, тогда сплющенный вектор может быть очень медленным.

Однако, если его размеры фиксированы, вы можете сделать много лучше, чем std::vector. std::array - одна из альтернатив. (Если вы идете по маршруту std::array, будьте осторожны с тем, что вы выделили в стеке)