嵌套STL結構

Question

我想知道與編譯和運行時相關的嵌套STL結構的性能。所以如果想要實現一些嵌套的結構，例如那樣

vector<vector<map<int, vector<> > > > 

怎樣才能訪問每個容器影響整個執行時間？

感謝您的任何幫助。給予一些具體的鏈接考慮這個問題也非常讚賞。

我最好。

Answer 1

訪問每個容器如何影響整個執行時間？

沒有什麼可說的，甚至更少的參考 - 除了STL。 std::vector提供了O(1)對元素的訪問性能（random access），std::map提供了O(log(n))訪問元素的性能。

IOW：

vector<vector<map<int, vector<int> > > > x; 

int i,j,k,l;  
x[i] // goes via std::vector, O(1) 
[j] // goes via std::vector, O(1) 
[k] // goes via std::map, O(log(n)) 
[l]; // goes via std::vector, O(1) 

大多數的訪問將被內聯/由編譯器優化掉了。

爲了幫助編譯器中的位可以在一個變量一些經常訪問的緩存容器，例如：

typedef map<int, vector<int> > map_type; 
typedef vector<vector<map_type> > bigvec_type; 
bigvec_type x; 

int i,j,k,l; 

map_type &m = x[i][j]; 
for (/* some loop over k and l */) { 
    m[k][l]; 
} 

在特定情況下有沒有太大的性能問題。

當代碼使用幾個這樣的大型結構（例如將數據從一個bigvec_type容器移動到另一個容器）時，我的小小挑剔是。儘管漸近式性能不會改變，但編譯器需要生成的代碼量相當大，因爲它無法將所有必需的索引和指針放入寄存器中。爲了避免這種情況，人們通常試圖將結構邏輯地分成幾個層（類似於我的第二個代碼示例），並提供僅與1或2級容器一起工作的方法。

Answer 2

表現正是你所期望的。僅僅因爲它們是「嵌套的STL容器」，並不會強加任何隱藏的性能變化。