Dynamic array question....

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.

quote:

---

Original post by Fruny
...or a std::map but that''s wasteful

---

Why do you consider a map wasteful? In my instruction and experience, map has been ideal for sparse distributions that do not permit duplicate keys. For example, a sparse matrix (required in large-scale database applications - business, etc) which may span 10,000 by 10,000 but contain only 500 elements, is best implemented with some variant of map.

In any case where the data is non-sequential (data with significant gaps), std::map is a fairly useful structure. Thus, I''m sure you have some information that I don''t. If you don''t want to bother the board with this, please feel free to email me as I''m really interested in this discussion.

Thanks.

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?