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!

Answer 1

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)?