First all zero row of a matrix in C++

Question

The problem of finding the first all zero row in a NxN matrix was featured in a letter to the CACM in 1974 by Frank Rubin who claimed it was a problem for which using a GOTO was better than alternatives.

But many languages have labeled break statements and other features that make the problem trivial. In fact, in JavaScript we need only write:

a.findIndex(row => row.every(x => x === 0))

which gives us the index of the first nonzero row or -1 if no such row exists. I'm interested in implementing this functional approach in C++ 14. As I don't have a huge amount of C++ experience, I came up with:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

bool isAllZeroRow(const vector<int>& row) {
  return all_of(row.begin(), row.end(), [](int x){return x==0;});
}

int firstAllZeroIndex(const vector<vector<int>>& m) {
  return distance(m.begin(), find_if(m.begin(), m.end(), isAllZeroRow));
}

vector<vector<int>> matrix1 = {{1, 2}, {0, 0}, {1, 1}};
vector<vector<int>> matrix2 = {{0, 0, 1, 2}, {3, 0, 0}, {0, 0, 0}};
vector<vector<int>> matrix3 = {{0, 0, 1, 2}, {3, 0, 0}, {0, 0, 5}};

int main() {
  assert(firstAllZeroIndex(matrix1) == 1);
  assert(firstAllZeroIndex(matrix2) == 2);
  assert(firstAllZeroIndex(matrix3) == 3); // not found
  cout << "ok\n";
}

I'm interested in hearing things like:

• whether the lambda is okay, or should it be a named function or a C++ unary predicat
• Are distance and find_if best expressed with iterators like I have done here?
• Was it right to use the helper function, or is there a way in C++ to make things almost as concise as the JavaScript solution?

I know how to do this function with nested loops with a return in the inner loop, but I'm intrigued by trying out the functional forms and was wondering how I did.

Answer 1

avoid importing namespaces

You have using namespace std;. You are obviously working in a .cpp where it is usually fine to do this; but I (and many others) don't like to remove the std::. It is short enough to write it every time you are trying to access a function/class or whatever of the std scope. Use it; it makes things clearer (at least for me ;))

use free functions over member functions

Herb Sutter described it nice in one of his articles; please forgive me that I am not able to provide you with a short text but on stackoverflow there are plenty of topics like this. E.g. click me

It is more generic to use the std::begin and std::end functions than the container specific one. Technically it is totally the same; it just makes it easier to change the container type.

keep things local

I think you know that you should keep your objects as local as possible. I don't see a good reason here to declare your matrix objects in the global scope.

lambdas

The lambdas are fine. You could use a lambda for the isAllZeroRow() function instead of declaring a free function for this, but this is also fine.

You can declare the lambda parameters as auto. You don't have to define types explicitly anymore. This safes us from some annoying typing and redundancy and - one of my most loved arguments - it's more generic.

You could also delete the other free function, too, and just create a local lambda object.

int main() {
    std::vector<std::vector<int>> matrix1 = {{1, 2}, {0, 0}, {1, 1}};

    auto firstAllZeroIndex = [](const auto& m) {
        return std::distance(std::begin(m), std::find_if(std::begin(m), std::end(m), [](const auto& row){
            return std::all_of(std::begin(row), std::end(row), [](int x){return x==0;});
        }));
    };
    assert(firstAllZeroIndex(matrix1) == 1);
}

more meaningful return type

You should use a return type which offers you the possibility to return an invalid statement. In c++17 we'll get the comfortable type std::optional, but for now we can use a std::pair<int, bool> statement. In this case, the int of the type has a valid value as long as the bool of the pair is true. I recommend this, because it makes the code more self-descriptive.

some praises

You are using the c++ headers; <cassert> is the right one, as every other header with the c prefix and without the .h. Good job :D

From my point of view your solution looks almost perfect (at least with the given requirements). You should be aware of the fact, that in this example you could use std::array types instead of std::vector and that it could be possible to resize your matrix objects which could lead to different row sizes in one matrix object. In the end I would write a class for this, to prevent me (and others) from doing such dumb stuff and getting frustrated ;)