c++ - Working with a secondary datastructure//数据结构的建议

Question

我正在尝试基于已经存在的数据结构(我无法修改并且它本身不是图形)构建图形数据结构。我想我对如何构建与图形本身有关的大部分结构有所了解，但现在我必须引用原始数据结构来获得一个小的“比较”功能，并且很难对其进行建模妥妥的……

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

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) 对数据使用 void 指针，有一些变量来存储类型，然后将 void 指针转换为相应的类型
-> 可能会工作，但看起来真的很危险(类型安全？)而且真的很丑(如果你想在其他数据上使用它，基本上没有图结构的可重用性)。看起来有点像蛮力方法。

想法 2) 创建一个提供一些“isCompatible(data)”函数的抽象数据类，并分别为 A 和 B 提供从抽象类继承并覆盖该函数的包装类。在覆盖的函数中，可以使用 dynamic_cast 然后比较对象。
-> 看起来仍然不是好的设计，但应该也能工作？

想法 3) 让模板起作用？这是我第一次使用 C++，所以我在正确地解决这个问题时遇到了一些问题。我认为类似下面的内容应该可以用于比较:

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

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

当然，我也愿意接受任何其他建议。

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

Answer 1

如果您的数据是 A 或 B，这两种类型没有任何共同点，那么听起来您想要的是一个变体 数据类型。 C++ 标准库还没有，但你可以使用 Boost's :

boost::variant<A, B> data;

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

使用上述变体，您可以使用 binary visitation 进行比较:

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
    }    
};