c++ - What are the Disadvantages of Nested Vectors? -

i'm still new c++ , have lot left learn, i've become quite attached using nested (multidimensional) vectors. may typically end this:

std::vector<std::vector<std::string> > table; 

which can access elements of this:

std::string data = table[3][5]; 

however, i've been getting impression it's better (in terms of performance) have single-dimensional vector , use "index arithmetic" access elements correspondingly. assume performance impact significant larger or higher dimensional vectors, have no idea , haven't been able find information far.

while, intuitively, kind of makes sense single vector have better performance a higher dimensional one, don't understand actual reasons why. furthermore, if use single-dimensional vectors, lose intuitive syntax have accessing elements of multidimensional ones. here questions:

why multidimensional vectors inefficient? if use single-dimensional vector instead (to represent data in higher dimensions), best, intuitive way access elements?

it depends on exact conditions. i'll talk case, when nested version true 2d table (i.e., rows have equal length).

a 1d vector faster on every usage patterns. or, @ least, won't slower nested version.

nested version can considered worse, because:

• it needs allocate number-of-rows times, instead of one.
• accessing element takes additional indirection, slower (additional indirection slower multiply needed in 1d case)
• if process data sequentially, slower, if 2d data scattered around memory. because there lot of cache misses, depending how memory allocator returns memory areas of different rows.

so, if go performance, i'd recommend create 2d-wrapper class 1d vector. way, simple api nested version, , you'll best performance too. , even, if cause, decide use nested version instead, can change internal implementation of wrapper class.

the intuitive way access 1d elements y*width+x. but, if know access patterns, can choose different one. example, in painting program, tile based indexing better storing , manipulating image. here, data can indexed this:

int tilemask = (1<<tilesizel)-1; // tilesizel log of tilesize int tilex = x>>tilesizel; int tiley = y>>tilesizel; int tileindex = tiley*numberoftilesinarow + tilex; int index = (tileindex<<(tilesizel*2)) + ((y&tilemask)<<tilesizel) + (x&tilemask); 

this method has better spatial locality in memory (pixels near each other tend have near memory address). index calculation slower simple y*width+x, method have less cache misses, in end, faster.