I skimmed the thread you linked to, but couldn't find any mention of n-d vectors being 'slow'. Where did you see that?

In any case, I'd recommend looking into boost::multi_array, as suggested in the other thread. (Also, I doubt any slight variations in performance you might encounter will amount to much in the context of accessing a tile map.)

Quote:Original post by Mybowlcut

Quote:In C++, it's often not a good idea to use n-D arrays or vectors, because they're (generally) not very space or memory efficient, and they're almost always jagged arrays (not rectangular) instead.

Cheers for the multi-array advice - it looks alright. :)

Q: What makes them better than nD vectors? How do they improve performance?

Real multi-dimensional arrays are rectangular. When you write 'int foo[20][15]', that sets aside a chunk of 300 consecutive int-sized pieces of memory, at least conceptually, and indexing in - 'foo[x][y]' - really means 'foo[x * 15 + y]'.

When you make a vector of vectors, each contained vector can have its own size. That means it has to create and maintain its own memory allocation. That adds space overhead, and costs speed in two ways: first, an extra "indirection" (when you grab an element, the first vector has to follow a pointer to find the contained vector in memory, and then that vector has to follow another pointer to find the element), and second, "cache coherency" (the allocations made by the contained vectors could be spread out all over memory, which sometimes causes problems - but there is no real exact way to measure how long any given memory access will take if it's not in the cache: a modern computer is a very complex system).

Boost::multi_array basically takes a single chunk of memory, and remembers a "width", instead of just the size of the allocated memory. When you index in, it does the necessary math to find an element - except that (a) it gets the width from a data member at runtime, instead of figuring it all out at compile-time (the way the static array does), and (b) it actually does a bunch of fancier stuff, in order to present the *illusion* that each "row" is a separate chunk of memory (and it "just happens" that they're all one after another in sequence). :)

This means you lose the flexibility to make something "jagged", but accordingly you don't pay the overhead that's required to make that work.

Quote:Original post by Jason Petrasko
"Real multi-dimensional arrays are rectangular." For values of rectangular that equate to linear, as you point out in your next statement. I might be nit-picking, but that sentence made me laugh. I'd go with: "Real multi-dimensional arrays are contiguous." or something :)

"Rectangular" here refers to the abstract model: every row is necessarily the same length. This is implemented using a single contiguous block of memory and some arithmetic; it doesn't have to be that way (you could implement it, for example, by wrapping up a vector of vectors in another class that makes sure all the vectors are .resize()d in sync), but it's more efficient.