Scoping of nested enhanced for loops in c++

Question

Here is my code to generate the power set of a set, but it doesn't work as expected.

#include <string>
#include <stdio.h>
#include <vector>

using namespace std;

vector<vector<int>> powerSet(vector<int> set){
    vector<vector<int>> result;
    vector<int> emptySet;
    result.push_back(emptySet);

    for(int i: set){
        for(vector<int> subSet:result){
            subSet.push_back(i);
            result.push_back(subSet);
        }
    }

    return result;
}

int main(){
    vector<int> a = {1, 2, 3};
    vector<vector<int>> r = powerSet(a);

    for(vector<int> v: r){
        for(int n : v){
            printf("%d ", n);
        }
        printf("\n");
    }
    return 0;
}

This code prints:

1
2
2
3
3
3
3

After I change it a little bit, it works. Here is my working code:

#include <string>
#include <stdio.h>
#include <vector>

using namespace std;

vector<vector<int>> powerSet(vector<int> set){
    vector<vector<int>> result;
    vector<int> emptySet;
    result.push_back(emptySet);

    for(int i: set){
        vector<vector<int>> moreSets; // here is the changes
        for (vector<int> subSet: result){
            subSet.push_back(i); 
            moreSets.push_back(subSet); // here is the changes
        }
        result.insert(result.end(), moreSets.begin(), moreSets.end()); // here is the changes        }

    return result;
}

int main(){
    vector<int> a = {1, 2, 3};
    vector<vector<int>> r = powerSet(a);

    for(vector<int> v: r){
        for(int n : v){
            printf("%d ", n);
        }
        printf("\n");
    }
    return 0;
}

Can anybody tell my what is the problem of the first code? Thank you so much!

I think it must be the scoping problem of for loops, so I changed it, but I am not quit clear that why the first code doesn't work. — lxw, Jan 05 '15 at 04:52
Note that the size of powerset is exponential in the size of original set. — Cheers and hth. - Alf, Jan 05 '15 at 05:17

score 3 · Answer 1 · edited May 23 '17 at 12:20

3

In first code look at the following code

for(vector<int> subSet:result){
    subSet.push_back(i);
    result.push_back(subSet);
}

You are changing the result on which you are iterating. This won't end up good and may even cause infinite loops, program crash etc.

Range-based for loop iterate between begin(container) and end(container), which are found via argument-dependent lookup (non-ADL lookup is not performed).

If you change the container in the loop_statement, previous (internally used) iterators are invalid which cause undefined behavior.

For more details please read 6.5.4 The range-based for statement [stmt.ranged]

Related post: Erasing an element from a container while inside a range-based for loop

edited May 23 '17 at 12:20

Community

1
1

answered Jan 05 '15 at 04:53

Mohit Jain

30,259
8
73
100

But, in that case, it will never end, right? But, it ends up printing something wrong. – lxw Jan 05 '15 at 04:56
1

If you modify the container you are iterating on, it **may** never end or **may** give incorrect result or **may** crash. Moral: Don't modify the container you are iterating upon. – Mohit Jain Jan 05 '15 at 04:58
Ok, it caused an undefined behavior in this case, right? – lxw Jan 05 '15 at 05:02

score 1 · Accepted Answer · edited May 23 '17 at 10:26

When you are appending to the result, this will invalidate iterators when the reallocation occurs and reallocation occurs when you exceed vector capacity.

        for(vector<int> subSet:result){
            subSet.push_back(i);
            result.push_back(subSet);
        }

If you reserve enough space in the vector result at the beginning via reserve () member function, it should work. I didn't check the standard, but I'm pretty sure that the iterators should remain valid since you are not removing or inserting any elements before the end iterator and that one is initialized at the beginning of the loop.

Such are vector guarantees if I'm not mistaken. Not that I encourage you to write code like this.

EDIT:

Ok, I'll take it back. Apparently the end iterator is invalidated.

Does std::vector::insert() invalidate iterators if the vector has enough room (created through reserve)?

Scoping of nested enhanced for loops in c++

2 Answers2