CODEWITHSUNDEEP
c++c++11
Brandon
Brandon

Reputation: 23498

Explain 2D array iteration with 1 loop

Can someone explain why this algorithm works for iterating a 2D array as a 1D array? In other words.. with one loop?

const int Width = 6;
const int Height = 4;

int Array[Width][Height];

for (int I = 0; I < Width * Height; ++I)
{
    Array[I % Width][I / Width] = I; //This line :S
}

for (int I = 0; I < Height; ++I)
{
    for (int J = 0; J < Width; ++J)
    {
        std::cout<<Array[J][I]<<"  ";
    }
    std::cout<<"\n";
}

Upvotes: 3

Views: 6859

Answers (4)

Dan M. Katz
Dan M. Katz

Reputation: 337

for (int x = 1, y = 1; y <= 5; (x < 5) ? (x++) : (x = 1, y++))

I'm sorry.

Upvotes: 1

paddy
paddy

Reputation: 63471

You are not using it as a 1D array. You are still indexing it as a 2D array. However, you're using maths (modulo and integer division) to recover the 2D indices from a 1D index based on the array's dimensions. This is pretty normal, but it's unusual to do this in a loop the way you've done so, as it could be computationally expensive.

Upvotes: 1

user2454182
user2454182

Reputation:

The memory allocated for a 2 dimensional array is still laid out linearly. So if you were to examine the memory at your variable Array, it would consist of Width number of ints followed by Width number of ints again... for Height times.

If Width = 5, and Height = 2... the memory for Array would look something like this (where each [] set is an integer):

[w0/h0][w1/h0][w2/h0][w3/h0][w4/h0][w0/h1][w1/h1][w2/h1][w3/h1][w4/h1]

When you use Array[j][i] to access the array, it's just automatically doing that math for you, to offset correctly into the linear block of memory.

Upvotes: 1

Yuushi
Yuushi

Reputation: 26040

The easiest way to see how it works is to plug in the numbers yourself. Starting from 0, we'll get:

Array[0 % 6][0 / 6] = Array[0][0]
Array[1 % 6][1 / 6] = Array[1][0]
...
Array[5 % 6][5 / 6] = Array[5][0]
Array[6 % 6][6 / 6] = Array[0][1]
...
Array[11 % 6][11 / 6] = Array[5][1]

and so on. Because it uses integer division, each time we go through Width values, it i / Width will be one more. Utilizing i % Width, this will then loop over each value (in this case, 0 to 5) at that specific i / Width. Because integer division truncates, this will be the same until i becomes the next multiple of Width.

Upvotes: 8

Related Questions