How to Map the Indexes of a Matrix to a 1-Dimensional Array (C++)

How to map the indexes of a matrix to a 1-dimensional array (C++)?

The way most languages store multi-dimensional arrays is by doing a conversion like the following:

If matrix has size, n (rows) by m (columns), and we're using "row-major ordering" (where we count along the rows first) then:

matrix[ i ][ j ] = array[ i*m + j ].

Here i goes from 0 to (n-1) and j from 0 to (m-1).

So it's just like a number system of base 'm'. Note that the size of the last dimension (here the number of rows) doesn't matter.

---

For a conceptual understanding, think of a (3x5) matrix with 'i' as the row number, and 'j' as the column number. If you start numbering from i,j = (0,0) --> 0. For 'row-major' ordering (like this), the layout looks like:

           |-------- 5 ---------|
  Row      ______________________   _ _
   0      |0    1    2    3    4 |   |
   1      |5    6    7    8    9 |   3
   2      |10   11   12   13   14|  _|_
          |______________________|
Column     0    1    2    3    4 

As you move along the row (i.e. increase the column number), you just start counting up, so the Array indices are 0,1,2.... When you get to the second row, you already have 5 entries, so you start with indices 1*5 + 0,1,2.... On the third row, you have 2*5 entries already, thus the indices are 2*5 + 0,1,2....

For higher dimension, this idea generalizes, i.e. for a 3D matrix L by N by M:

matrix[ i ][ j ][ k ] = array[ i*(N*M) + j*M + k ]

and so on.

---

For a really good explanation, see: http://www.cplusplus.com/doc/tutorial/arrays/; or for some more technical aspects: http://en.wikipedia.org/wiki/Row-major_order

Map a 2D array onto a 1D array

You need to decide whether the array elements will be stored in row order or column order and then be consistent about it. http://en.wikipedia.org/wiki/Row-major_order

The C language uses row order for Multidimensional arrays

To simulate this with a single dimensional array, you multiply the row index by the width, and add the column index thus:

 int array[width * height];

 int SetElement(int row, int col, int value)
 {
    array[width * row + col] = value;  
 }

Map array index to matrix

If index is an index into a single-dimensional array of 9 elements, the array can be viewed as a two-dimensional 3x3 array with this:

int row = index / 3;
int column = index % 3;
int foo = array[row][column];

How to map a 2D array in a 1D array in C++?

Let W be the width of the 2D array, and H its height. Then assuming row-major layout, the 1D index 'ix' relates to the 2D-index [x,y] as such:

ix = y*w + x;
y = ix / w;  // implicit floor
x = ix % w;

e.g.:

const int W = 3, H=2;
int m[H][W] = {{1,2,3}, {4,5,6}};
int* oneD = &m[0][0];
assert(oneD[1*W + 2] == m[1][2]); // element 6, y=1, x=2

How do I map a position in a n dimensional matrix to 1D, in C++ at compile time?

If I understand correctly... your looking something as follows

template <auto ... as>
auto constexpr pos_nd_to_1d ()
 { 
   std::size_t  i { 0u };

   ((i *= DIM, i += as - 1u), ...);

   return i;
 }

Or maybe you can use std::common_type, for i,

std::common_type_t<decltype(as)...>  i {};

but for indices I suggest the use of std::size_t (also std::size_t ... as).

The following is a full compiling example

#include <iostream>

constexpr auto DIM = 3u;

template <auto ... as>
auto constexpr pos_nd_to_1d ()
 { 
   std::size_t  i { 0u };

   ((i *= DIM, i += as - 1u), ...);

   return i;
 }

int main ()
 {
   std::cout << pos_nd_to_1d<1u, 1u, 1u>() << std::endl;
   std::cout << pos_nd_to_1d<1u, 2u, 1u>() << std::endl;
   std::cout << pos_nd_to_1d<1u, 3u, 1u>() << std::endl;
 }

-- EDIT --

The OP ask

could you explain how this code works?I am a bit new to c++.

I'm better at coding that at explaining, anyway...

What I've used here

   ((i *= DIM, i += as - 1u), ...);
//...^^^^^^^^^^^^^^^^^^^^^^   repeated part

is called "fold expression" (or also "folding" or "template folding"), and is a new C++17 feature (you can obtain the same result also in C++14 (also C++11 but not constexpr) but in a less simple and elegant way) that consist in expanding a variadic template pack with an operator.

By example, if you want to sum the indexes, you can simply write

(as + ...);

and the expression become

(a0 + (a1 + (a2 + (/* etc */))));

In this case I've used the fact that the comma is an operator, so the expression

   ((i *= DIM, i += as - 1u), ...);

become

   ((i *= DIM, i += a0 - 1u), 
     ((i *= DIM, i += a1 - 1u),
        ((i *= DIM, i += a2 - 1u),
           /* etc. */ )))))

Observe that, this way, the first i *= DIM is unuseful (because i is initialized with zero) but the following i *= DIM multiply as - 1u the right number of times

So, when as... is 1, 2, 1, by example, you get

  (1 - 1)*DIM*DIM + (2 - 1)*DIM + (1 - 1)

Representing a 2D array as a 1D array

Take a look at Performance of 2-dimensional array vs 1-dimensional array

3D to 1D mapping function confusion

You computed the mapped index for out-of-bounds values of y.

You said height * width * depth= 12, and:

index = y * width * depth + x * depth + z

And we see in your table:

#.| Y | X | Z | index
--+---+---+---+------
1 | 0 | 1 | 0 | 2
2 | 1 | 0 | 0 | 6

This implies:

1. 0 * width * depth + 1 * depth + 0 = 2 => depth = 2
2. 1 * width * depth + 0 * depth + 0 = 6 => width * depth + 6 => width = 3
3. height * width * depth= 12 => height = 2

Thus:

• y is in [0, 1]
• x is in [0, 2]
• z is in [0, 1]

The maximum index is at {x, y, z} = {2, 1, 1} and its value is 1 * 2 * 3 + 2 * 2 + 1 = 11.

How to flatten or index 3D-array in 1D array?

The algorithm is mostly the same. If you have a 3D array Original[HEIGHT, WIDTH, DEPTH] then you could turn it into Flat[HEIGHT * WIDTH * DEPTH] by

Flat[x + WIDTH * (y + DEPTH * z)] = Original[x, y, z]

As an aside, you should prefer arrays of arrays over multi-dimensional arrays in .NET. The performance differences are significant

Navigating multidimensional array using one variable

I need to be able to navigate the array using a single int like:
int i = 4;
cout << arrayOne[4];
It it possible to do it like this

Yes, it is:

int arrayOne[3][3] {
  {1,2,3},
  {4,5,6},
  {7,8,9},
};

int* array = arrayOne[0];
std::cout << array[4];

Map 2D matrix to 1D array

If you have a 2d array and a 1d array having same elements,then the following will be true

  2d[i][j]=1d[i*number_of_columns+j]

I am assuming from your post that you already have created a 1d array out of a 2d one.
Note i and j are indices and rememeber indices begin from 0

EDIT:If you are accessing an element at [5][5] (as last element)it means your array is of order 6 by 6 and not 5 by 5.So your 1d array will have 6*6=36 elements and not 25.

---

Related Topics