如何获得'Disjoint Sets'中所有元素的列表

在我的问题中，我有一堆元素（类元素）。假设我有1000个元素。这些元素最初是不相关的，这意味着它们在自己的集合中。如何获得'Disjoint Sets'中所有元素的列表

后来我需要使用联合操作来合并一些基于我的程序流程的这些集合。我打算使用增强库的disjoint_set（http://www.boost.org/doc/libs/1_57_0/libs/disjoint_sets/disjoint_sets.html）

我的问题是如何列出给定代表该集合的元素。

Disjoint_set是此类任务的最佳数据结构。那么我应该考虑使用别的东西吗？

来源

2014-11-08 mkuse

在看了（新的disjoint_set_ *类）之后，我不认为他们提供了迭代集合的成员。它们的作用就像从元素到集合代表的单向映射。如果它可以帮助你：http://paste.ubuntu.com/8881626/ – sehe 2014-11-08 10:21:45

从你的散文描述，我没有得到任何信息，该集合实际上会形成任何图形。

如果你想要做的是联营元素与一组，我建议

std::map<ElementId, SetId>

（其中ElementId可能仅仅是Element*如果你知道指针保持有效）。

如果你也希望能够查询逆有效

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

将是一个候选人。看到一个示范 ~~住在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似乎下来。稍后再添加

来源

2014-11-08 09:54:24 sehe

如何获得'Disjoint Sets'中所有元素的列表

回答

相关问题