2

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

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

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

4

2 回答 2

3

在第一个代码中查看以下代码

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

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

基于范围的 for 循环begin(container)在和之间进行迭代end(container)，这是通过依赖于参数的查找找到的（不执行非 ADL 查找）。

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

有关更多详细信息，请阅读6.5.4 基于范围的 for 语句 [stmt.ranged]

相关文章：在基于范围的 for 循环内从容器中擦除元素

于 2015-01-05T04:53:26.437 回答
1

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

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

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

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

编辑：

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

如果向量有足够的空间（通过保留创建），std::vector::insert() 是否会使迭代器无效？

于 2015-01-05T05:38:14.403 回答