Need help, I do not understand why following code is not getting compiled.

Question

Header file is "graph.h"

#ifndef _GRAPH_H_
#define _GRAPH_H_

#include <map>
#include <vector>

using namespace std;

template <class T>
class VERTEX
{
public:
    VERTEX(T inVertex): m_vertex(inVertex), m_visited(false){}
    ~VERTEX(){}
private:
    T m_vertex;
    bool m_visited;
};

template <class T>
class GRAPH
{
public:
    GRAPH() {}
    ~GRAPH(){}
    typedef VERTEX<T> GRAPHVERTEX;
    typedef vector<GRAPHVERTEX> ADJLIST;
    typedef map<GRAPHVERTEX, ADJLIST> GRAPHMAP;

    void insert(GRAPHVERTEX inSRC, GRAPHVERTEX inDST)
    {
        GRAPHMAP::iterator itr = m_graph.find(inSRC);
    }

private:
    GRAPHMAP m_graph;
};

#endif

And test file is

#include "graph.h"

int main( int argc, char**argv)
{
    GRAPH<int> *G = new GRAPH<int>();
    G->insert(VERTEX<int>(0), VERTEX<int>(2));
    return 0;
}

Answer 1

There are two problems.

First you have to qualify the dependent type in insert:

void insert(GRAPHVERTEX inSRC, GRAPHVERTEX inDST)
{
    typename GRAPHMAP::iterator itr = m_graph.find(inSRC);
}

Second, you need a < operator for your vertex class. In the public section of VERTEX add this:

bool operator<(const VERTEX<T>& right) const { return m_vertex < right.m_vertex; }

As a matter of style note that in C++ ALL CAPS names are usually reserved for constants. Vertex would be a much more normal name for your class. Also note that having using namespace in a header can have many undesired and unpredictable results depending on include order and should be completely avoided.

EDIT: At least when I compiled this with g++ the first error I got was regarding GRAPHMAP::iterator. When a compiler sees an identifier that could be treated as a variable or a type, it choose to interpret it as a variable by default, but then at a later point discovered it was actually a type. You tell the compiler that it's really a type by using the typename keyword.

The second thing to note is that map is an ordered container and as such you need to either pass in a comparison function OR provide a < operator for the key of the map. Since VERTEX is the map key, I set up an operator< so that the objects can be sorted and have an order maintained. You may need to adjust the comparison operator as your VERTEX class evolves.

Answer 2

You can't create a map with GRAPHVERTEX as a key because you need to be able to compare the key with operator <. So you must define this operator.

Answer 3

Your VERTEX class is used as a key in the map; it is required to have a "less" operator defined.

Answer 4

To use a class as the key in a map, you have to either define operator< for that type, or else you need to specify a comparator when you create the map. Assuming objects of that type have a "natural" order, you normally want to use that to implement operator<. You typically use a separate comparator object when you need to arrange objects of a given type in a number of different orders, and no one order is really more "natural" or dominant than the others (e.g., when working with employees, you might look at them about equally often by social security number, name, and seniority).