Re: Improving a short program in C++

Rog?rio Brito wrote:


valgrind will help you to detect where the memory has been allocated, so
you get at least a clue where the error is.


Allow me a couple of comments:

class Vertex {
private:
        int l;
        Vertex *following;

public:
        Vertex(int n=0): l(n), following(NULL) {}
        int label() { return l; }
        int label(int l_) { l = l_; return l; }
        Vertex* next() { return following; }
        Vertex* next(Vertex *v) { following = v; return v; }
};

First of all, I would add a copy constructor and an assignment operator.
Or at least make them private, because the compiler default
implementation does not what you want (it does a raw copy, including the
 linkage pointer). I would further recommend to represent a list of
vectors by one of the containers of the STL, and not by hand, unless you
have very very good reasons for why the STL is not suitable for you.
Third, I would make the program const-correct, i.e. add const qualifiers
where necessary. Naming getters and setters the same is probably a bit
misleading (at least to me). Probably you want to return a reference, so
you could write vertex->next() = w? (If at all, I would recommend using
the STL containers).

class Graph {
        int n;
        int m;
        Vertex **vertices;

public:
        Graph(int n_): n(n_), m(0), vertices(new Vertex *[n]) {
                for (int i = 0; i < n; i++)
                        vertices[i] = NULL;
        }

See above. Raw arrays should be substituted by vectors, or by any other
suitable container.

        Graph(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();
                        }
                }
        }

This is not exception-safe. Consider what would happen if "new Vertex()"
throws. Then, the vertex-array is not yet initialized (or partially
initialized) and the class destructor will follow invalid pointers.
Furthermore, you access here vertices[i], while having initialized this
to NULL before. This will cause a segfault, at best, but is at least
undefined.

int main(void)
{
        Graph *g = new Graph(5);

        g->add_edge(1, 3);
        g->add_edge(1, 4);
        g->add_edge(2, 4);
        g->add_edge(3, 4);

        g->print_graph();

        return 0;
}

Here you allocate a new g, but never release it. Why do you allocate it
on the heap anyhow, wouldn't it be easier to use an automatic variable
for g?

As a remark, even though C++ *looks* like C, it is nevertheless very
different. It *can* be used similar to C, but it might be better (and
easier) to follow a different programming paradigm. Hints: Avoid raw
pointers, and raw arrays. Unless you have very specific needs, there are
better alternatives waiting for you.

So long,
    Thomas

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]