Bidimensional array annihilator

We have in input a bidimensional array of integers. We should modify it so that any row and column that has originally at least a single element set to zero would have all of them set to zero.

Conceptually it is an easy problem, its main issue is a technical one, since that working with multidimensional arrays in C/C++ has never been exactly a piece of cake.

The idea is to store in two boolean vectors the status of each row and column, setting to true anyone that needs a reset.

Then using that flags to set to zero the elements that need it.

Firstly, let's see how to implement a solution that won't use any STL container.

The C harder way

All is done through C-arrays and raw pointers.

Here is the prototype of the function I want to define:

void cAnnihilator(int* data, const unsigned nRows, const unsigned nCols);

The problem does not specify the array size, so we need to keep it open in our call. For this reason I am forced to pass to the function just the pointer to the first element.

A couple of test case:

TEST(cAnnihilator, CaseSimple) // 1
{
  const int nRows = 5;
  const int nCols = 3;
  int data[nRows][nCols] = {
    { 1, 2, 3 },
    { 4, 5, 6 },
    { 7, 8, 9 },
    { 10, 11, 0 },
    { 13, 14, 15 }
  };

  cAnnihilator(&data[0][0], nRows, nCols); // 2

  for(int i = 0; i < nRows; ++i)
    ASSERT_EQ(data[i][2], 0);
  for(int i = 0; i < nCols; ++i)
    ASSERT_EQ(data[3][i], 0);
}

TEST(cAnnihilator, CaseNothing) // 3
{
  const int nRows = 2;
  const int nCols = 3;
  int data[2][3] = {
    { 1, 2, 3 },
    { 4, 5, 6 }
  };

  cAnnihilator(&data[0][0], nRows, nCols);

  for(int i = 0; i < nRows; ++i)
    for(int j = 0; j < nCols; ++j)
    ASSERT_NE(data[i][j], 0);
}

1. The simple case creates a 5x3 array with only a zero element, after the call to the annihilator, all the elements in column 2 and row 3 are expected to be set to zero.
2. I pass to the annihilator the pointer to the first element in the array and its dimensions.
3. This "nothing" test case gives in input a 3x2 array with no zero element. No change is expected in output.

Here is how I implemented the function:

void cAnnihilator(int* data, const unsigned nRows, const unsigned nCols)
{
  bool rows[nRows]; // 1
  for(unsigned i = 0; i < nRows; ++i)
    rows[i] = false;
  bool cols[nCols];
  for(unsigned i = 0; i < nCols; ++i)
    cols[i] = false;

  for(unsigned i = 0; i < nRows; ++i)
    for(unsigned j = 0; j < nCols; ++j)
      if(*(data + (i * nCols) + j) == 0) // 2
        rows[i] = cols[j] = true;

  for(unsigned i = 0; i < nRows; ++i)
    for(unsigned j = 0; j < nCols; ++j)
      if(rows[i] || cols[j])
        *(data + (i * nCols) + j) = 0; // 3
}

1. The rows and cols boolean array are initialized to "all false". When I'll find a zero element I'll set the relative row and column flag to true.
2. Convert the current element position in bidimensional array notation to its plain distance from the first array element.
3. Set to zero all the elements in rows and columns that require it.

The C++ way

There are a couple of improvement I'd like to to on the function parameter. Firstly, I'd like to give more work to the compiler, let it the burden of deducing the array's size, instead of requiring the client to pass the number of rows and columns. And secondly, I'd prefer to use a STL container instead the raw C-array.

As a result of these consideration, I wrote this function declaration:

template<size_t N, size_t M>
void annihilator(std::array<std::array<int, N>, M>& data);

Now I am passing to the annihilator a reference to an STL array of arrays. A M-sized array of N N-sized int arrays. N and M are template parameters that are deduced from the passed bidimensional array, so that the user doesn't have to specify them in the call.

The test cases for this version of my function look like this:

TEST(Annihilator, CaseSimple)
{
  std::array<std::array<int, 3>, 5> data {{ // 1
    {{ 1, 2, 3 }},
    {{ 4, 5, 6 }},
    {{ 7, 8, 9 }},
    {{ 10, 11, 12 }},
    {{ 13, 14, 15 }}
  }};

  unsigned row = 3; // 2
  unsigned col = 2;
  data[row][col] = 0;

  annihilator(data); // 3

  for(unsigned i = 0; i < data.size(); ++i) // 4
    ASSERT_EQ(data[i][col], 0);
  for(unsigned i = 0; i < data[3].size(); ++i)
    ASSERT_EQ(data[row][i], 0);
}

TEST(Annihilator, CaseNothing)
{
  std::array<std::array<int, 3>, 2> data {{
    {{ 1, 2, 3 }},
    {{ 4, 5, 6 }}
  }};

  annihilator(data);

  for(unsigned i = 0; i < data.size(); ++i)
    for(unsigned j = 0; j < data[i].size(); ++j)
      ASSERT_NE(data[i][j], 0);
}

1. This bracket surplus is a bit annoying. It is not required by the C++11 standard but the current GCC implementation. Your compiler could understand a single bracket.
2. Set a value to zero.
3. The annihilator call is so much cleaner.
4. Ensure the annihilator works as expected.

And finally, here is my C++11 annihilator implementation:

template<size_t N, size_t M>
void annihilator(std::array<std::array<int, N>, M>& data)
{
  std::array<bool, N> cols {}; // 1
  std::array<bool, M> rows {};

  for(unsigned i = 0; i < M; ++i)
    for(unsigned j = 0; j < N; ++j)
      if(data[i][j] == 0) // 2
        rows[i] = cols[j] = true;

  for(unsigned i = 0; i < M; ++i)
    for(unsigned j = 0; j < N; ++j)
      if(rows[i] || cols[j])
        data[i][j] = 0;
}

1. The initializer list is much more expressive than a for-loop. All the elements in cols and rows are initialized to false.
2. Accessing STL-array elements as if they were C-array one (and they actually are, after all).

The source code is on github.