Another extension of that approach is to use std::vector and just .reserve() x*y entries for your two-dimensional structure. Access them with [x + y*row_width].
This of course only works if all of your "rows" are the same length.
c++ Performance boost needed
Another extension of that approach is to use std::vector and just .reserve() x*y entries for your two-dimensional structure. Access them with [x + y*row_width].
This of course only works if all of your "rows" are the same length.
I think a better way to achieve this memory layout would be a unique_ptr<array<array<int,X>,Y>>. That allows you to heap allocate the memory no earlier than you need it, uses normal array indexing syntax, and disallows resizing of the array, In theory it could also allow compile time bounds checking (as of C++14) for constant indexes.
std::array is also much easier to use than C style arrays, so I'd recommend always preferring it.
I think a better way to achieve this memory layout would be a unique_ptr<array<array<int, X>,Y>>.
Unless I'm missing something, I don't see a need for unique pointer. It sounds like OP builds the table out once and then only uses it for lookup. If that's the case, the lifetime of the table can almost certainly be determined by its location on the stack. Also, std::array<int, X*Y> is still valid -- You'll have to calculate the index like ApockPiQ showed, but you'll still get whatever static or runtime checks std::array offers, you won't get them on each dimension individually but you'll get them on the whole of the std::array, and that ought to at least help prevent most bugs (most indexing bugs are going to go off the reservation entirely, especially with a non-square array; its pretty rare to see an indexing bug that manages to stay only inside its dimensionality and never step outside its total bounds.)
Do be aware of axis swapping, though -- array<array<int, X>, Y> is the same memory layout as int[Y][X], which are both what you want for row-major traversal patterns, but notice how the relative placement of X and Y are swapped depending on whether nested containers or native arrays are used.
I think a better way to achieve this memory layout would be a unique_ptr<array<array<int, X>,Y>>.
Unless I'm missing something, I don't see a need for unique pointer. It sounds like OP builds the table out once and then only uses it for lookup. If that's the case, the lifetime of the table can almost certainly be determined by its location on the stack. Also, std::array<int, X*Y> is still valid -- You'll have to calculate the index like ApockPiQ showed, but you'll still get whatever static or runtime checks std::array offers, you won't get them on each dimension individually but you'll get them on the whole of the std::array, and that ought to at least help prevent most bugs (most indexing bugs are going to go off the reservation entirely, especially with a non-square array; its pretty rare to see an indexing bug that manages to stay only inside its dimensionality and never step outside its total bounds.)
The point of the unique pointer in my example is to move the large array from the stack to the heap. You generally don't want large arrays eating up your stack space. I also wanted to show an identical layout as Apoch suggested, but with more safety.
Yes you could use array<int,X*Y>, but why would you?
The point of the unique pointer in my example is to move the large array from the stack to the heap.
I see, that makes sense if the size of the array is a problem. But the size might not be a problem, and if it isn't its quicker to allocate the array on the stack. If a size or range of sizes is known statically, OP can simply tune the function. If size is determined at runtime and spans a range of sizes from stack-appropriate to not, then there might be a clever way to switch at runtime without duplicating too much code.
Yes you could use array<int, X*Y>,, but why would you?
My bad, I was under the impression that array<array<int,X>, Y> would not create a single block of memory contiguous in both directions [e.g. &(cell[0][width]) + 1 != &(cell[1][0])] but I see that's mistaken.
If size is determined dynamically, you need to use a vector. What you're talking about, using an in-place small array instead when there are only a few elements, is called small vector optimization. Many vector implementations and libraries with vector like containers will do this, usually for one or zero elements. There's no need to roll your own implementation. This is even more common for strings, because you can fit a lot of characters in the space of a few pointers.The point of the unique pointer in my example is to move the large array from the stack to the heap.
I see, that makes sense if the size of the array is a problem. But the size might not be a problem, and if it isn't its quicker to allocate the array on the stack. If a size or range of sizes is known statically, OP can simply tune the function. If size is determined at runtime and spans a range of sizes from stack-appropriate to not, then there might be a clever way to switch at runtime without duplicating too much code.
Yep. std::array is just a simple wrapper around old C/C++98 arrays with all the capabilities thereof.My bad, I was under the impression that array<array<int,X>, Y> would not create a single block of memory contiguous in both directions [e.g. &(cell[0][width]) + 1 != &(cell[1][0])] but I see that's mistaken.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
