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

考慮到內存開銷對於我的應用程序至關重要，我認爲對於上述兩個選項來說，後者會更輕。我對麼？我基於這個事實，矢量有4個指針的內存開銷，以跟蹤begin(),end(),size()和分配器。因此，對於整個模型的總大小將是在std :: vector <std :: vector <T>> vs std :: vector <T*>

(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。

提前感謝您的關注和任何想法。

注意：我明白並且非常樂意支付處理指針的價格。分配，遍歷和釋放它，而且我可以做到這一點，而沒有任何顯着的性能開銷。

來源

2014-01-09 squashed.bugaboo

一個'開始（） '，'end（）'和'size（）'是多餘的。「矢量」並不是那麼糟糕。 – 2014-01-09 15:12:43

如果你正在分配大量的元素，'std :: vector'可能會有問題，因爲它需要連續分配內存。根據你的需要，'std :: deque'可能會有幫助。 –

「在我的申請中，」不「是巨大的，而'Ni' <<<<'否'。」一個明顯的解決方案是切換內部和外部矢量的索引，除非需要傳遞內部矢量。 – dasblinkenlight

它實際上是4，你錯過了分配器。請參閱What is the overhead cost of an empty vector?

取決於您的應用程序。你永遠不會追加到內部向量？它們都具有相同數量的元素嗎？存儲在內部向量中的數據的平均大小是否小？

如果您對上述所有問題回答「是」，也許T*是可接受的解決方案。如果不考慮如果沒有向量的支持，你將如何處理這個問題。只要記住內存就可能更容易。

來源

2014-01-09 15:17:06 Sorin

謝謝您的回覆和更正;那就是更好的儲蓄。是的，我不追加它。我正在構建這個快速查找。我需要它們是連續的，我可能會對它們進行排序，但通常倪與「否」相比非常小，這並不重要。映射的實現（我之前的嘗試）在內存方面太昂貴了。 –

在Linux上，它只是三個指針（'sizeof（vector ）== 24'），我相信分配器存儲在類型中，而不是在運行時。還有相當多的開銷。 – cmaster

如您所見here，std::vector的確切開銷與實施相關。

另請注意，如果No非常大，則在某些實現中，您的數據很可能會以塊的形式存儲，在這種情況下，您的開銷也與塊的數量級有關。

但總的來說，我同意指針實現在空間上更便宜。

來源

2014-01-09 15:20:39 adrin

我認爲[vector<T*>會更好。我對麼？

它會更小，但它不一定是「更好」。這種改變會讓你感到必須分配和釋放內部數組。你將不再有辦法知道內部數組的大小。

另請注意，大小上的一些開銷將保持不變：只要您的內部數組是分別分配的，除了所請求的塊大小外，分配器還會保留一些額外的存儲空間，以便讓分配例程知道大塊的大小。

如果您的內存要求太緊，請考慮爲整個數組分配一個向量，然後將各個塊分組爲一個指針向量。這將消除單個分配內部陣列的每塊開銷。

來源

2014-01-09 15:25:15 dasblinkenlight

如果您擔心向量的開銷，你也應該關心的開銷malloc()/new：典型的內存分配器開銷是每個存儲區域至少有兩個以上的指針，帶來的一個小vector<>開銷最多五個指針（linux上的sizeof(vector<int>) == 3*sizeof(void*)）。

所以，我會做的是問自己，內部數組的大小是否需要改變，一旦他們已經被初始化。如果有可能避免這些陣列的後面重新分配，我將分配一個巨大的存儲器，這是我然後可以分配到不同的內部陣列塊，僅存儲它們的位置：

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. 
    } 
}

來源

2014-01-09 15:52:34 cmaster

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

回答

相關問題