Pointer to template class as that class parameter

Question

Basically while trying to implement a graph through adjacency list, I get stucked defining a graph node:

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

I realize that I can't give parameters to GraphNode template pointer, because they are not defined yet. My question to c++ templates gurus is: what technique is used in this case?

Thanks.

OK, I'm not sure what the question is... Do you want the GraphNode to have a pointer to another GraphNode with unknown template params..? — Grimm The Opiner
– Grimm The Opiner, Commented Feb 21, 2012 at 16:13
I can't just write GraphNode*, it needs to be GraphNode<Vertex, Edge, EdgeLink, Alloc>* but EdgeLink and Alloc are not defined. — Borzh
– Borzh, Commented Feb 21, 2012 at 16:16
Does the user really need to specify EdgeLink (and the Allocator) ? — Matthieu M.
– Matthieu M., Commented Feb 21, 2012 at 16:18
EdgeLink is really not necessary, but I want allocator to be template parameter — Borzh
– Borzh, Commented Feb 21, 2012 at 16:22

Matthieu M. · Accepted Answer · 2012-02-21 18:45:44Z

6

Precising the allocator does not necessitate to precise what the allocator can be used for. For example, in a std::list<T> the allocator passed is std::allocator<T> and yet the list will allocate _ListNode<T> (implementation defined). This is because allocators need to provide a rebind mechanism.

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

In action at ideone.

Note that even though list will do a rebind itself, you should still do it, because the allocator types reference and pointer (and their const version) will be pulled as typedef inside the list.

EDIT: Allow container specification.

This is tricky because the allocator is unfortunately only defined once you are within GraphNode, you thus need to pass it to the container only within the class, and thus cannot use it in the template outside.

This means using template template parameters, and we thus need to "fix" the arity. Since both vector and list only take two parameters we are lucky here, but it might not always hold... fortunately with C++11 allowing template aliases, it won't be too harsh a requirement for the user.

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

This can be invoked so:

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

Demo.

edited Feb 21, 2012 at 18:45

answered Feb 21, 2012 at 16:35

Matthieu M.

303k58 gold badges495 silver badges754 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Borzh Over a year ago

Thanks for the info, it is amazing, the things you can do with template programming!

Borzh Over a year ago

Another quick question: how can I use template parameter to specify container, for example to use std::vector instead of std::list?

Matthieu M. Over a year ago

@Borzh: updated :) As I said in the answer though, it's trickier than it should because the (proper) allocator only exists within the class.

Mike Seymour · Accepted Answer · 2012-02-21 16:21:14Z

1

If your EdgeLink is going to be 'inside' of GraphNode, it's better not to declare it as a template parameter. Instead use this approach:

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

edited Feb 21, 2012 at 16:21

Mike Seymour

256k30 gold badges467 silver badges658 bronze badges

answered Feb 21, 2012 at 16:15

Vite Falcon

6,6413 gold badges33 silver badges48 bronze badges

5 Comments

Matthieu M. Over a year ago

The use of identifiers starting with _[A-Z] is forbidden in any scope (reserved to implementation).

Vite Falcon Over a year ago

Modified my answer. Thanks for that info :)

Borzh Over a year ago

The problem is that I want allocator to be a template parameter. Could you modify the answer in a way to allocator to be a template parameter?

Vite Falcon Over a year ago

What information would the 'Edge' type contain? Does it already have information about the two connecting nodes?

Borzh Over a year ago

Vertex could be a town name and Edge a number that holds distance from one town to another, for example

Collectives™ on Stack Overflow

Pointer to template class as that class parameter

2 Answers 2

3 Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related