which would be a better STL object to use in a game, vector or list? or is there another, even better one? i''m just using it linked-list style (iterate through contents once per frame and update them). thanks
_________________Gecko___ Gecko Design

Depends on the purpose. Iterating over a vector is faster, but lists can do fast insertions in arbitrary places. The vector push_back operator averages out to the same speed as an insertion as a list (if not slightly faster). IMO vectors a better general purpose data structures, but again use what''s best for the job.

If the size is not expected to grow randomly or dramatically, then a vector is superior, because it takes less space AND has faster access.

If the list is small and will not grow and shrink OFTEN, than a vector is still better. A vector ceases to be better than a list as soon as the size grows exceptionally large and might change AT ALL, the size is moderately large and will GROW more than a few times over its life, or the size is completely arbitrary and will change at random.

The list is the BEST option when the size changes an extremely large number of times, or the list as a whole grows often.

There is another alternative though. A deque. A deque is better than a vector in almost all cases where the container''s size will grow, because a deque grows in chunks and therefore doesn''t need to copy ALL of the data each time the current availible block is exceeded (a vector MUST be a single block of contiguous memory - at least i THINK that''s what the standard says).

The deque DOES have a slightly slower access time than a vector (when using the subsript operator, for iterators the access is the same, but the ++ operator is slightly slower), but the access is faster than a list and much faster than would matter in most cases.

To save on instantiated types I use a deque by default for all of my general containers. Sometimes you find you HAVE to use a vector, when a client expects a block of contiguous memory. Other times you realize that you are often adding new elements into a sorted list, meaning for a deque you would have to add the element and then re-sort the container, which is WAY less efficient than adding the element into the proper location of a list container. Those are the main criteria I use to determine which container to use.

Here''s a summary:

1. Need contiguous memory OR your program''s primary operation consists of repeatedly accessing the container''s elements (speed critical) - USE A VECTOR.

2. Maintaining a sorted list, and elements must be inserted arbitrarily into the container (they will not be added always already in order) OR you need any container (sorted or not) in which the growing and shrinking operations are called nearly as often (say within one order of magnitude, 10% or more of the total) as accesses - USE A LIST.

3. Otherwise - USE A DEQUE.

Note - I did not mention maps or sets in this post, because there behavior is not interchangeable with the other 3 containers. You should always first make sure what functionality you need from a container (list, map, set, stack, heap, etc) before worrying about the performance trade-offs of a particular implementation.

Hope this was helpfull.

Xai, that was great, thanks! Now if I can only get past the bug in VC++ 6 sp 3 vector thingy it will be great.

Xai,
I agree with much of what you said, but not all of it. If the growing/shrinking of your container always happens at the end of your container, I still see no reason to not use a vector. Assume that your container is always going to have 10,000, plus or minus 5000 items in it. Once you hit around 10,000 items in it, the vector will grow to around 20,000 (this all depends on the initial size, since it keeps doubling). At that point, it doesn''t really matter anymore, it will no longer do ANY allocation/deallocation. (At least, I don''t think any implementation SHRINKS the allocated memory for a vector when you remove many elements.) In this case, all those extra push_back() and pop_back() calls to the vector will be blazingly fast, since you''re just filling values in already owned memory.

With a list, you''re still going to have to allocate and deallocate a node EVERY time you want to insert or remove an item. (You could use your own memory manager/allocator to pre-grab a big chunk, and you''d end up with performance similar to the vector...) Why go through the trouble? I honestly think that unless you NEED to insert things in the middle of the container, there are few instances that really call for a list.

As for contiguous vector: This has been discussed several times on comp.lang.c++.moderated. Apparently, some of the people that wrote the standard INTENDED for contiguous vector to be a requirement, but the standard doesn''t actually say it anywhere. No implementation doesn''t do it, though, and it has been filed as a defect report, which means that the next time the standard is updated for defects (not new features, so some time relatively soon) it will be changed to require contiguousness.

I also like your reccomendation of using deque. It is a bit slower than vector (like you said) for certain operations, but just having push_front() can sometimes make up for that. Also, you don''t HAVE to insert and then re-sort, you know... All the STL containers (even vector and deque) support insertion in the middle, it''s just slower in those two. For deque, you just need an iterator to where you want to insert, and then call .insert() with the new value and iterator. And for this operation, deque is (slightly) faster than vector, since it figures out which end the insert location is closer to, and only shifts those elements.

Gecko - my final answer to your original question is as it was in a previous thread: "Unless you have some earth-shattering need otherwise (which it sounds like you don''t) use a vector".

-Brian

The problem with vector allocation is that the whole array must be copied. So, if you have 10,000 elements, and go to 20,000, that is 10,000 copies. Since this is a one time thing, in a game that would only slow a frame. And, memory is not deallocated with pops(in a vector).
I prefer vectors because random access much faster.


Mike

ah thanks, that was exactly the kind of info i was looking for. STL is damn cool...


_________________Gecko___
Gecko Design

Look up an old thread in this board by yours truly, titled "Container Holy Wars" or something like that. It was a long discussion on this exact topic.

I got a question...

deque,

Is it "D-Q" or "Deck"?





~!@#$%^&*()_+_()*&^%$#@!~

Pie are round!

To the best of my knowledge (and I''m pretty certain on this) it''s "deck". It stands for Double Ended QUEue.

-Brian