Dynamic array

[Jan Krumsiek]

Hi all.

I have a virtual "world" with different objects which are "born" and
which "die" sometimes. This means I have a variable amount of objects in
this world which I need to store in some structure.

Sounds like a perfectly good job for vectors (STL).

Another method would be to create a pre-defined, empty array. Now if an
object is born, the next free slot in this array is searched and the new
object is stored at that position. When an object dies, the
corresponding slot is simply "freed" again.

Now my question:

Which of this methods (STL, array) will be faster if my world has a huge
number of objects (5000-10000)?

Maybe any other ideas?

Regards,

Jan

[Clark Cox]

In article <MP************************@news.t-online.com>,
Jan Krumsiek <ja**********@gmx.de> wrote:

Hi all.

I have a virtual "world" with different objects which are "born" and
which "die" sometimes. This means I have a variable amount of objects in
this world which I need to store in some structure.

Sounds like a perfectly good job for vectors (STL).

If most of your insertions and deletions are at the end of the
sequence, then yes, vector sounds reasonable. However, if it is likely
that objects anywhere in your "world" can "die", (i.e. if you will
frequently be removing items from the middle of the sequence), another
container may be better (like list or set).

[Billy O'Connor]

Clark Cox <cl*******@mac.com> writes:

In article <MP************************@news.t-online.com>,
Jan Krumsiek <ja**********@gmx.de> wrote:

Hi all.

I have a virtual "world" with different objects which are "born" and
which "die" sometimes. This means I have a variable amount of objects in
this world which I need to store in some structure.

Sounds like a perfectly good job for vectors (STL).

If most of your insertions and deletions are at the end of the
sequence, then yes, vector sounds reasonable. However, if it is likely
that objects anywhere in your "world" can "die", (i.e. if you will
frequently be removing items from the middle of the sequence), another
container may be better (like list or set).

You may also want to look into using some sort of small object
allocator routine, depending on the size of these objects, since they
are so many.

[John Harrison]

"Jan Krumsiek" <ja**********@gmx.de> wrote in message
news:MP************************@news.t-online.com...

Hi all.

I have a virtual "world" with different objects which are "born" and
which "die" sometimes. This means I have a variable amount of objects in
this world which I need to store in some structure.

Sounds like a perfectly good job for vectors (STL).

Another method would be to create a pre-defined, empty array. Now if an
object is born, the next free slot in this array is searched and the new
object is stored at that position. When an object dies, the
corresponding slot is simply "freed" again.

Now my question:

Which of this methods (STL, array) will be faster if my world has a huge
number of objects (5000-10000)?
I would expect them to be almost exactly the same. You should choose on the
basis of which results in simpler code.

Maybe any other ideas?

Actaully sounds much more like a task for STL list or map depending on your
requirements. I would expect either of those to be faster than vector or
array.

The most important thing is that, whatever data structure you choose, you
create a class that hides the details of that representation from the rest
of your program. That way you can change the representation in the future
without affecting the rest of the program. This seems especally imoprtant in
this case because you are unsure of what is the best, and you seem
interested in expereimenting to find out.

john

[Jan Krumsiek]

John Harrison wrote:

The most important thing is that, whatever data structure you choose, you
create a class that hides the details of that representation from the rest
of your program. That way you can change the representation in the future
without affecting the rest of the program. This seems especally imoprtant in
this case because you are unsure of what is the best, and you seem
interested in expereimenting to find out.

Yes, i get what you mean. I will create some CWorld class with "add",
"remove" and "getobject" methods.

Jan

[Jan Krumsiek]

Clark Cox wrote:

If most of your insertions and deletions are at the end of the
sequence, then yes, vector sounds reasonable. However, if it is likely
that objects anywhere in your "world" can "die", (i.e. if you will
frequently be removing items from the middle of the sequence), another
container may be better (like list or set).

Yes, actually objects can spawn and be removed all the time during the
main loop. Why is list or set better then? What are the differences?

Regards,
Jan

[Jan Krumsiek]

Billy O'Connor wrote:

You may also want to look into using some sort of small object
allocator routine, depending on the size of these objects, since they
are so many.

Thanks for the tip, but what do you mean with "small object allocater
routine"? Wouldn't that be something like the array I described in my
original posting?

Regards,

Jan

[red floyd]

Jan Krumsiek wrote:

Clark Cox wrote:

If most of your insertions and deletions are at the end of the
sequence, then yes, vector sounds reasonable. However, if it is likely
that objects anywhere in your "world" can "die", (i.e. if you will
frequently be removing items from the middle of the sequence), another
container may be better (like list or set).

Yes, actually objects can spawn and be removed all the time during the
main loop. Why is list or set better then? What are the differences?

Regards,
Jan

because removing from the middle of a vector involves copying everything
after the removal point. It's O(n), whereas removing from a list is
O(1), and (i think) a set is O(log(n))