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]

Re: Dynamic array

In article <MPG.1a9dfaa941 b91498989698@ne ws.t-online.com>,
Jan Krumsiek <jan.krumsiek@g mx.de> wrote:
[color=blue]
> 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).[/color]

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]

Re: Dynamic array

Clark Cox <clarkcox3@mac. com> writes:
[color=blue]
> In article <MPG.1a9dfaa941 b91498989698@ne ws.t-online.com>,
> Jan Krumsiek <jan.krumsiek@g mx.de> wrote:
>[color=green]
>> 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).[/color]
>
> 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).[/color]

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]

Re: Dynamic array


"Jan Krumsiek" <jan.krumsiek@g mx.de> wrote in message
news:MPG.1a9dfa a941b9149898969 8@news.t-online.com...[color=blue]
> 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)?[/color]

I would expect them to be almost exactly the same. You should choose on the
basis of which results in simpler code.
[color=blue]
>
> Maybe any other ideas?[/color]

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]

Re: Dynamic array

John Harrison wrote:[color=blue]
>
> 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.[/color]

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

Jan

[Jan Krumsiek]

Re: Dynamic array

Clark Cox wrote:[color=blue]
> 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).[/color]

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]

Re: Dynamic array

Billy O'Connor wrote:[color=blue]
> 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.[/color]

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]

Re: Dynamic array

Jan Krumsiek wrote:[color=blue]
> Clark Cox wrote:
>[color=green]
>> 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).[/color]
>
>
> 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[/color]

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))