Как получить список всех элементов из «Непересекающихся множеств»
В моей задаче у меня есть куча элементов (Class Element). Скажем, у меня есть 1000 элементов. Эти элементы изначально не связаны, что означает, что они находятся в своих собственных наборах.
Позже мне нужно использовать операцию объединения, чтобы объединить некоторые из этих наборов на основе моего программного потока.
Я планирую использовать библиотеку надстройки disjoint_set (http://www.boost.org/doc/libs/1_57_0/libs/disjoint_sets/disjoint_sets.html)
Мой вопрос заключается в том, как можно перечислить элементы в наборе с учетом представителя набора.
Является ли disjoint_set лучшей структурой данных для такой задачи. Так я должен изучить использование чего-то еще?
Решение
Из вашего описания прозы я не получаю информации о том, что наборы на самом деле образуют какие-либо графики.
Если все, что вы хотите сделать, это связать элементы с набором, я бы предложил
std::map<ElementId, SetId>
(где ElementId может быть просто Element* если вы знаете, указатели остаются в силе).
Если вы также хотите иметь возможность эффективно запрашивать обратное
bimap<Element, bimaps::multiset_of<SetId> >
был бы кандидатом. Увидеть демонстрацию Жить на Колиру¹
#include <boost/range/iterator_range.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/bimap.hpp>
#include <iostream>
using namespace boost;
int main() {
using Element = int; // for simplicity :)
using SetId = int;
using Sets = bimap<Element, bimaps::multiset_of<SetId> >;
Sets sets;
sets.insert({ Element(1), 300 });
sets.insert({ Element(2), 300 });
sets.insert({ Element(3), 400 });
sets.insert({ Element(4), 300 });
// give us set #300
for (auto& e : make_iterator_range(sets.right.equal_range(300)))
std::cout << e.first << " - Element(" << e.second << ")\n";
}
Печать
300 - Element(1)
300 - Element(2)
300 - Element(4)
¹ Колиру кажется внизу. Добавлю позже
Другие решения