I need some sort of a dynamic array for my particle system (it will only hold a few objects, not all my particles!). I have talked with a few people about using STL or the vector class thats in STL (isn''t it?). I would consider writing my own linked list class, but I am rather restricted on time, and I want to keep things simple. What are the advantages of both, and disadvantages of both? I heard someone say that one of them has to shift all the elements over if you add or remove one element. Is that true? I want to be able to add and remove, say, five objects per frame without a major slowdown. Is this feasible?

Well, even if you want to use a linked list, you don''t necessarily have to roll your own, you''ve got std::list for that.

The biggest problem with a linked list is that access time is linear : you have to go through the list to reach an element. However, once you point to an element, removing it can be done in constant time. Insertion at any point (as long as you are pointing to that spot) is also constant time.

If you only plan to iterate through the list and never have to access a specific particle, you can go with a std:list. Remember that your code may have to evolve though.

As for a vector, access time is always constant, but insertions/removal can only be done at the end of the vector. Otherwise some rearrangement is needed. If you absolutely want to keep your objects in order, then yes, shifting is needed.

However, if you don''t care about the exact ordering, then you can always insert at the end of the vector, and if you need to delete an item in the middle of the vector, you can overwrite it with a copy of the last element in the vector, then delete that last element. This can be done quickly with the following call:

  bool pred( object& obj ); // returns true if the object must be removed.vect.erase(remove_if(vect.begin(), vect.end(), pred ), vect.end());  

Plus a std::vector is backward-compatible with C APIs : just use &vect[0] when you are asked the address of an array.

Then you have the std::deque, which works like a vector, except that you can insert/remove at both ends of the list.

Finally you may want to consider a std::set (or a std::map but that''s wasteful) which still let you iterate through them in linear time, like all the other containers, but have logarithmic insert/remove/access times.

For a particle system, I would store the individual particles in a vector, and "identified" objects (that is, objects that must be accessed by ID) in a set or a map.

So you think it would be feasible to use STL (lets say adding one element, removing one element, and cycling through all elements 10 times) on a per frame basis without costing to much CPU time?