Datatype for vector<vector<int> > not matching-CodePudding

So, in the following piece of code i am calculating the exponent of a matrix. Here,

long long mod = (1e 9) 7;

vector<vector<int>> matrixMultiply(vector<vector<int>>& A, vector<vector<int>>& B){
    vector<vector<int>> ans(2, vector<int> (2));
    for(int i = 0; i < 2;   i)
        for(int j = 0; j < 2;   j)
            for(int k = 0; k < 2;   k){
                ans[i][j]  = ((A[i][k]%mod) * (A[k][j]%mod))%mod;
                ans[i][j] = ans[i][j]%mod;
            }
    return ans;
}

vector<vector<int>> matrixPower(int n, vector<vector<int>>& M){
    if(n==1) {
        return M;
    }
    vector<vector<int>> temp = matrixPower(n/2,M);
    if(n%2==0){
        return matrixMultiply(temp,temp);
    }
    else{
        return matrixMultiply(matrixMultiply(temp,temp),M);
    }
}

int solve(int A){
    vector< vector<int>> M{{1,1},{1,0}};
    vector< vector<int>> Mpower = matrixPower(A-1,M);
    return Mpower[0][0];
}

int main(){
    cout << solve(4);
    return 0;
}

Here when i run the code, I get the following error,

main.cpp: In function 'std::vector<std::vector<int> > matrixPower(int, 
std::vector<std::vector<int> >&)': main.cpp:41:49: error: invalid initialization of non-const 
reference of type 'std::vector<std::vector<int> >&' from an rvalue of type 
'std::vector<std::vector<int> >' return matrixMultiply(matrixMultiply(temp,temp),M);
                                                       ~~~~~~~~~~~~~~^~~~~~~~~~~
main.cpp:21:25: note:   initializing argument 1 of 'std::vector<std::vector<int> > 
matrixMultiply(std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)'
vector<vector<int>> matrixMultiply(vector<vector<int>>& A, vector<vector<int>>& B){
                    ^~~~~~~~~~~~~~

However when I do little bit of modification in my matrixPower function, like this,

vector<vector<int>> matrixPower(int n, vector<vector<int>>& M){
    if(n==1) {
        return M;
    }
    vector<vector<int>> temp = matrixPower(n/2,M);
    vector<vector<int>> multiplied_matrix = matrixMultiply(temp,temp);
    if(n%2==0){
        return multiplied_matrix;
    }
    else{
        return matrixMultiply(multiplied_matrix,M);
    }
}

It works without any compilation error. Please help me understood what exactly is the difference between this two pieces of code. Thank you.

CodePudding user response：

The parameters of matrixMultiply are of type vector<vector<int>>& - i.e. "reference to vector of vector of int". (The & means reference.)

This means that instead of the compiler making a copy of the matrix, and giving that copy to matrixMultiply to use, it instead just gives it a reference (basically just the memory address) to the existing copy that the caller already has.

However, in your first example, the caller doesn't actually store the matrix returned by the first matrixMultiply call anywhere, it just passes it straight to the second matrixMultiply call. This is known as a temporary object, and can't be passed as a non-const reference.

If you want the efficiency of passing by reference, without having to create the multiplied_matrix variable, you could change matrixMultiply to take const references instead - i.e. vector<vector<int>> const&. This means that matrixMultiply can't modify the original matrices, but it can still use the data in them to create a new (multiplied) matrix. In this case you would not need to make any changes to the body of matrixMultiply to allow it to work with const references.

So why can you pass a temporary object to a const reference? Well, if the callee were allowed to modify the referenced object, where would those modifications go? There's no actual variable in the caller's scope where that object "lives", so clearly the caller doesn't expect to receive information back from the callee through the reference.

Ok, but what if the caller wants to modify the parameter for its own purposes (e.g. because it wants to make some changes to the parameter, and doesn't want to have to copy it)? Well, that's where "move semantics" come in. This gets a bit more complicated though, so you may just want to use a const reference for now, and then if your function needs to take a copy of the referenced object, it can do that explicitly.

Here are some links for more info on temporary objects and move semantics: