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或weighted_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++是否有机制可以选择这两个基类中更接近的一个？

- fledgling Cxx user

---

如果您提供一个最小的工作示例，让人们可以扩展您所要求的功能，我们将会给予+1。通常来说，使Boost Graph能够识别您的结构只需要适应和添加特征即可，但是除非我们看到其中的内容，否则我们无法展示如何实现。 - sehe

PS. 你是在尝试使用还是避免使用BGL？ - sehe

我认为问题已经被合理地阐述了，代码从编码方面解释了一切。无论如何，我试图避免使用BGL——我提到它是因为我曾试图从中学习，但失败得很惨 :）。 - fledgling Cxx user

Answer 1

_{提前说明: 我假设您已经考虑过将基本的edge类中的getWeight()方法设置为虚拟方法(并使默认实现返回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<edge::weight>（boost/TR1）或decltype(edge::weight)（C++0x）来避免硬编码result_type typedefs。这将是真正的归纳。

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

- sehe

---

我对这个解决方案有点困惑，因为你是基于边缘类型进行模板化的。不管怎样，我发现对于我的具体问题，最好的解决方案确实是我在原始帖子中写的，即一个基于返回类型进行模板化并针对不同边缘类型进行重载的函数。 - fledgling Cxx user

因为我不理解你的返回类型模板的目的，所以我假设你想要推断返回类型，这可以使用我的解决方案来实现。我更新了我的答案，展示了如何使用_type_traits_接受任何weighted_edge的派生类。 - sehe

Answer 2

感谢回复，sehe；我已经找到了解决我的问题的最佳方案。那就是编写两个函数，

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的行为区分开来。

- fledgling Cxx user

---

很高兴你找到了一个可行的解决方案，而且还很简单！我想我把要求复杂化了，因为你的“按返回类型模板”实际上并没有做任何事情：它只是一种奇怪的写法来进行强制转换（get_weight<double>(e) 和 (double) get_weight(e) 是完全相同的）。 - sehe

我正在从纯C转向C++，所以这应该更接近于我的通常的(T) e :).模板化T的原因是未加权情况下很可能希望使用整数类型来计算路径成本，因此有能力对其进行模板化而不仅仅在所有地方使用double/float是有意义的。 - fledgling Cxx user