Equivalent iteration of 2D and 3D array flattened as 1D array?

[triumphost]

I have the following code for 2D dimensional arrays being flattened as 1D C-style arrays:

#include <iostream>

int main()
{
    int width = 4, height = 10;

    int arr[width * height];

    for (int i = 0, k = 0; i < height; ++i)
    {
        for (int j = 0; j < width; ++j)
        {
            arr[i * width + j] = k++;
        }
    }



    for (int i = 0; i < height; ++i)
    {
        for (int j = 0; j < width; ++j)
        {
            int* ptr = &arr[0] + height * i; //perfect also works with &arr[0] + width * i;
            std::cout<<ptr[j]<<"   ";
        }
    }
}

It prints: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
as demonstrated here: http://ideone.com/gcgocu
The array does NOT have to be a square (4x4) and the above still works.

Knowing that the above works, I made a class out of it and I defined an index operator as:

int* operator [](const int index) {return ptr + width * index;}

Such that I can do: Instance[i][j] and it works just fine.

Now I'm trying to do the same thing with a 3D array so I did:

#include <iostream>

int main()
{
    int width = 4, height = 4, depth = 4;

    int arr[width * height * depth];

    for (int i = 0, l = 0; i < depth; ++i)
    {
        for (int j = 0; j < height; ++j)
        {
            for (int k = 0; k < width; ++k)
            {
                arr[k + width * (j + depth * i)] = l++; //works just fine. perfect.
            }
        }
    }

    //Fails below.. Run-time access violation error.

    for (int i = 0; i < depth; ++i)
    {
        for (int j = 0; j < height; ++j)
        {
            for (int k = 0; k < width; ++k)
            {
                int** ptr = reinterpret_cast<int**>(&arr[0] + width * i); //this can't be right.
                std::cout<<ptr[j][k]; //this line should stay the same.
            }
        }
    }

    return 0;
}

It fails as demonstrated here: http://ideone.com/yqY2oK

How can I do the same thing for a 3D array? I tried asking stackoverflow and got a simple answer:

Never do this. In fact by doing this you are cheating your compiler. Old saying: Cheating is not a problem but if it being caught, then it is a problem. Sometimes you may get some unexpected result.

Answers like that one just doesn't help me. It's vague and just makes me want to get it done even more if it is possible at all. I was told not to do it for n-dimensional arrays starting from 2. So 2D, 3D, 4D, etc.. It has never failed me for 2D arrays so I want to know why I shouldn't do it and how can I do it for 3D arrays.

Any ideas??

[vmanes]

For starters, I think you're off in setting the ptr
int** ptr = reinterpret_cast<int**>(&arr[0] + width * i)
If ptr is to point to the beginning of each "page" ( dimension specified by depth ) then you also need to multiply by height;
int** ptr = reinterpret_cast<int**>(&arr[0] + height * width * i)

But that's not the problem with accessing the data. Using the two indexes [j][k] won't work, as there's no way of knowing where any row (j) begins. You can only access the pointer based array in one dimension, as you did in your first example. There you found the starting point of row, and offset from that. In the second program, you have to know how far the offset from the pointer is for a specific row, then offset to the desired column.

This works.

int** ptr = reinterpret_cast<int**>(&arr[0] + height*width * i); 
int offset = j * height + k;
std::cout<< ptr[offset] << std::endl;

[vijayan121]

This is a canonical way to flatten out arrays of more than one (runtime) dimension. (The code below is for three dimensions):

#include <vector>
#include <memory>

template < typename T > struct array_3d_flat
{
    array_3d_flat( std::size_t i, std::size_t j, std::size_t k,
                   const T& v = T() ) : data( i*j*k, v )
    {
        for( std::size_t m = 0 ; m < data.size() ; m += k )
            inner.push_back( std::addressof( data[m] ) ) ;

        for( std::size_t m = 0 ; m < inner.size() ; m += j )
            outer.push_back( std::addressof( inner[m] ) ) ;
    }

    // moveable, non-copyable
    array_3d_flat( const array_3d_flat<T>& ) = delete ;
    array_3d_flat<T>& operator= ( const array_3d_flat<T>& ) = delete ;
    array_3d_flat( array_3d_flat<T>&& ) noexcept = default ;
    array_3d_flat<T>& operator= ( array_3d_flat<T>&& ) = default ;

    T** operator[] ( std::size_t i ) { return outer[i] ; }
    T& operator() ( std::size_t i, size_t j, size_t k )
    { return outer[i][j][k] ; }

    const T** operator[] ( std::size_t i ) const ; // elided for brevity
    const T& operator() ( std::size_t i, size_t j, size_t k ) const ; // elided

    private:
         std::vector<T**> outer ;
         std::vector<T*> inner ;
         std::vector<T> data ;
};

Compiled code is here: http://coliru.stacked-crooked.com/a/7c570672c13ca3bf

[Banfa]

You have this wrong

arr[k + width * (j + depth * i)] = l++; //works just fine. perfect.

Compare with your 2D example, in that it is the outer loop variable that is missing from the calculation but that is not the case here. It works only because you have depth == height == width. It should be

arr[k + width * (j + height * i)] = l++; //works just fine. perfect.

This wont work (as you say it can't be right

int** ptr = reinterpret_cast<int**>(&arr[0] + width * i); //this can't be right.
std::cout<<ptr[j][k]; //this line should stay the same.

vmanes solution doesn't work either but only because at line 1 he used int** not int*.

However vmanes solution only has a single index not 2 as you want. The reason that your 2 indexes don't work is because a pointer is not an array and it is absolutely not an array of arrays. int** is still just a pointer don't let the 2 stars confuse you and because it is a pointer all it knows is the size of the object pointed to, int* in this case so the first index moves the pointer on by the size of int* not the size of your virtual array.

You could make this cast work (in theory) like this

int (*ptr)[4] = reinterpret_cast<(*ptr)[4]>(&arr[0] + width * i);
std::cout<<ptr[j][k]; //this line should stay the same.

Instead of using a pointer to pointer to int we are now using a pointer to array of 4 ints. Now the first index knows the size of the array it is pointing to and can move on the right amount and the second index can find the specific int in the array.

I suspect this will not work for you because I suspect you are looking for a solution that allows a dynamic size for the 3D array and the 4 in the cast and variable declaration are, and can only be, hardcoded.

vijayan121's solution works because it goes the extra mile and sets up the arrays (or vectors in this case) of data required to correctly direct the compiler when it performs the pointer arithmatic from the top level. i.e. at the first index instead of jumping straight into the data array it is directed to an array of pointers that point to the correct place so that when you move the index long one, which size it is a pointer to pointer moves the pointer on along one it accesses a pointer to the data array that is moved along by width * height not 1.