Friend function defined in class template is not in scope

[Mike]

You have only declared those functions as friends, but you have not

declared the functions themselves in the outer scope. You need to add
those declarations to the global scope. In other words:
edge_list& edges(vertex_pointer p);
edge_pointer add_edge(vertex_pointer from, vertex_pointer to,
const EDGE& e=EDGE());

This seem to contradict what C++ FAQ
(http://www.parashift.com/c++-faq-lite/templates.html#faq-35.16) says:

Another approach is to define the friend function within the class body
at the same moment you declare it to be a friend. For example:

#include <iostream>

template<typename T>
class Foo {
public:
Foo(T const& value = T());

friend Foo<T> operator+ (const Foo<T>& lhs, const Foo<T>& rhs)
{
...
}

friend std:stream& operator<< (std:stream& o, const Foo<T>& x)
{
...
}

private:
T value_;
};

But I tried defining add_edge before the graph class and just including
friend declaration for add_edge inside the graph class (see below). It
still didn't work.
This time I got: "template-id 'add_edge<>' for ... does not match any
template declaration" error message.

#include <iostream>
#include <list>
using namespace std;


template<typename EDGE, typename VERTEX> struct graph; // pre-declare
the template class itself
template<typename EDGE, typename VERTEX>
typename graph<EDGE,VERTEX>::edge_pointer
add_edge(
typename graph<EDGE,VERTEX>::vertex_pointer from,
typename graph<EDGE,VERTEX>::vertex_pointer to,
const EDGE& e=EDGE()
)
{
edges(from).push_back(make_pair(e,to));
typename graph<EDGE,VERTEX>::edge_pointer p = edges(from).end();
return --p;
}

template<typename VERTEX /*Vertex Satellite data*/, typename EDGE=string
/*Edge Satellite data*/> struct graph
{

struct EDGE_LIST
{

>::iterator> > edges;

};

>::iterator> > edge_list;

typedef typename edge_list::iterator edge_pointer;

typedef list<pair<VERTEX, EDGE_LIST> > vertex_list;

typedef typename vertex_list::iterator vertex_pointer;

vertex_list V;

friend edge_list& edges(vertex_pointer p){return p->second.edges;}

vertex_pointer add_vertex(VERTEX v)
{
V.push_back(make_pair(v, EDGE_LIST()));
vertex_pointer p = V.end();
return --p;
}

friend edge_pointer add_edge<>(vertex_pointer from, vertex_pointer
to, const EDGE& e);

};


int main()
{
graph<int> G;
graph<int>::vertex_pointer a = G.add_vertex(1);
graph<int>::vertex_pointer b = G.add_vertex(2);
add_edge(a,b);
return 0;
}

 

[Öö Tiib]

This seem to contradict what C++ FAQ
(http://www.parashift.com/c++-faq-lite/templates.html#faq-35.16) says:

It does not. FAQ example friends have parameters of type Foo<T> so ADL
finds them. Yours do not have parameters of type graph<VERTEX,EDGE> so
you have to declare them in surrounding namespace to make them visible.

 

[Mike]

finds them. Yours do not have parameters of type graph<VERTEX,EDGE> so
you have to declare them in surrounding namespace to make them visible.

I see. Any comment on why the following code where add_edge is defined
as template function in global scope and declared as friend in body of
graph class still does not compile with "template-id 'add_edge<...>'
... does not match any template declaration" error message?
Thanks.

#include <list>
using namespace std;


template<typename EDGE, typename VERTEX> struct graph;
template<typename EDGE, typename VERTEX>
typename graph<EDGE,VERTEX>::edge_pointer
add_edge(
typename graph<EDGE,VERTEX>::vertex_pointer from,
typename graph<EDGE,VERTEX>::vertex_pointer to,
const EDGE& e=EDGE()
)
{
edges(from).push_back(make_pair(e,to));
typename graph<EDGE,VERTEX>::edge_pointer p = edges(from).end();
return --p;
}

template<typename VERTEX /*Vertex Satellite data*/, typename EDGE=string
/*Edge Satellite data*/> struct graph
{

struct EDGE_LIST
{

>::iterator> > edges;

};

>::iterator> > edge_list;

typedef typename edge_list::iterator edge_pointer;

typedef list<pair<VERTEX, EDGE_LIST> > vertex_list;

typedef typename vertex_list::iterator vertex_pointer;

vertex_list V;

friend edge_list& edges(vertex_pointer p){return p->second.edges;}

vertex_pointer add_vertex(VERTEX v)
{
V.push_back(make_pair(v, EDGE_LIST()));
vertex_pointer p = V.end();
return --p;
}

friend typename graph<VERTEX,EDGE>::edge_pointer
add_edge<VERTEX,EDGE>
(typename graph<VERTEX,EDGE>::vertex_pointer from,
typename graph<VERTEX,EDGE>::vertex_pointer to,
const EDGE& e
); //Error message refers to this line

};


int main()
{
graph<int> G;
graph<int>::vertex_pointer a = G.add_vertex(1);
graph<int>::vertex_pointer b = G.add_vertex(2);
add_edge(a,b);
return 0;
}

 

[Bart van Ingen Schenau]

I see. Any comment on why the following  code where add_edge is defined
as template function in global scope and declared as friend in body of
graph class still does not compile with  "template-id 'add_edge<...>'
.. does not match any template declaration" error message?
Thanks.

You have made your design too complicated to be able to use friend
effectively.
The easiest way to resolve the current problems is just to make the
nested types of graph public, so you don't need a friend declaration.

The root of your problem is that you have created a chicken-and-egg
situation. The function 'add_edge' depends on a nested type of graph,
so the definition of graph should come before your declaration of
add_edge. But to declare add_edge properly as a friend, it should be
declared before the definition of graph.

Additionally, your current design allows for a different (potential)
problem: As add_edge is not a member of graph, the following code is
also possible:
graph<int> G1, G2;
graph<int>::vertex_pointer a = G1.add_vertex(1);
graph<int>::vertex_pointer b = G2.add_vertex(2);
add_edge(a,b);

meaning you have an edge that connects vertices from two unrelated
graphs.
As edges are at least as much part of a graph as the vertices are, I
would recommend making add_edge a member function of graph.

Bart v Ingen Schenau

 

[Mike]

You have made your design too complicated to be able to use friend
effectively.
The easiest way to resolve the current problems is just to make the
nested types of graph public, so you don't need a friend declaration.
The root of your problem is that you have created a chicken-and-egg
situation. The function 'add_edge' depends on a nested type of graph,
so the definition of graph should come before your declaration of
add_edge. But to declare add_edge properly as a friend, it should be
declared before the definition of graph.
Additionally, your current design allows for a different (potential)
problem: As add_edge is not a member of graph, the following code is
also possible:
graph<int> G1, G2;
graph<int>::vertex_pointer a = G1.add_vertex(1);
graph<int>::vertex_pointer b = G2.add_vertex(2);
add_edge(a,b);
meaning you have an edge that connects vertices from two unrelated
graphs.
As edges are at least as much part of a graph as the vertices are, I
would recommend making add_edge a member function of graph.
Bart v Ingen Schenau

Thank you for your critique.
My design idea is pretty straightforward: to store structures containing
vertex satellite data and corresponding adjacency lists in a list where
adjacency lists members will be structures containing edge satellite
data and a pointer to corresponding element of vertex list.
Having vertex and edge satellite data as parameter types should make
graph parametrized type to be really convenient for implementation of
various graph algorithms, where depending on algorithm different data
is supposed to be supplied with vertices/edges. I would like to use STL
in implementation, so I don't have to worry about memory management.
It is really frustrating that it is so difficult to express such a
simple idea in C++ with STL.
My main objectives for design were efficiency (adding/removing edges in
constant time) and ease of use, but no so much doing safety checks for
programmer. So it is kind of similar to STL interface in this respect.
STL allows a programmer to supply b and e iterators pointing to
different containers in the copy(b,e,c) call, so it is up to a
programmer to know what he/she is doing.

Mike

 

[Bart van Ingen Schenau]

Thank you for your critique.
My design idea is pretty straightforward: to store structures containing
vertex satellite data and corresponding adjacency lists in a list where
adjacency lists members will be structures containing edge satellite
data and a pointer to corresponding element of vertex list.

Yes, that design is not too complicated. What makes it complicated is
the way you try to express the design in your code.
By declaring the types that describe your vertices and edges as nested
types of the templated graph type, while the functions for
manipulating (adding) edges to the edge-list of a vertex are non-
member functions.

I tried to rewrite your code with non-friend, non-member functions for
add_edge() and edges(), and I found that this is hardly possible
without having to specify the VERTEX and EDGE types over and over
again when calling these functions.

Your best bet at getting a working system is to make edges() and
add_edge() into member-functions as well.
Although these functions are not directly manipulating members of
graph, edges are conceptually as much part of a graph as the vertices
are. It is just an implementation detail that they are not stored
directly in the graph.
Additionally, your use of nested typedefs within a template makes it
impossible for the compiler to deduce the template parameters of
graph<> when you are to make add_edge() and edges() non-member
functions. This means you can not call these functions as free-
standing functions without specifying the template parameters for
graph<> in each and every call. When these functions are members of
graph<>, you don't have that inconvenience.

As member functions, the code just becomes:

#include <list>
using namespace std;

template<typename VERTEX, typename EDGE=string>
struct graph
{

struct EDGE_LIST
{

::iterator> > edges;

};
typedef list<pair<VERTEX, EDGE_LIST> > vertex_list;
typedef typename vertex_list::iterator vertex_pointer;
typedef list< pair<EDGE, vertex_pointer> edge_list;
typedef typename edge_list::iterator edge_pointer;

vertex_list V;

//BVIS: removed friend
edge_list& edges(vertex_pointer p){return p->second.edges;}

vertex_pointer add_vertex(VERTEX v)
{
V.push_back(make_pair(v, EDGE_LIST()));
vertex_pointer p = V.end();
return --p;
}

//BVIS: removed friend
edge_pointer add_edge(vertex_pointer from, vertex_pointer to,
const EDGE& e=EDGE())
{
edges(from).push_back(make_pair(e,to));
edge_pointer p = edges(from).end();
return --p;
}

};

int main()
{
graph<int> G;
graph<int>::vertex_pointer a = G.add_vertex(1);
graph<int>::vertex_pointer b = G.add_vertex(2);
//BVIS: added graph object to add the edge to
G.add_edge(a,b);
return 0;
}

My main objectives for design were efficiency (adding/removing edges in
constant time) and ease of use, but no so much doing safety checks for
programmer. So it is kind of similar to STL interface in this respect.
STL allows a programmer to supply b and e iterators pointing to
different containers in the copy(b,e,c) call, so it is up to a
programmer to know what he/she is doing.

There is very little you can actually do to prevent such incorrect
usage, apart from giving the programmer a reminder about the correct
usage of the function.
I just wanted to make sure you were aware of this potential issue.

Mike

Bart v Ingen Schenau

 

[Mike]

Yes, that design is not too complicated. What makes it complicated is

the way you try to express the design in your code.
By declaring the types that describe your vertices and edges as nested
types of the templated graph type, while the functions for
manipulating (adding) edges to the edge-list of a vertex are non-
member functions.
I tried to rewrite your code with non-friend, non-member functions for
add_edge() and edges(), and I found that this is hardly possible
without having to specify the VERTEX and EDGE types over and over
again when calling these functions.
Your best bet at getting a working system is to make edges() and
add_edge() into member-functions as well.
Although these functions are not directly manipulating members of
graph, edges are conceptually as much part of a graph as the vertices
are. It is just an implementation detail that they are not stored
directly in the graph.
Additionally, your use of nested typedefs within a template makes it
impossible for the compiler to deduce the template parameters of
graph<> when you are to make add_edge() and edges() non-member
functions. This means you can not call these functions as free-
standing functions without specifying the template parameters for
graph<> in each and every call. When these functions are members of
graph<>, you don't have that inconvenience.
As member functions, the code just becomes:

Thanks, Bart. It's really helpful.

Mike