foreach — улучшена область действия вложенных циклов для переполнения стека

Вот мой код для генерации набора мощности набора, но он не работает, как ожидалось.

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

Кто-нибудь может сказать мне, в чем проблема первого кода? Спасибо вам большое!

2

Решение

Когда вы добавляете результат, это делает недействительными итераторы, когда происходит перераспределение, и перераспределение происходит, когда вы превышаете емкость вектора.

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

Если вы зарезервировали достаточно места в векторном результате в начале через reserve () функция-член, это должно работать. Я не проверял стандарт, но я почти уверен, что итераторы должны оставаться действительными, поскольку вы не удаляете и не вставляете какие-либо элементы перед конечным итератором, и этот элемент инициализируется в начале цикла.

Таковы векторные гарантии, если я не ошибаюсь. Не то чтобы я поощрял вас писать такой код.

РЕДАКТИРОВАТЬ:

Хорошо, я возьму это обратно. Видимо, конечный итератор признан недействительным.

Делает ли std :: vector :: insert () недействительными итераторы, если в векторе достаточно места (созданного с помощью резерва)?

1

Другие решения

В первом коде посмотрите на следующий код

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

Вы меняете result на котором вы итерируете. Это не будет хорошо, и может даже привести к бесконечным циклам, сбоям программы и т. Д.

Диапазон на основе цикла итерация между begin(container) а также end(container), которые находятся через поиск, зависящий от аргументов (поиск без ADL не выполняется).

Если вы измените контейнер в loop_statementпредыдущие (используемые внутри) итераторы недопустимы, что приводит к неопределенному поведению.

Для более подробной информации, пожалуйста, прочитайте 6.5.4 На основе диапазона для оператора [stmt.ranged]


Связанный пост: Стирание элемента из контейнера внутри цикла for на основе диапазона

3

По вопросам рекламы [email protected]