Должен ли я всегда использовать 1D-вектор с моим собственным индексированием или многомерный вектор нормально?

Question

Я храню и генерирую некоторые данные, которые, естественно, представлены с размером> 1. Однако я видел много ответов, рекомендующих программистам использовать 1D-вектор со своим собственным индексом для представления нескольких измерений. Мой вопрос: что можно получить, используя только 1-мерность?

В моем текущем проекте производительность является приоритетом (сначала я знаю код, а затем профиль, но этот проект импортируется на C++ с другого языка для скорости). Я видел, как только один векторный объект может уменьшить накладные расходы, но разве это намного больше, чем часто вычисление индексов? Я видел один ответ отметил, что с помощью вложенных векторов:

vector < vector<int> > 

Вызывает много звонков new. Я видел, как это волнует, это правда?

Answer 1

Прежде всего, std::vector<std::vector<int>> может иметь внутренние векторы разного размера. Тем не менее, я предполагаю, что вы говорите конкретно об использовании этого типа для имитации 2D-массивов. Предполагая, что вы создаете размеры векторов при их создании, вам, вероятно, не нужно беспокоиться о количестве динамического распределения, поскольку все это происходит за один раз.

Вектор внутренне выделяет массив своих элементов. Таким образом, внешний вектор выделяет массив векторов, и каждый из этих внутренних векторов выделяет массив из int. Вы можете думать об этом так:

┌─────┐ 
│ vec │ 
└──╂──┘ 
    ┃ 
    ▼ 
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ 
│ vec │ vec │ vec │ vec │ vec │ vec │ vec │ vec │ vec │ 
└──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┘ 
    ┃  ┗━━━━━━━━━━┓ 
    ▼    ▼ 
┌─────┬─────┬┄ ┌─────┬─────┬┄ 
│ int │ int │ │ int │ int │ 
└─────┴─────┴┄ └─────┴─────┴┄ 

Как вы можете видеть, массивы int с полностью отделены друг от друга. Они могут находиться в совершенно разных местах памяти. Это называется фрагментацией. Они почти наверняка не будут в одном непрерывном блоке памяти. Из-за этого доступ к элементам из разных «строк» ​​вашего 2D-вектора, скорее всего, приведет к промахам в кеше.

Однако, если выделить один вектор int с и сделать свой собственный 2-мерную индексацию, то есть макет памяти больше как это:

┌─────┐ 
│ vec │ 
└──╂──┘ 
    ┃ 
    ▼ 
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬┄ 
│ int │ int │ int │ int │ int │ int │ int │ int │ int │ 
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴┄ 

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