Friend function defined in class template is not in scope

Discussion in 'C++' started by Mike, Jan 16, 2011.

  1. Mike

    Mike Guest

    > 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::eek:stream& operator<< (std::eek: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
    {
    list< pair<EDGE, typename list<pair<VERTEX, EDGE_LIST>
    >::iterator> > edges;

    };

    typedef list< pair<EDGE, typename list<pair<VERTEX, EDGE_LIST>
    >::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;
    }
     
    Mike, Jan 16, 2011
    #1
    1. Advertising

  2. Mike

    Öö Tiib Guest

    On Jan 16, 11:21 pm, Mike <> wrote:
    > > 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:


    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.
     
    Öö Tiib, Jan 16, 2011
    #2
    1. Advertising

  3. Mike

    Mike Guest

    > 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.

    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
    {
    list< pair<EDGE, typename list<pair<VERTEX, EDGE_LIST>
    >::iterator> > edges;

    };

    typedef list< pair<EDGE, typename list<pair<VERTEX, EDGE_LIST>
    >::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;
    }
     
    Mike, Jan 17, 2011
    #3
  4. On Jan 17, 6:06 am, Mike <> wrote:
    > > 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.

    >
    > 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
     
    Bart van Ingen Schenau, Jan 17, 2011
    #4
  5. Mike

    Mike Guest


    > 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
     
    Mike, Jan 19, 2011
    #5
  6. On Jan 19, 5:21 am, Mike <> wrote:
    >
    > 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
    {
    list< pair<EDGE, typename list<pair<VERTEX, 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;
    }

    <snip>
    > 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
     
    Bart van Ingen Schenau, Jan 19, 2011
    #6
  7. Mike

    Mike Guest

    > 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
     
    Mike, Jan 20, 2011
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Yueh-Wei Hu
    Replies:
    0
    Views:
    472
    Yueh-Wei Hu
    May 23, 2004
  2. Replies:
    2
    Views:
    501
    John Harrison
    Nov 9, 2005
  3. A L
    Replies:
    1
    Views:
    530
    Alf P. Steinbach /Usenet
    Aug 25, 2010
  4. Peter
    Replies:
    8
    Views:
    2,272
    James Kanze
    Dec 20, 2010
  5. Mike
    Replies:
    1
    Views:
    439
    Juha Nieminen
    Jan 16, 2011
Loading...

Share This Page