Re: Improving a short program in C++
In article <flisvl$h8a$1@aioe.org>, rbrito@ime.usp.br says...
Dear readers,
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 may not be the source of the problem. Just glancing through your
code, one piece jumps out as a potential problem. Your Graph::operator=
does not appear to work correctly when/if a Graph already contains
anything. For example, it starts with:
n = g.n;
m = g.m;
vertices = new Vertex *[n];
If vertices already points at some allocated memory, this will leak that
memory. You never assign a Graph in your code, so I don't think that's
the source of the leak you saw though.
Other than that, I'd probably implement Graph and Vertex using
std::vector and std::list respectively. The code would look something
like this:
class Vertex {
std::list<int> adjacents;
public:
void add(int x) { adjacents.push_back(x); }
std::ostream &print(std::ostream &os) const {
std::copy(adjacents.begin(), adjacents.end(),
std::ostream_iterator<int>(os, "\t"));
return os;
}
};
std::ostream &operator<<(std::ostream &os, Vertex const &v) {
return v.print(os);
}
class Graph {
std::vector<Vertex> vertices;
public:
Graph(int num_vertices) : vertices(num_vertices) {}
void add_arc(int v1, int v2) { vertices[v1].add(v2); }
void add_edge(int v1, int v2) {
add_arc(v1, v2);
add_arc(v2, v1);
}
std::ostream &print(std::ostream &os) const {
std::copy(vertices.begin(), vertices.end(),
std::ostream_iterator<Vertex>(os, "\n"));
return os;
}
};
std::ostream &operator<<(std::ostream &os, Graph const &g) {
return g.print(os);
}
For the sake of simplicity, I left out the "Vertex" label on each line,
but that wouldn't be terribly difficult to add if you really want it.
Incidentally, while I used std::list for Vertex since you'd used a
linked list representation, you could just as well use a vector, deque,
or just about any other ordered collection. Likewise, since you never
resize it after creation, I believe you should be able to use
std::tr1::array instead of std::vector to implement Graph. These changes
wouldn't have any material effect on the basic function though -- at
most they'd be rather minor optimizations.
Adding the last piece there (the operator<< for a Graph) allows us to
write out a graph in the usual way, so main comes out something like
this:
Graph g(5);
g.add_edge(1, 3);
g.add_edge(1, 4);
g.add_edge(2, 4);
g.add_edge(3, 4);
std::cout << g;
Oh, I almost forgot to mention: the source of your leak was pretty
simple: in main you dynamically allocated your Graph object, but you
never deleted it. Since you never deleted it, its destructor never ran
at all and all its contents was leaked. Since it didn't need to be
dynamic anyway, I just allocated it automatically so it would be
destroyed automatically upon going out of scope. Since we used standard
containers, we didn't have to write the code for the copy constructor,
copy assignment or destructor at all, and about the only memory leaks we
might have would be due to problems in the standard library.
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]