December 8, 2010

cazador7907 cazador7907
Lab Rat
78 posts

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.

  1. int main(int argc, char *argv[])
  2. {
  3.     QCoreApplication a(argc, argv);
  4.  
  5.     Graph newGraph;
  6.  
  7.     newGraph.AddNode("Chicago", 0);
  8.     newGraph.AddNode("St. Louis", 1);
  9.     newGraph.AddNode("Omaha", 3);
  10.  
  11.     std::cout << "Program Finished." << std::endl;
  12.  
  13.     return 0;
  14. }

//This is the Graph Node Class
  1. class GraphNode : public Node
  2. {
  3. private:
  4.     QVector<Node*> m_vNeighbors;
  5.  
  6.     bool NodeExists(Node &newNode);
  7.  
  8. public:
  9.     GraphNode();
  10.     GraphNode(QString name, int heuristic, int Index);
  11.  
  12.     int NeighborCount();
  13.     void AddNeighbor(GraphNode node);
  14.     void AddNeighbor(QString name, int heuristic, int Index);
  15.  
  16. };

//This code is of the graph class.

  1. Graph::Graph(QObject *parent) :
  2.     QObject(parent)
  3. {
  4.  
  5. }
  6.  
  7. bool Graph::NodeExists(GraphNode &nodeIn)
  8. {
  9.     for(int idx = 0; idx < graph.size(); idx++)
  10.     {
  11.         if( graph[idx] == &nodeIn )
  12.         {
  13.             return true;
  14.         }
  15.     }
  16.     return false;
  17. }
  18.  
  19. void Graph::AddNode(QString name, int heuristic)
  20. {
  21.     //Advance the Node index
  22.     m_iNodeIndex++;
  23.  
  24.     //Create the new graph node
  25.     GraphNode newNode(name, heuristic, m_iNodeIndex);
  26.  
  27.     //Determine if the Node already exists
  28.     if ( !NodeExists(newNode) )
  29.         std::cout << "Node Not Found." << std::endl;
  30.     else
  31.         std::cout << "Node Found." << std::endl;
  32.  
  33.         graph.push_back(&newNode);
  34.  
  35. }
  36.  
  37. int Graph::GraphSize()
  38. {
  39.     return graph.size();
  40. }
  41.  
  42. GraphNode* Graph::GetGraphNode(int index)
  43. {
  44.     return graph[index];
  45. }

 Signature 

Laurence -

 

15 replies

December 8, 2010

Volker Volker
Ant Farmer
5428 posts

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

  1. 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.

December 8, 2010

Bradley Bradley
Lab Rat
314 posts

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.
 Signature 

Nokia Certified Qt Specialist.

December 8, 2010

cazador7907 cazador7907
Lab Rat
78 posts

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.

 Signature 

Laurence -

 

December 8, 2010

Bradley Bradley
Lab Rat
314 posts

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

 Signature 

Nokia Certified Qt Specialist.

December 8, 2010

GordonSchumacher GordonSchuma..
Lab Rat
93 posts

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.

December 9, 2010

cazador7907 cazador7907
Lab Rat
78 posts

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?

 Signature 

Laurence -

 

December 9, 2010

Volker Volker
Ant Farmer
5428 posts

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.

December 9, 2010

GordonSchumacher GordonSchuma..
Lab Rat
93 posts
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.

December 11, 2010

Robin Burchell Robin Burchell
Lab Rat
21 posts
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:

  1. d.exec();

is a perfectly valid way of doing things.

What wouldn’t be valid would be something like:

  1. QDialog other_d;
  2. other_d = d;

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

 Signature 


http://rburchell.com

December 11, 2010

GordonSchumacher GordonSchuma..
Lab Rat
93 posts

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:

  1. QList<QDialog> dlgList;
  2. 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 [artima.com] will presumably make this workable, however…

December 11, 2010

Franzk Franzk
Lab Rat
834 posts

Robin Burchell wrote:
  1. d.exec();

is a perfectly valid way of doing things.

Ah yes, but that could produce unpredictable behavior [labs.qt.nokia.com]. Given that information, I’m all for creating the widgets on the heap in literally all circumstances. Objects not necessarily.

 Signature 

“Horse sense is the thing a horse has which keeps it from betting on people.”—W.C. Fields

http://www.catb.org/~esr/faqs/smart-questions.html

December 11, 2010

Bradley Bradley
Lab Rat
314 posts

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.

 Signature 

Nokia Certified Qt Specialist.

December 11, 2010

Franzk Franzk
Lab Rat
834 posts

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.

 Signature 

“Horse sense is the thing a horse has which keeps it from betting on people.”—W.C. Fields

http://www.catb.org/~esr/faqs/smart-questions.html

December 11, 2010

Volker Volker
Ant Farmer
5428 posts

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

December 11, 2010

Bradley Bradley
Lab Rat
314 posts

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

 Signature 

Nokia Certified Qt Specialist.

 
  ‹‹ Resizing the Tablewidget column is crashing the application      Overloading signal possible? Or adding new signals to base classes? ››

You must log in to post a reply. Not a member yet? Register here!