C++

Forum

 
Having a hard time understanding the * operator

Tinito16 (5)
Hi,

I'm doing a school project, and I'd been making ok progress up until today. I was working on an implementation of Dijkstra's Algorithm. It was all in a single .cpp file. I wanted to separate it into discrete files so I could manipulate and change certain things more easily.

Understand I'm mostly familiar with Java. So I'm slightly confused as to how to make the "separation" happen. Essentially, I'd like to separate the code into "classes" in order to change stuff later (which is going to be less elegant if it's all in one file).

This is the original code:
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
// Dijkstra_Vanilla.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
#include<vector>

using namespace std;

void DijkstrasTest();

int _tmain(int argc, _TCHAR* argv[])
{
	DijkstrasTest();
	system("Pause");
	return 0;
}

////////

class Node;
class Edge;

void Dijkstras();
vector<Node*>* AdjacentRemaningNodes(Node* node);
Node* ExtractSmallest(vector<Node*>& nodes);
int Distance(Node* node1, Node* node2);
bool Contains(vector<Node*>& nodes, Node* node);
void PrintShortestRouteTo(Node* destination);

vector<Node*> nodes;
vector<Edge*> edges;

class Node
{
public:
	Node(char id)
		: id(id), previous(NULL), distanceFromStart(INT_MAX)
	{
		nodes.push_back(this);
	}

public:
	char id;
	Node* previous;
	int distanceFromStart;
};

class Edge
{
public:
	Edge(Node* node1, Node* node2, int distance)
		: node1(node1), node2(node2), distance(distance)
	{
		edges.push_back(this);
	}
	
	bool Connects(Node* node1, Node* node2)
	{
		return (
			(node1 == this->node1 && node2 == this->node2) ||
			(node1 == this->node2 && node2 == this->node1));
	}

public:
	Node* node1;
	Node* node2;
	int distance;
};

///////

void DijkstrasTest()
{
	Node* a = new Node('a');
	Node* b = new Node('b');
	Node* c = new Node('c');
	Node* d = new Node('d');
	Node* e = new Node('e');
	Node* f = new Node('f');
	Node* g = new Node('g');
	
	Edge* e1 = new Edge(a,c,1);
	Edge* e2 = new Edge(a,d,2);
	Edge* e3 = new Edge(b,c,2);
	Edge* e4 = new Edge(c,d,1);
	Edge* e5 = new Edge(b,f,3);
	Edge* e6 = new Edge(c,e,3);
	Edge* e7 = new Edge(e,f,2);
	Edge* e8 = new Edge(d,g,1);
	Edge* e9 = new Edge(g,f,1);
	
	a->distanceFromStart = 0; //Set start node
	Dijkstras();
	PrintShortestRouteTo(f);

	//Node/Edge memory cleanup not included
}

////////

void Dijkstras()
{

	while(nodes.size() > 0)
	{
		Node* smallest = ExtractSmallest(nodes);
		vector<Node*>* adjacentNodes = AdjacentRemaningNodes(smallest);

		const int size = adjacentNodes->size();

		for(int i=0; i<size; ++i)
		{
			Node* adjacent = adjacentNodes->at(i);
			int distance = Distance(smallest, adjacent) +
				smallest->distanceFromStart;

			if(distance < adjacent->distanceFromStart)
			{
				adjacent->distanceFromStart = distance;
				adjacent->previous = smallest;
			}
		}
		
		delete adjacentNodes;
	}
}

(...)
}


It basically finds the shortest route on a Weighted Graph, then puts the result out to the console.

Now, this is what I've broken it up to so far:

Dijkstra header:
1
2
3
4
5
 
#include<iostream>
#include<vector>
#include<string>

using namespace std;


class Node:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
#include "Dijkstra.h"

class Node
{
public:
	Node(){}
	Node(char id, vector<Node*> nodes)
		: id(id), previous(NULL), distanceFromStart(INT_MAX)
	{
		nodes.push_back(this);
	}

public:
	char id;
	Node* previous;
	int distanceFromStart;
};


class Edge:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include "Dijkstra.h"
#include "Node.cpp"

class Edge
{
public:
	Edge(Node* node1, Node* node2, int distance, vector<Edge*> edges)
		: node1(node1), node2(node2), distance(distance)
	{
		edges.push_back(this);
	}
	
	bool Connects(Node* node1, Node* node2)
	{
		return (
			(node1 == this->node1 && node2 == this->node2) ||
			(node1 == this->node2 && node2 == this->node1));
	}

public:
	Node* node1;
	Node* node2;
	int distance;
};


class Graph (this seems to be part of the problem):
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
 
#include "Dijkstra.h"
#include "Node.cpp"
#include "Edge.cpp"

vector<Node*> nodes;
vector<Edge*> edges;

class Graph
{
public:
	Graph()
	{
		Node* a = new Node('a', nodes);
		Node* b = new Node('b', nodes);
		Node* c = new Node('c', nodes);
		Node* d = new Node('d', nodes);
		Node* e = new Node('e', nodes);
		Node* f, *dest = new Node('f', nodes);
		Node* g = new Node('g', nodes);
	
		Edge* e1 = new Edge(a,c,1,edges);
		Edge* e2 = new Edge(a,d,2,edges);
		Edge* e3 = new Edge(b,c,2,edges);
		Edge* e4 = new Edge(c,d,1,edges);
		Edge* e5 = new Edge(b,f,3,edges);
		Edge* e6 = new Edge(c,e,3,edges);
		Edge* e7 = new Edge(e,f,2,edges);
		Edge* e8 = new Edge(d,g,1,edges);
		Edge* e9 = new Edge(g,f,1,edges);
	
		a->distanceFromStart = 0; //Set start node
	}

public:
	vector<Node*> nodes;
	vector<Edge*> edges;
	Node* dest;
}


Dijkstra Implementation with main:
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
64
65
 
// Dijkstra_MyImp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Dijkstra.h"
#include "Graph.cpp"
#include "Node.cpp"
#include "Edge.cpp"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	Graph *graph = new Graph();
	Dijkstras(*graph);
	PrintShortestRouteTo(graph->dest);
	system("Pause");
	return 0;
}

////////

class Node;
class Edge;

void Dijkstras(Graph graph);
vector<Node*>* AdjacentRemaningNodes(Node* node);
Node* ExtractSmallest(vector<Node*>& nodes);
int Distance(Node* node1, Node* node2);
bool Contains(vector<Node*>& nodes, Node* node);
void PrintShortestRouteTo(Node* destination);

//vector<Node*> nodes;
//vector<Edge*> edges;

//vector<Node*>& nodes, vector<Edge*>& edges

void Dijkstras(Graph graph)
{
	nodes = graph->nodes;
	while(nodes.size() > 0)
	{
		Node* smallest = ExtractSmallest(nodes);
		vector<Node*>* adjacentNodes = AdjacentRemaningNodes(smallest);

		const int size = adjacentNodes->size();

		for(int i=0; i<size; ++i)
		{
			Node* adjacent = adjacentNodes->at(i);
			int distance = Distance(smallest, adjacent) +
				smallest->distanceFromStart;

			if(distance < adjacent->distanceFromStart)
			{
				adjacent->distanceFromStart = distance;
				adjacent->previous = smallest;
			}
		}
		
		delete adjacentNodes;
	}
}

(...)


Specifically, in this line in the implementation file, I have an error relating to the Graph file:
PrintShortestRouteTo(graph->dest);
The error is: "Argument of type "Node*" is incompatible with parameter of type "Node*"

There are other errors in my code, but this error in particular has got me stumped. I've been trying for hours to figure out what is wrong, to no avail.

If anyone can help, it would be greatly appreciated!
Last edited on
Jikax (236)
i'm not really sure (to much code to read fast), but i think graph->dest is empty, it points to nothing.

Node* f, *dest = new Node('f', nodes);

*dest point to the location of a Node object, but you never initialised it. *dest = not a Node object.

and second you are creating a new instance of dest. you are not usin the one you already got as a private.

1
2
 
Node* f = new Node('f', nodes);
dest = new Node('f', nodes);


I maybe wrong though...;)
doug4 (1538)
The * means pointer. Pointers are probably the biggest stumbling block for people first learning C or C++.

Start by reading this document. This should answer most of your questions. You may not understand the answer immediately, but...

http://cplusplus.com/doc/tutorial/pointers

Edit - not as terse
Last edited on
closed account (zb0S216C)
Tinito16 wrote:
"Having a hard time understanding the * operator"

Hang on a minute. You don't fully understand pointers, and yet, you go nuts with pointers, and DMA? The asterisk operator is used in two contexts that pertain to pointers: In the declaration of a pointer, and the dereferencing of a pointer.

P.S: Your program is leaking like a colander. C++ doesn't have a garbage collector.

Wazzak
Last edited on
Tinito16 (5)
Thanks for the doc, doug4! That cleared some things up. I was using them opposite of how they're supposed to be used in some instances.

Framework, most of the code I found through the internet; the actual project involves using OpenMP to do Dijkstra's Algorithm, but I wanted to make sure I understood the algorithm and how to work with C++ first. So this version is just a vanilla implementation of Dijkstra.
About the memory leaks, I'll have to work on that for sure. I'm so used to Java it's hard to do everything myself now in C++. But I shall learn. Even though it is a bit stressing to be learning this on a deadline, it's also very interesting to learn such a complex language.
doug4 (1538)
It is important to learn about pointers and references in C++. And the code you are looking at makes use of them a lot.

The program you are working with seems overly dependent on dynamic memory. With good program design there are ways to minimize a lot of the potential memory leak situations. I suspect there are some efficiencies that could be realized in the implementation from which you are starting to make things easier. But I don't want to confuse you with that.

I guess the point I'm trying to make is that there are good and bad ways to manage memory in C++, and with experience you will be able to mitigate many of the risks. So don't think the code in front of you is what you'll be dealing with in all C++ programs.
doug4 (1538)
I keep coming back to your program. A couple of things really bug me about the sample code you started from. Mainly, the Node and Edge classes are storing themselves in global data structures. YUCK!!

In your code, you have created a Graph class. This class should contain the Node and Edge lists. The Node list can be a list of Node objects (instead of pointers), and the Graph class should manage the lists. Instead of Node* = new Node('a', nodes), you can do

1
2
 
Node a('a');
nodes.push_back(a);


Your Edge objects would contain references to Node objects (Node&) instead of pointers.

Doing this would get rid of all of the dynamic memory allocation in your code (I think) and solve your problem of garbage collection / memory leaks.

Of course, this is the stuff I didn't want to confuse you with, but I couldn't let it go. If you have the time and ability to rework some of this code, it will probably make things easier for you in the long run. But I understand if you don't want to undertake the endeavor.
Tinito16 (5)
I actually managed to get the code to work, but it was giving me garbage output, so I actually did what you suggested (without actually having read your reply, I did this during the day then I collapsed in bed as I'd been coding almost non-stop for about 12 hrs). I did it because I realized the 'nodes' and 'edges' vectors were not initializing.

Let me explain myself a bit. What I wanted to do was pass 'nodes' and 'edges' to the classes themselves and have the constructor push them into the vectors. That way I only had to write nodes/edges.push_back(this); once. In Java this would be a piece of cake. However this brings up a question: If it's bad practice in C++, is it bad practice in Java as well?

Here is my updated code for the node, edge and graph classes. It actually works - but again, I'm not 100% sure it's correct with respect to memory management.

Node Class:
1
2
3
4
5
6
7
8
9
 
#include "stdafx.h"
#include "Dijkstra.h"

Node::Node(char id, vector<Node*>& nodes)
		: id(id), previous(NULL), distanceFromStart(INT_MAX)
	{
		nodes.push_back(this);
	}


Edge Class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include "stdafx.h"
#include "Dijkstra.h"

Edge::Edge(Node* node1, Node* node2, int distance, vector<Edge*>& edges)
{
	this->node1 = node1;
	this->node2 = node2;
	this->distance = distance;
	edges.push_back(this);
}

bool Edge::Connects(Node* node1, Node* node2)
	{
		return (
			(node1 == this->node1 && node2 == this->node2) ||
			(node1 == this->node2 && node2 == this->node1));
	}


Graph Class:
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
#include "stdafx.h"
#include "Dijkstra.h"

Graph::Graph(): dest(NULL)	
{
	
}

void Graph::SelectGraph(int i)
{
	if(i==1)
		DoGraph1();
	else 
		DoGraph2();
}

void Graph::DoGraph1()
{
	cout << "Graph 1 Analysis: " << endl;

	nodes.clear();
	edges.clear();
	Node* a = new Node('a', nodes);
	Node* b = new Node('b', nodes);
	Node* c = new Node('c', nodes);
	Node* d = new Node('d', nodes);
	Node* e = new Node('e', nodes);
	Node* f = new Node('f', nodes);
	Node* g = new Node('g', nodes);
	
	Edge* e1 = new Edge(a,c,1,edges);
	Edge* e2 = new Edge(a,d,2,edges);
	Edge* e3 = new Edge(b,c,2,edges);
	Edge* e4 = new Edge(c,d,1,edges);
	Edge* e5 = new Edge(b,f,3,edges);
	Edge* e6 = new Edge(c,e,3,edges);
	Edge* e7 = new Edge(e,f,2,edges);
	Edge* e8 = new Edge(d,g,1,edges);
	Edge* e9 = new Edge(g,f,1,edges);

	a->distanceFromStart = 0; //Set start node
	dest = f;
}

void Graph::DoGraph2()
{
	cout << "Graph 2 Analysis: " << endl;

	nodes.clear();
	edges.clear();
	Node* a = new Node('a', nodes);
	Node* b = new Node('b', nodes);
	Node* c = new Node('c', nodes);
	Node* d = new Node('d', nodes);
	Node* e = new Node('e', nodes);
	Node* f = new Node('f', nodes);
	Node* g = new Node('g', nodes);
	
	Edge* e1 = new Edge(a,c,1,edges);
	Edge* e2 = new Edge(a,d,3,edges);
	Edge* e3 = new Edge(b,c,2,edges);
	Edge* e4 = new Edge(c,d,1,edges);
	Edge* e5 = new Edge(b,f,3,edges);
	Edge* e6 = new Edge(c,e,3,edges);
	Edge* e7 = new Edge(e,f,2,edges);
	Edge* e8 = new Edge(d,g,1,edges);
	Edge* e9 = new Edge(g,f,1,edges);

	a->distanceFromStart = 0; //Set start node
	dest = f;
}

void Graph::DoGraph3()
{
	cout << "Graph 3 Analysis: " << endl;

	nodes.clear();
	edges.clear();
	Node* a = new Node('a', nodes);
	Node* b = new Node('b', nodes);
	Node* c = new Node('c', nodes);
	Node* d = new Node('d', nodes);
	Node* e = new Node('e', nodes);
	Node* f = new Node('f', nodes);
	Node* g = new Node('g', nodes);
	Node* h = new Node('h', nodes);
	Node* i = new Node('i', nodes);
	Node* j = new Node('j', nodes);
	Node* l = new Node('l', nodes);
	Node* m = new Node('m', nodes);
	Node* n = new Node('n', nodes);
	Node* o = new Node('o', nodes);
	Node* p = new Node('p', nodes);

	Edge* e1 = new Edge(a,c,1,edges);
	Edge* e2 = new Edge(a,d,3,edges);
	Edge* e3 = new Edge(b,c,2,edges);
	Edge* e4 = new Edge(c,d,1,edges);
	Edge* e5 = new Edge(b,f,3,edges);
	Edge* e6 = new Edge(c,e,3,edges);
	Edge* e7 = new Edge(e,f,2,edges);
	Edge* e8 = new Edge(d,g,1,edges);
	Edge* e9 = new Edge(g,f,1,edges);
	Edge* e10 = new Edge(f,h,1,edges);
	Edge* e11 = new Edge(f,i,4,edges);
	Edge* e12 = new Edge(h,i,2,edges);
	Edge* e13 = new Edge(i,j,3,edges);
	Edge* e14 = new Edge(h,m,10,edges);
	Edge* e15 = new Edge(j,m,1,edges);
	Edge* e16 = new Edge(j,l,1,edges);
	Edge* e17 = new Edge(m,n,2,edges);
	Edge* e18 = new Edge(l,p,7,edges);
	Edge* e19 = new Edge(n,o,1,edges);
	Edge* e20 = new Edge(o,p,1,edges);

	a->distanceFromStart = 0; //Set start node
	dest = o;
}

//Testing
void Graph::PrintNodes()
{
	cout << "Size of Nodes: " << nodes.size() << endl;
	cout << "Size of Edges: " << edges.size() << endl;
	cout << "Nodes of Graph: " << endl;

	for(int i=0; i<nodes.size(); ++i)
	{
		cout << nodes.at(i)->id << " ";
	}
	cout << endl;
}

doug4 (1538)
When using pointers, there is actually memory in 2 places. First, there is the momory for the actual object, frequently dynamically allocated, as you did with your "new" operations. The other memory is the pointers, a form of metadata which merely tells you where the real data is. Your pointers are stored in your lists.

When you clear the lists, you remove the pointers, but you do not delete the memory allocated for the objects. This is the memory leak that Framework mentioned. My last post suggested storing actual objects in the lists rather than pointers. This may be a little over your head right now, so instead we will talk about deleting the memory when you clear the lists.

My suggestion is to create 2 new classes--NodeList and EdgeList. If you know about templates, they can be a single template class, but for now you can just write 2 classes.

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
 
class NodeList
{
public:
	void addNode(Node* node) { nodes.push_back(node); }
	void clear();
	void dumpInfo(ostream& outfile);

private:
	vector<Node*> nodes;
};

void NodeList::clear()
{
	for (int i = 0; i < nodes.size(); i++)
	{
		delete (nodes[i]);
	}
	nodes.clear();
}

void NodeList::dumpInfo(ostream& outfile)
{
	for (int i = 0; i < nodes.size(); i++)
	{
		outfile << nodes[i]->id << " ";
	}
	outfile << endl;
}


I think the syntax is correct (I haven't had a chance to compile it). I know I didn't add all the include files.

Have your Graph class contain a NodeList and an EdgeList object, and get rid of the global lists (lines 31 and 32 of your original post).

Hopefully there is enough here to get you started. Let me know if you run into problems.


Topic archived. No new replies allowed.