Source
r/cpp•
Chanz

Cleaner alternatives to multidimensional arrays declared at runtime

At work, I am implementing a simple (x and y) grid system for a game. I declare a two dimensional array containing pointers to game objects that are created at runtime.

Firstly, that's a triple pointer declaration right there and it can be daunting for other people who are looking at my code.

Secondly, even initializing this thing looks like a huge mess. Barely readable.

My questions:

Are there any better solutions for this? One idea I had was to use a map with the key as a data pair, an x and y. It's a hell of a lot cleaner but I am wondering what performance effect that might have as opposed to going with a straightforward array where the cost of accessing is always O(1).

Thanks for your time.

Posted Mar 30, 2015, 5:38 PM UTC

024
__Cyber_Dildonics__•

I've seen this question pop up a lot in various places and I can give you a very clear answer from experience. First though I would think about if you really need a matrix structure for this particular use case since you will use it to store pointers to objects (why not just store the objects themselves, or make a object matrix, where each member is a matrix instead of the matrix containing full objects?).

Anyway, what you want is to leave behind the [][] syntax. Let go of that. operator[] takes only one argument, so making that work at least gives your first [] returning a pointer and your second [] offsetting that and dereferencing it. That's bad. Pointer jumping like that is inefficient and in this case the syntax can be better anyway.

Make a matrix class or find one that does the following:

  1. One allocation based on rows and columns. Using a vector underneath is good. Don't worry about stack vs heap, it is only one allocation that shouldn't be inside any tight loops.

  2. Use operator() to dereference the underlying memory. Your memory layout could be row or column major. Lets say the rows are linearly congruent. you can use data[row*columns + column] or put differently - data[y*xres + x]

  3. You can make this return a pointer and dereference it outside the function or you can make two member functions - one returns a reference, one return a const reference and the function is declared const.

There are many advantages to this. You can pass a function to run on every member if it doesn't matter what the coordinates are, you can make sure to loop through it in a memory local way etc.

One thing: If you make it yourself, don't make a template first. Do that and you will get burned from compiler errors. Make it a class with a type and do the template conversion later.

7
lurkotato•

Agreed on using operator() vs operator[]

From cppreference.com

To provide multidimensional array access semantics, e.g. to implement a 3D array access a[i][j][k] = x;, operator[] has to return a reference to a 2D plane, which has to have its own operator[] which returns a reference to a 1D row, which has to have operator[] which returns a reference to the element. To avoid this complexity, some libraries opt for overloading operator() instead, so that 3D access expressions have the Fortran-like syntax a(i,j,k) = x;

3
bames53•

Anyway, what you want is to leave behind the [][] syntax. Let go of that. operator[] takes only one argument, so making that work at least gives your first [] returning a pointer and your second [] offsetting that and dereferencing it. That's bad. Pointer jumping like that is inefficient and in this case the syntax can be better anyway.

This isn't necessarily true: it's entirely possible to have chained [] access a contiguous block of memory. For example:

struct S {
  std::vector<int> storage;
  int columns;

  int *operator[] (int i) { return &storage[0] + i * columns; };
};

S s{{1,2,3,
     4,5,6,
     7,8,9}, 3};
assert(s[2][0] == 7);

Now, this example is absolutely minimal and doesn't enforce any safety, but hopefully you can see how one might flesh it out with, for example, a row_view type that implements the second level operator[] and still keep the memory contiguous.

Secondly, you can make operator[] work as though it takes any number of arguments you like:

struct S {
  struct index_type {int row, col;};

  void operator[] (index_type i);
};

S s;
s[{3, 4}];

This is the syntax I used when I recently demonstrated a matrix class with contiguous storage and that supports any number of dimensions with each dimension size determined at runtime: https://gist.github.com/bames53/3d23426afbf47dc62514

1
__Cyber_Dildonics__•

Your second trick is interesting and I will tuck that away for possible future use.

Your first example is exactly what I said in my post, operator[] returns a pointer that is itself de-referenced.

making that work at least gives your first [] returning a pointer and your second [] offsetting that and dereferencing it.

1
bames53•

But the memory is contiguous and there's no 'pointer jumping'; my code does not disable fast, linear memory access patterns. This is in contrast to using int** or vector<vector<int>> in order to get the chained [] syntax.

1
__Cyber_Dildonics__•

It could be the same I suppose depending on how it is implemented and the compiler, so I agree that is much closer to ideal than non.

If operator[] only increments an address and returns that, then it should be the same, so I would say you are right, it is the same.

1
remotion4d•

For example here you can find faster version of 2d and 3d Array based on single continuous array.

array2.h

array3.h

Please do Not use code like below for 2D (or more dimensional) arrays.

std::vector<std::vector<T>> my_slow_and_bad_2d_array;

std::map<std::vector<T>> my_very_very_slow_and_bad_2d_array;

It will be terrible slow because of cache misses and consume unnecessary memory.

3
bames53•

I recently wrote a proof of concept matrix class that supports any number of dimensions with dimension sizes set at runtime:

matrix<float, 3> mat({4, 4, 3}); // a 4x4x3 matrix
mat[{0, 0, 2}] // access third element in first row of first plane.

Under the covers it uses a vector<float> as contiguous storage, and it uses a bunch of template meta-programming to figure out how to compute the 'flattened' index

i * dimension2size * dimension3size + j * dimension3size + k

into the underlying vector, for an arbitrary number of dimensions. I usedC++1z (C++17) fold expressions to simplify that part of the work.

1
remotion4d•

It is nice piece of highly templated code, but accession array like this array[{1,2}] looks not really pretty.

Here is simple demo that allow array access like this array[1][2]
And compiler can optimize it away.
http://goo.gl/WUZuhR

1
salgat•

To expand on this, if you just want a very quick implementation of this, initialize with std::vector<T> array(widthheight) then use array[x + widthy] (which is essentially what those includes use).

1
manni66•

Have a look at Boost.MultiArray.

2
Arandur•

If you want performance, the two-dimensional array is the way to go. To make the syntax nicer, you could write your own class for the grid that overloads the [] operator.

1
Rabensky•

Isn't a one dimensional array with a stride better performance?

But completely agree on creating a grid class with operator (and operator()(size_t,size_t) as well).

3
Arandur•

I am reasonably certain -- but I may be wrong -- that a C-style n-dimensional array is semantically equivalent to a one-dimensional array with strides. It's just a syntactic nicety.

2
Rabensky•

But, at least in C++, the size of the array must be known at compile time. You can't have a C-style n-dimensional array with dynamic sizes.

1
Arandur•

That is correct.

1
__Cyber_Dildonics__•

I think this is only if it is declared outside any function and lives in the data segment. I'm not sure if a 2 dimensional array on the stack ends up being a strided 1 dimensional array underneath. Can someone clarify? I've actually tried and failed to look this up before.

1
minno•

If the array bounds are statically determined, you can go with std::array<std::array<Thing*, N>, M> to get an MxN array.

1
Rabensky•

Or, you know, Thing* thing[N][N]...

edit - * instead of &...

1
minno•

You get no added efficiency from that, and it's less convenient.

1