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
– lxw, Commented Jan 5, 2015 at 4:52
Note that the size of powerset is exponential in the size of original set. — Cheers and hth. - Alf
– Cheers and hth. - Alf, Commented Jan 5, 2015 at 5:17

Community · Accepted Answer · 2017-05-23 12:20:34Z

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

But, in that case, it will never end, right? But, it ends up printing something wrong.
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.

Community · Accepted Answer · 2017-05-23 10:26:09Z

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

Collectives™ on Stack Overflow

Scoping of nested enhanced for loops in c++

2 Answers 2

3 Comments

Comments

Linked

Hot Network Questions