Указатель на шаблонный класс как этот параметр класса

Question

Обычно, пытаясь реализовать граф через список смежности, я зацикливаюсь на определении узла графа:

template <
    typename Vertex, 
    typename Edge,
    typename EdgeLink = std::pair< Edge, GraphNode* >,
    typename Alloc = std::allocator< EdgeLink >
>
class GraphNode
{
public:
    Vertex vertex;
    std::list< EdgeLink, Alloc > neighbours;
};

Я понимаю, что не могу дать параметры указателю шаблона GraphNode, потому что они не определеныеще.Мой вопрос к гуру шаблонов c ++: какая техника используется в этом случае?

Спасибо.

Answer 1

Уточнение распределителя не требует точного определения того, для чего может использоваться распределитель.Например, в std::list<T> переданный распределитель равен std::allocator<T>, и все же list выделит _ListNode<T> (реализация определена).Это связано с тем, что распределители должны предоставлять механизм rebind* 1007. *.

template <
    typename Vertex, 
    typename Edge,
    typename Allocator = std::allocator<void*>
>
class GraphNode
{
public:
    typedef GraphNode<Vertex, Edge, Allocator> NodeType;
    typedef std::pair< Edge, NodeType* > LinkType;
    typedef typename Allocator::template rebind<LinkType>::other AllocatorType;

    Vertex vertex;
    std::list< LinkType, AllocatorType > neighbours;
};

В действии на ideone .

Обратите внимание, что даже при list сам сделает rebind, вы все равно должны это сделать, потому что типы распределителя reference и pointer (и их постоянная версия) будут вытягиваться как typedef внутри list.

РЕДАКТИРОВАТЬ: Разрешить спецификацию контейнера.

Это сложно, потому что распределитель, к сожалению, определяется только тогда, когда вы находитесь в пределах GraphNode, поэтому вам нужно передать его в контейнер только в пределахкласс, и, следовательно, не может использовать его в шаблоне снаружи.

Это означает использование параметров шаблона шаблона, и поэтому мы должны "исправить" арность.Поскольку и vector, и list принимают только два параметра, нам здесь повезло, но это может не всегда выполняться ... к счастью, в C ++ 11 допускается использование псевдонимов шаблонов, это не будет слишком жестким требованием для пользователя.

template <
    typename Vertex, 
    typename Edge,
    template <typename, typename> class Container = std::vector,
    typename Allocator = std::allocator<void*>
>
class GraphNode
{
public:
    typedef GraphNode<Vertex, Edge, Container, Allocator> NodeType;
    typedef std::pair< Edge, NodeType* > LinkType;
    typedef typename Allocator::template rebind<LinkType>::other AllocatorType;
    typedef Container<LinkType, AllocatorType> NeighboursType;

    Vertex vertex;
    NeighboursType neighbours;
};

Это может быть вызвано так:

GraphNode<std::string, int>
GraphNode<std::string, int, std::list>
GraphNode<std::string, int, std::vector>

Демо .

Answer 2

Если ваш EdgeLink будет «внутри» GraphNode, лучше не объявлять его как параметр шаблона. Вместо этого используйте этот подход:

template <
    typename Vertex, 
    typename Edge
>
class GraphNode
{
public:
    typedef GraphNode<Vertex, Edge> NodeType;
    typedef std::pair< Edge, NodeType* > LinkType;
    typedef std::allocator< Linktype > AllocType;
    Vertex vertex;
    std::list< LinkType, AllocType > neighbours;
};