c++ - 嵌套STL结构

Question

我想知道与编译和运行时相关的嵌套 STL 结构的性能。所以如果想实现一些嵌套结构，例如那样

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

访问每个容器对整个执行时间有何影响？

感谢您的帮助。提供一些考虑到这个问题的特定链接也非常感谢。

我最好的。

Answer 1

How could the access to each container effects on the whole execution time?

没什么好说的，更不用说引用了——除了STL。 std::vector 提供对元素(random access)、std::map 的O(1) 访问性能提供 O(log(n))访问元素的性能。

注意事项:

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 层容器的方法。