Nested class specialization in terms of outer class template arguments

Question

I am writing a Graph class and I want to provide multiple types of graphs with the same class. More specifically, I want to consider directed or undirected graphs, as well as the possibility for vertices (and edges) to have values.

Right now, my class looks something like that.

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

For convenience, I will skip anything related to edges implementation.

What I want to do now is to "specialize" the Vertex class to provide - or not - a value, and different methods depending on whether the graph is directed or not. I would like to be able to do something like the following (note : Vertex methods are only for illustrating purposes, directed and undirected versions of Vertex having different methods).

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

Unfortunately, I would have to specialize the whole Graph class in order to do that. So I tried something else : having the Vertex class being a template, and forwarding the outer template arguments.

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

This would work ; however, I do not like the idea of forwarding the template arguments, and it also introduces a burden, the dummy template parameter. I have also thought about defining the Vertex class outside of the Graph class, like so :

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

...or even like that :

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

...but I prefer the idea of nested class, where the Vertex class really is a property of the Graph class. Plus, even if this solution, out of the three, would still have my preference, I do not find any other name for "GraphVertex". And it bothers me.

In the end, here is my question. Is there any other way to do what I want (namely, provide different Vertex classes - or features - depending on the Graph template arguments) ? If so, how to and what would be the advantages ; if not, what should I prefer and why ?

Answer 1

Your first implementation is not directly possible, because:

Paragraph 14.5.5.3/1 of the C++11 Standard

[...] class template specialization is a distinct template. The members of the class template partial specialization are unrelated to the members of the primary template. [...]

This means that the member struct Vertex need not to exist in the partial template specialization of the class Graph and can thus not be defined directly, without specializing the whole class.

So, you can not do something like:

template<typename T1, typename T2>
class Graph { struct Vertex; };

template<typename T2> 
struct Graph<double, T2>::Vertex { };

(see also Template class incomplete specialization)

Paragraph 14.7.3/15 of the C++11 Standard

A member or a member template may be nested within many enclosing class templates. In an explicit specialization for such a member, the member declaration shall be preceded by a template<> for each enclosing class template that is explicitly specialized

(see also Specializing inner template with default parameters as indicated by IdeaHat)

This means:

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

works fine.

Workaround

A possible solution could be to put all the types you want to specialize into a base class of Graph and then specialize this base class completely:

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

But this is very similar to your approach with an external GraphVertex class, that I would prefer.