Рекурсия в C++

[george66]

Дан список людей (на самом деле некоторых объектов, в списке указатели на них). Для каждого человека есть список его детей (тоже список указателей). Списки детей могут перекрываться (у разных людей бывают общие дети). Программа должна по данному человеку выдавать список всех его потомков (его самого, детей, внуков, правнуков и т.д.) без повторений. В функциональном языке я бы сделал так: функция кладёт в список самого человека, а потом рекурсивно применяется ко всем его детям. Получается список с повторами, повторы потом удаляем. Можно сразу удалять повторы, определив функцию с двумя параметрами (человек и список людей), она перечисляет потомков этого человека, не входящих в этот список, определение рекурсивное. Как это правильно сделать на C++?

[slavav]

Создайте два контейнера: grey, black. Контейнеры хранят людей без повторений.

Container grey(start_list_of_people);
Container black;
while (!grey.empty()) {
    Man man = grey.remove_some();
    if (!black.contains(man)) {
        black.put(man);
        grey.put(man.children());
    }
}
return black;

[aitap]

george66 в сообщении #1478880 писал(а):

Программа должна по данному человеку выдавать список всех его потомков (его самого, детей, внуков, правнуков и т.д.) без повторений.

Если используете C++ $\ge 11$ и можете задать size_t std::hash<Person>::operator() (например, можете гарантировать, что два Person* отличаются тогда и только тогда, когда отличаются указатели, или можете гарантировать уникальность имени, от которого можно взять std::hash<std::string>()), то детей можно сложить в стандартный std::unordered_set<Person>.

Хотя стоп. Если каждый человек уникально определяется указателем Person*, то достаточно собрать множество указателей std::unordered_set<Person*>, поскольку для любых указателей std::hash уже определён.

[Утундрий]

А почему рекурсия? Просто обход расширяющегося списка.

[george66]

Спасибо. Это спрашивалось в связи с этой темой
topic142136.html
но там такой забил фонтан идей, что всё изменилось.