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.

• Andreas: not sure what you are after. the "lambda is okay", "best expressed with iterators" and "was it right" questions are missing prerequisites. what are your requirements?
• phy nju: The question is finding "First all zero row ", why do you scan row and column?
• Ray Toal: @andreas Right, great questions, I meant lambdas vs. things like unary_functions and predicates from <functional>. and iterators vs. collection-specific methods, if any. Only "requirements" are to employ the most idiomatic uses of the standard library possible.
• Ray Toal: @phynju Is there a way to determine if a row contains all zeros without "scanning the columns"? I think all_of is perfectly safe; it returns as soon as it finds an element not meeting the condition.

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

• Ray Toal: Much appreciated feedback - I should use explicit std:: and auto more often indeed! (And yeah the test cases could have been in main :) ) Oh and also, having optionals would have been nice; I've been doing this in a lot of languages and it looks very good in Elm and Haskell with Maybe!