Trivial function gives unexpected return value-CodePudding

I have coded a function which receives a double matrix and looks backwards for a zero entry. If it finds one it changes the value of that entry to -2.0 and returns true. Otherwise it returns false.

Here's the code:

#include <iostream>
#include <vector>

bool remove1zero(std::vector<std::vector<double>> & matrix)
{
    size_t dim = matrix.size();
    for (size_t j = dim - 1; j >= 0; j--)
        for (size_t i = dim - 1; i >= 0; i--)
            if ((matrix[j])[i] == 0.0)
            {
                (matrix[j])[i] = -2.0;
                return true;
            }
    return false;
}

int main()
{
    std::vector<std::vector<double>> testMatrix(3);
    testMatrix[0] = std::vector<double> {-2.0, -2.0, 3.0};
    testMatrix[1] = std::vector<double> {-2.0, -1.0, 3.0};
    testMatrix[2] = std::vector<double> {2.0, 2.0, -1.0};
    std::cout << remove1zero(testMatrix);
}

Since that matrix has no zero entry, the if-condition shouldn't activate, and eventually remove1zero should return false. However, that's not what happens. I have tried it on my machine as well as in http://cpp.sh/ and the output is 1/true. I would appreciate any insight on why this happens.

CodePudding user response：

As mentioned in the comments, as size_t is an unsigned type, the j >= 0 and i >= 0 comparisons will always evaluate as "true" and, when either index reaches zero, the next value (after decrementing that zero value) will wrap around to the maximum value for the size_t type, causing undefined behaviour (out-of-bounds access).

A nice 'trick' to get round this is to use the "goes to" pseudo-operator, -->, which is actually a combination of two operators: What is the "-->" operator in C/C ?.

You can use this in your for loops as outlined below, leaving the "iteration expression" blank (as the decrement is done in the "condition expression") and starting the loop at a one higher index in the "init-statement" (as that decrement will be applied before entering the body of the loop).

Here's a version of your function using this approach (note that I have included a space in the x-- > 0 expressions, to clarify that there are actually two separate operators involved):

bool remove1zero(std::vector<std::vector<double>>& matrix)
{
    size_t dim = matrix.size();
    for (size_t j = dim ; j-- > 0; )
        for (size_t i = dim ; i-- > 0; )
            if (matrix[j][i] == 0.0) {
                matrix[j][i] = -2.0;
                return true;
            }
    return false;
}

CodePudding user response：

Don't use size_t as type for the loops. It can evaluate less than zero because it is unsigned. Just cast the size to an integer and work with that.

bool remove1zero(std::vector<std::vector<double>> & matrix)
{
    int dim = (int)matrix.size();
    printf("matrix size=%d\n",dim);
    for (int j = dim - 1; j >= 0; j--)
        for (int i = dim - 1; i >= 0; i--)
        {
            printf("%d, %d\n",i,j);
            if ((matrix[j])[i] == 0.0)
            {
                (matrix[j])[i] = -2.0;
                return true;
            }
        }
    return false;
}

CodePudding user response：

size_t is equal to unsigned long. When you check j or i in the for loop, you can't get a negative number. Therefore j and i get a weird value when you subtract 1 from 0. The solution is to change size_t to a simple long.

#include <iostream>
#include <vector>

bool remove1zero(std::vector<std::vector<double>> & matrix)
{
    long dim = (long)matrix.size();
    for (long j = dim - 1; j >= 0; j--)
    {
        for (long i = dim - 1; i >= 0; i--)
            if (matrix[j][i] == 0.0)
            {
                matrix[j][i] = -2.0;
                return true;
            }
    }
    return false;
}

int main()
{
    std::vector<std::vector<double>> testMatrix(3);
    testMatrix[0] = std::vector<double> {-2.0, -2.0, 3.0};
    testMatrix[1] = std::vector<double> {-2.0, -1.0, 3.0};
    testMatrix[2] = std::vector<double> {2.0, 2.0, -1.0};
    std::cout << remove1zero(testMatrix);
}

CodePudding user response：

With (unsigned) size_t j = dim - 1;, j >= 0 is always true. so you have out of bound access, instead of stopping the loop.

In C 20, with std::ranges::reverse_view

you might do:

bool remove1zero(std::vector<std::vector<double>> & matrix)
{
    for (auto& col : matrix | std::views::reverse)) {
        for (double& d : col | std::views::reverse) {
            if (d == 0.0) {
                d = -2.0;
                return true;
            }
        }
    }
    return false;
}

Demo