Вот мой код для генерации набора мощности набора, но он не работает, как ожидалось.
#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;
}
Кто-нибудь может сказать мне, в чем проблема первого кода? Спасибо вам большое!
Когда вы добавляете результат, это делает недействительными итераторы, когда происходит перераспределение, и перераспределение происходит, когда вы превышаете емкость вектора.
for(vector<int> subSet:result){
subSet.push_back(i);
result.push_back(subSet);
}
Если вы зарезервировали достаточно места в векторном результате в начале через reserve ()
функция-член, это должно работать. Я не проверял стандарт, но я почти уверен, что итераторы должны оставаться действительными, поскольку вы не удаляете и не вставляете какие-либо элементы перед конечным итератором, и этот элемент инициализируется в начале цикла.
Таковы векторные гарантии, если я не ошибаюсь. Не то чтобы я поощрял вас писать такой код.
РЕДАКТИРОВАТЬ:
Хорошо, я возьму это обратно. Видимо, конечный итератор признан недействительным.
В первом коде посмотрите на следующий код
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 на основе диапазона