Is std::list made for speed at all? Is it reasonable to create a linked list of 100+ pointers every single frame when you''re running hundreds of frames a second, or would this significantly slow the game down?

What are you going to be using the list for?

"Sneftel is correct, if rather vulgar." --Flarelocke

It depends on the list implementation. The MSVC++ 6.0 implementation is a good deal slower than stlport''s implementation. I''m using an std::list (the stlport implementation) for my render queue, which creates and clears a list of over 1000 objects, and I haven''t had a noticeable slowdown at all.

Well, I'm redesigning my directx 2d engine and I want to batch together all the triangles that use the same texture so I can make less calls to SetTexture and DrawPrimative. Now that my engine is using a bunch of different objects, some having multiple textures, I can't simply sort the list of objects by texture to render them in that order. So, I thought maybe I could make each object in my engine spit out what they need to draw, triangle by triangle, and then I will make a list of triangles, sorting them by what texture they use as the list is being made. Then render the list of triangles, batching as many together as possible.

This would take place every frame though, so basically I would be creating a huge list of pointers every frame.

Edit: What I'm really wondering is whether the slowdown from creating and destroying a huge linked list every frame would be worse than the slowdown from rendering each object by itself with no kind of batching.

[edited by - Subconscious on April 3, 2004 4:23:55 PM]

Eeeyike. An element per-triangle in pretty much any STL container is going to be something of a slowdown.

"Sneftel is correct, if rather vulgar." --Flarelocke

Deyja, I''m not going to be drawing the triangles individually, I''m just sorting them individually so that I can push all the ones using the same texture into a vertex buffer and draw at once with one DrawPrimitive and one SetTexture

The minimum permissable speeds of the STL containers is specified in the C++ standard using the O notation (if you''re not familiar with it the number in brackets tells you roughly how many times the operations (not opcodes!) must be performed to complete the required task in the worst case). What I have listed is from memory - but I''m sure it''s about right.

For std::list :
insert anywhere into the chain (front, back or middle) - O( 1 )
find any particular element - O( n * log( n ) )

For std::vector :
insert to the start of the list: O( n )
insert at the end of the list: O( 1 ) if the vector doesn''t need to be enlarged, else O( n )
look up a numbered element: O( 1 )

For either if you have a list of items you want to work through sequentially then you can use iterators that will give you O(1) time to access the next/previous element. If you have a large list you are more likely to get hit with a speed penalty by the vector as it initially allocates some memory for elements, when that''s filled up it allocates a larger chunk & copies what was already in the smaller chunk into the larger chunk and deletes the old chunk of memory. On the other hand a list allocates a new chunk of memory for every insertion. If you have a reasonable idea of the ammount of elements required when you initialise a vector you could specify the number of elements that it should start with, then you could avoid the need for it to expand

The only cases ever when a linked list has been faster than a vector for me, were special algorithms in which the algorithm traversed the list back and forth, inserting and/or deleting nodes. But I can tell you that that kind of algorithms are RARE and vector is a much better general purpose container (e.g. a vector of pointers, if you need to delete from the middle every not-so-often and you want the elements to stay in fixed memory locations).