CODEWITHSUNDEEP
c++for-loopforeach
Lusha Li
Lusha Li

Reputation: 319

for each in C++ fails to update the vector

I for_each an vector and changed the vector inside the for-loop. However, when I ran the program, after the program left the for-loop the vector was still unchanged. What caused the problem? If I still want to use for_each loop, how can I fix it?

Here is the code (my solution for leetcode 78):

class Solution {
public:

    void print(vector<int> t){
        for(int a:t){
            cout<<a<<" ";
        }
        cout<<endl;
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        res.push_back(vector<int>{});
        int m=nums.size();
        for(int a:nums){
            cout<<"processing "<<a<<endl;

            for(auto t:res){
                vector<int> temp{a};
                temp.insert(temp.end(),t.begin(), t.end());
                res.push_back(temp); 
                cout<<"temp is ";
                print(temp);
                res.reserve();
            }

            // int s=res.size();
            // for(int i=0;i<s;i++){
            //     vector<int> temp{a};
            //     temp.insert(temp.end(), res[i].begin(), res[i].end());
            //     res.push_back(temp);
            // }

        }
        return res;
    }
};

If I used the placed I commented out to replace the for_each loop, it gave the correct solution.

Upvotes: 0

Views: 216

Answers (2)

Walter
Walter

Reputation: 45434

The problem here is that you are looping over the subsets created so far and then add more subsets in the same loop, appending them. There are two problems with this.

  • First (as pointed out by Sam), vector::push_back() may invalidate iterators which control the loop, thus breaking the code.
  • Second, even when using a container (such deque or list), where push_back() would not invalidate any pointers, your loop would run indefinitely, as you keep adding new elements.

The correct way is to only loop the subsets created before the loop starts, but then add new subsets, i.e. doubling the number of subsets. The easiest way to achieve this is to use good old index-based loops and allocate/reserve enough subsets (2^n) at the onset.

vector<vector<int>> subsets(vector<int> const& nums)
{
    const auto n=nums.size();
    vector<vector<int>> subset(1<<n);    // there are 2^n distinct subsets
    for(size_t i=0,j=1; i!=n; ++i)       // loop distinct nums
        for(size_t k=j,s=0; s!=k; ++s) { //  loop all subsets so far s=0..j-1
            auto sset = subset[s];       //   extract copy of subset
            sset.push_back(nums[i]);     //   extend it by nums[i]
            subset.at(j++) = move(sset); //   store it at j
        }
    return subset;
}

Upvotes: 0

Sam Varshavchik
Sam Varshavchik

Reputation: 118340

The shown code exhibits undefined behavior.

Inside the for-loop:

    res.push_back(temp);

Adding new elements to a std::vector invalidates all existing iterators to the vector (there are several edge cases, on this topic, but they are not relevant here). However, this is inside the for-loop itself:

for(auto t:res){

The for-loop iterates over the vector. Range iteration, internally, uses iterators to iterate over the container. As soon as the first push_back here adds a value to the vector, the next iteration of this for-loop is undefined behavior. Game over.

Upvotes: 3

Related Questions