Passing two-dimensional array address to a function

[ehsantl]

Hi folks

I'm trying to do my assignment in c++, I suppose to develope a maze traversal using backtracking algorithm. I have to write a constructor for my Maze with this sign.

Maze(**c, int size);

which takes a n-by-n two-dimensional character array.

Can you guide how can pass an array to this constructor? and how can I use it in the function?

Cheers
Ethan

[Narue]

This is one area where arrays and dynamic arrays are different. To pass an actual array as a function parameter, the following syntax is used:

T (*param_name)[COLS]

Alternatively, you can use the empty dimension syntactic sugar:

T param_name[][COLS]

The first dimension can also hold a size, even though it's ignored:

T param_name[ROWS][COLS]

In real code it looks like this:

#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <ostream>

template <typename T>
std::ostream& display(std::ostream& out, T (*array)[5], std::size_t n)
{
    for (std::size_t i = 0; i < n; i++) {
        for (std::size_t j = 0; j < n; j++)
            out<< std::setw(std::numeric_limits<T>::digits10 + 2) << array[i][j];
        out<< out.widen('\n');
    }

    return out;
}

int main()
{
    const int N = 5;

    int a[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            a[i][j] = rand();
    }

    display(std::cout, a, N);
}

The reason for this odd syntax is the rule that an array is converted to a pointer to the first element when used in value context (ie. int a[10] becomes int *a ). Passing an array to a function is value context, so the first dimension of a two-dimensional array "decays" into a pointer. But multi-dimensional arrays in C++ are not true multi-dimensional arrays. Rather, they're arrays of arrays. The difference is subtle, but the end result is that this pointer decay rule only applies to the first dimension of a multi-dimensional array, and an array of arrays of T becomes a pointer to an array of T ( int a[2][5] becomes int (*a)[5] ).

One glaring problem with this conversion is while the size of the first dimension becomes irrelevant, all subsequent dimensions are still arrays, and an array in C++ requires a size. In the above example code, you could pass an array defined as int a[20][5] because the first dimension becomes a pointer, but you could not pass an array where the second dimension has a size of anything but 5.

When an array of arrays is simulated with pointers and dynamic memory, no such conversion rule exists; the object is already a pointer, after all. A multi-dimensional array is simulated (most commonly) with pointers to pointers, one pointer per dimension:

#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <ostream>

template <typename T>
std::ostream& display(std::ostream& out, T **array, std::size_t n)
{
    for (std::size_t i = 0; i < n; i++) {
        for (std::size_t j = 0; j < n; j++)
            out<< std::setw(std::numeric_limits<T>::digits10 + 2) << array[i][j];
        out<< out.widen('\n');
    }

    return out;
}

int main()
{
    const int N = 5;

    int **a = new int*[N]; // Create the first dimension

    // Create each second dimension
    for (int i = 0; i < N; i++)
        a[i] = new int[N];

    // Working with the "array" remains the same
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            a[i][j] = rand();
    }

    display(std::cout, a, N);

    // Downside: the memory needs to be released
    for (int i = 0; i < N; i++)
        delete[] a[i];
    delete a;
}

Note how the function parameter matches the declaration in main perfectly. One of the reasons for using simulated arrays is to remove the limitation of multi-dimensional array parameters requiring a size for all but the first dimension. If you have a function that expects multi-dimensional arrays where the sizes are variable, actual arrays are extremely awkward.

Sometimes people use a non-portable trick for passing a multi-dimensional array as a single-dimensional array to get around the size requirement and also avoid dynamic allocation:

#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <ostream>

template <typename T>
std::ostream& display(std::ostream& out, T *array, std::size_t n)
{
    for (std::size_t i = 0; i < n; i++) {
        for (std::size_t j = 0; j < n; j++)
            out<< std::setw(std::numeric_limits<T>::digits10 + 2) << *((array + i * n) + j);
        out<< out.widen('\n');
    }

    return out;
}

int main()
{
    const int N = 5;

    int a[5][5];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            a[i][j] = rand();
    }

    display(std::cout, &a[0][0], N);
}

The address of the first element of the array is passed, then inside the function manual indexing is done with pointer arithmetic. It's not a recommended practice if you can avoid it, but I have yet to see an implementation where this trick fails to work as expected.

Of course, all of this could be avoided by using a suitable container class such as std::vector or boost::multi_array, but I suspect your assignment doesn't allow for any of the better options. ;)

[Ancient Dragon]

Pass it just like you would any other array

class foo
{
public:
    foo(char **ar, int n)
    {
    }



};



int main()
{
    char** mz = new char*[5];
    for(int i = 0; i < 5; i++)
        mz[i] = new char[5];
    foo f2(mz,5);
}

[edit]Oops! Sorry Narue, I didn't see your post.

[ehsantl]

Thanks guys, with your help I finished the project last night ;)

Good day

[mrnutty]

And since it looks like you are already using classes, you can do something like this :

//creates a NxN maze
template<typename T, int N>
class Maze{
private:
 T _maze[N*N];
public:
 //some codes
 T& operator()(int row, int col){
   //some validation
   assert(isPositive(row) && isPositive(col) );
   assert(row*col < N*N);
   return _maze[ col + row*N]; //indexing conversion from 2d to 1d
 }
}

I suspect, you should be doing something like this, at the very least, instead of raw pointer to pointers.