C++和通用图距离算法

Question

我的问题如下。我正在通过编写图形库来学习 C++，并希望尽可能多地利用通用编程技术；因此，通过“使用 BOOST”回答我的问题对我没有帮助；事实上，我尝试通过 BOOST 的代码来寻找我的问题的答案，但这是一次令人羞愧的经历，因为我什至无法弄清楚某些函数是在哪里定义的；以我的水平来说，C++ 的水平太高了。

也就是说，我的库是通过以下方式进行模板化的：

class edge { ... };

template <class edge_T>
class node { ... };

template <class edge_T, class node_T>
class graph { ... };

并且我通过使用从边或节点派生的类来创建更复杂的图，因此加权边类将很简单

template <class T>
class weighted_edge : public edge {
   public:
     T weight;

   ...
};

现在的问题是我想在此结构上实现一个算法计算两个顶点之间的最短距离。我可以轻松地编写其中两个，一个用于加权边缘，一个用于未加权，但变化很小：一个将访问 weighted_edge （或派生类）的成员字段，另一个将假设单一权重。

有没有办法做到这一点，以便我可以只用一段代码来处理这两种情况？

一种解决方案是使用成员函数 edge::get_weight() ，该函数将返回权重（或在未加权的情况下返回“1”），但这将迫使我为边类使用特定的权重类型这是未加权的，所以闻起来很有趣。我的意思是，模板需要

template <class T>
class edge {
   public:
     ...
     virtual T get_weight(void) { return T(1); } 
}

不完全用户友好，或者至少令人困惑，因为您不希望涉及任何权重。

BGL使用get()函数来获取权重；我可以编写一个根据 edge_T 返回 1 或 weight 的函数，但我担心的是当从 edge 或 派生时会发生什么代码>加权边缘？如果有人写道：

template <class T>
inline T get_weight(edge & e) { return T(1); }

template <class T>
inline T get_weight(weighted_edge & e) { return T(e.weight); }

如果传递一个派生类会发生什么？是否有一种 C++ 机制可以从这两个基类中选择“更接近”的基类？

Answer 1

谢谢您的回复，呵呵；我找到了解决我的问题的最佳解决方案。就是编写两个函数，

template <class T>
inline T get_weight(edge const & e)
{ return T(1); }

template <class T>
inline T get_weight(weighted_edge const & e)
{ return T(e.weight); }

这样，当我编写最短路径算法时，它可以要求这两个类或任何派生类的权重，这对我来说很重要，因为我可能稍后想要向基本边缘类添加属性（如颜色等）。因此，当我编写

class my_edge : public edge { ... };

my_edge e;

和使用 get_weight(e) 时，我将获得未加权边缘的行为。边缘类型上的模板在这里没有帮助，因为它无法在从 edge 派生的所有类上使用规定的行为，并将其与 weighted_edge 的行为区分开来。

Answer 2

_{前面：我假设您已经考虑过将 getWeight() 设为基 edge 类中的虚拟方法（并将默认设置为执行返回1)。我知道这种方法的灵活性有限，只是想检查一下。}

---

因为我不明白您的返回类型模板的目的，所以我假设您想要推断返回类型，您可以使用我的解决方案来做到这一点。

让 get_weight 选择正确实现的常用方法是使用模板特化（请注意，您显示的代码通过返回类型进行特化；根据定义，编译器永远不会推导出这种类型）：

namespace detail
{
    template <class Edge> struct get_weight_impl;

    template <> struct get_weight_impl<edge>
    {
        typedef typename result_type int;

        result_type operator()(const edge& e) const
            { return result_type(1); }
    };

    template <> struct get_weight_impl<weighted_edge>
    {
        typedef typename result_type int;

        result_type operator()(const weighted_edge& e) const
            { return result_type(e.weight); }
    };
}

更新 1 您可以使用 result_of (boost/TR1) 或 decltype(edge::weight) ( C++0x）以避免对 result_type typedef 进行硬编码。这将是真正的归纳法。

更新 2 要获得 weighted_edge const& 到“服务”派生边缘类型的重载，还要应用一点 type_trait 魔法：

>http://ideone.com/AqmsL

struct edge {};
struct weighted_edge : edge          { virtual double get_weight() const { return 3.14; } };
struct derived_edge  : weighted_edge { virtual double get_weight() const { return 42; } };

template <typename E, bool is_weighted>
struct edge_weight_impl;

template <typename E>
struct edge_weight_impl<E, false>
{
    typedef int result_type;
    int operator()(const E& e) const { return 1; }
};

template <typename E>
struct edge_weight_impl<E, true>
{
    // typedef decltype(E().weight()) result_type; // c++0x
    typedef double result_type;

    result_type operator()(const E& e) const 
    { 
        return e.get_weight();
    }
};

template <typename E>
    typename edge_weight_impl<E, boost::is_base_of<weighted_edge, E>::value>::result_type 
        get_weight(const E& e)
{
    return edge_weight_impl<E, boost::is_base_of<weighted_edge, E>::value>()(e);
}

int main()
{
    edge e;
    weighted_edge we;
    derived_edge de;

    std::cout << "--- static polymorphism" << std::endl;
    std::cout << "edge:\t"          << get_weight(e) << std::endl;
    std::cout << "weighted_edge:\t" << get_weight(we) << std::endl;
    std::cout << "derived_edge:\t"  << get_weight(de) << std::endl;

    // use some additional enable_if to get rid of this:
    std::cout << "bogus:\t"         << get_weight("bogus") << std::endl;

    std::cout << "\n--- runtime polymorphism" << std::endl;

    edge* ep = &e;
    std::cout << "edge:\t"          << get_weight(*ep) << std::endl;
    weighted_edge* wep = &we;
    std::cout << "weighted_edge:\t" << get_weight(*wep) << std::endl;
    wep = &de;
    std::cout << "bogus:\t"         << get_weight(*wep) << std::endl;
}