casting a void ** to object **

Quote:

Original post by saeedm I have a void ** which I would like to point to either an array of Vertex pointers or Edge pointers.

You probably don't, actually. Legitimate uses for void*s in C++ are few and far between. Why are you trying to do this?

I'm looking for a way of organizing a set of Vertex's and a set of Edges (in heap memory, since # of inputs will be huge). I need to constantly add edges and vertex's as they are read from input and as my algorithm progresses. I created a DynArray class that tries to do that, by storing a void * to either a Vertex array or an Edge array. I will create several DynArray objects, some containing Edges, some Vertex's. However, just after writing this post I realized that I might be better off using polymorphism. I'm still unsure about whether I'm better off having an array of objects, or an array of object pointers. How do I decide what works better for my situation (or is one usually prefered?)

It sounds like your "DynArray" class is just a reimplementation of std::vector. Why are you preferring it over that?

I knew someone was going to mention that :)
I was told to avoid using Vector since it would slow down my algorithm time with its resize operations. But then I remembered there is a feature to set a Vector's start size, which would eliminate this problem. The idea was still a little grey to me so I decided why not just do my own quick implementation of exactly what I need, and I came up with DynArray. I think I will end up using std::Vector since I'm pressed for time. BTW that question about arrays of objects vs arrays of pointers to objects still stands! (I guess it would now be Vector of objects vs Vector of pointers to objects).

It depends on your usage patterns and size of the objects. The only way to know for sure is to code it both ways and see which one performs better.

Quote:

Original post by saeedm I knew someone was going to mention that :) I was told to avoid using Vector since it would slow down my algorithm time with its resize operations.

A little bit of knowledge is a dangerous thing. Someone who understands the idea of vector resizing, but who does not understand amortized complexity analysis, is apt to get entirely the wrong opinion about std::vector.

Quote:

But then I remembered there is a feature to set a Vector's start size, which would eliminate this problem. The idea was still a little grey to me so I decided why not just do my own quick implementation of exactly what I need, and I came up with DynArray.

Lack of understanding is a terrible basis for decisions.

Quote:

BTW that question about arrays of objects vs arrays of pointers to objects still stands! (I guess it would now be Vector of objects vs Vector of pointers to objects).

The two are different things. An array of objects is a contiguous area of storage, with each slice of the storage holding an object. An array of pointers to objects is a contiguous area of storage, with each slice of storage large enough only to hold a pointer. The actual objects are stored elsewhere. You'll do the latter thing if your objects are stored elsewhere and you only want to reference them in the array. You'll also need it if your objects are polymorphic, since in that case each one will be of a different size.

Q1:Wouldn't an array of pointers to objects always perform better, since the actual object would remain in the same place in memory and the only data moved around when operations are performed on the array would be the actual 4byte pointers?

Q2:I need to dynamically allocate my Vertex's and Edges, is the following the only way of doing it, while storing them in a Vector? It seems like data is being copied around unnecessarily...

myVector.push_back(*(new Edge(2,3,10)));

Quote:

I was told to avoid using Vector since it would slow down my algorithm time with its resize operations.

'Slow down' in comparison to what?

If you know in advance how large the array needs to be (such as when loading vertex, color, and index data from a model file), then there's only one allocation involved, and there's no problem.

If this is a situation where you need to add things to the array as the application proceeds, you can use reserve(), use a custom allocator, use a different container type, or - wait for it - just not worry about it (the cost of resizing is unlikely to be significant unless you're doing something unusual and/or ill-advised, such as building a local vertex buffer from scratch using push_back() for every model that's rendered in a given frame).

How does your DynArray class handle reallocations? How do you know it handles them more efficiently than vector?

It seems like you've already figured this out, but the advice you got was not very good (unless there was more to it than was presented in your post). std::vector is a perfectly suitable solution for storing mesh/model data.

I'd probably need to read your original post again to give you a good answer to your second question, but a good general rule is, store objects in your containers rather than pointers to objects unless you have a good reason to do otherwise.

A1) Dereferencing pointers isn't free. Storing pointers to objects takes up additional space. You lose spatial locality of access.

A2) myVector.push_back(Edge(2, 3, 10));

Quote:

Original post by saeedm Q1:Wouldn't an array of pointers to objects always perform better, since the actual object would remain in the same place in memory and the only data moved around when operations are performed on the array would be the actual 4byte pointers?

Sure, if you were actually moving it around a lot. In your case, you won't be. Again, this is a situation where you need to understand amortized complexity analysis in order to have an informed opinion.

Quote:

Q2:I need to dynamically allocate my Vertex's and Edges, is the following the only way of doing it, while storing them in a Vector? It seems like data is being copied around unnecessarily...

Your code has a memory leak and allocates memory for no good reason. Generally you would do:

myVector.push_back(Edge(2,3,10));

SiCrane and Sneftel: first thing that comes to mind, me being a noobie coder, is where's the 'new' keyword? But I'm assuming Vector will take care of dynamically allocating the Edge or Vertex, correct?

Quote:

Original post by saeedm SiCrane and Sneftel: first thing that comes to mind, me being a noobie coder, is where's the 'new' keyword?

Nowhere. There's no allocation happening outside vector. There's probably no allocation happening inside vector (since the memory's probably already been allocated).

Quote:

But I'm assuming Vector will take care of dynamically allocating the Edge or Vertex, correct?

The vector will take care of deciding where to put the object, including allocating more space if necessary. Even if you did "new" yourself, it would still do the same thing.

jyk: I know the max number of Edges and Vertex's from the start. I can't simply use an array because I will gradually add elements, so I need to keep an index or the current number of elements inserted.

Quote:

But I'm assuming Vector will take care of dynamically allocating the Edge or Vertex, correct?

Yes (as far as you're concerned, at least).

The details are a little more complicated, but all you really need to know is that:

1. The vector will make room for a new object of the specified type (if necessary)
2. The vector will add a new object that is an exact copy of the input object (under normal circumstances, at least)

So (you might ask), does this mean that vector allocates memory every single time I add a new object? The answer is 'no' (this is where Sneftel's 'amortized complexity analysis' comes into play).

Quote:

Original post by saeedm jyk: I know the max number of Edges and Vertex's from the start. I can't simply use an array because I will gradually add elements, so I need to keep an index or the current number of elements inserted.

As mentioned previously, you can use reserve(), e.g.:

edges.reserve(anticipated_max_edges);verts.reserve(anticipated_max_verts);

And then just use push_back() from there.

Or you could just not worry about it, add the new elements as needed, and see if you run into any performance problems. My guess is you won't, but if you do, then you can try (e.g.) reserve().

got it! thanks to everyone for helping me out

[Edited by - saeedm on March 2, 2008 5:18:45 PM]

Why would you want the same variable to refer to either a set of Vertices or a set of Edges? Could we see more context - what are you doing with the data?