Auto reference for vectors?

Question

The following code will not alter the contents of i in the for loop:

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if (target == 0) {return vector<vector<int>>{{}};} 
        else if (!candidates.size() || target < 0) {return vector<vector<int>>();}
        else {
            vector<vector<int>> with = combinationSum(candidates, target - candidates[0]); 
            vector<int> new_vector(candidates.begin() + 1, candidates.end());
            vector<vector<int>> without = combinationSum(new_vector, target);
            for (auto i : with) {i.push_back(candidates[0]);}

            with.insert(with.end(), without.begin(), without.end());
            return with;
                                        
        }
    }
};

However, if I change it to auto& i : with ..., it works. Is there a reason why? I thought references were only relevant if you are working with pointed objects or if you don't want the variable (in this case i) to change in the local scope.

Answer 1

auto defaults to being neither const nor a reference. So for (auto i : with) { is storing to i by value, which invokes the copy constructor for each of the nested vectors. That copy has nothing to do with the version stored in your vector of vectors, so no changes persist when the copy goes away. Your addition of & makes it a reference that aliases the underlying inner vector so changes to the reference change the original vector.

If you don't want to change the object in question, the efficient way to do this is to use const auto& to both prevent changes and avoid copies; it's fairly rare you want to iterate by value this way unless you really want a mutable copy that won't affect the original, since the copy constructor costs can get pretty nasty.

Answer 2

On using for (auto i : with), you are copying the element i from the vector with and then using it.

On using for (auto & i : with), you are referencing the element i from the vector with and then using it.

Your vector would change if you were copying the addresses of its elements then dereferencing (or you were using a vector of pointers) but here you are copying the objects.

Answer 3

for (auto i : with) { ... is equivalent to:

for (vector<int>::iterator it = with.begin(); it != i.end(); it++)
{
    vector<int> i = *it;
    ...

And you can then see that i makes a copy each time round the loop. Changes to this copy therefore affect only the copy, which is a temporary.

OTOH for (auto &i : with) ... is equivalent to:

for (vector<int>::iterator it = with.begin(); it != i.end(); it++)
{
    vector<int>& i = *it;
    ...

which assigns a reference each time round the loop. Changes to this reference therefore affect the original object.