nested STL structure

I am wondering about the performance of nested STL structure related to compile and run time. So if want to implement something a nested structure e.g. that way

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

How could the access to e开发者_高级运维ach container effect on the whole execution time?

Thanks for any help. Giving some specific links considered this issue are very appreciated as well.

My best.

---

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

It's not much to say, even less to reference - except for the STL. std::vector provides O(1) access performance to the elements (the random access), std::map provides O(log(n)) access performance to the elements.

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)

Most of the accesses would be inlined/optimized out by the compiler.

To help compiler a bit one can cache in a variable some often accessed containers, for example:

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];
}

In the particular case there are not much performance concerns.

My minor nitpick would be is when code uses several such large structures (e.g. moving data from one bigvec_type container to another). Though assymptotically performance wouldn't change, the amount of code compiler need to generate would be quite large since it wouldn't be able put all required indexes and pointers into registers. To avoid that, one generally tries to split logically the structure into several layers (akin to my second code example) and provide methods which work with 1 or 2 level of containers only.

---

The performance is exactly what you'd expect. Just because they are "nested STL containers" does not impose any hidden performance changes.