使用数据结构的辅助数据结构//通知

Question

我正在尝试基于一个已经存在的Datastructure构建一个(我不能修改它，它本身不是一个图形)。我想我有点掌握了如何构建有关图本身的大多数结构，但现在我不得不参考原始数据结构，以获得一个小小的“比较”函数，并且很难正确地建模.

我的顶点表示原始数据结构的两个不同的类A和B，它们有不同的成员变量，没有共同的祖先。对于一个算法，我必须检查两个顶点是否兼容。规则是:A-顶点和B-顶点总是不兼容的，但是如果两个顶点代表相同的类型，我必须检查相应类型的一些细节。所以基本想法大致是这样的：

bool isCompatible(const Vertex& other){
  // if this->data is of other type than other->data
  //    return false;
  // else return compareFunction(this->data, other->data)
       // where maybe one could overload that compare-function 
       // or make a template out of it
}

但我真的不知道如何存储对数据的引用，而不会让它变得非常丑陋。

想法1)对数据使用一个空指针，有一些变量来存储类型，然后将空指针转换成相应的类型。

->可能会起作用，但看起来真的很危险(类型安全？)而且非常难看(如果您想在其他数据上使用它，基本上没有图形结构的可重用性)。看上去有点像蛮力法。

想法2)创建一个抽象数据类，它提供了一些“isCompatible(数据)”函数，并分别为A和B提供了包装器类，这些类继承了抽象类并覆盖了该函数。在重写的函数中，可以使用dynamic_cast，然后比较对象。

->看起来仍然不是很好的设计，但也应该工作吗？

想法3)使模板工作吗？这是我第一次使用C++，所以我在正确地处理这个问题上遇到了一些问题。我认为这样的比较应该是可行的：

template<typename T1, typename T2>
bool compare(T1 object1, T2 object2){
    return false;
}

然后有(A，A)和(B，B)的实例来覆盖这一点。对我来说，这似乎是比较本身的方法。但我不知道如何在不丢失Type的情况下管理从顶点到对象的引用。有什么建议吗？

当然，我也愿意听取任何其他建议。

编辑:如果相关的话，我使用的是C++11。

Answer 1

如果您的数据是A或B，其中这两种类型没有任何共同之处，那么听起来您想要的是一种变体数据类型。C++标准库还没有，但您可以使用波普氏

boost::variant<A, B> data;

变体为您提供类型安全性( void*不提供)，并且不要求您在这两种类型之间有一个共同的祖先(显然这两种类型在概念上无关)。

使用上述变体，您可以使用二进制访问实现您的比较

bool isCompatible(const Vertex& other) {
    boost::apply_visitor(is_compatible(), data, other.data);
}

通过以下方式：

class is_compatible
    : public boost::static_visitor<bool>
{
public:

    template <typename T, typename U>
    bool operator()( const T &, const U & ) const
    {
        return false; // cannot compare different types
    }

    bool operator()( const A& lhs, const A& rhs ) const
    {
        // whatever A-specific comparison
    }

    bool operator()( const B& lhs, const B& rhs ) const
    {
        // whatever B-specific comparison
    }    
};