1

say you have a matrix of dimensions x per y (per z) defined like:

int** tab = new int*[x];
for(int i=0; i<x; ++i) tab[i] = new int[y];

or

int*** tab = new int**[x];
for(int i=0; i<x; ++i) {
  tab[i] = new int*[y];
  for(int j=0; j<y; ++y) tab[i][j] = new int[z];
}

is there any smart way to access sub-matrix (get int**(*) without data copying, plain C++) which will have top-left(-front) corner [a,b(,c)] and size of [A, B(,C)]?

Here are (better or worse) graphical examples of the problem.

matrix 2d example enter image description here

ad absurdum
  • 19,498
  • 5
  • 37
  • 60
michelson
  • 686
  • 9
  • 22
  • Access to sub-arrays will only work in a very limited way. Have a look at [SO: How are 2-Dimensional Arrays stored in memory?](https://stackoverflow.com/q/38204677/7478597) to understand why. – Scheff's Cat Oct 28 '17 at 09:28
  • Btw. you can allocate a 3d array with `int (*pA3d)[3][4][5] = new int[3][4][5];` but this is limited to multi-dim arrays with fixed size. For varying sizes, _I_ would drop the multi-dim. trouble and work with a 1 dim. array. If you really want this multi-dim things `std::vector` could make your life easier (e.g. `std::vector > >` but again: I would prefer `std::vector` and do the multi-dim indexing on my own. You could wrap it in a dedicated `class MyMatrix` as the Eigen lib. did.) – Scheff's Cat Oct 28 '17 at 09:34
  • Hmm. better forget about `int (*pA3d)[3][4][5] = new int[3][4][5];`. I'm really not sure about pointer to array vs. pointer to first element. (This cries for trouble although I remember that I someday mastered it when I tried out of curiosity.) – Scheff's Cat Oct 28 '17 at 09:37

1 Answers1

2

You are using what is called a jagged array. It is an array of arrays, where nothing besides runtime enforces that the sub arrays are the same size. Hence jagged, because you could have the subarrays vary in size.

In order to have a submatrix that is also a jagged array, you need for there to exist a jagged array of pointers pointing at the subarrays of the submatrix. These don't exist in general, so no, you cannot do this "without copying" at least some arrays of pointers to subarrays.

Had your matrix been not jagged array based, but instead single array with stride, then views of subarrays could be created without allocating new subarray pointer arrays. Also it would be more cache friendly.

To write the non-jagged matrix, start by writing an array view or span class that handles one dimension.

For two dimensions, you augment the span class to store a tuple of dimension sizes or strides. [] instead of returning a reference to the calculated element, creates a one-dimension-lower span instance pointing at the calculated position, until the dimension 0 case where you return a reference.

This will be highly efficient, permit efficient subarrays, but requires a few dozen or 100 lines of code to get right.

Scheff's Cat
  • 19,528
  • 6
  • 28
  • 56
Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • "stride" was my next idea but your answer appeared before I could write it down. Thus, I at least fixed some typos and added a link as stride may not be so common (if you don't know what its used for). – Scheff's Cat Oct 28 '17 at 09:52