You create your GraphNode object on the stack (line 25 of the Graph implementation).

So, as soon as AddNode is finished, the newly created GraphNode (newNode) will be destroyed. And worse, that way you have dangling pointers in your vector!

You must create the node on the heap using

Also your NodeExists method should take a pointer, rather than a reference as an argument.

Additionally, as a rule of thumb: QObject derived classes should always be created on the heap using new.

Also it is generally better to use QList [doc.qt.nokia.com] rather than QVector [doc.qt.nokia.com].

Excerpt from Qt docs [doc.qt.nokia.com]

• For most purposes, QList is the right class to use. Operations like prepend() and insert() are usually faster than with QVector because of the way QList stores its items in memory (see Algorithmic Complexity for details), and its index-based API is more convenient than QLinkedList’s iterator-based API. It also expands to less code in your executable.

• If you want the items to occupy adjacent memory positions, or if your items are larger than a pointer and you want to avoid the overhead of allocating them on the heap individually at insertion time, then use QVector.

This is the problem with having a little bit of knowledge. I know enough to be really dangerous (at least to myself).

Thanks for the input. Seems I need to go back to the online reference works.

To be conscious that you are ignorant is a great step to knowledge. (Benjamin Disraeli)

As a curiosity, have you looked into using Boost::Graph? It might be too heavyweight for what you need, but it’s an already-written and very, very complete graph structure implementation.

I’m actually trying to work through the basics of things like graphs, binary search trees etc on my own. I figure that once I know how they work, I’ll better understand the inner workings of things like Boost.

I do have one other question. When I create the actual graph object, I do not create it in the heap. Should it be created there or is the stack fine?

If you store pointers in your list you must create it on the heap (using new). If you create the object on the stack (using “GraphNode xy;” in your code, without “new”), it will be destroyed once you leave the block where the object was instantiated. Your list then contains a pointer that isn’t valid anymore (aka “dangling pointer”). Your program will crash if you access them later.

If your objects do have an assignment operator and/or a copy constructor you can create them on the stack too, as they will be copied once you put them into the list. If you have a “heavy” amount of data, you could consider using a reference counter and copy-on-write (like the Trolls do with QString, for example). If your graph node contains only what you’ve provided in your original post, this would not be necessary.

See the API docs on Container Classes [doc.qt.nokia.com] in general, and on QList [doc.qt.nokia.com] for some details.

Volker wrote:

If your objects do have an assignment operator and/or a copy constructor you can create them on the stack too, as they will be copied once you put them into the list. If you have a “heavy” amount of data, you could consider using a reference counter and copy-on-write (like the Trolls do with QString, for example). If your graph node contains only what you’ve provided in your original post, this would not be necessary.

Bear in mind that QObjects cannot be copied, so they must be created on the heap. Also, if you do the copy-on-write thing, look at QSharedData; it will make your job a lot easier.

GordonSchumacher wrote:

Bear in mind that QObjects cannot be copied, so they must be created on the heap. Also, if you do the copy-on-write thing, look at QSharedData; it will make your job a lot easier.

While I understand what you’re saying, I’d like to make a slight correction for anyone else who stumbles across this and is confused by it.

While you can’t copy a QObject, at the same time, you don’t need to copy anything to use stack allocation:

is a perfectly valid way of doing things.

What wouldn’t be valid would be something like:

because (as you correctly point out) all classes inheriting QObject have an inaccessible copy constructor.

Sorry, I was not clear; what I meant was that in order to put them in a container (QVector et al) they must be created on the heap – in other words, this will not work:

I believe that even the QList definition will fail, but the second line most certainly will because it will create a QDialog on the stack, then try to copy it into dlgList.

The C++ move constructor [artima.com] will presumably make this workable, however…

Robin Burchell wrote:

1. QDialog d;
2. d.exec();

is a perfectly valid way of doing things.

That link is an article about the unpredictable behavior from having multiple event loops (from the d.exec()), not that widget must be on the heap. What they recommend does require the widget to be on the heap but only as a side-effect of avoiding the exec() call.

True. The only way to properly avoid the exec() call is to create the widget on the heap and call open() or show(), which was what I implicitly meant.

That would be subject to a new thread, I’d suggest… nothing really related to a QVector, I suspect.

It is still related to memory management of Qt classes, which is the real topic of this thread.