0

在我的问题中，我有一堆元素（类元素）。假设我有 1000 个元素。这些元素最初是不相关的，这意味着它们在自己的集合中。

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

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

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

4

1 回答 1

0

从您的散文描述中，我没有得到任何信息表明这些集合实际上会形成任何图表。

如果您只想将元素与集合相关联，我建议

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-08T09:54:24.043 回答