Making Adjacency List with Vectors?

hubbu (5)
I'm trying to make an adjacency list with a class "Graph" containing a vector with type "Node." The Node class has integer members for storage. The Node class also has a vector of type "Edge." The Edge class has edge names and an integer weight.

When I push back a Node into Graph's vector the information seems to get lost in action. I get numbers like -82711038F, etc.

I've been at this for days and I should say that I'm new to using STL and a beginner in class structuring. Also, I'm not aiming for optimization (speed). Any help is appreciated!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
#include "vector"
#include "iostream"
#include "functional"

using namespace std;

class Edge
{
public:
	int edgeID;
	int edgeWeight;

	Edge(int edge, int weight): edgeID(edge), edgeWeight(weight) { }

	friend ostream& operator<<(ostream& out, const Edge& e)
	{
		cout << e.edgeID << " " << e.edgeWeight << endl;

		return out;
	}
};

class Node
{
public:
	int nodeID;
	int g, h, f;
	vector<Edge> edgeList;

	Node(int nID, int gCost, int hCost): nodeID(nID), g(gCost), h(hCost)
	{
		f = gCost + hCost;
	}

	Node(const Node& n)
	{
		f = n.g + n.h;
	}

	friend ostream& operator<<(ostream& out, const Node& n)
	{
		cout <<"ID: " << n.nodeID << " - F Cost: " << n.f << endl;

		return out;
	}
};

class Graph
{
public:
	vector<Node> nodeList;

	Graph()
	{
		nodeList.push_back(Node(1, 4, 0));
		nodeList.push_back(Node(2, 3, 1));

		Edge edge1(1, 1), edge2(2, 1);

		nodeList[0].edgeList.push_back(edge1);
		nodeList[1].edgeList.push_back(edge2);
	}
};


1
2
3
4
5
6
7
8
9
 
void main()
{
	Graph graph;

	for(vector<int>::size_type i = 0; i< graph.nodeList.size(); i++)
		cout << "Node " << i << ": " << graph.nodeList.at(i) << endl;

	_getch();
}
Disch (13742)
When you have a vector/list/whatever of a class, what actually ends up happening is the object you create gets copied into the list.

So when you are doing this:

 
 
nodeList.push_back(Node(1, 4, 0));


what's really happening is this:

1
2
3
4
 
Node(1,4,0)   // <-- a temporary unnamed Node object is created

nodeList.push_back()  //  <--- a copy of that temporary object is added to the list
   // ie, the temp object itself is not added to the list


Because the object is copied into the list, it's calling the copy constructor for Node... and your copy constructor never inits h, g, or nodeID. It only inits f.

You don't need a custom copy ctor in this case. My advise is just to get rid of it and let the default copy ctor do the work.
Last edited on
hubbu (5)
Solved thanks to you Disch! Now I can get some shut eye.
Topic archived. No new replies allowed.