Re: Improving a short program in C++
Rog?rio Brito <rbrito@ime.usp.br> wrote:
I'm in the process of learning C++ with the scarce resources that I have
and
I
decided to make just a simple program in C++ to understand the issues
involved.
The program implements a simple graph data structure with adjacency lists
and
is
quite incomplete at this point. The source code is available at:
<http://www.ime.usp.br/~rbrito/graphs.cpp>.
I know many things that are still missing from it, but for my first
purposes
it
seems to run fine. The compiler (GCC, in my case, from Debian's sid
distribution) shows *no* warnings even when activating all that I know
(which
may not be sufficient).
Unfortunately (and this is the reason why I'm writing here) is that when I
run
it under valgrind (which is a tool to analyze memory leaks), I see that I
have
lost 240 bytes and more may be wasted with bigger graphs. It seems like
the
destructor is not performing all the actions that I wanted to.
That is because the destructor isn't being called, put "delete g;" in
main, or make it an auto variable to fix the leak. Generally, I must
second all of Thomas Richter's comments.
Thomas missed a leak though...
// operator=(const Graph&)
Graph & operator=(const Graph &g) {
n = g.n;
m = g.m;
vertices = new Vertex *[n];
// Now, perform deep copy
for (int i = 0; i < n; i++) {
Vertex *v = g.vertices[i];
vertices[i] = NULL;
while (v != NULL) {
Vertex *w = new Vertex(v->label());
vertices[i]->next(w);
v = v->next();
}
}
return *this;
}
What if *this has already been initialized with a set of vertices? You
are throwing away the 'vertices' pointer without deleting it, or its
contents.
The canonical op= looks something like this:
Graph& operator=( const Graph& g ) {
Graph tmp( g ); // use copy constructor to copy 'g'
swap( tmp ); // swap the contents of *this with the contents of tmp
return *this;
// upon return, the contents of tmp will be destroyed
// with the destructor.
}
Or more compactly as:
Graph& operator=( Graph g ) { // 'g' is a copy of the incoming parameter
swap( g );
return *this;
}
In some cases, you can make a more efficient version of the op= than the
above, but the above will always work (if the copy constructor,
destructor and swap work of course.)
==== other issues ====
Graph has a member-variable 'm' that is assigned to properly, but never
seems to be used for anything. Remove it, unless it has some purpose I
didn't see.
Graph has a member-variable 'n' which seems to track the size of the
'vertices' array. It should probably have a more descriptive name.
Actually, both 'vertices' and 'n' can be replaced by a vector<Vertex*>.
If you make that substitution, the code can be vastly simplified, and
made much more dynamic as well.
Basically, your "Graph" class consists of 'n' single linked lists with
'n' determined at object construction and it is up to Graph's clients to
make sure they don't try to write past the bounds of Graph's array. The
Graph class should guard against such errors.
Check this out:
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
using namespace std;
typedef map<int, list<int> > VerticeMap;
void print_vertice(const VerticeMap::value_type& vert) {
cout << "Vertex " << vert.first << ": ";
copy(vert.second.begin(), vert.second.end(),
ostream_iterator<int>(cout, " "));
cout << endl;
}
class Graph {
int m;
VerticeMap vertices;
public:
Graph(int n): m(0) { }
void add_arc(int v1, int v2) {
vertices[v1].push_front(v2);
}
void add_edge(int v1, int v2) {
add_arc(v1, v2);
add_arc(v2, v1);
}
void print_graph() {
for_each(vertices.begin(), vertices.end(), &print_vertice);
}
};
int main()
{
Graph g(5);
g.add_edge(1, 3);
g.add_edge(1, 4);
g.add_edge(2, 4);
g.add_edge(3, 4);
g.print_graph();
}
The above code has slightly different behavior than yours, can you spot
it?
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]