我正在编写一个Graph类,我想为同一类提供多种类型的图。更具体地说,我想考虑有向或无向图,以及顶点(和边)具有值的可能性。
现在,我的班级看起来像这样。
template<typename VertexValue = void, typename EdgeValue = void, bool directed = false>
class Graph {
public:
struct Vertex;
using Edge = Vertex::Edge;
Graph() = default;
//void addVertex(const VertexValue& vertex);
private:
std::vector<Vertex> m_vertices;
};
为方便起见,我将跳过与边缘实现相关的任何内容。
我现在想做的是"专门化"顶点类以提供 - 或不提供 - 一个值,以及取决于图形是否定向的不同方法。我希望能够做如下事情(注意:顶点方法仅用于说明目的,顶点的有向和非定向版本具有不同的方法)。
template<typename VertexValue = void, bool directed = false>
class Graph {
public:
struct Vertex;
private:
std::vector<Vertex> m_vertices;
};
// Directed, with value
template<typename VertexValue, bool directed>
struct Graph<VertexValue, directed>::Vertex {
using ValueType = VertexValue;
EdgeIterator inEdges();
EdgeIterator outEdges();
ValueType value;
};
// Directed, without value
template<bool directed>
struct Graph<void, directed>::Vertex {
using ValueType = void;
EdgeIterator inEdges();
EdgeIterator outEdges();
};
// Undirected, with value
template<typename VertexValue>
struct Graph<VertexValue, false>::Vertex {
using ValueType = VertexValue;
EdgeIterator edges();
ValueType value;
};
// Undirected, without value
template<>
struct Graph<void, false>::Vertex {
using ValueType = void;
EdgeIterator edges();
};
不幸的是,我必须专门化整个 Graph 类才能做到这一点。所以我尝试了其他东西:将 Vertex 类作为模板,并转发外部模板参数。
template<typename VertexValue = void, bool directed = false>
class Graph {
public:
template<typename Value, bool, typename dummy = void>
struct Vertex;
private:
std::vector<Vertex<VertexValue, directed>> m_vertices;
};
// Directed, with value
template<typename VertexValue, bool directed>
template<typename Value, bool, typename dummy>
struct Graph<VertexValue, directed>::Vertex {
using ValueType = Value;
EdgeIterator inEdges();
EdgeIterator outEdges();
ValueType value;
};
// Directed, without value
template<typename VertexValue, bool directed>
template<bool directed_, typename dummy>
struct Graph<VertexValue, directed>::Vertex<void, directed_, dummy> {
using ValueType = void;
EdgeIterator inEdges();
EdgeIterator outEdges();
};
// Undirected, with value
template<typename VertexValue, bool directed>
template<typename Value, typename dummy>
struct Graph<VertexValue, directed>::Vertex<Value, false, dummy> {
using ValueType = Value;
EdgeIterator edges();
ValueType value;
};
// Undirected, without value
template<typename VertexValue, bool directed>
template<typename dummy>
struct Graph<VertexValue, directed>::Vertex<void, false, dummy> {
using ValueType = void;
EdgeIterator edges();
};
这将起作用;但是,我不喜欢转发模板参数的想法,并且它还引入了一个负担,即虚拟模板参数。我还考虑过在 Graph 类之外定义顶点类,如下所示:
template<typename ValueType, bool directed>
class GraphVertex {
EdgeIterator inEdges();
EdgeIterator outEdges();
ValueType value;
};
// Specializations...
template<typename Vertex = GraphVertex<void, false>>
class Graph {
public:
// ...
private:
std::vector<Vertex> m_vertices;
};
。甚至像那样:
template<typename ValueType, bool directed>
class GraphVertex {
EdgeIterator inEdges();
EdgeIterator outEdges();
ValueType value;
};
// Specializations...
template<typename VertexValue = void, bool directed = false>
class Graph {
public:
// ...
private:
std::vector<GraphVertex<VertexValue, directed>> m_vertices;
};
。但我更喜欢嵌套类的想法,其中顶点类实际上是 Graph 类的属性。另外,即使这个解决方案,在三个中,仍然有我的偏好,我找不到"GraphVertex"的任何其他名称。这让我很困扰。
最后,这是我的问题。有没有其他方法可以做我想要的(即,根据图形模板参数提供不同的顶点类 - 或功能 - )?如果是这样,如何以及将有什么优势;如果没有,我应该更喜欢什么,为什么?
您的第一个实现不是直接可能的,因为:
C++11标准第14.5.5.3/1段
[...] 类模板专用化是一个独特的模板。类模板部分专用化的成员与主模板的成员无关。[...]
这意味着成员struct Vertex
不需要存在于类Graph
的部分模板专用化中,因此不能直接定义,而无需专用于整个类。
因此,您不能执行以下操作:
template<typename T1, typename T2>
class Graph { struct Vertex; };
template<typename T2>
struct Graph<double, T2>::Vertex { };
(另请参阅模板类不完整专用化)
C++11标准第14.7.3/15段
成员或成员模板可以嵌套在许多封闭类模板中。 在此类成员的显式专用化中,成员声明之前应为每个明确专用的封闭类模板提供一个
template<>
(另请参阅具有 IdeaHat 指示的默认参数的专用内部模板)
这意味着:
template<typename VertexValue = void, bool directed = false>
struct Graph {
struct Vertex;
};
// template implementation
template<typename VertexValue, bool directed>
struct Graph<VertexValue, directed>::Vertex {
using ValueType = VertexValue;
};
// full specialization
template<>
struct Graph<void, false>::Vertex {
using ValueType = void;
};
工作正常。
解决方法
一个可能的解决方案是将要专用化的所有类型放入Graph
基类中,然后完全专用化此基类:
template<typename VertexValue, bool directed>
struct BaseGraph;
template<typename VertexValue = void, bool directed = false,
typename Base = BaseGraph<VertexValue, directed> >
struct Graph : public Base {
using Vertex = typename Base::Vertex;
};
// Directed, with value
template<typename VertexValue, bool directed>
struct BaseGraph {
struct Vertex {
using ValueType = VertexValue;
};
};
// Directed, without value
template<bool directed>
struct BaseGraph<void, directed> {
struct Vertex {
using ValueType = void;
};
};
// Undirected, with value
template<typename VertexValue>
struct BaseGraph<VertexValue, false> {
struct Vertex {
using ValueType = VertexValue;
};
};
// Undirected, without value
template<>
struct BaseGraph<void, false> {
struct Vertex {
using ValueType = void;
};
};
但这与您使用外部 GraphVertex 类的方法非常相似,我更喜欢。