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 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 2

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; };