#### Archived

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

# Dynamic array question....

This topic is 5907 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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?

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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?