3

我的问题如下。我正在通过编写图形库来学习 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()函数来获取权重；我可以编写一个返回 1 或weight取决于的函数edge_T，但我关心的是当一个从edgeor派生时会发生什么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++ 机制可以从这两个中选择“更接近”的基类？

4

2 回答 2

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<edge::weight>(boost/TR1) 或decltype(edge::weight)(C++0x) 来避免对result_typetypedef 进行硬编码。这将是真正的归纳。

更新 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;
}
于 2011-11-10T08:16:05.903 回答
2

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

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

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

class my_edge : public edge { ... };

my_edge e;

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

于 2011-11-11T03:18:55.123 回答