How do you return a 2d array in C++?

Question

How do I return a 2d array in C++?

For example, I have the following method in java:

public static int[][] getFreeCellList(int[][] grid) {
    // Determine the number of free cells
    int numberOfFreeCells = 0;
    for (int i=0; i<9; i++) 
      for (int j=0; j<9; j++)
        if (grid[i][j] == 0)
          numberOfFreeCells++;

    // Store free cell positions into freeCellList
    int[][] freeCellList = new int[numberOfFreeCells][2];
    int count = 0;
    for (int i=0; i<9; i++)
      for (int j=0; j<9; j++)
        if (grid[i][j] == 0) {
          freeCellList[count][0] = i;
          freeCellList[count++][1] = j;
        }
    return freeCellList;
  }

I'm trying to replicate this in C++. Normally, I would pass in the 2d array i wanted to return as reference parameter of the method in C++.

However, as you see in the method above the size of the array being returned isn't known until run-time.

So, in this case I'm guessing I need to actually return a 2d array, right?

Answer 1

You can put it in a struct and then return the struct. Otherwise C++ doesn't allow returning arrays. You can also return a pointer to the first element (of flat 1D array or fully dynamic 2D array).

Answer 2

You can use a vector of a vector as well.

typedef vector<vector<int> > array2d_t;

array2d_t etFreeCellList(array2d_t grid) {
    // ...

    array2d_t freeCellList;

    // Determine the number of free cells
    int numberOfFreeCells = 0;
    for (int i=0; i<9; i++) 
       for (int j=0; j<9; j++)
          if (grid[i][j] == 0) {
      freeCellList[count][0] = i;
      freeCellList[count++][1] = j;
    }
    return freeCellList; 
}

Answer 3

The inner arrays seem to be fixed to size of 2. You could therefor use a vector of array

static std::vector< array<int, 2> > getFreeCellList(int grid[][9]) {
    // Determine the number of free cells
    int numberOfFreeCells = 0;
    for (int i=0; i<9; i++) 
      for (int j=0; j<9; j++)
        if (grid[i][j] == 0)
          numberOfFreeCells++;

    // Store free cell positions into freeCellList
    std::vector< array<int, 2> > freeCellList(numberOfFreeCells);
    int count = 0;
    for (int i=0; i<9; i++)
      for (int j=0; j<9; j++)
        if (grid[i][j] == 0) {
          freeCellList[count][0] = i;
          freeCellList[count++][1] = j;
        }
    return freeCellList;
}

Usage is like

int x[9][9] = { ... };
std::vector< array<int, 2> > pa = getFreeCellList(x);

No need for manual memory management since you use std::vector. array is in boost, but you can quickly write a similar class manually

template<typename E, int N>
struct array {
  E &operator[](int I) { return data[I]; }
  E data[N];
};

The data member is an array of N elements of type E.

Alternatively, you can write this using low-level 2d arrays. Since the inner dimension is fixed in your code, you can actually allocate a real, native 2d array instead of a complicated 1d array of pointers to separate buffers:

static identity<int[2]>::type *getFreeCellList(int grid[][9]) {
    // Determine the number of free cells
    int numberOfFreeCells = 0;
    for (int i=0; i<9; i++) 
      for (int j=0; j<9; j++)
        if (grid[i][j] == 0)
          numberOfFreeCells++;

    // Store free cell positions into freeCellList
    int (*freeCellList)[2] = new int[numberOfFreeCells][2];
    int count = 0;
    for (int i=0; i<9; i++)
      for (int j=0; j<9; j++)
        if (grid[i][j] == 0) {
          freeCellList[count][0] = i;
          freeCellList[count++][1] = j;
        }
    return freeCellList;
}

Now you can use it like

int x[9][9] = { ... };

// equivalent: identity<int[2]>::type *pa = ...;
int (*pa)[2] = getFreeCellList(x);
// ...
delete[] pa;

Notice the use of identity (from boost or see below) to simplify the syntax. You would need to write the following otherwise

static int (*getFreeCellList(int grid[][9]))[2] {
  // ...
}

---

// identity implementation (for working around the evil C++ syntax)
template<typename T>
struct identity { typedef T type; };

Answer 4

You can't return an arbitrary-sized 2d array, just as you can't pass an arbitrary-sized 2d array as a parameter.

C++ arrays are horrible compared to Java arrays. Don't touch them! Use a vector instead.

Answer 5

A construct like

int[][] 

in C and C++ only exists for static data, such as

int[][] =
{
    {1, 2},
    {0, 1}
};

where the compiler can determine the size of the elements at compile time. If you know the size of the inner arrays at compile time - or if you can just can make them fix, then use a typedef such as:

typedef int[16] IntArr16;

Then your function can return a array of this type

IntArr16* getFreeCellList(...).

This all is plain C. Other possibilities are (as explained by dirkgently) to return stl containers.

Answer 6

It's more of a C-style solution than a C++-style solution, but you can always return a structure like

struct {
    int   dimension_one;
    int   dimension_two;
    void* pArray;
} return_type_t;

Allocate your 2D array dynamically, store the two array dimensions and a pointer to the allocated memory in the structure, and pass that back to the caller.