相关疑难解决方法(0)

我本来期望这样一个有用的数据结构被包含在内,C++ Standard Library但我似乎无法找到它.

假设您有许多元素,并且需要跟踪它们之间的等价关系.如果元素A等价于元素B,则它等效于所有其他元素B等价.

我正在寻找一种有效的数据结构来编码这些信息.应该可以通过与现有元素的等价来动态添加新元素,并且从该信息中可以有效地计算新元素等效的所有元素.

例如,考虑以下元素[0,1,2,3,4]的等价集:

0 = 1 = 2
3 = 4

等号表示等价的.现在我们添加一个新元素5

0 = 1 = 2
3 = 4 
5

并强制执行等价5=3,数据结构变为

0 = 1 = 2
3 = 4 = 5

由此,人们应该能够有效地迭代任何元素的等价集.对于5,这个集合将是[3,4,5].

Boost已经提供了一个方便的数据结构disjoint_sets,似乎满足了我的大多数要求.考虑这个简单的程序,说明如何实现上面的例子:

#include <cstdio>
#include <vector>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/unordered/unordered_set.hpp>

/*
    Equivalence relations
    0 = 1 = 2
    3 = 4
 */

int main(int , char* [])
{
    typedef std::vector<int> VecInt;
    typedef boost::unordered_set<int> SetInt;

    VecInt rank (100);
    VecInt parent (100);
    boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]); …

我必须实现一个数组结构,该结构将等价类的元素分组.

API:

interface Grouper<T>{
  void same(T l, T r);
  Set<EquivalenceClass<T>> equivalenceClasses();
}

interface EquivalenceClass<T>{
    Set<T> members();
}

例如,分组行为如下:

Grouper g;
g.same(a, b);
g.equivalenceClasses() -> [[a,b]]

g.same(b, a);
g.equivalenceClasses() -> [[a,b]]

g.same(b, c);
g.equivalenceClasses() -> [[a,b,c]]

g.same(d, e);
g.equivalenceClasses() -> [[a,b,c], [d,e]]

g.same(c, d);
g.equivalenceClasses() -> [[a,b,c,d]]

我正在寻找一个可以达到约1000万条目的实现.它应该被优化以填充它并获得一次等价类.