在 C++ 中实现等价关系（使用 boost::disjoint_sets）

Question

假设您有很多元素，并且需要跟踪它们之间的等价关系。如果元素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]);
    SetInt elements;
    for (int i=0; i<5; ++i) {
        ds.make_set(i);
        elements.insert(i);
    }

    ds.union_set(0,1);
    ds.union_set(1,2);
    ds.union_set(3,4);

    printf("Number of sets:\n\t%d\n", (int)ds.count_sets(elements.begin(), elements.end()));

    // normalize set so that parent is always the smallest number
    ds.normalize_sets(elements.begin(), elements.end());
    for (SetInt::const_iterator i = elements.begin(); i != elements.end(); ++i) {
        printf("%d %d\n", *i, ds.find_set(*i));
    }

    return 0;
}

如上所示，可以有效地添加元素，并动态扩展不相交的集合。如何有效地迭代单个不相交集合的元素，而不必迭代所有元素？

Answer 1

您很可能无法做到这一点，disjoint_sets 不支持仅对一组进行迭代。无论如何，底层数据结构和算法都无法有效地完成此操作，即即使 disjoint_sets 内置支持仅对一组进行迭代，那也会与迭代一样慢所有集合，并过滤掉错误的集合。

Answer 2

要么我遗漏了一些东西，要么你忘了提及一些东西，或者你可能想得太多了；）

令人高兴的是，对等不是平等。对于 A & B 等效；他们只需要共享具有相同值的属性。这可以是标量甚至向量。无论如何，我认为您发布的要求可以通过使用 std 来实现： :multiset ，它是 std::multiset::equal_range() 成员函数。

//////////////////////////////////////
class E
{
    //could be a GUID or something instead but the time complexity of
    //std::multiset::equal_range with a simple int comparison should be logarithmic
    static size_t _faucet;

public:

    struct LessThan
    {
        bool operator()(const E* l, const E* r) const { return (l->eqValue() < r->eqValue()); }
    };

    using EL=std::vector<const E*>;
    using ES=std::multiset<const E*, E::LessThan>;
    using ER=std::pair<ES::iterator, ES::iterator>;


    static size_t NewValue() { return ++_faucet; }

    ~E() { eqRemove(); }
    E(size_t val) : _eqValue(val) {}
    E(std::string name) : Name(name), _eqValue(NewValue()) { E::Elementals.insert(this); }


    //not rly a great idea to use operator=() for this. demo only..
    const E& operator=(const class E& other) { eqValue(other);  return *this; }

    //overriddable default equivalence interface
    virtual size_t eqValue() const  { return _eqValue; };

    //clearly it matters how mutable you need your equivalence relationships to be,,
    //in this implementation, if an element's equivalence relation changes then
    //the element is going to be erased and re-inserted.
    virtual void   eqValue(const class E& other)
    {
        if (_eqValue == other._eqValue) return;

        eqRemove();
        _eqValue=other._eqValue;
        E::Elementals.insert(this);
    };

    ES::iterator eqRemove() 
    {
        auto range=E::Elementals.equal_range(this);
        //worst-case complexity should be aprox linear over the range
        for (auto it=range.first; it!=range.second; it++)
            if (this == (*it))
                return E::Elementals.erase(it);            
        return E::Elementals.end();
    }

    std::string Name; //some other attribute unique to the instance
    static ES   Elementals; //canonical set of elements with equivalence relations

protected:
    size_t _eqValue=0;

};

size_t E::_faucet=0;
E::ES  E::Elementals{};


//////////////////////////////////////
//random specialisation providing
//dynamic class-level equivalence
class StarFish : public E
{

public:

    static void EqAssign(const class E& other)
    {
        if (StarFish::_id == other.eqValue()) return;

        E el(StarFish::_id);
        auto range=E::Elementals.equal_range(&el);

        StarFish::_id=other.eqValue();

        E::EL insertList(range.first, range.second);
        E::Elementals.erase(range.first, range.second);
        E::Elementals.insert(insertList.begin(), insertList.end());
    }


    StarFish() : E("starfish") {}

    //base-class overrides
    virtual size_t eqValue() const { return StarFish::_id; };

protected: //equivalence is a the class level
    virtual void eqValue(const class E& other) { assert(0); }

private:
    static size_t _id;
};

size_t StarFish::_id=E::NewValue();


//////////////////////////////////////
void eqPrint(const E& e)
{
    std::cout << std::endl << "elementals equivalent to " << e.Name << ": ";
    auto range=E::Elementals.equal_range(&e);
    for (auto it=range.first; it!=range.second; it++)
        std::cout << (*it)->Name << " ";
    std::cout << std::endl << std::endl;
}

//////////////////////////////////////
void eqPrint()
{
    for (auto it=E::Elementals.begin(); it!=E::Elementals.end(); it++)
        std::cout << (*it)->Name << ": " << (*it)->eqValue() << "  ";
    std::cout << std::endl << std::endl;
}

//////////////////////////////////////
int main()
{
    E e0{"zero"}, e1{"one"}, e2{"two"}, e3{"three"}, e4{"four"}, e5{"five"};

    //per the OP
    e0=e1=e2;
    e3=e4;
    e5=e3;

    eqPrint(e0);
    eqPrint(e3);
    eqPrint(e5);
    eqPrint();

    StarFish::EqAssign(e3);
    StarFish starfish1, starfish2;
    starfish1.Name="fred";

    eqPrint(e3);

    //re-assignment
    StarFish::EqAssign(e0);
    e3=e0;

    {   //out of scope removal
        E e6{"six"};
        e6=e4;
        eqPrint(e4);
    }

    eqPrint(e5);
    eqPrint(e0);
    eqPrint();

    return 0;
}

在线演示

注意：C++类继承还提供了另一种不可变等价非常有用;)