Неожиданный вывод: вектор вектора (набор мощности) - PullRequest
Новая
       33

Неожиданный вывод: вектор вектора (набор мощности)

0 голосов
/ 25 мая 2018

Я пытаюсь написать решение одной из проблем CTCI - написать метод для возврата всех подмножеств набора.Тем не менее, я не получаю ожидаемый результат.Кажется, глупая ошибка, но я не могу ее обнаружить.Ниже приведен код: 

template <typename T>
std::vector<std::vector<T>> power_set( const std::vector<T>& input ) {
    std::vector<std::vector<T>> output;
    for ( const auto& element : input ) {
        power_set_helper( element, output );
    }
    return output;
}

template <typename T>
void power_set_helper( const T& element, std::vector<std::vector<T>>& output ) {
    for ( auto set_element : output ) {
        set_element.push_back( element );
        output.push_back( set_element );
    }
    output.emplace_back( std::initializer_list<T>{element} );
}

ДЕЛО ТЕСТА: 

std::vector<int> input                       = {1, 2, 3};
std::vector<std::vector<int>> expected_ouput = {{1}, {1, 2}, {2}, {1, 3}, {1, 2, 3}, {2, 3}, {3}};

Но вывод, который я получаю: {{1}, {1, 2}, {2}, {1, 3}, {1, 2, 3}, {3}, {3}}

Не могли бы вы помочь определить ошибку и сообщить о ее причине?

1 Ответ

0 голосов
/ 25 мая 2018 
for ( auto set_element : output ) {
    // ...
    output.push_back( set_element );

Здесь вы изменяете вектор, по которому вы выполняете итерацию, что приводит к UB

Возможное решение - сделать копию 

for ( auto set_element : std::vector<std::vector<T>>(output) ) {
    // ...
    output.push_back( set_element );
...