Pre allocation of memory
-
Ok! So this leads me into a slightly more involved question.
I have created a graph data structure that holds pointers to the node and edge objects that make up the graph. I am wondering if perhaps my implementation is not as efficient as it could be. The data for the graph is read in from an XML file and as the reader comes to each new node the following code runs:
@
//Determine if the node already exists in the graph ... skip is yes.
if( !NodeExists(name, heuristic) )
nodeList.push_back(new GraphNode(name, heuristic, m_iNodeIndex));//Advance the Node index. m_iNodeIndex++;@
NodeList is a vector of pointers. Based on your responses, it seems that each new graph node will be created on the heap in a random location. Is that correct? If so, would it be better to store the node itself rather than a pointer to the node in the NodeList vector?
Edges are created in roughly the same manner except pointers to each edge are stored in a vector or edge pointers that are a part of each node.
Or, is this a difference of programming style?
Laurence -
-
It depends what you do with the objects later on.
From pure creational view, It could be better to store objects than pointers. But that also leads to other implications. If you store the pointers (or use the pointers) somwhere else and the modify the vector, the pointer might be invalid.
So it can't be answered generally.
-
How could an object be rendered invalid?!? That almost seems counter-intuitive. If I create and object and then pass a pointer reference to some other part of the program, even if the data in the object is changed, it should not invalidate the object itself.
After a little more reading, my question should be, are you referring the possibility that the vector may have to re-allocate and move the underlying objects around thus invalidating the pointers? If so, I am not sure that I have to worry about this possibility. The graph's nodes and edges are fixed in number.
-
An std::vector (and also a QVector) is a C - array. SO if you have 20 elements in and need to reallocate the vector, the old content MUST be moved in memory, so pointers to the old (unchanged) array would definitly get invalid.
If you can preallocate the vector and do not resize it, than you can also give pointers out of it. Think of it like a C-style array. If you have no space left and want to add elements, you have to move all elements to a new array which is bigger.
Both vectors have just a bit more comfort, like moving, adding, preallocating, but in general, they are C-style arrays.
-
Not sure if this helps, since I don't like arrays, never used them and would not know how they compare to a vector, just giving another angle to the discussion.
I think a std::vector is contiguous through out its life. When the allocated memory block for a vector is exhausted during a growth, the entire vector gets copied into a larger block, and whatever is contained gets copied with it. Any type of data can be accessed in this vector as before the copy took place.
The catch is when the vector is created at run time and is filled with a horde of pointers and needs to be destructed, than all those pointers in the vectors need to be destroyed as well and at programming time you don't know which one's will be created and where - you are stuck or it's time for smart pointers.
Bottom line? I practise and test stuff to the hilt. If the vector works the way I want it, it's end of story.
-
I believe that I understand now. Coming from the Visual Basic and C# universes, I was shielded (to an extent) from this sort of thing. Is there a way to check if a pointer assignment is still valid?
Laurence -
-
@ cazador7907
That is more or less a save pointer.
Hopefully I will not get shot down showing a link to the competition, but I learned so much from those guys. -
But unique_ptr ist no solution here. A unique_ptr implies that you own the object pointed to and
that the lifetime of the object and the unique_ptr are (more or less) identical. So you should know if its valid, regardless of the use of unique_ptr.In fact there is no way no ensure, that a pointer points to an object that has not been deleted.
-
My humblest apologies.
The pointer style in my previous link does work in std::vectors, and those vectors that had been moved(copied). The topic is about effectively using vectors, and I added information to that.And sure, no smart/save pointer is a direct answer to cazador7907 question, but the topic is about vectors; that's why I wrote 'That is more or less ...' , I assumed his/her question was in context to the topic, since we all agreed that to allocate space for a vector is a good idea, and what left to figgure out is what to do with its contents. :)