A vector of class objects
-
Hi,
I am storing a series of node class objects in a vector and I have a question about what I'm seeing when the program runs and I examine the data contained within the graph vector variable nothing makes any sense. Now when I say doesn't make sense, I mean that the data that should be in the classes stored in the vector appear to be either random numbers for the int values or (when they are string values) are "not in scope." I've posted the code below.
Had to edit so that the code would be readable ...
//This is the main subroutine from where it's all called.
@int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);Graph newGraph; newGraph.AddNode("Chicago", 0); newGraph.AddNode("St. Louis", 1); newGraph.AddNode("Omaha", 3); std::cout << "Program Finished." << std::endl; return 0;}
@
//This is the Graph Node Class
@class GraphNode : public Node
{
private:
QVector<Node*> m_vNeighbors;bool NodeExists(Node &newNode);public:
GraphNode();
GraphNode(QString name, int heuristic, int Index);int NeighborCount(); void AddNeighbor(GraphNode node); void AddNeighbor(QString name, int heuristic, int Index);};@
//This code is of the graph class.
@Graph::Graph(QObject *parent) :
QObject(parent)
{}
bool Graph::NodeExists(GraphNode &nodeIn)
{
for(int idx = 0; idx < graph.size(); idx++)
{
if( graph[idx] == &nodeIn )
{
return true;
}
}
return false;
}void Graph::AddNode(QString name, int heuristic)
{
//Advance the Node index
m_iNodeIndex++;//Create the new graph node GraphNode newNode(name, heuristic, m_iNodeIndex); //Determine if the Node already exists if ( !NodeExists(newNode) ) std::cout << "Node Not Found." << std::endl; else std::cout << "Node Found." << std::endl; graph.push_back(&newNode);}
int Graph::GraphSize()
{
return graph.size();
}GraphNode* Graph::GetGraphNode(int index)
{
return graph[index];
}@ -
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
@
GraphNode *newNode = new GraphNode(name, heuristic, m_iNodeIndex);
@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":http://doc.qt.nokia.com/4.7/qlist.html rather than "QVector":http://doc.qt.nokia.com/4.7/qvector.html.
Excerpt from "Qt docs":http://doc.qt.nokia.com/4.7/qvector.html#details
-
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.
-
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":http://doc.qt.nokia.com/4.7/containers.html in general, and on "QList":http://doc.qt.nokia.com/4.7/qlist.html for some details.
-
[quote author="Volker" date="1291851383"]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.[/quote]
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.
-
[quote author="GordonSchumacher" date="1291917913"]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.[/quote]
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:
@QDialog d;
d.exec();@is a perfectly valid way of doing things.
What wouldn't be valid would be something like:
@QDialog d;
QDialog other_d;
other_d = d;@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:
@QList<QDialog> dlgList;
dlgList << QDialog();@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":http://www.artima.com/cppsource/rvalue.html will presumably make this workable, however...
-
[quote author="Robin Burchell" date="1292024166"]@QDialog d;
d.exec();@is a perfectly valid way of doing things.[/quote]Ah yes, but that could produce "unpredictable behavior":http://labs.qt.nokia.com/2010/02/23/unpredictable-exec/. Given that information, I'm all for creating the widgets on the heap in literally all circumstances. Objects not necessarily.
-
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.