Public Group

# nD Vectors/Arrays - Tile Maps

This topic is 4013 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I was reading this thread and it said that nD arrays/vectors are slow. Incidentally, I have to create a container to hold tiles as well (the guy in the thread did too). (My game uses 2D graphics) I need to hold 12 tile maps... don't ask why. :) So far I've been using a 3D array:
std::vector<std::vector<std::vector<std::string>>>


But I was wondering if it WOULD be faster to use a 2D array? I can't use a 1D array because each tile map is a separate entity.. I just can't in other words. If so, how would I access the elements? I've got this and was wondering if it was right:
tile_maps[tile_map][row * col + col].push_back(name);


Cheers. :)

##### Share on other sites
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.)

##### Share on other sites
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?

##### Share on other sites
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.

##### Share on other sites
"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 :)

##### Share on other sites
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.

1. 1
2. 2
Rutin
20
3. 3
4. 4
frob
13
5. 5

• 9
• 13
• 10
• 9
• 17
• ### Forum Statistics

• Total Topics
632601
• Total Posts
3007356

×