Archived

This topic is now archived and is closed to further replies.

Moe

Fastest/easiest way of doing a dynamic array?

Recommended Posts

Moe    1256
I need a dynamic array for my particle system that I am working on. It is based on the ideas of John Van Der Burg in this article. On the third page of the article he talks about his manager class. He says he uses something called an Array Template. What is this and how is it used? Any articles on dynamic arrays (using STL or anything) would be helpful. Moe''s Site

Share this post


Link to post
Share on other sites
Moe    1256
Thanks for the suggestion. Let me see if I am getting this right.

A vector is a type of dynamic array. You can create your own type of vector by doing something like:
  
//the custom vector type of bag_of_int


typedef std::vector<int> bag_of_int;

//then when you want to use that custom vector type:

bag_of_int this_is_the_variable;


Am I right so far?

Moe''s Site

Share this post


Link to post
Share on other sites
NewDeal    134
Im guessing, since you''re creating a particle system, that you will need to delete particles from the middle of the list as well.

In that case a simple linked list might be a better choice. Im not sure exactly how the std::vector works though, so it might be equally good.

Share this post


Link to post
Share on other sites
Shannon Barber    1681
IIRC, a vector is not a bag, it''s an ordered container - otherwise yes.

The problem with link-list, is the links. Unless you build/use a heavy duty small object allocator, the memory allocations made by list are rather inefficent in both memory usage and execution speed. Likely slower than growing the vector!

Call .reserve on the vector to set aside as much space as you think you''ll need - then it will grow if/when it needs more room (by 10 I think, the implementations are smart enough to allocate more than 1 more item).

Share this post


Link to post
Share on other sites
invective    118
I think on most c++ compilers the vector grows by doubling its memory size (which supposedly leads to less allocations that linear increases in size). Unfortunately, other that calling reserve you can''t affect the allocation size, like you can in java. I doubt it matters here, since you probably have a maximum number of particles anyways, and you can just reserve that much space.

A vector is probably faster than a list, since it is continguous is memory and does not need as many allocation. The one problem with vectors is deleting items in the middle of the container, which causes the vector to copy all of the elements after the hole back one space to plug the resulting "hole." To avoid this (assuming the order of items in the vector does not matter) swap the item to be deleted with the item at the rear and always delete from the rear of the container.

Share this post


Link to post
Share on other sites
Moe    1256
Hehe - jumping to conclusions are we?

I am NOT using the dynamic array for the individual particles. That would be a total waste of memory/power. Instead I am using the dynamic array to keep track of the different effects that are occuring (eg: rocket trails, sparks, spraying water, etc).

Moe''s Site

Share this post


Link to post
Share on other sites
Oluseyi    2115
quote:
Original post by invective
To avoid this (assuming the order of items in the vector does not matter) swap the item to be deleted with the item at the rear and always delete from the rear of the container.

While you are absolutely right in general, in the specific case of a particle system you can simply recycle particles in-place.

I wanna work for Microsoft!
[ GDNet Start Here | GDNet Search Tool | GDNet FAQ | MS RTFM [MSDN] | SGI STL Docs | Google! ]
Thanks to Kylotan for the idea!

Share this post


Link to post
Share on other sites
Shannon Barber    1681
quote:
Original post by invective
Unfortunately, other that calling reserve you can''t affect the allocation size, like you can in java.

You can pass an Allocator class as a template parameter, which gives you control over the entire allocation of the vector...
In fact, IIRC, the default allocator in MSVC6 defaults to 10 additional elements, but it takes a template parameter so you can pick a different value if you want.

And unless the size of the vector is friggin'' huge (like several megs), the copy operation is extremely quick.

Share this post


Link to post
Share on other sites
Moe    1256
I am afraid I couldn''t find a huge amount of info on STD::vector on MSDN. All I could find was other articls that use it, not a decent article on it.

Moe''s Site

Share this post


Link to post
Share on other sites
Oluseyi    2115
quote:
Original post by Moe
I am afraid I couldn''t find a huge amount of info on STD::vector on MSDN. All I could find was other articls that use it, not a decent article on it.

Try SGI''s std::vector documentation. See my .sig for the link.

I wanna work for Microsoft!
[ GDNet Start Here | GDNet Search Tool | GDNet FAQ | MS RTFM [MSDN] | SGI STL Docs | Google! ]
Thanks to Kylotan for the idea!

Share this post


Link to post
Share on other sites