如何从“不相交集"中获取所有元素的列表.

本文介绍了如何从“不相交集"中获取所有元素的列表.的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

在我的问题中，我有一堆元素(类元素).假设我有1000个元素.这些元素最初是未关联的，这意味着它们在自己的集合中.

In my problem, I have a bunch of Elements (Class Element). Say I have 1000 Elements. These Elements are initially un-associated which means they are in their own sets.

稍后，我需要使用并集操作根据我的程序流来合并其中的一些集合.我计划使用Boost库的disjoint_set( www.boost/doc/libs/1_57_0/libs/disjoint_sets/disjoint_sets.html )

Later I need to use the union operation to merge some of these sets based of my program flow. I plan to use the boost library's disjoint_set (www.boost/doc/libs/1_57_0/libs/disjoint_sets/disjoint_sets.html)

我的问题是，在给定集合代表的情况下，如何列出集合中的元素.

My question is how is it possible to list the Elements in a set given the representative of the set.

为此类任务设置了最佳的数据结构.那我应该考虑使用其他东西吗?

Is disjoint_set the best data structure for such a task. So should I look into using something else?

推荐答案

从您的散文描述中，我不知道这些集合实际上会形成任何图形.

From your prose description, I get no information that the sets would actually form any graphs.

如果您要做的只是将元素与集合相关联，我建议

If all you want to do is associate Elements with a set, I'd suggest

std::map<ElementId, SetId>

(如果您知道指针仍然有效，则 ElementId 可以简单地是 Element * ).

(where ElementId could simply be Element* if you know the pointers stay valid).

如果您还希望能够高效地查询逆数

If you also want to be able to query the inverse efficiently

bimap<Element, bimaps::multiset_of<SetId> >

将是候选人.观看演示 Coliru现场直播 ¹

would be a candidate. See a demonstration Live On Coliru¹

#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)

¹Coliru似乎情绪低落.以后会添加

¹ Coliru seems down. Will add later