std :: vector <std :: vector <T>> vs std :: vector <T*>

Question

Учитывая, что накладные расходы памяти имеют решающее значение для моего приложения, я думаю, что из двух вариантов выше, последний был бы более легким. Я прав? Я основываю это на том факте, что у вектора есть память из 4 указателей для отслеживания begin(), end(), size() и распределителя. Таким образом, общий размер для всей модели будет в порядке

(4*sizeof(T*) + sizeof(T)*Ni)*No + 3*sizeof(std::vector<T>*) 

Здесь я предполагаю, Ni, No быть число элементов во внутренних и внешних векторов, resply. Используя последнее выражение, я надеюсь сохранить 4*sizeof(T*)*No, поскольку в моем приложении No является огромным, а Ni <<<< No. Чтобы исправить идеи, No находится в заказе 100 миллионов и более, Ni обычно находится в заказе 3 до 50.

Заранее благодарим за ваши интересы и любые идеи.

ПРИМЕЧАНИЕ: Я понимаю и более чем счастлив заплатить цену за сделку с указателем вкл. распределяя, перемещая и освобождая его, и я могу сделать это без каких-либо существенных издержек производительности.

Answer 1

Это на самом деле 4, вы пропустили распределитель. См. What is the overhead cost of an empty vector?

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

Если вы ответили «да» на все вопросы выше, чем, возможно, T* является приемлемым решением. Если вы не думаете, как бы вы справились с этой проблемой без поддержки вектора. Возможно, было бы проще просто взять удар по памяти.

Answer 2

Как вы видите here, точные накладные расходы std::vector зависят от реализации.

Также обратите внимание, что если No очень велико, очень вероятно, что ваши данные будут храниться в кусках в некоторых реализациях, и в этом случае у вас также есть накладные расходы, которые имеют порядок количества кусков.

Но в целом я согласен с тем, что реализация указателя дешевле по размеру.

Answer 3

Я думаю, что [vector<T*> будет лучше. Я прав?

Это будет меньше, но это не обязательно будет «лучше». Изменение сменит вас необходимостью выделять и освобождать внутренние массивы. У вас больше не будет возможности узнать размер внутреннего массива.

Также обратите внимание, что некоторые избыточные данные по размеру останутся: до тех пор, пока ваши внутренние массивы распределены индивидуально, в дополнение к размеру запрошенного фрагмента будет добавлено дополнительное хранилище, зарезервированное распределителем, чтобы знать, размер куска.

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

Answer 4

Если вы обеспокоены накладных расходов вектора, вы также должны быть обеспокоены накладных malloc()/new: типичный накладные Распределитель памяти по крайней мере, еще два указателя на область памяти, которая приносит над головой небольшой vector<> до пяти указателей (sizeof(vector<int>) == 3*sizeof(void*) на linux).

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

int** pointerArray = new int*[innerArrayCount + 1]; 
int* store = new int[totalSizeOfInnerArrays]; 
for(int* nextArray = store, i = 0; i <= innerArrayCount; i++) { 
    pointerArray[i] = nextArray; 
    nextArray += innerArraySize[i]; 
} 

Размер массива может затем выводится из разности следующего указателя и его собственные:

for(int i = 0; i < innerArrayCount; i++) { 
    int* curArray = pointerArray[i]; 
    size_t curSize = pointerArray[i + 1] - pointerArray[i]; 
    //Do whatever you like with curArray. 
} 

Или, вы можете непосредственно использовать этот конечный указатель для итерация внутренних массивов:

for(int i = 0; i < innerArrayCount; i++) { 
    for(int* iterator = pointerArray[i]; iterator < pointerArray[i + 1]; iterator++) { 
     //Do whatever you like with *iterator. 
    } 
}