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

感谢回复，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 的行为区分开来.