Speed of std::list?
Heheh... I wrote my own container class, and used it for batching. It worked well, but I could have saved three days if I had just used a superior, already-made one.
If it''s just 2d, how many objects do you have? I render thousands of quads every frame, using direct-mode in opengl (glvertex3f 
and it runs blazingly fast...
and it runs blazingly fast...
Bear in mind that big-O notation doesn''t tell you how efficient an algorithm is, only its time complexity.
So it only expresses, by a factor of what, does the time taken increase as the size of the problem increases.
It''s sometimes better to have an algorithm with a worse big-O, if you know the size of the problem in advance (and it will never increase beyond a known limit), if the "worse" algorithm is a lot faster in a particular case.
An algorithm with a better "big-O" will of course scale better as you tend towards infinity, but a lot of problems don''t tend towards infinity
My best guess as to where the time is spent with std::list, would be inside the memory allocator which it uses to allocate its nodes. As other posters have mentioned, vector gets around this problem by reusing the same nodes (although of course it doesn''t handle random insertion / deletion efficiently).
Mark
So it only expresses, by a factor of what, does the time taken increase as the size of the problem increases.
It''s sometimes better to have an algorithm with a worse big-O, if you know the size of the problem in advance (and it will never increase beyond a known limit), if the "worse" algorithm is a lot faster in a particular case.
An algorithm with a better "big-O" will of course scale better as you tend towards infinity, but a lot of problems don''t tend towards infinity
My best guess as to where the time is spent with std::list, would be inside the memory allocator which it uses to allocate its nodes. As other posters have mentioned, vector gets around this problem by reusing the same nodes (although of course it doesn''t handle random insertion / deletion efficiently).
Mark
quote:It depends on the list implementation. The MSVC++ 6.0 implementation is a good deal slower than stlport''s implementation
No it isn''t. Which isn''t surprising, really, since for the most part their implementations are identical.
The slow part of MSVC containers is the memory allocator. It''s design for maximum efficency of memory use, whereas some allocators today are tweaked for speed of (de)allocation.
In this case vector will undoubtably out-perform the list due to the locality of reference rule.
In this case vector will undoubtably out-perform the list due to the locality of reference rule.
Yeah, you can plug in your own allocation scheme with std::list, look at the interface for std::allocator<> or google for a tutorial.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
