C ++中嵌套增强for循环的作用域

Question

这是我生成集合的幂集的代码，但它没有按预期工作。

#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;
}

此代码打印：

1
2
2
3
3
3
3

稍微改一下就可以了。这是我的工作代码：

#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;
}

谁能告诉我第一个代码的问题是什么？太感谢了！

Answer 1

在第一个代码中看下面的代码

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

您正在更改正在迭代的 result。这不会有好结果，甚至可能导致无限循环、程序崩溃等。

Range-based for loop 在 begin(container) 和 end(container) 之间迭代，它们是通过参数相关查找找到的（不执行非 ADL 查找）。

如果您更改 loop_statement 中的容器，之前的（内部使用的）迭代器无效，这会导致未定义的行为。

详情请阅读6.5.4 基于范围的for语句[stmt.ranged]

相关post：Erasing an element from a container while inside a range-based for loop

Answer 2

当您附加到结果时，这将使迭代器在重新分配时无效，并且在您超过向量容量时重新分配。

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

如果通过 reserve () 成员函数在开头的矢量结果中保留足够的 space，它应该可以工作。我没有检查标准，但我很确定迭代器应该保持有效，因为您没有在结束迭代器之前删除或插入任何元素，并且该迭代器是在循环开始时初始化的。

如果我没记错的话，这就是矢量保证。并不是说我鼓励你这样写代码。

编辑：

好的，我收回。显然结束迭代器是无效的。

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

C ++中嵌套增强for循环的作用域

Scoping of nested enhanced for loops in c++

c++

foreach

powerset