Re: Improving a short program in C++

Rog?rio Brito <rbrito@ime.usp.br> wrote:


and


and


purposes


(which


the


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! ]