C和通用图距离算法-Java 学习之路

我的问题如下 . 我正在通过编写图形库来学习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 ，但我担心的是当一个派生自 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机制可以从这两个中选择“更接近”的基类？

2 回答

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); }
```
这样，当我写一个最短路径算法时，它可以要求这两个类中的任何一个的权重或 any derived ones ，这对我来说很重要，因为我可能想稍后在基本边类上添加属性（比如颜色等）） . 因此，当我写作
```
class my_edge : public edge { ... };

my_edge e;
```
并使用 get_weight(e) 我将获得未加权边缘的行为 . 边缘类型的模板化在这里没有用，因为它无法在从 edge 下降的所有类上使用规定的行为，并将其与 weighted_edge 的行为区分开来 .
回复于 2024-06-02T15:22:50+08:00

预先：我假设您已经考虑过将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); }
    };
}

Update 1您可以使用result_of <edge :: weight>（boost / TR1）或decltype（edge :: weight）（C 0x）来避免对result_type typedef进行硬编码 . 这将是真正的归纳 . 更新2要获得weighted_edge const和'service'派生边类型的重载，还要应用一些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;
}

回复于 2024-06-02T15:22:50+08:00

C和通用图距离算法

2 回答

相关问题